High speed flexible packet classification using network processors
In one embodiment, a system comprises logic to receive a data packet. The logic is further to identify, based on the data packet, a plurality of candidate rules. The candidate rules may comprise a first candidate rule from a first database of rules and a second candidate rule from a second database of rules. The logic is further to select a rule from among the plurality of candidate rules based on a priority associated with the rule and a determination that the rule matches the data packet. The rule specifies at least one action to be performed on the data packet.
1. A system comprising:
logic comprising at least one logic gate, the logic to:
receive a data packet;
perform a parallel mask-based indexing function on the data packet against a rules database comprising a plurality of rules tables, wherein the mask-based indexing function yields zero or more candidate rules per rules table, wherein a rule is to be designated as not a candidate rule if it is guaranteed to not match the data packet, wherein a rule designated as a candidate rule is not guaranteed to match the data packet, and wherein the logic is to search the rules database substantially in parallel;
identify a set of matching rules from among the candidate rules; and
select a selected rule from among the set of matching rules based on a priority associated with the selected rule, the selected rule specifying at least one action to be performed on the data packet.
2. The system of claim 1 , further comprising a first random access memory comprising a first rules table of the rules database and a second random access memory comprising a second rules table of the rules database.
3. The system of claim 2 , further comprising a content addressable memory to store a third rules table of the rules database, and wherein the candidate rules comprise a rule identified from the third rules table of the rules database.
4. The system of claim 1 , wherein the logic is further to:
calculate an index based on the data packet; and
identify a first candidate rule from a first rules table of the rules database based on the calculated index.
5. The system of claim 4 , wherein calculating the index based on the data packet comprises applying a bitwise mask to the data packet.
6. The system of claim 4 , wherein calculating the index based on the data packet comprises calculating a hash value based on the data packet.
7. The system of claim 4 , wherein the logic is further to:
access a table of indices based on the calculated index to obtain one or more second indices; and
access the first rules table of the rules database based on the one or more second indices to identify at least one candidate rule from among the candidate rules.
8. The system of claim 4 , wherein the logic is further to:
access a table of cages based on the calculated index, wherein a cage comprises an array of elements, an element comprising an index to a rule and a preliminary function that indicates whether it is possible for the rule to match the data packet; and
wherein the first candidate rule is identified based on a determination that a preliminary function of a cage indicates that it is possible for the first candidate rule to match the data packet.
9. The system of claim 4 , wherein the logic is further to calculate the index using a mask based index function comprising:
a masking unit that performs a bitwise AND operation between the data packet and a mask; and
a plurality of compression units, a compression unit to compute a hash based at least in part on a portion of an output of the masking unit.
10. The system of claim 7 , wherein the table of indices comprises a plurality of entries, an entry of the plurality of entries corresponds to an index that may be calculated based on the data packet, and at least one entry of the plurality of entries comprises a plurality of second indices.
11. The system of claim 4 , wherein the candidate rules comprise a plurality of rules selected from the first rules table of the rules database based on distinct indices computed based on the data packet.
12. The system of claim 1 , wherein the logic is further to distribute a majority of a plurality of rules among a plurality of databases of rules stored in random access memories and to assign the remaining rules of the plurality of rules to a content addressable memory.
13. The system of claim 1 , wherein the logic is further to perform, on the data packet, the at least one action specified by the selected rule.
14. A method comprising:
receiving a data packet;
performing a parallel mask-based indexing function on the data packet against a rules database comprising a plurality of rules tables, wherein the mask-based indexing function yields zero or more candidate rules per rules table, wherein a rule is to be designated as not a candidate rule if it is guaranteed to not match the data packet, wherein a rule designated as a candidate rule is not guaranteed to match the data packet, and wherein the rules database is to be searched substantially in parallel;
identifying a set of matching rules from among the candidate rules; and
selecting a selected rule from among the set of matching rules based on a priority associated with the selected rule, the selected rule specifying at least one action to be performed on the data packet.
15. The method of claim 14 , further comprising:
calculating an index based on the data packet; and
identifying a first candidate rule from a first rules table of the rules database based on the calculated index.
16. The method of claim 15 , further comprising:
accessing a table of indices based on the calculated index to obtain one or more second indices; and
accessing the first rules table of the rules database based on the one or more second indices to identify at least one candidate rule from among the candidate rules.
17. The method of claim 14 , further comprising distributing a majority of a plurality of rules among a plurality of databases of rules to be stored in random access memories and assigning the remaining rules of the plurality of rules to a content addressable memory.
18. At least one non-transitory machine readable storage medium having instructions stored thereon, the instructions when executed by a machine to cause the machine to:
receive a data packet;
perform a parallel mask-based indexing function on the data packet against a rules database comprising a plurality of rules tables, wherein the mask-based indexing function yields zero or more candidate rules per rules table, wherein a rule is to be designated as not a candidate rule if it is guaranteed to not match the data packet, wherein a rule designated as a candidate rule is not guaranteed to match the data packet, and wherein the the rules database is to be searched substantially in parallel;
identify a set of matching rules from among the candidate rules;
select a selected rule from among the set of matching rules based on a priority associated with the selected rule, the selected rule specifying at least one action to be performed on the data packet.
19. The at least one non-transitory machine readable storage medium of claim 18 , the instructions when executed by the machine to further cause the machine to:
calculate an index based on the data packet; and
identify a first candidate rule from a first rules table of the rules database based on the index.
20. The at least one non-transitory machine readable storage medium of claim 19 , the instructions when executed by the machine to further cause the machine to:
access a table of indices based on the calculated index to obtain one or more second indices; and
access the first rules table of the rules database based on the one or more second indices to identify at least one candidate rule from among the candidate rules.
21. The at least one non-transitory machine readable storage medium of claim 18 , the instructions when executed by the machine to further cause the machine to distribute a majority of a plurality of rules among a plurality of databases of rules to be stored in random access memories and to assign the remaining rules of the plurality of rules to a content addressable memory.
22. An apparatus comprising:
means for performing a parallel mask-based indexing function on a data packet against a rules database comprising a plurality of rules tables, wherein the mask-based indexing function yields zero or more candidate rules per rules table, wherein a rule is to be designated as not a candidate rule if it is guaranteed to not match the data packet, wherein a rule designated as a candidate rule is not guaranteed to match the data packet, and wherein the rules database is to be searched substantially in parallel;
means for identifying a set of matching rules from among the candidate rules; and
means for selecting a rule from among the set of matching rules based on a priority associated with the selected rule, the selected rule specifying at least one action to be performed on the data packet.
23. The apparatus of claim 22 , further comprising:
means for calculating an index based on the data packet; and
means for identifying a first candidate rule from a first rules table of the rules database based on the calculated index.
24. The apparatus of claim 23 , further comprising:
means for accessing a table of indices based on the calculated index to obtain one or more second indices; and
means for accessing the first rules table of the rules database based on the one or more second indices to identify at least one candidate rule from among the candidate rules.
25. The apparatus of claim 22 , further comprising means for distributing a majority of a plurality of rules among a plurality of databases of rules to be stored in random access memories and for assigning the remaining rules of the plurality of rules to a content addressable memory.