Lookup cluster complex
View Patent ↗A packet processor provides for rule matching of packets in a network architecture. The packet processor includes a lookup cluster complex having a number of lookup engines and respective on-chip memory units. The on-chip memory stores rules for matching against packet data. Each of the lookup engines receives a key request associated with a packet and determines a subset of the rules to match against the packet data. As a result of the rule matching, the lookup engine returns a response message indicating whether a match is found.
1. A method comprising:
receiving a request associated with a packet, the request including an identifier (ID);
selecting at least one entry in a table indicated by the ID, the entry providing a starting address associated with a set of rules;
determining a subset of rules based on at least one field of the request, the subset of rules being a portion of the set of rules;
applying the at least one field against the subset of rules; and
outputting a response signal indicating whether the at least one field matches at least one rule of the subset of rules.
2. The method of claim 1 , wherein the request includes a key format table index.
3. The method of claim 2 , further comprising parsing the request based on the key format table index.
4. The method of claim 1 , wherein the set of rules is a portion of rules stored in a memory.
5. The method of claim 1 , wherein determining a subset of rules includes determining at least one bucket, the at least one bucket including pointers to the subset of rules.
6. The method of claim 5 , wherein the at least one bucket includes a plurality of buckets, and wherein the entry includes a node associated with the plurality of buckets.
7. The method of claim 6 , wherein processing the entry includes processing the node to determine the plurality of buckets.
8. The method of claim 6 , wherein the node is associated with the plurality of buckets via at least one intermediary node.
9. The method of claim 1 , wherein the subset of rules is ordered by priority.
10. The method of claim 9 , wherein the at least one field is applied against the subset of rules in a descending order of priority.
11. The method of claim 10 , wherein the response signal is output after a first match between the at least one field and the subset of rules is located.
12. The method of claim 11 , wherein applying the at least one field against the subset of rules is stopped after the first match is located.
13. The method of claim 1 , wherein selecting at least one entry in a table indicated by the ID includes selecting a plurality of entries.
14. The method of claim 13 , further comprising selecting among a plurality of match results based on a predetermined priority, each match result corresponding to one of the plurality of entries.
15. An apparatus for processing a packet comprising:
a first engine configured to:
receive a request associated with a packet, the request including an identifier (ID);
select at least one entry in a table indicated by the ID, the entry providing a starting address associated with a set of rules; and
determine a subset of rules based on at least one field of the request, the subset of rules being a portion of the set of rules; and
a second engine configured to apply the at least one field against the subset of rules and output a response signal indicating whether the at least one field matches at least one rule of the subset of rules.
16. The apparatus of claim 15 , wherein the request includes a key format table index.
17. The apparatus of claim 16 , wherein the first engine is further configured to parse the request based on the key format table index.
18. The apparatus of claim 15 , wherein the set of rules is a portion of rules stored in a memory.
19. The apparatus of claim 15 , wherein the first engine determines at least one bucket, the at least one bucket including pointers to a subset of rules.
20. The apparatus of claim 19 , wherein the at least one bucket includes a plurality of buckets, and wherein the entry includes a node associated with the plurality of buckets.
21. The apparatus of claim 20 , wherein processing the entry includes processing the node to determine the plurality of buckets.
22. The apparatus of claim 20 , wherein the node is associated with the plurality of buckets via at least one intermediary node.
23. The apparatus of claim 15 , wherein the subset of rules is ordered by priority.
24. The apparatus of claim 23 , wherein the at least one field is applied against the subset of rules in a descending order of priority.
25. The apparatus of claim 24 , wherein the response signal is output after a first match between the at least one field and the subset of rules is located.
26. The apparatus of claim 25 , wherein applying the at least one field against the subset of rules is stopped after the first match is located.
27. The apparatus of claim 15 , further comprising a third engine configured to retrieve the subset of rules from a memory.