Ternary content-addressable memory (TCAM) devices are increasingly used for performing high-speed packet classification. A TCAM consists of an associative memory that compares a search key in parallel against all entries. TCAMs may suffer from error events that cause ternary cells to change their value to any symbol in the ternary alphabet {”0”,“1”,“*”}. Due to their parallel access feature, standard error detection schemes are not directly applicable to TCAMs; an additional difficulty is posed by the special semantic of the “*” symbol. This paper introduces PEDS, a novel parallel error detection scheme that locates the erroneous entries in a TCAM device. PEDS is based on applying an error-detecting code to each TCAM entry and utilizing the parallel capabilities of the TCAM by simultaneously checking the correctness of multiple TCAM entries. A key feature of PEDS is that the number of TCAM lookup operations required to locate all errors depends on the number of symbols per entry in a manner that is typically orders of magnitude smaller than the number of TCAM entries. For large TCAM devices, a specific instance of PEDS requires only 200 lookups for 100-symbol entries, while a naive approach may need hundreds of thousands of lookups. PEDS allows flexible and dynamic selection of tradeoff points between robustness, space complexity, and number of lookups.
DEEPNESS Lab 2022 © all rights reserved
@article{DBLP:journals/ton/Bremler-BarrHHR10, author = {Anat Bremler{-}Barr and David Hay and Danny Hendler and Ron M. Roth}, title = {{PEDS:} {A} Parallel Error Detection Scheme for {TCAM} Devices}, journal = {{IEEE/ACM} Trans. Netw.}, volume = {18}, number = {5}, pages = {1665--1675}, year = {2010}, url = {https://doi.org/10.1109/TNET.2010.2047730}, doi = {10.1109/TNET.2010.2047730}, timestamp = {Sat, 27 May 2017 14:24:27 +0200}, biburl = {https://dblp.org/rec/journals/ton/Bremler-BarrHHR10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }