PEDS: A Parallel Error Detection Scheme for TCAM Devices 

Anat Bremler-Barr, David Hay, Danny Handler, Ronny Roth
ACM/IEEE Transactions on Networking,
2010
Journal
Deep Packet Inspection (DPI)

Abstract

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.

Prizes

February 9, 2009
Best paper award runner-up.
@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}
}