Performing lookup operations on associative memory entries

• US 7,237,059 B2
• Filed: 12/28/2005
• Issued: 06/26/2007
• Est. Priority Date: 08/10/2002
• Status: Expired due to Term

• 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, Holbrook, Hugh Weber, Priyadarshan, Bangalore L., Warkhede, Priyank Ramesh
• Primary Examiner(s): Farrokh; Hashem
• Application Number:
  US11/321,918
• Publication Number:
  US 20060106977A1
• Time in Patent Office: 545 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

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 the associative memory, the associative memory including a plurality of associative memory entries and memory for storing a plurality of modification mappings, said modification mappings including a particular modification mapping, the method comprising:

receiving a search key;

receiving modification data;

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

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

2. The method of claim 1, comprising receiving a profile ID;

and retrieving the particular modification mapping from said memory based on the profile ID.

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

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

wherein the result identifies a no-hit based on the force no-hit indication of the particular entry.

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

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

wherein the result identifies a hit based on the force no-hit indication of the particular entry.

5. The method of claim 1, wherein the associative memory is a binary content-addressable memory.

6. The method of claim 1, wherein the associative memory is a ternary content-addressable memory.

7. The method of claim 1, wherein modifying the search key includes replacing one or more bits or bytes in the search key with data from said modification data based on the modification mapping.

8. An apparatus including a plurality of associative memory entries, each of the plurality of associative memory entries comprising:

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

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; and

logic for identifying a no-match result indicating that there was not a matching entry of said associative memory entries if the second field of the highest-priority matching entry of said associative memory entries matching the lookup word indicates that a successful match should force a no-hit result.

9. The apparatus of claim 8, wherein each of the plurality of associative memory entries includes a third field including a mask for use in the matching operation on the lookup word.

10. The apparatus of claim 9, wherein each of the plurality of associative memory entries includes a fourth field indicating whether the entry is valid or not valid.

11. The apparatus of claim 10, wherein each of the plurality of associative memory entries includes a fifth field indicating an error detection value for the entry.

12. A method performed by an associative memory in generating a lookup result, the associative memory including 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, the method comprising:

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.

13. The method of claim 12, wherein the associative memory is a binary content-addressable memory.

14. The method of claim 12, wherein the associative memory is a ternary content-addressable memory.

15. An associative memory configured to generated a lookup result, the associative memory including 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, the associative memory comprising:

means for performing a lookup operation based on a lookup word to identify the particular entry as a highest-priority matching entry, and 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.

16. The associative memory of claim 15, wherein the associative memory is a binary content-addressable memory.

17. The associative memory of claim 15, wherein the associative memory is a ternary content-addressable memory.

18. A method for generating a lookup result on a first plurality of associative memory entries and on a second 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, the first plurality of associative memory entries having a higher priority than the second plurality of associative memory entries, the method comprising:

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.

19. The method of claim 18, 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.

20. The method of claim 18, wherein each of said first plurality and second plurality of associative memory entries is a binary content-addressable memory entry.

21. The method of claim 18, wherein each of said first plurality and second plurality of associative memory entries is a ternary content-addressable memory.

22. A method for generating a lookup result on a first plurality of associative memory entries and on a second 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, the first plurality of associative memory entries having a higher priority than the second plurality of associative memory entries, the method comprising:

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

identifying the second particular entry as the lookup result in response to the first particular entry being identified as the first highest-priority matching entry, the first particular entry including the force no-hit indication, and the second particular entry being identified as the second highest-priority matching entry.

23. The method of claim 22, 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.

24. The method of claim 22, wherein each of said first plurality and second plurality of associative memory entries is a binary content-addressable memory entry.

25. The method of claim 22, wherein each of said first plurality and second plurality of associative memory entries is a ternary content-addressable memory.

26. An apparatus for generating a lookup result on a first plurality of associative memory entries and on a second 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, the first plurality of associative memory entries having a higher priority than the second plurality of associative memory entries, the apparatus comprising:

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

means for identifying the second particular entry as the lookup result in response to the first particular entry being identified as the first highest-priority matching entry, the first particular entry including the force no-hit indication, and the second particular entry being identified as the second highest-priority matching entry.

27. The apparatus of claim 26, wherein each of said first plurality and second plurality of associative memory entries is a binary content-addressable memory entry.

28. The apparatus of claim 26, wherein each of said first plurality and second plurality of associative memory entries is a ternary content-addressable memory.

29. An associative memory configured to perform lookup operations on a plurality of associative memory entries, 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, the associative memory comprising:

means for performing a lookup operation based on a lookup word to identify the particular entry as a highest-priority matching entry of said associative memory entries; 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.

30. The associative memory of claim 29, wherein the associative memory is a binary content-addressable memory.

31. The associative memory of claim 29, wherein the associative memory is a ternary content-addressable memory.