PERFORMING LOOKUP OPERATIONS USING ASSOCIATIVE MEMORIES OPTIONALLY INCLUDING MODIFYING A SEARCH KEY IN GENERATING A LOOKUP WORD AND POSSIBLY FORCING A NO-HIT INDICATION IN RESPONSE TO MATCHING A PARTICULAR ENTRY

• US 7,103,708 B2
• Filed: 08/10/2002
• Issued: 09/05/2006
• 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: Eatherton, William N., Kanekar, Bhushan Mangesh, Devireddy, Dileep Kumar, Pullela, Venkateshwar Rao, Ertemalp, Fusun, Lee, Jaushin, Priyadarshan, Bangalore L., Warkhede, Priyank Ramesh, Holbrook, Hugh Weber
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): FARROKH, HASHEM
• Application Number:
  US10/215,719
• Publication Number:
  US 20040030803A1
• Time in Patent Office: 1,487 Days
• Field of Search: 711/108, 707/10, 370/235, 370/328, 370/382, 370/386, 370/389, 370/392, 370/400, 370/466, 370351-356, 370/395.3, 370/395.31, 370/395.52, 709/238, 709/242, 709245-246
• 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 performing lookup operations using associative memories, including, but not limited to modifying search keys within an associative memory based on modification mappings, forcing a no-hit condition in response to a highest-priority matching entry including a force no-hit indication, selecting among various sets or banks of associative memory entries in determining a lookup result, and detecting and propagating error conditions. In one implementation, each block retrieves a modification mapping from a local memory and modifies a received search key based on the mapping and received modification data. In one implementation, each of the associative memory entries includes a field for indicating that a successful match on the entry should or should not force a no-hit result. In one implementation, an indication of which associative memory blocks or sets of entries to use in a particular lookup operation is retrieved from a memory.

Claims

1. A method performed by an associative memory for use in performing a lookup operation on a plurality of associative memory entries included in the associative memory, the method comprising:

receiving a search key and modification data;

identifying a modification mapping;

modifying the search key based on the modification data and the modification mapping to generate a lookup word; and

performing the lookup operation on the plurality of associative memory entries based on the lookup word to generate a result.

2. The method of claim 1, wherein said identifying the modification mapping includes identifying the modification mapping based on a profile ID corresponding to the search key.

3. The method of claim 2, wherein the associative memory includes a memory;

and the modification mapping is retrieved from the memory based on the profile ID.

4. The method of claim 2, comprising receiving the profile ID.

5. The method of claim 1, wherein said performing the lookup operation includes identifying a particular entry of the plurality of associative entries as a highest priority matching entry;

wherein the particular entry includes a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result; and

wherein the result includes a no-hit value or signal based on the force no-hit indication of the particular entry.

6. The method of claim 1, wherein said performing the lookup operation includes identifying a particular entry of the plurality of associative entries as a highest priority matching entry;

wherein the particular entry includes a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result; and

wherein the result includes a no-hit value or signal based on the force no-hit indication of the particular entry.

7. An associative memory comprising:

a memory for storing a plurality of modification mappings;

a plurality of associative memory entries;

one or more inputs for receiving a search key and modification data; and

a control for retrieving a particular modification mapping of said plurality of modification mappings from the memory, for modifying the search key based on the modification data and the particular modification mapping to generate a lookup word, and for initiating a lookup operation in the plurality of associative memory entries based on the lookup word.

8. The associative memory of claim 7, wherein said one or more inputs is configured for receiving a profile ID;

and

wherein the control is configured to retrieve the particular modification mapping from the memory based on the profile ID.

9. An associative memory including a plurality of associative memory entries, the associative memory comprising:

means for receiving a search key and modification data;

means for identifying a modification mapping;

means for modifying the search key based on the modification data and the modification mapping to generate a lookup word;

means for performing a lookup operation on the plurality of associative entries based on the lookup word to generate a result.

10. The associative memory of claim 9, including means for identifying the modification mapping based on a profile ID.

11. The associative memory of claim 10, including means for retrieving the modification mapping from memory based on the profile ID.

12. The associative memory of claim 10, including means for receiving the profile ID.

13. The associative memory of claim 9, wherein said means for performing a lookup operation includes means for identifying a particular entry of the plurality of associative entries as a highest priority matching entry;

wherein the particular entry includes a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result; and

wherein the result includes a no-hit value or signal based on the force no-hit indication of the particular entry.

14. The associative memory of claim 9, wherein said means for performing a lookup operation includes means for identifying a particular entry of the plurality of associative entries as a highest priority matching entry;

wherein the particular entry includes a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result; and

wherein the result includes a no-hit value or signal based on the force no-hit indication of the particular entry.

15. A method for use in performing a lookup operation in an associative memory, the associative memory including a first associative memory block and a second associative memory block, the method comprising:

the first associative memory block receiving a profile ID;

the first associative memory block retrieving a first modification mapping based on the profile ID;

the first associative memory block receiving a search key and modification data;

the first associative memory block modifying the search key based on the first modification mapping and said modification data to generate a first lookup word;

the first associative memory block performing a lookup operation based on the first lookup word to produce a first lookup result;

the second associative memory block receiving the profile ID;

the second associative memory block retrieving a second modification mapping based on the profile ID;

the second associative memory block receiving the search key and said modification data;

the second associative memory block modifying the search key based on the second modification mapping and said modification data to generate a second lookup word; and

