Generating and merging lookup results to apply multiple features

• US 7,177,978 B2
• Filed: 07/29/2003
• Issued: 02/13/2007
• Est. Priority Date: 08/10/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kanekar, Bhushan Mangesh, Bhattacharya, Dipankar, Devireddy, Dileep Kumar, Pullela, Venkateshwar Rao, Saharia, Gyaneshwar S., Chen, Qizhong
• Primary Examiner(s): Peugh; Brian R.
• Assistant Examiner(s): Farrokh; Hashem
• Application Number:
  US10/630,174
• Publication Number:
  US 20040170171A1
• Time in Patent Office: 1,295 Days
• Field of Search: 711/108
• US Class Current: 711/108
• 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. An access list is identified. A first set of entries corresponding to a first feature of the access control list entries and a second set of entries corresponding to a second feature of the access control list entries are identified. First and second associative memory banks are programmed respectively based on the first and second sets of entries. Lookup operations are then typically performed substantially simultaneously on the first and second sets of associative memory entries programmed in the associative memory banks to generate multiple lookup results, with these results typically being identified directly, or via a lookup operation in an adjunct memory or other storage mechanism. These lookup results are then combined to generate a merged lookup result.

Claims

1. A method for indentifying a merged lookup result, the method comprising:

identifying an access control list including a plurality of access control list entries;

identifying a first set of access control list entries corresponding to a first feature of said plurality of access control list entries;

programming a first associative memory bank and a first adjunct memory with first associative memory entries corresponding to the first set of access control list entries

identifying a second set of access control list entries corresponding to a second feature of said plurality of access control list entries; and

programming a second associative memory bank and a second adjunct memory with second associative memory entries corresponding to the second set of access control list entries;

wherein said first associative memory entries have a higher lookup precedence than said second associative memory entries.

2. The method of claim 1, comprising:

identifying a lookup value;

performing lookup operations in the first associative memory bank and the first adjunct memory to generate a first lookup result;

performing lookup operations in the second associative memory bank and the second adjunct memory to generate a second lookup result; and

merging the first and the second lookup results to identify a merged result.

3. The method of claim 2, wherein said lookup operations in the first and the second associative memory banks are performed substantially simultaneously.

4. The method of claim 2, wherein if the first associate memory result corresponds to a deny operation, the merged result corresponds to a drop packet operation.

5. The method of claim 2, wherein if the first associate memory result corresponds to a permit operation and the second associative memory result corresponds to a permit operation, the merged result corresponds to a permit operation.

6. The method of claim 2, wherein if the first associate memory result corresponds to a permit operation and the second associative memory result corresponds to a deny operation, the merged result corresponds to a drop packet operation.

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

identifying a packet;

identifying a first lookup value;

performing substantially simultaneous lookup operations in a plurality of associative memories and adjunct memories to generate a plurality of first lookup results;

merging the plurality of first lookup results to identify a merged first result;

identifying a second lookup value;

performing substantially simultaneous lookup operations in the plurality of associative memories and adjunct memories to generate a plurality of second lookup results; and

merging the plurality of second lookup results and the merged first result to identify a merged second result.

8. The method of claim 7, each of the plurality of first lookup results correspond to a different feature of a first type as defined in an access control list.

9. The method of claim 8, each of the plurality of second lookup results correspond to a different feature of a second type as defined in the access control list.

10. The method of claim 9, wherein the first type includes a security operation and the second type includes a quality of service operation.

11. The method of claim 7, wherein the first 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.

12. A computer-readable medium containing computer-executable instructions for performing steps for identifying a merged lookup result, said steps comprising:

identifying an access control list including a plurality of access control list entries;

identifying a first set of access control list entries corresponding to a first feature of said plurality of access control list entries;

programming a first associative memory bank and a first adjunct memory with first associative memory entries corresponding to the first set of access control list entries

identifying a second set of access control list entries corresponding to a second feature of said plurality of access control list entries; and

programming a second associative memory bank and a second adjunct memory with second associative memory entries corresponding to the second set of access control list entries;

wherein said first associative memory entries have a higher lookup precedence than said second associative memory entries.

13. The computer-readable medium of claim 12, wherein said steps comprise:

identifying a lookup value;

performing lookup operations in the first associative memory bank and the first adjunct memory to generate a first lookup result;

performing lookup operations in the second associative memory bank and the second adjunct memory to generate a second lookup result; and

merging the first and the second lookup results to identify a merged result.

14. The computer-readable medium of claim 13, wherein if the first associate memory result corresponds to a deny operation, the merged result corresponds to a drop packet operation.

15. The computer-readable medium of claim 13, wherein if the first associate memory result corresponds to a permit operation and the second associative memory result corresponds to a permit operation, the merged result corresponds to a permit operation.

16. The computer-readable medium of claim 13, wherein if the first associate memory result corresponds to a permit operation and the second associative memory result corresponds to a deny operation, the merged result corresponds to a drop packet operation.

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

means for identifying an access control list including a plurality of access control identifying an access control list including a plurality of access control list entries;

means for identifying a first set of access control list entries corresponding to a first feature of said plurality of access control list entries;

means for programming a first associative memory bank and a first adjunct memory with first associative memory entries corresponding to the first set of access control list entries

means for identifying a second set of access control list entries corresponding to a second feature of said plurality of access control list entries; and

means for programming a second associative memory bank and a second adjunct memory with second associative memory entries corresponding to the second set of access control list entries;

wherein said first associative memory entries have a higher lookup precedence than said second associative memory entries.

18. The apparatus of claim 17, comprising:

means for identifying a lookup value;

means for performing lookup operations in the first associative memory bank and the first adjunct memory to generate a first lookup result;

means for performing lookup operations in the second associative memory bank and the second adjunct memory to generate a second lookup result; and

means for merging the first and the second lookup results to identify a merged result.

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

means for identifying a packet;

means for identifying a first lookup value;

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

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

means for identifying a second lookup value;

means for performing substantially simultaneous lookup operations in the plurality of associative memories and adjunct memories to generate a plurality of second lookup results; and

means for merging the plurality of second lookup results and the merged first result to identify a merged second result.

20. The apparatus of claim 19, wherein:

each of the plurality of first lookup results correspond to a different feature of a first type as defined in an access control list; and

each of the plurality of second lookup results correspond to a different feature of a second type as defined in the access control list.