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

Patent metadata

Field	Value
Publication number	US-9940191-B2
Application number	US-201514948273-A
Country	US
Kind code	B2
Filing date	Nov 21, 2015
Priority date	Mar 28, 2015
Publication date	Apr 10, 2018
Grant date	Apr 10, 2018

Abstract

A plurality of data words are written into a TCAM; each has binary digits and don't-care digits. Contemporaneously, for each of the words: a first checksum is calculated on the binary digits; and the following are stored in a corresponding portion of a RAM: an identifier of the binary digits and the first checksum. The ternary content-addressable memory is queried with an input word. Upon the querying yielding a match, further steps include retrieving, from the random-access memory, corresponding values of the identifier of the binary digits and the first checksum; computing a second checksum on the input word, using the identifier of the binary digits; and if the second and first checksums are not equal, determining in real time that the match is a false positive.

First claim

What is claimed is:

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

Assignees

• IBM

Inventors

• Abali Bulent
• Blaner Bartholomew

Classifications

• G06F11/1004 Primary

  to protect a block of data words, e.g. CRC or checksum (G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00) · CPC title

• H03M13/6318

  using variable length codes · CPC title

• H03M13/09

  Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit · CPC title

• G06F11/1064

  in cache or content addressable memories · CPC title

• H03M13/096

  Checksums · CPC title