US6000008A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for matching data items of variable length in a content addressable memory
Assignee: Extreme Networks Inc
•
Filing: 1997-04-17
•
Granted: 1999-12-07
•
Expires: 2017-04-17
Abstract
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.
Inventors
- 👤 Robert J. Simcoe
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 10:28
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0893; G11; G11C; G11C15/00; G11C15/04
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
305 words
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.
Claim 2
Dependent Claim
305 words
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.
Claim 3
Dependent Claim
42 words
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.
Claim 4
Dependent Claim
31 words
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.
Claim 5
Dependent Claim
32 words
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.
Claim 6
Dependent Claim
168 words
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.
Claim 7
Dependent Claim
68 words
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.
Claim 8
Dependent Claim
63 words
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.
Claim 9
Dependent Claim
63 words
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.
Claim 10
Independent Claim
300 words
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.
Claim 11
Independent Claim
300 words
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.
Claim 12
Dependent Claim
42 words
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.
Claim 13
Dependent Claim
31 words
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.
Claim 14
Dependent Claim
31 words
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.
Claim 15
Dependent Claim
163 words
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.
Claim 16
Dependent Claim
66 words
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.
Claim 17
Dependent Claim
61 words
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.
Claim 18
Dependent Claim
65 words
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.
References Cited (Backward Citations)
US3261000A
Cited
US3257646A
Cited
US3264616A
Cited
US3290659A
Cited
US3353159A
Cited
US4065756A
Cited
US4296475A
Cited
US4377855A
Cited
US4907194A
Cited
US4805093A
Cited
US4845668A
Cited
US5010516A
Cited
US5175860A
Cited
US5329405A
Cited
US5053991A
Cited
US5463751A
Cited
US5319762A
Cited
US5222222A
Cited
US5457788A
Cited
US5383146A
Cited
US5299147A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-06 | 2003-06-07 | 2003-12-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-06 | 2007-06-07 | 2007-12-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-06 | 2011-06-07 | 2011-12-07 | $7700.00 | Window Closed / Lapsed |