US6715029B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information
Assignee: Cisco Technology Inc
•
Filing: 2002-01-07
•
Granted: 2004-03-30
•
Expires: 2022-01-07
Abstract
Abstract Methods and apparatus are disclosed for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information. One implementation operates on a set of information, the set of information including a lookup word portion and a discriminator portion. A lookup word is derived based on the lookup word portion. A lookup operation is performed on an associative memory, such as, but not limited to a binary or ternary content-addressable memory, using the lookup word to generate an associative memory result. A memory lookup operation is performed on a memory based on the associative memory result and the discriminator portion.
Inventors
- 👤 Oded Trainin
- 👤 Dov A. Freund
- 👤 Gil Goren
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:50
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/60; G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90339; H04L45/74; H04L45/745; H04L45/7453
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
82 words
A method performed using a set of information, the set of information including a lookup word portion and a discriminator portion and the lookup word portion includes a plurality of non-contiguous data from the set of information, the method comprising: performing a lookup operation on an associative memory using a lookup word including the lookup word portion to generate an associative memory result; and performing a memory lookup operation on a memory based on the associative memory result and the discriminator portion.
Claim 2
Independent Claim
82 words
A method performed using a set of information, the set of information including a lookup word portion and a discriminator portion and the lookup word portion includes a plurality of non-contiguous data from the set of information, the method comprising: performing a lookup operation on an associative memory using a lookup word including the lookup word portion to generate an associative memory result; and performing a memory lookup operation on a memory based on the associative memory result and the discriminator portion.
Claim 3
Dependent Claim
37 words
The method of claim 1 , wherein said performing the memory lookup operation based on the associative memory result and the discriminator portion includes deriving a memory address including the associative memory result and the discriminator portion.
Claim 4
Dependent Claim
20 words
The method of claim 2 , wherein the memory address includes the associative memory result concatenated with the discriminator portion.
Claim 5
Dependent Claim
15 words
The method of claim 1 , wherein the associative memory includes a ternary content-addressable memory.
Claim 6
Dependent Claim
16 words
The method of claim 1 , wherein the discriminator portion includes a small number of bits.
Claim 7
Dependent Claim
14 words
The method of claim 5 , wherein the small number of bits equals two.
Claim 8
Dependent Claim
15 words
The method of claim 1 , wherein the set of information includes a network address.
Claim 9
Dependent Claim
17 words
The method of claim 7 , wherein the discriminator portion includes a part of the network address.
Claim 10
Dependent Claim
13 words
The method of claim 1 , further comprising receiving the set of information.
Claim 11
Independent Claim
110 words
A method comprising: identifying a plurality of sets of potential discriminator bits; determining an associative memory programming for each of the plurality of sets of potential discriminator bits for each one of one or more configuration files to produce a set of results; analyzing the set of results to identify a discriminator portion and a lookup word portion of an input word; wherein the set of results includes a number of associative memory entries generated by said determining the associative memory programing; and wherein said analyzing the set of results includes determining which of the plurality of sets of potential discriminator bits produces a minimal number of associative memory entries.
Claim 12
Independent Claim
110 words
A method comprising: identifying a plurality of sets of potential discriminator bits; determining an associative memory programming for each of the plurality of sets of potential discriminator bits for each one of one or more configuration files to produce a set of results; analyzing the set of results to identify a discriminator portion and a lookup word portion of an input word; wherein the set of results includes a number of associative memory entries generated by said determining the associative memory programing; and wherein said analyzing the set of results includes determining which of the plurality of sets of potential discriminator bits produces a minimal number of associative memory entries.
Claim 13
Independent Claim
95 words
An apparatus configured to operate on a set of information, the set of information including a lookup word portion and a discriminator portion and the lookup word portion includes a plurality of non-contiguous data from the set of information, the apparatus comprising: means for deriving a lookup word based on the lookup word portion; means for performing a lookup operation on an associative memory using the lookup word to generate an associative memory result; and means for performing a memory lookup operation on a memory based on the associative memory result and the discriminator portion.
Claim 14
Independent Claim
95 words
An apparatus configured to operate on a set of information, the set of information including a lookup word portion and a discriminator portion and the lookup word portion includes a plurality of non-contiguous data from the set of information, the apparatus comprising: means for deriving a lookup word based on the lookup word portion; means for performing a lookup operation on an associative memory using the lookup word to generate an associative memory result; and means for performing a memory lookup operation on a memory based on the associative memory result and the discriminator portion.
Claim 15
Dependent Claim
41 words
The apparatus of claim 11 , wherein said means for performing the memory lookup operation based on the associative memory result and the discriminator portion includes means for deriving a memory address including the associative memory result and the discriminator portion.
Claim 16
Dependent Claim
20 words
The apparatus of claim 11 , wherein the memory address includes the associative memory result concatenated with the discriminator portion.
Claim 17
Dependent Claim
15 words
The apparatus of claim 11 , wherein the associative memory includes a ternary content-addressable memory.
Claim 18
Dependent Claim
15 words
The apparatus of claim 11 , wherein the set of information includes a network address.
Claim 19
Dependent Claim
17 words
The apparatus of claim 15 , wherein the discriminator portion includes a part of the network address.
Claim 20
Dependent Claim
98 words
The method of claim 10 , comprising: programming an associative memory with the associative memory programming corresponding to a particular set of the plurality of sets of potential discriminator bits that produces the minimal number of associative memory entries; receiving a particular input word comprising a particular discriminator portion and a particular lookup word portion; performing a lookup operation on an associative memory using a lookup word including the particular discriminator portion to generate an associative memory result; and performing a memory lookup operation on a memory based on the associative memory result and the particular discriminator portion.
Claim 21
Dependent Claim
15 words
The method of claim 17 , wherein the associative memory includes a ternary content-addressable memory.
Claim 22
Dependent Claim
15 words
The method of claim 17 , wherein the set of information includes a network address.
Claim 23
Dependent Claim
17 words
The method of claim 19 , wherein the discriminator portion includes a part of the network address.
Claim 24
Dependent Claim
119 words
A computer-readable medium containing computer-executable instructions for performing steps, said steps comprising: identifying a plurality of sets of potential discriminator bits; determining an associative memory programming for each of the plurality of sets of potential discriminator bits for each one of one or more configuration files to produce a set of results; analyzing the set of results to identify a discriminator portion and a lookup word portion of an input word; wherein the set of results includes a number of associative memory entries generated by said determining the associative memory programing; and wherein said analyzing the set of results includes determining which of the plurality of sets of potential discriminator bits produces a minimal number of associative memory entries.
Claim 25
Dependent Claim
119 words
A computer-readable medium containing computer-executable instructions for performing steps, said steps comprising: identifying a plurality of sets of potential discriminator bits; determining an associative memory programming for each of the plurality of sets of potential discriminator bits for each one of one or more configuration files to produce a set of results; analyzing the set of results to identify a discriminator portion and a lookup word portion of an input word; wherein the set of results includes a number of associative memory entries generated by said determining the associative memory programing; and wherein said analyzing the set of results includes determining which of the plurality of sets of potential discriminator bits produces a minimal number of associative memory entries.
Claim 26
Independent Claim
66 words
A method performed using a set of information, the set of information including a lookup word portion and a discriminator portion, the method comprising: performing a lookup operation on a ternary content-addressable memory (TCAM) using a lookup word including the lookup word portion to generate a TCAM result; and performing a memory lookup operation on a memory based on the TCAM result and the discriminator portion.
Claim 27
Independent Claim
66 words
A method performed using a set of information, the set of information including a lookup word portion and a discriminator portion, the method comprising: performing a lookup operation on a ternary content-addressable memory (TCAM) using a lookup word including the lookup word portion to generate a TCAM result; and performing a memory lookup operation on a memory based on the TCAM result and the discriminator portion.
Claim 28
Dependent Claim
37 words
The method of claim 22 , wherein said performing the memory lookup operation based on the associative memory result and the discriminator portion includes deriving a memory address including the associative memory result and the discriminator portion.
Claim 29
Dependent Claim
20 words
The method of claim 23 , wherein the memory address includes the associative memory result concatenated with the discriminator portion.
References Cited (Backward Citations)
US3648254A
Cited
US4296475A
Cited
US4791606A
Cited
US5088032A
Cited
US4996666A
Cited
US5440715A
Cited
US5481540A
Cited
US5319763A
Cited
US5564052A
Cited
US5383146A
Cited
US5898689A
Cited
US6000008A
Cited
US5450351A
Cited
US6047369A
Cited
US5515370A
Cited
US5835963A
Cited
US6041389A
Cited
US6091725A
Cited
US5740171A
Cited
US6243667B1
Cited
US5978885A
Cited
US6069573A
Cited
US5842040A
Cited
US5841874A
Cited
US5930359A
Cited
US5956336A
Cited
US5920900A
Cited
US5920886A
Cited
US6307855B1
Cited
US6181698B1
Cited
US6097724A
Cited
US6295576B1
Cited
US6034965A
Cited
US6026467A
Cited
US6199140B1
Cited
US6061368A
Cited
US6236658B1
Cited
US6148364A
Cited
US6141738A
Cited
US6233652B1
Cited
US6081440A
Cited
US6237061B1
Cited
US6137707A
Cited
US6175513B1
Cited
US6154384A
Cited
US6493812B1
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) | 2007-03-30 | 2007-09-29 | 2008-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-03-30 | 2011-09-29 | 2012-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-03-30 | 2015-09-29 | 2016-03-30 | $7700.00 | Window Closed / Lapsed |