Concurrent error detection in a ternary content-addressable memory (TCAM) device

1. A method comprising:

writing a plurality of data words into a ternary content-addressable memory, each of said data words having binary digits and don't-care digits;

contemporaneous with said writing, for each of said plurality of data words:

calculating a first checksum on said binary digits;

storing, in a corresponding portion of a random-access memory:

an identifier of said binary digits of said corresponding one of said data words, wherein said identifier includes a length of said binary digits; and

said first checksum for said corresponding one of said data words;

querying said ternary content-addressable memory into which said plurality of data words have been written with an input word;

upon said querying yielding a match:

retrieving from said random-access memory, corresponding values of said identifier of said binary digits and said first checksum;

computing a second checksum on said input word, using said identifier of said binary digits; and

determining in real time that said match is a false positive upon detecting that said second and first checksums are not equal.

2. The method of claim 1 , wherein:

said storing further comprises storing, in said corresponding portion of said random-access memory, a data portion of a corresponding one of said data words; and

said retrieving further comprises retrieving, from said random-access memory, a corresponding value of said data portion.

3. The method of claim 2 , wherein:

said storing further comprises storing a row index for said corresponding one of said data words, identifying a row in said ternary content-addressable memory where said corresponding one of said data words is stored; and

said retrieving further comprises retrieving a corresponding value of said row index;

further comprising replacing said erroneous entry using said row index.

4. The method of claim 3 , wherein:

in said storing step, said identifier of said binary digits of said corresponding one of said data words comprises said length of said binary digits, wherein said length of said binary digits is of a left-most binary portion of said corresponding one of said data words; and

said computing of said second checksum comprises computing said second checksum on said left-most binary portion of said input word.

5. The method of claim 3 , wherein:

in said storing step, said identifier of said binary digits of said corresponding one of said data words comprises a mask identifying a binary portion of said corresponding one of said data words; and

said computing of said second checksum comprises computing said second checksum on a binary portion of said input word, determined from said mask.

6. The method of claim 1 , wherein said checksum calculated in said calculating step comprises a parity check.

7. An apparatus comprising:

a ternary content-addressable memory array;

a random access memory array;

a loader coupled to said ternary content-addressable memory array and said random access memory array;

a querying entity coupled to said ternary content-addressable memory array; and

a matching logic module coupled to said random access memory array;

wherein:

said loader is configured to write a plurality of data words into said ternary content-addressable memory array, each of said data words having binary digits and don't-care digits;

said loader is configured to, contemporaneous with said writing, for each of said plurality of data words:

calculate a first checksum on said binary digits; and

store, in a corresponding portion of said random-access memory array:

an identifier of said binary digits of said corresponding one of said data words, wherein said identifier includes a length of said binary digits; and

said first checksum for said corresponding one of said data words;

said querying entity is configured to query said ternary content-addressable memory into which said plurality of data words have been written with an input word; and

said matching logic module is configured to, upon said querying yielding a match:

retrieve from said random-access memory array corresponding values of said identifier of said binary digits and said first checksum;

compute a second checksum on said input word, using said identifier of said binary digits; and

determine in real time that said match is a false positive upon detecting that said second and first checksums are not equal.

8. The apparatus of claim 7 , wherein:

said loader is further configured to, contemporaneous with said writing, for each of said plurality of data words, store, in said corresponding portion of said random-access memory, a data portion of said corresponding one of said data words; and

said matching logic module is further configured to, upon said querying yielding a match, retrieve, from said random-access memory, a corresponding value of said data portion.

9. The apparatus of claim 8 , wherein:

said loader further stores in said random access memory array a row index for said corresponding one of said data words, identifying a row in said ternary content-addressable memory array where said corresponding one of said data words is stored;

said matching logic module retrieves a corresponding value of said row index; and

said loader is further configured to replace said erroneous entry using said row index.

10. The apparatus of claim 9 , wherein:

said identifier of said binary digits of said corresponding one of said data words comprises said length of said binary digits, wherein said length of said binary digits is of a left-most binary portion of said corresponding one of said data words; and

said matching logic module computes said second checksum on said left-most binary portion of said input word.

11. The apparatus of claim 9 , wherein:

said identifier of said binary digits of said corresponding one of said data words comprises a mask identifying a binary portion of said corresponding one of said data words; and

said matching logic module computes said second checksum on a binary portion of said input word, determined from said mask.

12. The apparatus of claim 8 , wherein said loader comprises a hardware state machine.

13. The apparatus of claim 8 , wherein said loader comprises a software program tangibly embodied in a non-transitory computer-readable medium executing on at least one hardware processor.

14. The apparatus of claim 8 , wherein said querying entity and said loader are identical.

15. The apparatus of claim 8 , wherein said querying entity comprises a hardware state machine separate and distinct from said loader.

16. The apparatus of claim 8 , wherein said querying entity comprises a Huffman decoder.

17. The apparatus of claim 8 , further comprising a priority encoder coupled to said ternary content-addressable memory array and said random access memory array, said priority encoder being configured to, upon said querying yielding multiple putative matches, resolve same to obtain said match.

18. The apparatus of claim 7 , wherein said checksum calculated by said loader comprises a parity check.

19. A non-transitory computer readable medium comprising computer executable instructions which when executed by a computer cause the computer to perform the method of:

writing a plurality of data words into a ternary content-addressable memory, each of said data words having binary digits and don't-care digits;

contemporaneous with said writing, for each of said plurality of data words:

calculating a first checksum on said binary digits;

storing, in a corresponding portion of a random-access memory:

an identifier of said binary digits of said corresponding one of said data words, wherein said identifier includes a length of said binary digits; and

said first checksum for said corresponding one of said data words;

querying said ternary content-addressable memory into which said plurality of data words have been written with an input word;

upon said querying yielding a match:

retrieving from said random-access memory, corresponding values of said identifier of said binary digits and said first checksum;

computing a second checksum on said input word, using said identifier of said binary digits; and

determining in real time that said match is a false positive upon detecting that said second and first checksums are not equal.