Block mask ternary cam
AssigneeCisco Technology, Inc.
InventorsMark Ross, Andreas V. Bechtolsheim
Life of this patent
Estimating the term…
Abstract
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.
Claims38
A content addressable memory, comprising:
- a plurality V of value entries;
- a plurality M of mask entries;
- and
- a plurality of sections, each said section comprising one said mask entry and a plurality of said value entries;
- wherein M is less than V;
- and
- wherein said plurality of sections comprises a first section having either a first number or a second number of said value entries, a choice of said first number or said second number being dynamically selectable in response to a content element in said memory.
A content addressable memory, comprising:
- a plurality V of value entries;
- a plurality M of mask entries;
- and
- a plurality of sections, each said section comprising one said mask entry and a plurality of said value entries;
- wherein M is less than V;
- and
- wherein said plurality of sections comprises a first section having either a first number or a second number of said value entries, a choice of said first number or said second number being dynamically selectable in response to a lookup header for a packet.
A content addressable memory, comprising:
- a plurality V of value entries;
- a plurality M of mask entries;
- and
- a plurality of sections, each said section comprising one said mask entry and a plurality of said value entries;
- wherein M is less than V;
- and
- wherein said plurality of sections comprises a first section having a first number of said value entries;
- and
- a second section having a second number of said value entries;
- and
- wherein said first number and said second number are different.
A content addressable memory, comprising:
- a plurality M of mask entries;
- for each one of said mask entries, a plurality of value entries associated therewith;
- and
- a plurality of sections, each said section comprising one said mask entry and said plurality of said value entries;
- and
- wherein said plurality of sections comprises a first section having either a first number or a second number of said value entries, a choice of said first number or said second number being dynamically selectable in response to a content element in said memory.
A content addressable memory, comprising:
- a plurality M of mask entries;
- for each one of said mask entries, a plurality of value entries associated therewith;
- and
- a plurality of sections, each said section comprising one said mask entry and said plurality of said value entries;
- and
- wherein said plurality of sections comprises a first section having either a first number or a second number of said value entries, a choice of said first number or said second number being dynamically selectable in response to a lookup header for a packet.
A content addressable memory, comprising:
- a plurality M of mask entries;
- for each one of said mask entries, a plurality of value entries associated therewith;
- and
- a plurality of sections, each said section comprising one said mask entry and said plurality of said value entries;
- and
- wherein said plurality of sections comprises:
- a first section having a first number of said value entries;
- and
- a second section having a second number of said value entries;
- wherein said first number and said second number are different.
A method of operating a content addressable memory, said method comprising the steps of:
- matching an input against a plurality V of value entries, each said value entry having a number B of bits;
- matching said input against a plurality M of mask entries, M being less than V, each said mask entry having a number B of bits;.
- determining for each one of said value entries, a matching result responsive to a logical function of (a) each bit of said input, (b) a corresponding bit of said one value entry, and (c) a corresponding bit of one of said mask entries associated with said one value entry;
- and
- producing an output responsive to said matching results.
A method of operating a content addressable memory, said method comprising the steps of:
- matching an input against a plurality M of mask entries, each said mask entry having a number B of bits;
- for each one of said mask entries, matching said input against a plurality of value entries associated therewith, each said value entry having a number B of bits;
- determining for each one of said value entries, a matching result responsive to a logical function of (a) each bit of said input, (b) a corresponding bit of said one mask entry associated therewith, and (c) a corresponding bit of said one value entry;
- and
- producing an output responsive to said matching results.
Dependencies are inferred from the claim text.