Error protection for associative memory entries and lookup operations performed thereon

• US 7,305,519 B1
• Filed: 03/29/2004
• Issued: 12/04/2007
• Est. Priority Date: 03/29/2004
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Nagaraj, Ashwath
• Primary Examiner(s): PORTKA, GARY J
• Application Number:
  US10/813,210
• Time in Patent Office: 1,345 Days
• Field of Search: None
• US Class Current: 711/108
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories

Abstract

Error protection is provided for associative memory entries and lookup operations performed thereon. Protected associative memory entries are determined which include one or more protection bits. These protected entries are programmed into an associative memory, typically with each protected entry being programmed into two or more consecutive locations. Corresponding protected lookup words are generated and used to perform lookup operations in the associative memory. For binary content-addressable memories (CAMs) and ternary content-addressable memory (TCAMs), one or more error detection bits are used per entry to prevent or at least reduce the possibility of a lookup error. For example, a single parity bit or multiple error-correction code (ECC) bits may be used per entry. The use of the protection bits reduces the possibility of a false matching of a corrupted entry, and the duplicate entries reduce the possibility of not matching an entry that should be matched as all copies of the entry must be corrupt in order to not match one of the entries during a lookup operation.

Claims

1. A method for protecting associative memory entries, the method comprising:

identifying a plurality of masks used for a plurality of associative memory entries; and

determining a protected entry for each entry in the plurality of associative memory entries, said each entry including an original data portion and an original mask portion, the protected entry including a protected data portion and a protected mask portion, the protected data portion including the original data portion and a protection bit located at a bit position corresponding to the original mask portion, and the protected mask portion including the original mask portion and a mask to enable the protection bit corresponding to the original mask portion and to mask protection bits corresponding to other masks of the plurality of masks;

wherein the protection bit is determined by a parity or other error protection calculation on a result of the original data portion masked with the original mask portion.

2. The method of claim 1, comprising programming an associative memory with each of said protected entries.

3. The method of claim 2, wherein said programming the associative memory with each of said protected entries includes programming each of said protective entries in two consecutive locations in the associative memory.

4. The method of claim 3, comprising performing a lookup operation in the associative memory based on a protected lookup word.

5. The method of claim 4, wherein the protected lookup word includes a lookup word original data portion and a lookup word protected data portion, the lookup word protected data portion including a plurality of bits, each of the plurality of bits being determined by a parity or other error protection calculation on a result of the lookup word original data portion masked with a different one of the plurality of masks.

6. The method of claim 5, wherein the plurality of masks consists of n masks and the lookup word protected data portion consists of n bits.

7. The method of claim 2, comprising performing a lookup operation in the associative memory based on a protected lookup word.

8. The method of claim 7, wherein the protected lookup word includes a lookup word original data portion and a lookup word protected data portion, the lookup word protected data portion including a plurality of bits, each of the plurality of bits being determined by a parity or other error protection calculation on a result of the lookup word original data portion masked with a different one of the plurality of masks.

9. The method of claim 8, wherein the plurality of masks consists of n masks and the lookup word protected data portion consists of n bits.

10. The method of claim 1, wherein the plurality of masks consists of n masks and the mask in the protected mask portion consists of n bits.

11. A method for protecting associative memory entries, the method comprising:

determining a protected entry for each original entry of a plurality of original associative memory entries, the protected entry including the original entry and one or more protection bits, wherein said one or more protection bits are determined by a parity or other error protection calculation on the original entry; and

programming an associative memory with said each determined protected entry such that each particular entry of said determined protected entries is completely replicated in two or more consecutive entries in the associative memory.

12. The method of claim 11, comprising:

determining a protected lookup value based on an original lookup value, the protected lookup value including the original lookup value and one or more protection bits determined by said parity or other error protection calculation on the original lookup value; and

performing a lookup operation in the associative memory based on the protected lookup value.

13. An apparatus for protecting associative memory entries, the apparatus comprising:

