Method of error detection in a ternary content addressable memory

1. A method for error detection in a ternary content addressable memory, TCAM, preferably in real-time, wherein the error detection is initiated with a read operation at a specified input address ( 200 ), an additional random access memory, RAM, is provided, wherein said RAM has a same number of locations as the TCAM, wherein in both memories, TCAM and RAM, corresponding read data entries ( 210 ) which each consist of data and a mask are placed at the same input address locations, and wherein:

data and mask read operations from TCAM and RAM at the locations pointed by the input address ( 200 ) are performed and

in a first check phase ( 220 ) said data and mask read from the TCAM at a location pointed by the input address ( 200 ) are compared with the data and mask read from RAM at the location pointed by the same input address ( 200 ), and

if a result of the first check phase ( 220 ) is correct, a TCAM_SEARCH phase ( 270 ) is executed,

otherwise a data recovery check ( 230 ) is executed, which is followed by a data refresh ( 240 ), a second read of data entries ( 250 ) stored at said input address ( 200 ) in both TCAM and RAM, and a second check phase ( 260 ) is executed, in which second phase ( 260 ) a comparison of data and masks read from both TCAM and RAM is performed, and

and wherein the TCAM_SEARCH phase ( 270 ) uses the data read from RAM as input search key and returns as an output a TCAM match vector and/or a single TCAM address,

and wherein a TCAM match check ( 280 ) checks

in a case of a TCAM match vector, whether the result of the TCAM_SEARCH ( 270 ), that is a flag pointed by the address ( 200 ) from TCAM match vector ( 275 ), is binary 1, or

in the case of a non-matched (false) TCAM single address ( 300 ) checked in a TCAM address check ( 310 ),

and if the TCAM address ( 300 ) is a lower address than said input address ( 200 ), a TCAM read at said TCAM address ( 300 ) is performed, and if in a TCAM search validation ( 340 ) the TCAM data read at the TCAM address ( 300 ) is identical to the data read at the RAM, and wherein preferably the method moves to the next input address ( 286 ) provided by the scrubbing mechanism, and the whole proposed error detection method may be repeated.

2. The method of claim 1 , wherein a check and phases ( 220 , 260 ) that use TCAM and RAM low memory bandwidth demanding procedure of data entries check and comparison.

3. The method of claim 1 , wherein a check and phases ( 220 , 260 ) that use TCAM and RAM high memory bandwidth demanding procedure of data entries check and comparison, which includes error correction code or hash algorithms.

4. The method of claim 1 , wherein the data recovery check ( 230 ) raises a data integrity error flag ( 265 ), if the result of the check is false.

5. The method of claim 1 , wherein a second check ( 260 ) phase is provided that raises a data integrity error flag ( 265 ), if the result of the check is false.

6. The method of claim 1 , wherein a TCAM match check ( 280 ) is executed, which finishes the error detection if the result of the check is a binary 1, otherwise it raises a search error flag ( 285 ).

7. The method of claim 1 , wherein a TCAM search validation ( 340 ) is executed, which raises a search error flag ( 285 ), if the result of a comparison of data read at the TCAM address ( 300 ) does not provide a match in the RAM.

8. A memory device for the use in the method of claim 1 , the memory device comprising:

a ternary content addressable memory, TCAM, and

an additional random access memory, RAM, wherein said RAM has the same number of locations as the TCAM, wherein in both memories, TCAM and RAM, corresponding read data entries ( 210 ) which each consist of data and a mask may be placed at the same address locations.

9. A computer network comprising one or more memory devices according to claim 8 .

10. A device comprising:

a memory device which comprises a ternary content addressable memory, TCAM, and an additional random access memory, RAM, wherein said RAM has the same number of locations as the TCAM, wherein in both memories, TCAM and RAM, corresponding read data entries ( 210 ) which each consist of data and a mask may be placed at the same address locations,

wherein the networking device is configured to carry out the method of error detection according to claim 1 .

11. The device of claim 10 , which is a high speed networking device or a TCAM-based high speed search engine.

12. The device of claim 11 , wherein the high speed networking device is a router or a switch.

13. A computer network comprising one or more devices according to claim 10 .

14. A method for error detection in a ternary content addressable memory, TCAM, preferably in real-time, wherein an additional random access memory, RAM, is provided, wherein said RAM has a same number of locations as the TCAM, wherein in both memories, TCAM and RAM, corresponding read data entries which each consist of data and a mask are placed at the same input address locations, and wherein:

the error detection is initiated by a received input address ( 410 ) outputted from a TCAM_SEARCH command ( 400 ), wherein a memory read ( 420 ) reads data and the mask stored at said input addresses ( 410 ) in either TCAM and/or RAM, and wherein a check ( 430 ) checks a integrity of said data and the mask, and if no error is found, a key match check ( 440 ) is executed, in which the input search key ( 405 ) is compared with the data and the mask located at the address ( 410 ) in the memory, either TCAM and/or RAM.

15. The method of claim 14 , wherein the read ( 420 ) of the data value and the mask is performed at the RAM, in particular in the case of low available bandwidth of the TCAM, or, in particular if the available bandwidth of the TCAM is high, the memory read ( 420 ) is performed at the TCAM.

16. The method of claim 14 , wherein an integrity check ( 430 ) of the data and the mask is executed.

17. The method of claim 14 , wherein a key match check ( 440 ) is executed, and if there is no match between the input search key ( 405 ) and the data and the mask read from address ( 410 ), a search error ( 460 ) will be indicated.