Block mask ternary cam

• US 6,389,506 B1
• Filed: 08/07/1998
• Issued: 05/14/2002
• 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, Bechtolsheim, Andreas V.
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US09/130,890
• Time in Patent Office: 1,376 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

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 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.

2. 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.

3. 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.

4. The memory as in claim 3, wherein said first section comprises:

either a first number or a second number of said value entries, a first choice of said first number or said second number for said first section being dynamically selectable in response to a content element in said memory; and

said second section comprises either a first number or a second number of said value entries, a second choice of said first number or said second number for said second section being dynamically selectable in response to a content element in said memory and independently of said first choice.

5. The memory as in claim 3, wherein said first section comprises:

either a first number or a second number of said value entries, a first choice of said first number or said second number for said first section being dynamically selectable in response to a lookup header for a packet; and

said second section comprises either a first number or a second number of said value entries, a second choice of said first number or said second number for said second section being dynamically selectable in response to a content element in said memory and independently of said first choice.

6. 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.

7. 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.

8. 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.

9. The memory as in claim 8, wherein

said first section comprises either a first number or a second number of said value entries, a first choice of said first number or said second number for said first section being dynamically selectable in response to a content element in said memory; and

said second section comprises either a first number or a second number of said value entries, a second choice of said first number or said second number for said second section being dynamically selectable in response to a content element in said memory and independently of said first choice.

10. The memory as in claim 8, wherein

said first section comprises either a first number or a second number of said value entries, a first choice of said first number or said second number for said first section being dynamically selectable in response to a lookup header for a packet;

and

said second section comprises either a first number or a second number of said value entries, a second choice of said first number or said second number for said second section being dynamically selectable in response to a lookup header for a packet and independently of said first choice.

11. 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.

12. The method as in claim 11, wherein each said mask entry is associated with a discrete set of said value entries.

13. The method as in claim 12, wherein said discrete set includes either a first number or a second number of said value entries;

and comprising the step of dynamically choosing said first number or said second number in response to a content element in said memory.

14. The method as in claim 12, wherein said discrete set includes either a first number or a second number of said value entries;

and comprising the step of dynamically choosing said first number or said second number in response to a lookup header for a packet.

15. The method as in claim 12, wherein said memory includes

a first mask entry having a first number of said value entries in said associated discrete set; and

a second mask entry having a second number of said value entries in said associated discrete set;

wherein said first number and said second number are different.

16. The method as in claim 15, wherein

said first mask entry has either a first number or a second number of said value entries in said associated discrete set;

said second mask entry has either a first number or a second number of said value entries in said associated discrete set; and

comprising the steps of;

making a first dynamic choice, for said first mask entry, of either said first number or said second number, in response to a content element in said memory; and

making a second dynamic choice, for said second mask entry, of either said first number or said second number, in response to a content element in said memory and independently of said first choice.

17. The method as in claim 15, wherein

said first mask entry has either a first number or a second number of said value entries in said associated discrete set;

said second mask entry has either a first number or a second number of said value entries in said associated discrete set; and

comprising the steps of;

making a first dynamic choice, for said first mask entry, of either said first number or said second number, in response to a content element in said memory; and

making a second dynamic choice, for said second mask entry, of either said first number or said second number, in response to a lookup header for a packet and independently of said first choice.

18. The method as in claim 11, wherein said logical function is responsive to whether said bit of said input matches said corresponding bit of said one value entry;

and whether said corresponding bit of one of said mask entries equals a predetermined logical value.

19. The method as in claim 18, wherein each said mask entry is associated with a discrete set of said value entries.

20. The method as in claim 19, wherein said discrete set includes either a first number or a second number of said value entries;

and comprising the step of dynamically choosing said first number or said second number in response to a content element in said memory.

21. The method as in claim 19, wherein said discrete set includes either a first number or a second number of said value entries;

and comprising the step of dynamically choosing said first number or said second number in response to a lookup header for a packet.

22. The method as in claim 19, wherein said memory includes

a first mask entry having a first number of said value entries in said associated discrete set;

and

a second mask entry having a second number of said value entries in said associated discrete set;

wherein said first number and said second number are different.

23. The method as in claim 22, wherein

