US 7,024,516 B2 · Configurable ternary content addressable memory

Abstract

A Ternary/Content Addressable Memory (T/CAM) design is presented. The CAM includes a rule table implemented using a Random Access Module (RAM) storing n rule entries. An n-to-1 multiplexer module, responsive to a value C of a cycle counter, varying between 0 to n-1, provides a selected C'th rule entry to a comparator block which performs a comparison between the selected C'th rule entry and a matching key. The resulting comparison result together with the value C are used to decode the matched rule. In implementing a TCAM, a bitmask table implemented using a RAM module storing n bitmask entries is used. An n-to-1 multiplexer module, responsive to the value C provides a corresponding C'th bitmask to a masking module which modifies the comparison result to ignore a subgroup of results of bitwise comparisons between the C'th rule entry and the matching key. T/CAM implementations adhering to the described embodiment support comparison of the matching key against a number of N masked rules using masked comparison hardware of size m, where m is much smaller than N. Advantages are derived from the provision of a flexible rule-based classification, filtering and verification packets conveyed in accordance with various packet transport protocols at wire-speed in support of VoIP provisioning. The flexibility is especially beneficial in implementing convergent applications.

Claims18

Dependent claims

A Content Addressable Memory (CAM) module comprising:

a. a rule Random Access Memory (RAM) block storing n rule entries where n=(2^b) and b is a positive integer;
b. a rule n-to-1 multiplexer responsive to a value C varying between 0 and n-1, the rule multiplexer selecting a C'th stored rule entry in the rule RAM block;
c. a comparator performing a bitwise matching operation between a matching key and contents of the C'th entry in the rule RAM block provided by the multiplexer, the comparator providing a comparison result;
d. a rule decoder block responsive to the comparison result and the value C to identify a matched entry, the rule multiplexer and the rule decoder block enabling comparison between the matching key and n rules using a single comparator;
and
e. a comparison binary cycle counter register having b bits, the binary cycle counter register resetting to zero when incremented by one count from an n-1 value.

3 more elements

A Content Addressable Memory (CAM) module comprising:

a. m rule Random Access Memory (RAM) blocks each storing n rule entries where n=(2^b) and b is a positive integer;
b. m rule n-to-1 multiplexers responsive to a value C varying between 0 and n-1, each rule multiplexer selecting a C'th stored rule entry in the corresponding rule RAM block;
c. m comparators each performing a bitwise matching operation between a single matching key and contents of the C'th entry in the corresponding rule RAM block provided by the corresponding multiplexer, each comparator providing a comparison result;
d. a single rule decoder block responsive to the m comparison results and the value C to identify a matched entry, the m rule multiplexers and the single rule decoder block enabling comparison between the single matching key and N=n*m rules using m comparator;
and
e. a comparison binary cycle counter register having b bits, the binary cycle counter register resetting to zero when incremented by one count from an n-1 value.

3 more elements

Dependencies are inferred from the claim text.

Configurable ternary content addressable memory

Life of this patent

Configurable ternary content addressable memory

Life of this patent

Abstract

Claims18