Generating and merging lookup results to apply multiple features

• US 20070002862A1
• Filed: 08/01/2006
• Published: 01/04/2007
• Est. Priority Date: 08/10/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bhattacharya, Dipankar, Chen, Qizhong, Pullela, Venkateshwar, Devireddy, Dileep, Saharia, Gyaneshwar, Kanekar, Bhushan
• Granted Patent: US 7,350,020 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

Methods, apparatus, and other mechanisms are disclosed for merging lookup results, such as from one or more associative memory banks and/or memory devices. In one exemplary implementation, multiple associative memories or associative memory banks are configured to substantially simultaneously generate a plurality of lookup results based on a lookup value. Multiple memories are each configured to generate a corresponding result based on the lookup result generated by its corresponding associative memory or associative memory bank. A combiner is configured to receive and merge these corresponding results generated substantially simultaneously in order to identify the merged lookup result.

Claims

1. An apparatus configured to substantially simultaneously perform multiple lookup operations on associative memory entries and then on their corresponding adjunct memory entries in identifying a merged lookup result, the apparatus comprising:

a first plurality of associative memory entries and corresponding adjunct memory values programmed to implement a first set of access list control entries corresponding to a first feature of a plurality of access control list entries; and

a second plurality of associative memory entries and corresponding adjunct memory values programmed to implement a second set of access list control entries corresponding to a second feature of the plurality of access control list entries;

wherein said apparatus is configured to substantially simultaneously perform lookup operations based on a lookup value in the first plurality of associative memory entries and in the second plurality of associative memory entries in order to generate a plurality of associative memory lookup results which are used to retrieve corresponding results from said corresponding adjunct memory values; and

a combiner configured to receive and merge said corresponding results generated substantially simultaneously in order to identify the merged lookup result.

2. The apparatus of claim 1, wherein said corresponding results each include a precedence indication;

wherein the combiner selects one of said corresponding results as the merged lookup result based on said precedence indication.

3. The apparatus of claim 1, wherein each of said corresponding results correspond to a different feature as defined in an access control list including the first and second sets of access list control entries of the plurality of access control list entries.

4. The apparatus of claim 1, including a packet processor configured to determine the lookup value based on one or more fields extracted from a packet and to process the packet based on the merged lookup result.

5. An apparatus configured to substantially simultaneously perform multiple lookup operations on associative memory entries and then on their corresponding adjunct memory entries in identifying a merged lookup result, the apparatus comprising:

a plurality of associative memories configured to substantially simultaneously generate a plurality of lookup results based on a lookup value;

a plurality of memories;

wherein each of the plurality of memories is communicatively coupled to one of the plurality of associative memories, and is configured to generate a corresponding result based on said lookup result generated by said associative memory to which it is communicatively coupled; and

a combiner configured to receive and merge said corresponding results generated substantially simultaneously in order to identify the merged lookup result.

6. The apparatus of claim 5, wherein said merging includes evaluating indications included in each of said corresponding results.

7. The apparatus of claim 6, wherein said indications include precedence or action indications.

8. The apparatus of claim 6, wherein said indications include precedence indications.

9. The apparatus of claim 5, wherein each of said corresponding results correspond to a different feature as defined in an access control list.

10. The apparatus of claim 5, including a packet processor configured to determine the lookup value based on one or more fields extracted from a packet and to process the packet based on the merged lookup result.

11. An apparatus configured to substantially simultaneously perform multiple lookup operations on associative memory entries and then on their corresponding adjunct memory entries in identifying a merged lookup result, the apparatus comprising:

a plurality of associative memories banks configured to substantially simultaneously generate a plurality of lookup results based on a lookup value;

a plurality of memories;

wherein each of the plurality of memories is communicatively coupled to one of the plurality of associative memory banks, and is configured to generate a corresponding result based on said lookup result generated by said associative memory to which it is communicatively coupled; and

a combiner configured to receive and merge said corresponding results generated substantially simultaneously in order to identify the merged lookup result.

12. The apparatus of claim 11, wherein said merging includes evaluating indications included in each of said corresponding results.

13. The apparatus of claim 12, wherein said indications include precedence or action indications.

14. The apparatus of claim 12, wherein said indications include precedence indications.

15. The apparatus of claim 11, wherein each of said corresponding results correspond to a different feature as defined in an access control list.

16. The apparatus of claim 11, including a packet processor configured to determine the lookup value based on one or more fields extracted from a packet and to process the packet based on the merged lookup result.

17. A method for identifying a merged lookup result, the method comprising:

determining a lookup value based on one or more fields extracted from a packet;

performing substantially simultaneous lookup operations in a plurality of associative memories to generate a plurality of associative memory results, and performing lookup operations in corresponding adjunct memories based on the plurality of associative memory results to generate a plurality of lookup results;

merging the plurality of lookup results to identify the merged result; and

processing the packet based on the merged lookup result.

18. The method of claim 17, each of the plurality of lookup results corresponds to a different feature of a type defined in an access control list.

19. The method of claim 18, wherein the type includes a security operation or a quality of service operation.

120. The method of claim 17, wherein the lookup value includes at least one autonomous system number, said at least one autonomous system number identifying a set of communication devices under a single administrative authority.

21. The method of claim 17, wherein said merging the plurality of lookup results to identify the merged result includes evaluating indications included in each of the plurality of lookup results.

22. An apparatus for identifying a merged lookup result, the apparatus comprising:

means for determining a lookup value based on one or more fields extracted from a packet;

means for performing substantially simultaneous lookup operations in a plurality of associative memories to generate a plurality of associative memory results;

means for performing lookup operations in corresponding adjunct memories based on the plurality of associative memory results to generate a plurality of lookup results;

means for merging the plurality of lookup results to identify the merged result; and

means for processing the packet based on the merged lookup result.

23. The apparatus of claim 22, each of the plurality of lookup results corresponds to a different feature of a type defined in an access control list.

24. The apparatus of claim 23, wherein the type includes a security operation or a quality of service operation.

25. The apparatus of claim 22, wherein the lookup value includes at least one autonomous system number, said at least one autonomous system number identifying a set of communication devices under a single administrative authority.

26. The apparatus of claim 22, wherein said means for merging the plurality of lookup results to identify the merged result includes means for evaluating indications included in each of the plurality of lookup results.