US6526474B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Content addressable memory (CAM) with accesses to multiple CAM arrays used to generate result for various matching sizes
Assignee: Cisco Technology Inc
•
Filing: 1999-11-09
•
Granted: 2003-02-25
•
Expires: 2019-11-09
Abstract
Abstract The invention provides a method and system for operating a CAM with a variable size input tag. The improved CAM has multiple access sizes and is divided into multiple stored match sections. Each of the multiple stored match sections can be independently matched against a portion of the input tag, responsive to a type field for each entry. A size selection circuit accumulates the independent match results; a priority encoder coupled thereto collects the accumulated matches and presents a match as an output from the CAM. Each CAM entry can be selected from a set of preselected sizes, each corresponding to a contemplated input tag size, such as 72 bits, 144 bits, or 288 bits.
Inventors
- 👤 Mark A. Ross
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:17
CPC Classifications
G; G11; G11C; G11C15/00; G11C15/04
Claims Analysis
Total Claims: 68
Claim 1
Independent Claim
136 words
A method comprising: receiving an input tag; identifying one or more input tag widths; performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag; performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and generating one or more size selection CAM result indications based on the first and second CAM result indications and said one or more input tag widths; wherein each of the plurality of first and second CAM entries include a plurality of value bits.
Claim 2
Independent Claim
136 words
A method comprising: receiving an input tag; identifying one or more input tag widths; performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag; performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and generating one or more size selection CAM result indications based on the first and second CAM result indications and said one or more input tag widths; wherein each of the plurality of first and second CAM entries include a plurality of value bits.
Claim 3
Dependent Claim
48 words
The method of claim 1 , wherein when said one or more input tag widths include a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.
Claim 4
Dependent Claim
25 words
The method of claim 2 , further comprising generating a single priority result value based on said one or more size selection CAM result indications.
Claim 5
Dependent Claim
49 words
The method of claim 2 , wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.
Claim 6
Dependent Claim
42 words
The method of claim 4 , wherein said generating one or more size selection CAM result indications includes generating a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.
Claim 7
Dependent Claim
36 words
The method of claim 5 , further comprising generating a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.
Claim 8
Dependent Claim
53 words
The method of claim 6 , further comprising reading from, writing to, or reading from and writing to the first CAM array, the second CAM array, or the first and second CAM arrays based on the first priority result value, the second priority result value, or the first and second priority result values.
Claim 9
Dependent Claim
49 words
The method of claim 1 , wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.
Claim 10
Dependent Claim
25 words
The method of claim 8 , further comprising generating a single priority result value based on said one or more size selection CAM result indications.
Claim 11
Dependent Claim
24 words
The method of claim 1 , wherein each of the plurality of first and second CAM entries further includes a plurality of mask bits.
Claim 12
Dependent Claim
21 words
The method of claim 1 , wherein said performing the first lookup and said performing the second lookup are performed simultaneously.
Claim 13
Independent Claim
146 words
An apparatus comprising: means for receiving an input tag; means for identifying one or more input tag widths; means for performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag; means for performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and means for generating one or more size selection CAM result indications based on the first and second CAM result indications and said one or more input tag widths; wherein each of the plurality of first and second CAM entries include a plurality of value bits.
Claim 14
Independent Claim
146 words
An apparatus comprising: means for receiving an input tag; means for identifying one or more input tag widths; means for performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag; means for performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and means for generating one or more size selection CAM result indications based on the first and second CAM result indications and said one or more input tag widths; wherein each of the plurality of first and second CAM entries include a plurality of value bits.
Claim 15
Dependent Claim
48 words
The apparatus of claim 12 , wherein when said one or more input tag widths include a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.
Claim 16
Dependent Claim
27 words
The apparatus of claim 13 , further comprising means for generating a single priority result value based on said one or more size selection CAM result indications.
Claim 17
Dependent Claim
49 words
The apparatus of claim 13 , wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.
Claim 18
Dependent Claim
46 words
The apparatus of claim 15 , wherein said means for generating one or more size selection CAM result indications includes means for generating a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.
Claim 19
Dependent Claim
38 words
The apparatus of claim 16 , further comprising means for generating a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.
Claim 20
Dependent Claim
55 words
The apparatus of claim 17 , further comprising means for reading from, writing to, or reading from and writing to the first CAM array, the second CAM array, or the first and second CAM arrays based on the first priority result value, the second priority result value, or the first and second priority result values.
Claim 21
Dependent Claim
49 words
The apparatus of claim 12 , wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.
Claim 22
Dependent Claim
27 words
The apparatus of claim 19 , further comprising means for generating a single priority result value based on said one or more size selection CAM result indications.
Claim 23
Dependent Claim
24 words
The apparatus of claim 12 , wherein each of the plurality of first and second CAM entries further includes a plurality of mask bits.
Claim 24
Independent Claim
145 words
An apparatus comprising: a first content-addressable memory (CAM) array including a plurality of first CAM entries, the first CAM array configured to generate a first CAM result indication of which of the plurality of first CAM entries produce a hit based on an input tag; a second CAM array including a plurality of second CAM entries, each of the plurality of first and second CAM entries including a plurality of value bits, the second CAM array configured to generate a second CAM result indication of which of the plurality of second CAM entries produce a hit based on the input tag; and a size selection mechanism coupled to the first and second CAM arrays, the size selection mechanism configured to generate one or more size selection CAM result indications based on the first and second CAM result indications and one or more input tag widths.
Claim 25
Independent Claim
145 words
An apparatus comprising: a first content-addressable memory (CAM) array including a plurality of first CAM entries, the first CAM array configured to generate a first CAM result indication of which of the plurality of first CAM entries produce a hit based on an input tag; a second CAM array including a plurality of second CAM entries, each of the plurality of first and second CAM entries including a plurality of value bits, the second CAM array configured to generate a second CAM result indication of which of the plurality of second CAM entries produce a hit based on the input tag; and a size selection mechanism coupled to the first and second CAM arrays, the size selection mechanism configured to generate one or more size selection CAM result indications based on the first and second CAM result indications and one or more input tag widths.
Claim 26
Dependent Claim
30 words
The apparatus of claim 22 , further comprising an input request register coupled to the first and second CAM arrays, the input request register configured to store the input tag.
Claim 27
Dependent Claim
48 words
The apparatus of claim 22 , wherein when said one or more input tag widths include a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.
Claim 28
Dependent Claim
39 words
The apparatus of claim 24 , further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a single priority result value based on said one or more size selection CAM result indications.
Claim 29
Dependent Claim
49 words
The apparatus of claim 24 , wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.
Claim 30
Dependent Claim
40 words
The apparatus of claim 26 , wherein said one or more size selection CAM result indications include a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.
Claim 31
Dependent Claim
50 words
The apparatus of claim 27 , further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.
Claim 32
Dependent Claim
49 words
The apparatus of claim 22 , wherein when said one or more input tag widths include a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.
Claim 33
Dependent Claim
39 words
The apparatus of claim 29 , further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a single priority result value based on said one or more size selection CAM result indications.
Claim 34
Dependent Claim
24 words
The apparatus of claim 22 , wherein each of the plurality of first and second CAM entries further includes a plurality of mask bits.
Claim 35
Independent Claim
148 words
A method comprising: receiving an input tag; identifying a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths; performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag; performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and generating one or more size selection CAM result indications based on the first and second CAM result indications and the selected input tag width; wherein each of the plurality of first and second CAM entries include a plurality of value bits.
Claim 36
Independent Claim
148 words
A method comprising: receiving an input tag; identifying a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths; performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag; performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and generating one or more size selection CAM result indications based on the first and second CAM result indications and the selected input tag width; wherein each of the plurality of first and second CAM entries include a plurality of value bits.
Claim 37
Dependent Claim
47 words
The method of claim 32 , wherein when the selected input tag width corresponds to a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.
Claim 38
Dependent Claim
25 words
The method of claim 33 , further comprising generating a single priority result value based on said one or more size selection CAM result indications.
Claim 39
Dependent Claim
45 words
The method of claim 33 , wherein when the selected input tag width corresponds to a second width, said one or more size selection CAM result indications indicate which locations within the first and second CAM arrays produced a hit based on the input tag.
Claim 40
Dependent Claim
42 words
The method of claim 35 , wherein said generating one or more size selection CAM result indications includes generating a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.
Claim 41
Dependent Claim
36 words
The method of claim 36 , further comprising generating a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.
Claim 42
Dependent Claim
53 words
The method of claim 37 , further comprising reading from, writing to, or reading from and writing to the first CAM array, the second CAM array, or the first and second CAM arrays based on the first priority result value, the second priority result value, or the first and second priority result values.
Claim 43
Dependent Claim
45 words
The method of claim 32 , wherein when the selected input tag width corresponds to a second width, said one or more size selection CAM result indications indicate which locations within the first and second CAM arrays produced a hit based on the input tag.
Claim 44
Dependent Claim
25 words
The method of claim 39 , further comprising generating a single priority result value based on said one or more size selection CAM result indications.
Claim 45
Dependent Claim
23 words
The method of claim 32 , wherein each of the plurality of first and second CAM entries includes a plurality of mask bits.
Claim 46
Dependent Claim
21 words
The method of claim 32 , wherein said performing the first lookup and said performing the second lookup are performed simultaneously.
Claim 47
Independent Claim
158 words
An apparatus comprising: means for receiving an input tag; means for identifying a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths; means for performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag; means for performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and means for generating one or more size selection CAM result indications based on the first and second CAM result indications and the selected input tag width; wherein each of the plurality of first and second CAM entries include a plurality of value bits.
Claim 48
Independent Claim
158 words
An apparatus comprising: means for receiving an input tag; means for identifying a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths; means for performing a first lookup in a first content-addressable memory (CAM) array to generate a first CAM result indication of which of a plurality of first CAM entries within the first CAM array produced a hit based on the input tag; means for performing a second lookup in a second CAM array to generate a second CAM result indication of which of a plurality of second CAM entries within the second CAM array produced a hit based on the input tag; and means for generating one or more size selection CAM result indications based on the first and second CAM result indications and the selected input tag width; wherein each of the plurality of first and second CAM entries include a plurality of value bits.
Claim 49
Dependent Claim
47 words
The apparatus of claim 43 , wherein when the selected input tag width corresponds to a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.
Claim 50
Dependent Claim
27 words
The apparatus of claim 44 , further comprising means for generating a single priority result value based on said one or more size selection CAM result indications.
Claim 51
Dependent Claim
45 words
The apparatus of claim 44 , wherein when the selected input tag width corresponds to a second width, said one or more size selection CAM result indications indicate which locations within the first and second CAM arrays produced a hit based on the input tag.
Claim 52
Dependent Claim
46 words
The apparatus of claim 46 , wherein said means for generating one or more size selection CAM result indications includes means for generating a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.
Claim 53
Dependent Claim
38 words
The apparatus of claim 47 , further comprising means for generating a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.
Claim 54
Dependent Claim
55 words
The apparatus of claim 48 , further comprising means for reading from, writing to, or reading from and writing to the first CAM array, the second CAM array, or the first and second CAM arrays based on the first priority result value, the second priority result value, or the first and second priority result values.
Claim 55
Dependent Claim
45 words
The apparatus of claim 43 , wherein when the selected input tag width corresponds to a second width, said one or more size selection CAM result indications indicate which locations within the first and second CAM arrays produced a hit based on the input tag.
Claim 56
Dependent Claim
27 words
The apparatus of claim 50 , further comprising means for generating a single priority result value based on said one or more size selection CAM result indications.
Claim 57
Dependent Claim
23 words
The apparatus of claim 43 , wherein each of the plurality of first and second CAM entries includes a plurality of mask bits.
Claim 58
Independent Claim
159 words
An apparatus comprising: a first content-addressable memory (CAM) array including a plurality of first CAM entries, the first CAM array configured to generate a first CAM result indication of which of the plurality of first CAM entries produce a hit based on an input tag; a second CAM array including a plurality of second CAM entries, each of the plurality of first and second CAM entries including a plurality of value bits, the second CAM array configured to generate a second CAM result indication of which of the plurality of second CAM entries produce a hit based on the input tag; and a size selection mechanism coupled to the first and second CAM arrays, the size selection mechanism configured to generate one or more size selection CAM result indications based on the first and second CAM result indications and a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths.
Claim 59
Independent Claim
159 words
An apparatus comprising: a first content-addressable memory (CAM) array including a plurality of first CAM entries, the first CAM array configured to generate a first CAM result indication of which of the plurality of first CAM entries produce a hit based on an input tag; a second CAM array including a plurality of second CAM entries, each of the plurality of first and second CAM entries including a plurality of value bits, the second CAM array configured to generate a second CAM result indication of which of the plurality of second CAM entries produce a hit based on the input tag; and a size selection mechanism coupled to the first and second CAM arrays, the size selection mechanism configured to generate one or more size selection CAM result indications based on the first and second CAM result indications and a selected input tag width, the selected input tag width being one of a plurality of possible input tag widths.
Claim 60
Dependent Claim
30 words
The apparatus of claim 53 , further comprising an input request register coupled to the first and second CAM arrays, the input request register configured to store the input tag.
Claim 61
Dependent Claim
46 words
The apparatus of claim 53 , wherein when the selected tag width corresponds to a first width, said one or more size selection CAM result indications indicate which corresponding locations within both the first and second CAM arrays produced a hit based on the input tag.
Claim 62
Dependent Claim
39 words
The apparatus of claim 55 , further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a single priority result value based on said one or more size selection CAM result indications.
Claim 63
Dependent Claim
47 words
The apparatus of claim 55 , wherein when the selected tag width corresponds to a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.
Claim 64
Dependent Claim
40 words
The apparatus of claim 57 , wherein said one or more size selection CAM result indications include a first set of match bits corresponding to said first width and a second set of match bits corresponding to said second width.
Claim 65
Dependent Claim
50 words
The apparatus of claim 58 , further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a first priority result value based on the first set of match bits and a second priority result value based on the second set of match bits.
Claim 66
Dependent Claim
47 words
The apparatus of claim 53 , wherein when the selected tag width corresponds to a second width, said one or more size selection CAM result indications indicate which corresponding locations within one of the first and second CAM arrays produced a hit based on the input tag.
Claim 67
Dependent Claim
39 words
The apparatus of claim 60 , further comprising a priority encoder coupled to the size selection mechanism, the priority encoder configured to generate a single priority result value based on said one or more size selection CAM result indications.
Claim 68
Dependent Claim
24 words
The apparatus of claim 53 , wherein each of the plurality of first and second CAM entries further includes a plurality of mask bits.
References Cited (Backward Citations)
US3648254A
Cited
US4296475A
Cited
US4791606A
Cited
US5088032A
Cited
US4996666A
Cited
US5440715A
Cited
US5481540A
Cited
US5319763A
Cited
US5383146A
Cited
US5898689A
Cited
US6000008A
Cited
US5450351A
Cited
US6047369A
Cited
US5515370A
Cited
US6041389A
Cited
US6091725A
Cited
US5740171A
Cited
US6243667B1
Cited
US5978885A
Cited
US6069573A
Cited
US5842040A
Cited
US5841874A
Cited
US5930359A
Cited
US5956336A
Cited
US5920886A
Cited
US6181698B1
Cited
US6307855B1
Cited
US6097724A
Cited
US6295576B1
Cited
US6199140B1
Cited
US6061368A
Cited
US6236658B1
Cited
US6148364A
Cited
US6141738A
Cited
US6389506B1
Cited
US6081440A
Cited
US6237061B1
Cited
US6137707A
Cited
US6175513B1
Cited
US6374326B1
Cited
US6154384A
Cited
US6134135A
Cited
US6240003B1
Cited
US6246601B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-02-24 | 2006-08-26 | 2007-02-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-02-24 | 2010-08-26 | 2011-02-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-02-24 | 2014-08-26 | 2015-02-25 | $7700.00 | Window Closed / Lapsed |