Error protection for lookup operations in content-addressable memory entries

• US 7,290,083 B2
• Filed: 06/29/2004
• Issued: 10/30/2007
• Est. Priority Date: 06/29/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shoham, Doron, Listman, Shimon, Shapiro, Eliahu
• Primary Examiner(s): Elmore; Stephen C.
• Application Number:
  US10/879,254
• Publication Number:
  US 20050289295A1
• Time in Patent Office: 1,218 Days
• Field of Search: 711/108, 711/118, 711/221, 365/49, 370/392, 709/245
• US Class Current: 711/108
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

Error protection for lookup operations in a content-addressable memory (CAM) entries is disclosed. Values extended to include error protection or error protection fields are stored in CAM entries and a lookup operation is performed on a similarly extended lookup word to determine whether or not an entry is matched, that is, if all or all but some predetermined number of bits match one of the extended entries. For example, one implementation includes multiple CAM entries and logic configured to perform a lookup operation in parallel on each of the CAM entries based on a lookup word to determine whether or not a hit results, where the hit is determined if an entry matches the lookup word in all or all but k bit positions, where n and k are integers, n>k, and k>0.

Claims

1. A method for identifying matching values in a content-addressable memory, the method comprising:

determining a plurality of extended values based on a plurality of values, each of the plurality of extended values including a particular value of the plurality of values and an error-correcting or error-detecting code generated based on the particular value, wherein each of the plurality of extended values are guaranteed to differ from each other by at least n bits;

programming a plurality of content-addressable memory entries with the plurality of extended values; and

performing a lookup operation on said content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said content-addressable memory entries matches the lookup word in all bit positions except for up to a maximum of k bit positions;

wherein n and k are integers, n>

k, and k>

0.

2. The method of claim 1, wherein k is less than or equal to the result of the integer division of (n/2) when n is an odd number and k is less than the result of the integer division of(n/2) when n is an even number.

3. The method of claim 1, comprising identifying a position of the entry in said content-addressable entries if the hit is determined for the entry.

4. The method of claim 1, wherein the lookup word includes an original lookup value and a lookup word error-correcting or error-detecting code generated based on the original lookup value.

5. The method of claim 1, wherein said determining whether or not a hit results includes discriminating between a full and a partial hit, wherein the full hit corresponds to the entry matching the lookup word in all bit positions, and the partial hit corresponds to the entry not matching in all bit positions and the entry matching the lookup word in all bit positions except for up to a maximum of k bit positions.

6. The method of claim 5, comprising in response to said determining the partial hit, performing a lookup operation in a second data structure to verify the hit result.

7. The method of claim 6, comprising in response to said determining the partial hit, updating the entry.

8. The method of claim 5, comprising in response to said determining the partial hit, updating the entry.

9. The method of claim 5, wherein k is less than or equal to the result of the integer division of (n/2) when n is an odd number and k is less than the result of the integer division of (n/2) when n is an even number.

10. A method for identifying matching values in a content-addressable memory, the method comprising:

determining a plurality of extended values based on a plurality of values, each of the plurality of extended values including a particular value of the plurality of values and an error-correcting or error-detecting code determined based on the particular value, wherein each of the plurality of extended values are guaranteed to differ from each other by at least three bits;

programming a plurality of content-addressable memory entries with the plurality of extended values; and

performing a lookup operation on said binary content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said binary content-addressable memory entries matches the lookup word in all bit positions and the hit is also determined if said entry matches the lookup word in all bit positions but one bit position.

11. The method of claim 10, wherein said determining whether or not a hit results includes discriminating between a full and a partial hit, wherein the full hit corresponds to the entry matching the lookup word in all bit positions, and the partial hit corresponds to the entry matching the lookup word in all but one bit positions.

12. The method of claim 11, comprising in response to said determining the partial hit, performing a lookup operation in a second data structure to verify the hit result.

13. The method of claim 11, comprising in response to said determining the partial hit, updating the entry.

14. The method of claim 10, wherein the hit is also determined if the entry of said content-addressable memory entries matches the lookup word in all but two bit positions.

15. The method of claim 14, wherein said determining whether or not a hit results includes discriminating between a full and a partial hit, wherein the full hit corresponds to the entry matching the lookup word in all bit positions, and the partial hit corresponds to the entry matching the lookup word in all but one or two bit positions.

16. The method of claim 15, comprising in response to said determining the partial hit, performing a lookup operation in a second data structure to verify the hit result.

17. The method of claim 15, comprising in response to said determining the partial hit, updating the entry.

18. The method of claim 10, wherein the lookup word includes an original lookup value and a lookup word error-correcting or error-detecting code generated based on the original lookup value.

19. An apparatus for identifying matching values in a content-addressable memory, the apparatus comprising:

means for determining a plurality of extended values based on a plurality of values, each of the plurality of extended values including a particular value of the plurality of values and an error-correcting or error-detecting code determined based on the particular value, wherein each of the plurality of extended values are guaranteed to differ from each other by at least n bits;

means for programming a plurality of content-addressable memory entries with the plurality of extended values; and

means for performing a lookup operation on said content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said content-addressable memory entries matches the lookup word in all bit positions except for up to a maximum of k bit positions;

wherein n and k are integers, n>

k, and k>

0.

20. The apparatus of claim 19, wherein Ic is less than or equal to the result of the integer division of (n/2) when n is an odd number and k is less than the result of the integer division of (n/2) when n is an even number.

21. The apparatus of claim 19, including means for generating the lookup word, the lookup word including an original lookup value and a lookup word error-correcting or error-detecting code generated based on the original lookup value.

22. The apparatus of claim 19, wherein said determining whether or not a hit results includes discriminating between a frill and a partial hit, wherein the full hit corresponds to the entry matching the lookup word in all bit positions, and the partial hit corresponds to the entry not matching in all bit positions and the entry matching the lookup word in all bin bit positions except for up to a maximum of k bit positions.

23. The apparatus of claim 22, comprising means for performing a lookup operation in a second data structure to verify the hit result in response to said determining the partial hit.

24. The apparatus of claim 22, comprising means for updating the entry in response to said determining the partial hit.

25. The apparatus of claim 22, wherein k is less than or equal to the result of the integer division of (n/2) when n is an odd number and k is less than the result of the integer division of(n/2) when n is an even number.

26. An apparatus comprising:

a plurality of content-addressable memory entries;

logic configured to perform a lookup operation on said content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said content-addressable memory entries matches the lookup word in all bit positions except for up to a maximum of k bit positions;

wherein k is an integer greater than zero.

27. The apparatus of claim 26, wherein said logic is configured to identify a position of the entry in said content-addressable entries if the hit is determined for the entry.

28. The apparatus of claim 26, wherein k=1.

29. The apparatus of claim 26, wherein said determining whether or not a hit results includes discriminating between a full and a partial hit, wherein the full hit corresponds to the entry matching the lookup word in all bit positions, and the partial hit corresponds to the entry not matching in all bit positions and the entry matching the lookup word in all bit positions except for up to a maximum of k bit positions.

30. The apparatus of claim 29, wherein k=1.