PEDS: A Parallel Error Detection Scheme for TCAM Devices 

Anat Bremler-Barr, David Hay, Danny Handler, Ronny Roth
INFOCOM,
2009
Conferences & Workshops
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-detection 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 rather than the (orders-of-magnitude larger) 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 lookups. PEDS allows flexible and dynamic selection of trade-off points between robustness, space complexity, and number of lookups.

Prizes

February 9, 2009
Best paper award runner-up.
@INPROCEEDINGS{5062044,
  author={Bremler-Barr, A. and Hay, D. and Hendler, D. and Roth, R. M.},
  booktitle={IEEE INFOCOM 2009}, 
  title={PEDS: A Parallel Error Detection Scheme for TCAM Devices}, 
  year={2009},
  volume={},
  number={},
  pages={1296-1304},
  doi={10.1109/INFCOM.2009.5062044}