Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/TNET.2010.2047730 | IEEE/ACM Trans. Netw. |
Keywords | Field | DocType |
Computer science,Associative memory,Error correction codes,Computer vision,Robustness,Routing,Monitoring,Data security,Databases,Filters | Data security,Content-addressable memory,Computer science,Correctness,Parallel computing,Computer network,Error detection and correction,Robustness (computer science),Content-addressable storage,Alphabet,Distributed computing,Computational complexity theory | Journal |
Volume | Issue | ISSN |
18 | 5 | 1063-6692 |
ISBN | Citations | PageRank |
978-1-4244-3513-5 | 3 | 0.39 |
References | Authors | |
12 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anat Bremler-Barr | 1 | 505 | 39.95 |
| David Hay | 2 | 3 | 0.39 |
| Danny Hendler | 3 | 726 | 44.54 |
| Ron M. Roth | 4 | 266 | 50.68 |