Associative memory entries with force no-hit and priority indications of particular use in implementing policy maps in communication devices

• US 7,082,492 B2
• Filed: 07/29/2003
• Issued: 07/25/2006
• 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, Scheid, Stephen Francis, Devireddy, Dileep Kumar, Pullela, Venkateshwar Rao
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): Farrokh, Hashem
• Application Number:
  US10/630,176
• Publication Number:
  US 20040170172A1
• Time in Patent Office: 1,092 Days
• Field of Search: None
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

Abstract

Methods and apparatus are disclosed for defining and using associative memory entries with force no-hit and priority indications of particular use in implementing policy maps in communication devices. In one use, a set of entries is determined based on a policy map with a force no-hit indication being associated with one or more of the entries. Additionally, programmable priority indications may be associated with one or more of the entries, or with the associative memory devices, associative memory banks, etc. The force no-hit indications are often used in response to identified deny instructions in an access control list or other policy map. A lookup operation is then performed on these associative memory entries, with highest matching result or results identified based on the programmed and/or implicit priority level associated with the entries, or with the associative memory devices, associative memory banks, etc.

Claims

1. A method for performing operations for programming one or more associative memories, the method comprising:

identifying a specified policy map;

determining a set of entries based on the specified policy map; and

associating a force no-hit indication with one or more entries of the set of entries;

wherein the force no-hit indication, when associated with a determined highest-matching entry of a group of entries participating in a lookup operation, causes the result of the lookup operation for the group of entries to be considered as not resulting in a hit.

2. The method of claim 1, comprising programming one or more associative memories with the set of entries.

3. The method of claim 1, comprising programming a plurality of banks of an associative memory with the set of entries.

4. The method of claim 3, comprising associating a priority indication with each entry of the set of entries.

5. The method of claim 4, comprising:

programming a plurality of banks of an associative memory with the set of entries; and

associating a programmable priority level with each of the plurality of banks.

6. The method of claim 1, wherein at least one of said one or more entries corresponds to a deny operation.

7. A method for performing operations for programming one or more associative memories, the method comprising:

identifying a specified policy map;

determining a set of entries based on the specified policy map;

programming a plurality of banks of an associative memory with the set of entries; and

associating a programmable priority level with each of the plurality of banks.

8. An apparatus for programming one or more associative memories comprising:

means for identifying a specified policy map;

means for determining a set of entries based on the specified policy map; and

means for associating a force no-hit indication with one or more entries of the set of entries;

wherein the force no-hit indication, when associated with a determined highest-matching entry of a group of entries participating in a lookup operation, causes the result of the lookup operation for the group of entries to be considered as not resulting in a hit.

9. The apparatus of claim 8, comprising means for programming one or more associative memories with the set of entries.

10. The apparatus of claim 9, wherein at least one of said one or more entries corresponds to a deny operation.

11. The apparatus of claim 8, comprising means for programming a plurality of banks of an associative memory with the set of entries.

12. The apparatus of claim 11, comprising means for associating a priority indication with each entry of the set of entries.

13. The apparatus of claim 12, comprising:

means for programming a plurality of banks of an associative memory with the set of entries; and

means for associating a programmable priority level with each of the plurality of banks.

14. An apparatus for programming one or more associative memories comprising:

means for identifying a specified policy map;

means for determining a set of entries based on the specified policy map;

means for programming a plurality of banks of an associative memory with the set of entries, including means for associating a programmable priority level with each of the plurality of banks.

15. An associative memory comprising:

a plurality of associative memory banks;

wherein each of said one or more associative memory banks includes a plurality of entries; and

wherein each of the plurality of entries includes a force no-hit value field;

wherein the force no-hit indication, when associated with a determined highest-matching entry of a group of entries participating in a lookup operation, causes the result of the lookup operation for the group of entries to be considered as not resulting in a hit.

16. The associative memory of claim 15, wherein each of the plurality of entries includes a priority indication field.

17. The associative memory of claim 16, comprising:

a plurality of mechanisms for identifying a block highest priority matching entry for each of the plurality of associative memory banks; and

a priority mechanism for identifying a highest priority one of said associative memory entries based on the block highest priority matching entry of each of the plurality of associative memory banks and values of the priority indication fields associated with the for the block highest priority matching entry of each of the plurality of associative memory banks.

18. An associative memory comprising:

a plurality of associative memory banks, wherein each of said one or more associative memory banks includes a plurality of entries;

means for identifying a block highest priority matching entry for each of the plurality of associative memory banks; and

means for identifying a highest priority one of said associative memory entries based on the block highest priority matching entry of each of the plurality of associative memory banks and values of the priority indication fields associated with the block highest priority matching entry of each of the plurality of associative memory banks.

19. A computer-readable medium containing computer-executable instructions for performing steps for performing operations for programming one or more associative memories, said steps comprising:

identifying a specified policy map;

determining a set of entries based on the specified policy map; and

associating a force no-hit indication with one or more entries of the set of entries;

wherein the force no-hit indication, when associated with a determined highest-matching entry of a group of entries participating in a lookup operation, causes the result of the lookup operation for the group of entries to be considered as not resulting in a hit.

20. The computer-readable medium of claim 19, wherein said steps comprise programming one or more associative memories with the set of entries.

21. The computer-readable medium of claim 19, wherein said steps comprise programming a plurality of banks of an associative memory with the set of entries.

22. The computer-readable medium of claim 21, wherein said steps comprise associating a priority indication with each entry of the set of entries.

23. The computer-readable medium of claim 22, wherein said steps comprise:

programming a plurality of banks of an associative memory with the set of entries; and

associating a programmable priority level with each of the plurality of banks.

24. The computer-readable medium of claim 19, wherein at least one of said one or more entries corresponds to a deny operation.

25. A computer-readable medium containing computer-executable instructions for performing operations for programming one or more associative memories, said operations comprising:

identifying a specified policy map;

determining a set of entries based on the specified policy map;

programming a plurality of banks of an associative memory with the set of entries; and

associating a programmable priority level with each of the plurality of banks.