said first mask entry has either a first number or a second number of said value entries in said associated discrete set;

said second mask entry has either a first number or a second number of said

value entries in said associated discrete set; and

comprising the steps of;

making a first dynamic choice, for said first mask entry, of either said first number or said second number, in response to a content element in said memory; and

making a second dynamic choice, for said second mask entry, of either said first number or said second number, in response to a content element in said memory and independently of said first choice.

24. The method as in claim 22, wherein

said first mask entry has either a first number or a second number of said value entries in said associated discrete set;

said second mask entry has either a first number or a second number of said value entries in said associated discrete set; and

comprising the steps of;

making a first dynamic choice, for said first mask entry, of either said first number or said second number, in response to a lookup header for a packet; and

making a second dynamic choice, for said second mask entry, of either said first number or said second number, in response to a lookup header for a packet and independently of said first choice.

25. 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.

26. The method as in claim 25, wherein each said mask entry is associated with a discrete set of said value entries.

27. The method as in claim 26, wherein said discrete set includes either a first number or a second number of said value entries;

and comprising the step of dynamically choosing said first number or said second number in response to a content element in said memory.

28. The method as in claim 26, wherein said discrete set includes either a first number or a second number of said value entries;

and comprising the step of dynamically choosing said first number or said second number in response to a lookup header for a packet.

29. The method as in claim 26, wherein said memory includes

a first mask entry having a first number of said value entries in said associated discrete set; and

a second mask entry having a second number of said value entries in said associated discrete set;

wherein said first number and said second number are different.

30. The method as in claim 29, wherein

said first mask entry has either a first number or a second number of said value entries in said associated discrete set;

said second mask entry has either a first number or a second number of said value entries in said associated discrete set; and

comprising the steps of

making a first dynamic choice, for said first mask entry, of either said first number or said second number, in response to a content element in said memory; and

making a second dynamic choice, for said second mask entry, of either said first number or said second number, in response to a content element in said memory and independently of said first choice.

31. The method as in claim 29, wherein

said first mask entry has either a first number or a second number of said value entries in said associated discrete set;

said second mask entry has either a first number or a second number of said value entries in said associated discrete set; and

comprising the steps of;

making a first dynamic choice, for said first mask entry, of either said first number or said second number, in response to a lookup header for a packet; and

making a second dynamic choice, for said second mask entry, of either said first number or said second number, in response to a lookup header for a packet and independently of said first choice.

32. The method as in claim 25, wherein said logical function is responsive to whether said bit of said input matches said corresponding bit of said one value entry;

and whether said corresponding bit of one of said mask entries equals a predetermined logical value.

33. The method as in claim 32, wherein each said mask entry is associated with a discrete set of said value entries.

34. The method as in claim 33, wherein said discrete set includes either a first number or a second number of said value entries;

and comprising the step of dynamically choosing said first number or said second number in response to a content element in said memory.

35. The method as in claim 33, wherein said discrete set includes either a first number or a second number of said value entries;

and comprising the step of dynamically choosing said first number or said second number in response to a lookup header for a packet.

36. The method as in claim 33, wherein said memory includes

a first mask entry having a first number of said value entries in said associated discrete set;

and

a second mask entry having a second number of said value entries in said associated discrete set;

wherein said first number and said second number are different.

37. The method claim 36, wherein

said first mask entry has either a first number or a second number of said value entries in said associated discrete set;

said second ask entry has either a first number or a second number of said value entries in said associated discrete set; and

comprising the steps of;

making a first dynamic choice, for said first mask entry, of either said first number or said second number, in response to a content element in said memory; and

making a second dynamic choice, for said second mask entry, of either said first number or said second number, in response to a content element in said memory and independently of said first choice.

38. The method as in claim 36, wherein

said first mask entry has either a first number or a second number of said value entries in said associated discrete set;

said second mask entry has either a first number or a second number of said value entries in said associated discrete set; and

comprising the steps of;

making a first dynamic choice, for said first mask entry, of either said first number or said second number, in response to a lookup header for a packet; and

making a second dynamic choice, for said second mask entry, of either said first number or said second number, in response to a lookup header for a packet and independently of said first choice.