the second associative memory block performing a lookup operation based on the second lookup word to produce a second lookup result.

16. The method of claim 15, wherein the first lookup result has priority over the second lookup result;

and the method includes selecting the first lookup result over the second lookup result.

17. The method of claim 15, wherein a particular associative memory entry of the first associative memory block corresponding to the first lookup result includes a force no-hit indication identifying that a successful match on the particular associative memory entry should or should not force a no-hit result;

and wherein the first lookup result includes a no-hit value or signal based on the force no-hit indication of the particular associative memory entry.

18. The method of claim 17, wherein the first lookup result has priority over the second lookup result;

and the method includes selecting the second lookup result over the first lookup result based on the no-hit value or signal of the first lookup result.

19. An associative memory for producing a first lookup result and a second lookup result, the associative memory comprising:

a first associative memory block including;

a first control,

a first memory, and

a first plurality of associative memory entries;

wherein the first control is configured to receive a profile ID, a search key, and modification data, to retrieve a first modification mapping from the first memory based on the profile ID, to generate a first lookup word based on the search key, said modification data, and the first modification mapping, and to perform a lookup operation on the first plurality of associative memory entries based on the first lookup word to produce the first lookup result; and

a second associative memory block including;

a second control,

a second memory, and

a second plurality of associative memory entries;

wherein the second control is configured to receive the profile ID, the search key, and said modification data, to retrieve a second modification mapping from the second memory based on the profile ID, to generate a second lookup word based on the search key, said modification data, and the second modification mapping, and to perform a lookup operation on the second plurality of associative memory entries based on the second lookup word to produce the second lookup result.

20. The associative memory of claim 19, wherein the first lookup result has priority over the second lookup result;

and the associative memory includes means for selecting the first lookup result over the second lookup result.

21. The associative memory of claim 19, wherein a particular associative memory entry of the first plurality of associative memory entries corresponding to the first lookup result includes a force no-hit indication identifying that a successful match on the particular associative memory entry should or should not force a no-hit result;

and wherein the first lookup result includes a no-hit value or signal based on the force no-hit indication of the particular associative memory entry.

22. The associative memory of claim 21, wherein the first lookup result has priority over the second lookup result;

and the associative memory includes means for selecting the second lookup result over the first lookup result based on the no-hit value or signal of the first lookup result.

23. A computer-readable medium having stored thereon an associative memory entry, the associative memory entry comprising:

a first field including a value for use in a matching operation on a lookup word; and

a second field including data for indicating that a successful match on the associative memory entry should or should not force a no-hit result.

24. The computer-readable medium of claim 23, wherein the associative memory entry comprises a third field including a mask for use in the matching operation on the lookup word.

25. The computer-readable medium of claim 23, wherein the associative memory entry comprises a fourth field indicating whether the entry is valid or not valid.

26. The computer-readable medium of claim 23, wherein the associative memory entry comprises a fifth field indicating an error detection value for the entry.

27. A computer-readable medium having stored thereon an associative memory entry, the associative memory entry comprising:

a first field including a value for use in a matching operation on a lookup word; and

a second field including data to force a no-hit result should the associative memory entry be a highest-priority matching entry.

28. A method for generating a lookup result, the method comprising:

programming a plurality of associative memory entries, at least a particular entry of the plurality of associative memory entries including a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result;

performing a lookup operation based on a lookup word to identify the particular entry as a highest-priority matching entry; and

generating a no-hit signal in response to the particular entry being identified as the highest-priority matching entry and the particular entry including the force no-hit indication.

29. A method for generating a lookup result, the method comprising:

programming a first plurality of associative memory entries, at least a first particular entry of the first plurality of associative memory entries including a force no-hit indication;

programming a second plurality of associative memory entries, the first plurality of associative memory entries having a higher priority than the second plurality of associative memory entries;

performing a lookup operation based on a first lookup word to identify the first particular entry as a first highest-priority matching entry of the first plurality of associative memory entries;

generating a first no-hit signal in response to the first particular entry being identified as the first highest-priority matching entry and the first particular entry including the force no-hit indication;

performing a lookup operation based on a second lookup word to identify the second particular entry as a second highest-priority matching entry of the second plurality of associative memory entries;

generating a second highest-priority signal identifying the second particular entry; and

identifying the second particular entry as the lookup result in response to the first no-hit signal and the second highest-priority signal.

30. The method of claim 29, wherein a first bank of an associative memory includes the first plurality of associative memory entries, and a second bank of the associative memory includes the second plurality of associative memory entries.

31. An associative memory comprising:

a plurality of associative memory entries, each of the plurality of associative memory entries comprising a value for use in a matching operation on a lookup word and a force or do not force a no-hit indication identifying that a successful match on said associative memory entry should or should not force a no-hit result; and

control logic for performing a lookup operation on the plurality of associative memory entries based on a lookup word to identify a particular highest-priority matching entry.

32. The associative memory of claim 31, wherein said control logic signals a no-hit indication when the particular highest-priority matching entry includes a value corresponding to a force a no-hit indication.

33. An apparatus comprising:

means for programming a plurality of entries of an associative memory, at least a particular entry of the plurality of entries including a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result;

means for performing a lookup operation based on a lookup word to identify the particular entry as a highest-priority matching entry; and

means for generating a no-hit signal in response to the particular entry being identified as the highest-priority matching entry and the particular entry including the force no-hit indication.

34. The apparatus of claim 33, wherein the associative memory is a ternary or binary content-addressable memory.