Method and apparatus for matching data items of variable length in a content addressable memory

• US 6,000,008 A
• Filed: 04/17/1997
• Issued: 12/07/1999
• Est. Priority Date: 03/11/1993
• Status: Expired due to Term

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Simcoe, Robert J.
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US08/842,977
• Time in Patent Office: 964 Days
• Field of Search: 365/49, 365/189.01, 711/108, 711/202, 711/207
• US Class Current: 711/108
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• 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
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

A content addressable memory (CAM) structure, and a method for its use, wherein data items of different selected lengths stored in the CAM may be located by matching sequences of CAM data words with sequences of input data words. Extension bits associated with each CAM data word control a sequence of comparison cycles to permit an input data item to be compared simultaneously with multiple input data items of the same length stored in the CAM structure. The CAM structure can be used without modification to store data items of various selected lengths. A begin bit associated with each CAM data word is used to mark the beginning of each stored data item and, in an exact match mode of operation, a global line is used to mark the beginning of an input data item. Match logic associated with each CAM data word generates a match till now signal in each comparison cycle, and the signal is propagated to the end of the data item if an exact match is detected. The exact match and match till now signals are used to generate various global match indications in the CAM structure. The same CAM structure can also be operated in a sliding match mode in which each stored data item is compared with every possible sequence of input data words.

Claims

1. A content addressable memory (CAM) structure for storing and locating data items of various lengths, the structure comprising:

a set of CAM data words, each having a predetermined number of data bits and a plurality of control bits, including a match till now bit and a begin bit to be set when a respective CAM data word contains a first word of a stored data item;

means for inputting one word at a time of a sequence of input data words for simultaneous comparison with all of the CAM data words;

a comparator circuit associated with each respective CAM data word, for comparing the respective CAM data word with the inputted one word of input data, and generating a word match signal for the respective CAM data word as a result of the comparison;

match logic associated with each CAM data word, for generating a match till now signal indicating that the CAM data word and a preceding CAM data word have matched with a corresponding succession of input data words;

means associated with each CAM data word, for generating an exact match signal if the match till now signal is generated for the respective CAM data word and the respective CAM data word contains a last word of a stored data item; and

global match logic, for generating global match signals based on the match till now signals and exact match signals generated in all of the CAM data words,

wherein the match logic determines a setting for the match till now bit of the respective CAM data word based on the begin bit, the respective word match signal, a setting of the match till now bit associated with a preceding CAM data word, and a global signal indicating that a current input data word is a first word of an input data item.

2. A CAM structure as defined in claim 1, wherein the global match logic includes:

means for generating a global intermediate match signal if at least one match till now signal is generated to indicate that at least a partial match condition exists.

3. A CAM structure as defined in claim 1, wherein the global match logic includes:

means for generating a global exact match signal if at least one exact match signal is generated.

4. A CAM structure as defined in claim 1, wherein the global match logic includes:

means for generating a global multiple match signal if more than one match till now signal is generated.

5. A CAM structure as defined in claim 1, wherein the match logic includes:

means for setting the match till now bit of the respective CAM data word if the begin bit is set, if the first word of input data is being compared, and if the respective word match signal indicates a match, wherein the respective match till now bit will be set if the first word of the CAM data word and the first word of the input data match;

means for setting the match till now bit if the begin bit is not set, if the match till now bit from the preceding CAM data word is set, and if the word match signal indicates a match, wherein a subsequent matching CAM data word will have its match till now bit set only if the match till now bit was set in a preceding CAM data word; and

means for clearing the match till now bit of the respective CAM data word in all other conditions.

6. A CAM structure as defined in claim 5, wherein:

the means for generating an exact match signal include means for logically combining the respective match till now bit with the begin bit of a next succeeding CAM data word, the exact match signal being set when both the respective match till now bit is set and the begin bit is set in the next succeeding CAM data word.

7. A CAM structure as defined in claim 5, wherein:

one of the control bits of the CAM data word is a subfield bit indicating that a last subfield of the CAM data word does not contain valid data; and

the comparator circuit includes means, responsive to the subfield bit, for generating a match result for a subfield that does not contain valid data.

8. A CAM structure as defined in claim 5, wherein:

the global signal indicating a first input data word is always set, to indicate that every input word is to be treated as potentially starting an input data item; and

each stored data item is compared with all possible sequences of input data words having a same match length as the stored data item.

9. A method of operation of a content addressable memory (CAM) structure for storing and locating data items of various lengths, the CAM structure including a set of CAM data words, each having a predetermined number of data bits and a plurality of control bits, including a match till now bit and a begin bit to be set when a respective CAM data word contains a first word of a stored data item, the method comprising the steps of:

inputting one word at a time of a sequence of input data words for simultaneous comparison with all of the CAM data words;

comparing, in a comparator circuit associated with each respective CAM data word, the respective CAM data word with the inputted one word of input data, and generating a word match signal for the respective CAM data word as a result of the comparison;

generating for each CAM data word a match till now signal indicating whether the respective CAM data word and a preceding CAM data word have matched with a corresponding succession of input data words;

generating for each CAM data word an exact match signal if the match till now signal is generated for the respective CAM data word and the respective CAM data word contains a last word of a stored data item; and

generating global match signals based on the match till now signals and exact match signals generated in all of the CAM data words,

wherein the step of generating a match till now signal for the respective CAM data word is based on the begin bit, the respective word match signal, the match till now bit associated with a preceding CAM data word, and a global signal indicating that a current input data word is a first word of an input data item.

10. A method as defined in claim 9, wherein the step of generating global match signals includes:

generating a global intermediate match signal if at least one match till now signal is generated to indicate that at least a partial match condition exists.

11. A method as defined in claim 9, wherein the step of generating global match signals includes:

generating a global exact match signal if at least one exact match signal is generated.

12. A method as defined in claim 9, wherein the step of generating global signals includes:

generating a global multiple match signal if more than one match till now signal is generated.

13. A method as defined in claim 9, wherein the step of generating a match till now signal includes:

setting the match till now bit of the respective CAM data word if the begin bit is set, if the first word of input data is being compared, and if the respective word match signal indicates a match, wherein the respective match till now bit will be set if the first word of the CAM data word and the first word of input data match;

setting the match till now bit if the begin bit is not set, if the match till now bit from the preceding CAM data word is set, and if the word match signal indicates a match, wherein a subsequent matching CAM data word will have its match till not bit set only if the match till now bit was set in a preceding CAM data word; and

otherwise clearing the match till now bit of the respective CAM data word.

14. A method as defined in claim 13, wherein the step of generating an exact match signal includes logically combining the respective match till now bit with the begin bit of a next succeeding CAM data word, the respective exact match signal being set when both the respective match till now bit is set and the begin bit is set in the next succeeding CAM data word.

15. A method as defined in claim 13, wherein:

one of the control bits of the CAM data word is a subfield bit indicating that a last subfield of the CAM data word does not contain valid data; and

the comparing step includes generating a match result for a subfield that does not contain valid data, as indicated by the subfield bit.

16. A method as defined in claim 13, wherein

the method further comprises the step of setting the global signal indicating the first word of input data so that every input word is treated as potentially starting an input data item;

and

each stored data item is compared with all possible sequences of input data words having a same match length as the stored data item.