means for determining a protected entry for each original entry of a plurality of original associative memory entries, the protected entry including the original entry and one or more protection bits, wherein said one or more protection bits are determined by a parity or other error protection calculation on the original entry; and

means for programming an associative memory with said each determined protected entry such that each particular entry of said determined protected entries is completely replicated in two or more consecutive entries in the associative memory.

14. The apparatus of claim 13, comprising:

means for determining a protected lookup value based on an original lookup value, the protected lookup value including the original lookup value and one or more protection bits determined by said parity or other error protection calculation on the original lookup value; and

means for performing a lookup operation in the associative memory based on the protected lookup value.

15. A method for performing lookup operations on an associative memory, the method comprising:

determining a protected lookup word based on a lookup word, the lookup word including a lookup word original data portion, the protected lookup word including the lookup word original data portion and a plurality of error protection bits, each of the plurality of protection bits corresponding to one of a plurality of masks and being determined by a parity or other error protection calculation on a result of the original data portion masked with a different one of the plurality of masks; and

performing a lookup operation in the associative memory based on the protected data word.

16. An apparatus for performing lookup operations on an associative memory, the apparatus comprising:

means for determining a protected lookup word based on a lookup word, the lookup word including a lookup word original data portion, the protected lookup word including the lookup word original data portion and a plurality of error protection bits, each of the plurality of protection bits corresponding to one of a plurality of masks and being determined by a parity or other error protection calculation on a result of the original data portion masked with a different one of the plurality of masks; and

means for performing a lookup operation in the associative memory based on the protected data word.

17. An apparatus for performing lookup operations, the apparatus comprising:

a protected lookup word generator for determining a protected lookup word, the protected lookup word generator configured to receive a lookup word, the lookup word including a lookup word original data portion, the protected lookup word including the lookup word original data portion and a plurality of error protection bits, each of the plurality of protection bits corresponding to one of a plurality of masks and being determined by a parity or other error protection calculation on a result of the original data portion masked with a different one of the plurality of masks; and

an associative memory configured to receive the protected lookup word and to generate an associative memory result based on the protected lookup word.

18. The apparatus of claim 17, comprising a protective associative memory entry generator configured to determine a protected entry for each entry in a plurality of associative memory entries, said each entry including an original data portion and an original mask portion, the protected entry including a protected data portion and a protected mask portion, the protected data portion including the original data portion and a protection bit located at a bit position corresponding to the original mask portion, and the protected mask portion including the original mask portion and a mask to enable the protection bit corresponding to the original mask portion and to mask protection bits corresponding to other masks of the plurality of masks;

wherein the protection bit is determined by a parity or other error protection calculation on a result of the original data portion masked with the original mask portion;

wherein the associative memory is programmed with said determined protected entry for each entry in the plurality of associative memory entries.

19. An apparatus for protecting associative memory entries, the apparatus comprising:

means for identifying a plurality of masks used for a plurality of associative memory entries;

means for determining a protected entry for each entry in the plurality of associative memory entries, said each entry including an original data portion and an original mask portion, the protected entry including a protected data portion and a protected mask portion, the protected data portion including the original data portion and a protection bit located at a bit position corresponding to the original mask portion, and the protected mask portion including the original mask portion and a mask to enable the protection bit corresponding to the original mask portion and to mask protection bits corresponding to other masks of the plurality of masks;

wherein the protection bit is determined by a parity or other error protection calculation on a result of the original data portion masked with the original mask portion.

20. The apparatus of claim 19, comprising:

means for programming an associative memory with each of said protected;

entries; and

means for performing a lookup operation in the associative memory based on a protected lookup word;

wherein the protected lookup word includes a lookup word original data portion and a lookup word protected data portion, the lookup word protected data portion including a plurality of bits, each of the plurality of bits being determined by a parity or other error protection calculation on a result of the lookup word original data portion masked with a different one of the plurality of masks.

21. The apparatus of claim 20, wherein said means for programming the associative memory with each of said protected entries includes means for programming each of said protective entries in two consecutive locations in the associative memory.