US 2006/0080498 A1 · Error protection for lookup operations performed on ternary content-addressable memory entries

Abstract

Lookup operations are performed on ternary content-addressable memory (TCAM) entries, with error protection provided. Groups of TCAM entries are programmed such that each of its entries differ by more than a predetermined calculated count of ones distance of k bits, where k>0. Lookup operations are performed on these entries using a lookup word in a manner to detect k or less differences in entries within groups to identify a matching entry or no matching entry from each group. These matching entries are then verified using a corresponding error code to identify which entries are a full hit, a suspected hit, or a miss. One of the full and suspected hits is determined in a predetermined manner and identified as the lookup result (or a miss is the lookup result if there are no such entries).

Claims32

Dependent claims

A method for identifying a highest-priority matching entry in a ternary content-addressable memory, the ternary content-addressable memory includes a plurality of entries, each of the plurality of entries includes a value and a mask and is associated with at least one error code;

the plurality of entries comprises a plurality of groups of said entries, with all entries in each of said groups differing in a count of ones from each other entry in the same group by more than k, wherein k is an integer greater than zero, the method comprising:
for each particular group of said groups of entries, determining a highest-priority possible hit entry in said particular group, if any, for a lookup word;
for each particular highest-priority possible hit entry of said determined highest-priority possible hit entries, determining whether or not said particular highest-priority possible hit entry is a candidate for being the highest-priority matching entry based on said error code associated with said particular highest-priority possible hit entry;
and
determining a highest-priority candidate entry from said determined candidate entries.

2 more elements

An apparatus configured to identify a highest-priority matching entry, the apparatus comprising:

a plurality of groups of ternary content-addressable memory entries, each of said entries includes a value, a mask and at least one error code;
logic configured to perform a lookup operation on said groups of ternary content-addressable memory entries based on a lookup word to determine the highest-priority matching entry;
wherein said lookup operation includes:
(a) for each particular group of said groups of entries, determining a highest-priority possible hit entry in said particular group, if any, for the lookup word;
(b) for each particular highest-priority possible hit entry of said determined highest-priority possible hit entries, determining whether or not said particular highest-priority possible hit entry is a candidate for being the highest-priority matching entry based on said error code of said particular highest-priority possible hit entry, wherein said particular highest-priority possible hit entry is a candidate for being the highest-priority matching entry if it is a hit or a suspected hit, else it is not a candidate;
and (c) determining a highest-priority candidate entry from said determined candidate entries.

3 more elements

Dependencies are inferred from the claim text.

Error protection for lookup operations performed on ternary content-addressable memory entries

Life of this patent

Error protection for lookup operations performed on ternary content-addressable memory entries

Life of this patent

Abstract

Claims32