Block mask ternary CAM

• US 6,738,862 B1
• Filed: 04/29/2002
• Issued: 05/18/2004
• Est. Priority Date: 08/07/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ross, Mark A., Bechtolsheim, Andreas V.
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US10/135,711
• Time in Patent Office: 750 Days
• Field of Search: 711/108, 365/49
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

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.

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.

2. The ternary content-addressable memory of claim 1, wherein the plurality of first TCAM block entries includes a quantity J of entries, the plurality of second TCAM block entries includes a quantity K of entries, and the values of J and K are equal.

3. The ternary content-addressable memory of claim 1, wherein the plurality of first TCAM block entries includes a quantity J of entries, the plurality of second TCAM block entries includes a quantity K of entries, and the values of J and K are not equal.

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.

5. The ternary content-addressable memory of claim 4, further comprising:

a second TCAM block, the second TCAM block including;

a plurality of second TCAM entries, each of the plurality of second TCAM entries includes a plurality of value bits; and

a third block mask entry including a plurality of mask bits;

wherein each mask bit of the third block mask entry identifies whether a corresponding value bit is masked during a lookup operation on the plurality of second TCAM entries based on the lookup value.