Block mask ternary CAM
First Claim
Patent Images
1. A ternary content-addressable memory (TCAM) comprising:
- a first TCAM block including;
a plurality of first TCAM block entries, each of the plurality of first TCAM block entries includes a plurality of value bits; and
a first block mask entry including a plurality of mask bits;
wherein each mask bit of the first block mask entry identifies for each of the plurality of first TCAM block entries whether a corresponding value bit is masked during a lookup operation on the first TCAM block for a particular lookup value; and
a second TCAM block including;
a plurality of second TCAM block entries, each of the plurality of second TCAM block entries includes a plurality of value bits; and
a second block mask entry including a plurality of mask bits;
wherein each mask bit of the second block mask entry identifies for each of the plurality of second TCAM block entries whether a corresponding value bit is masked during a lookup operation on the second TCAM block for the particular lookup value.
0 Assignments
0 Petitions
Accused Products
Abstract
The invention provides a method and system for flexible matching of data in a CAM, that does not use the overhead of one mask bit for each matched value bit. The entries of the CAM are logically grouped in a set of blocks, each block having a single mask that applies to all entries in the block. Each block includes a predetermined number of CAM entries, such as a block of 16 entries. However, in alternative embodiments, the number of CAM entries for each block could be predetermined to be a different number, or could be dynamically selected with the values that are entered into the CAM.
-
Citations
5 Claims
-
1. A ternary content-addressable memory (TCAM) comprising:
-
a first TCAM block including;
a plurality of first TCAM block entries, each of the plurality of first TCAM block entries includes a plurality of value bits; and
a first block mask entry including a plurality of mask bits;
wherein each mask bit of the first block mask entry identifies for each of the plurality of first TCAM block entries whether a corresponding value bit is masked during a lookup operation on the first TCAM block for a particular lookup value; and
a second TCAM block including;
a plurality of second TCAM block entries, each of the plurality of second TCAM block entries includes a plurality of value bits; and
a second block mask entry including a plurality of mask bits;
wherein each mask bit of the second block mask entry identifies for each of the plurality of second TCAM block entries whether a corresponding value bit is masked during a lookup operation on the second TCAM block for the particular lookup value.- View Dependent Claims (2, 3)
-
-
4. A ternary content-addressable memory (TCAM) comprising a first TCAM block, the first TCAM block including:
- a plurality of TCAM entries, each of the plurality of TCAM entries includes a plurality of value bits, the plurality of TCAM entries includes a first subset of TCAM entries and a second subset of TCAM entries, the first and second subsets being non-overlapping subsets of the plurality of TCAM entries, with each of the first and second subsets including at least two TCAM entries;
a first block mask entry including a plurality of mask bits, wherein each mask bit of the first block mask entry identifies whether a corresponding value bit is masked during a lookup operation on the first subset of value entries based on a lookup value; and
a second block mask entry including a plurality of mask bits, wherein each mask bit of the second block mask entry identifies whether a corresponding value bit is masked during a lookup operation on the second subset of value entries based on the lookup value. - View Dependent Claims (5)
- a plurality of TCAM entries, each of the plurality of TCAM entries includes a plurality of value bits, the plurality of TCAM entries includes a first subset of TCAM entries and a second subset of TCAM entries, the first and second subsets being non-overlapping subsets of the plurality of TCAM entries, with each of the first and second subsets including at least two TCAM entries;
Specification