Computer network communications require fast packet categorization schemes for effective network administration and security. Computer networks are equipped with routers that organize and process packets according to patterns of rules in a classification list. Ternary content-addressable memory (TCAM) is an associative memory device with a table of preset-width entries of symbols generated from the threefold alphabet {“0,” “1,” “*”}, where “0” and “1” are appropriate bits and “*” represents “don’t care.” TCAM classifies packets that pass through a network device by comparing a search key to all table entries in parallel to avoid a traffic jam. Although TCAM devices exist for rapidly ordering packets, the recognition of error incidents in TCAM devices is a difficult problem, despite the existing well-known error-detection algorithms [1,2,3,4]. How should we design error-detection schemes for TCAM devices with parallel access attributes?

The authors introduce PEDS, an ingenious parallel error detection scheme for TCAM devices. PEDS capitalizes on the inbuilt concurrent-matching capability of TCAM devices, and requires only slight hardware modifications to detect errors. PEDS compares a search key against all entries simultaneously, and then sends the results to a match-line priority encoder that returns the index with the highest priority. Specifically, each entry is partitioned into symbol clauses, with symbols interspersed across clauses to tackle statistically dependent error occurrences of adjoining symbols. Preset error-detecting codes over the ternary alphabet are used to compute check symbols for the clauses.

The authors proficiently present binary modulo-2 counters and ternary modulo-3 counters as two alternative hardware mechanisms between the TCAM device’s cell array and its match-line priority encoder for fast error detection. They explore two Galois fields--GF(2) and GF(3)--as parity codes and parity checkers for error detection. PEDS operating with binary modulo-2 counters in GF(2) requires only XOR gates and single flip-flops at the ends of the match-lines prior to the match-line priority encoder. PEDS using ternary modulo-3 counters in GF(3) requires the insertion of two-bit registers and ternary semi-adders realized with eight NAND gates.

PEDS introduces a way to harness TCAM’s parallel operations by not sequentially searching through all packet entries for errors. The time it takes for PEDS to search for errors depends on the width of an entry rather than on the number of entries. Specifically, PEDS only has to perform twice the number of extra symbol lookups per entry to detect all errors. PEDS can even perform error-checking during idle TCAM cycles. PEDS with ternary modulo-3 counters only requires two-tenths of a millisecond to detect all of the errors on a 99 percent full TCAM device. This makes PEDS much more efficient than any other error-detection schemes.

PEDS is at a disadvantage with the extra spaces it uses to store error-detection data. However, PEDS can be configured to satisfy the requirements of an application. Different configurations of PEDS can take into consideration the tradeoffs among error resilience, space, time (to recognize all incorrect TCAM entries), and hardware changes. Any PEDS configuration requires only minimal hardware changes when compared to other error-detection options currently available. Parallel lookups, minimal hardware adjustments, and robust algorithms make PEDS a very interesting and promising solution to error detection in TCAM devices.