US6574701B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Technique for updating a content addressable memory
Assignee: Telsima Corp
•
Filing: 2001-09-27
•
Granted: 2003-06-03
•
Expires: 2021-09-27
Abstract
Abstract A technique for updating a content addressable memory is disclosed. In one exemplary embodiment, wherein the content addressable memory has a plurality of entries, and wherein each of the plurality of entries has a prefix field, a prefix length field, and an associated index identifier, the technique is realized by determining a first index identifier associated with a first of the plurality of entries, wherein the first entry has a first prefix with a first prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory. A second index identifier associated with a second of the plurality of entries is also determined, wherein the second entry has a second prefix with a second prefix length that is less than the third prefix length of the third prefix to be added to the content addressable memory. Based upon the first index identifier and the second index identifier, a third index identifier is determined. The third index identifier is associated with a third of the plurality of entries where the third prefix with the third prefix length may be added to the content addressable memory. The third index identifier is located at one of or between the first index identifier and the second index identifier.
Inventors
- 👤 Pattabhiraman Krishna
- 👤 Surya Kumar Kovvali
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 01:18
CPC Classifications
G; G11; G11C; G11C15/00
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
193 words
A method for updating a content addressable memory having a plurality of entries, each of the plurality of entries having a prefix field, a prefix length field, and an associated index identifier, the method comprising the steps of: determining a first index identifier associated with a first of the plurality of entries, the first entry having a first prefix with a first prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory; determining a second index identifier associated with a second of the plurality of entries, the second entry having a second prefix with a second prefix length that is less than the third prefix length of the third prefix to be added to the content addressable memory; and determining a third index identifier, based upon the first index identifier and the second index identifier, associated with a third of the plurality of entries where the third prefix with the third prefix length may be added to the content addressable memory, the third index identifier being located at one of or between the first index identifier and the second index identifier.
Claim 2
Independent Claim
193 words
A method for updating a content addressable memory having a plurality of entries, each of the plurality of entries having a prefix field, a prefix length field, and an associated index identifier, the method comprising the steps of: determining a first index identifier associated with a first of the plurality of entries, the first entry having a first prefix with a first prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory; determining a second index identifier associated with a second of the plurality of entries, the second entry having a second prefix with a second prefix length that is less than the third prefix length of the third prefix to be added to the content addressable memory; and determining a third index identifier, based upon the first index identifier and the second index identifier, associated with a third of the plurality of entries where the third prefix with the third prefix length may be added to the content addressable memory, the third index identifier being located at one of or between the first index identifier and the second index identifier.
Claim 3
Dependent Claim
70 words
The method as defined in claim 1 , wherein the first entry is a member of a prefix chain having at least one other member entry each having a respective prefix with a respective prefix length, wherein the first prefix length is less than the lengths of all other prefixes in other entries that are members of the prefix chain whose prefix lengths are greater than the third prefix length.
Claim 4
Dependent Claim
54 words
The method as defined in claim 2 , wherein the second entry is also a member of the prefix chain, wherein the second prefix length is greater than the lengths of all other prefixes in other entries that are members of the prefix chain whose prefix lengths are less than the third prefix length.
Claim 5
Dependent Claim
23 words
The method as defined in claim 3 , wherein all members of the prefix chain are sorted according to their respective prefix lengths.
Claim 6
Dependent Claim
43 words
The method as defined in claim 4 , wherein the step of determining the first index identifier comprises the step of: searching the content addressable memory for entries having prefixes with prefix lengths which match the third prefix having the third prefix length.
Claim 7
Dependent Claim
148 words
The method as defined in claim 5 , wherein the step of searching the content addressable memory comprises the steps of: generating a compare array having a plurality of compare array entries corresponding to the plurality of entries in the content addressable memory, each of the plurality of compare array entries having a compare array prefix and an associated index identifier corresponding to the index identifier of a respective entry in the content addressable memory; extending the third prefix length of the third prefix to obtain an extended third prefix with an extended third prefix length; and comparing the extended third prefix to the plurality of compare array prefixes so as to identify index identifiers associated with compare array prefixes which match the extended third prefix, each identified index identifier corresponding to a respective entry in the content addressable memory that is a member of the prefix chain.
Claim 8
Dependent Claim
43 words
The method as defined in claim 4 , wherein the step of determining the second index identifier comprises the step of: searching the content addressable memory for entries having prefixes with prefix lengths which match the third prefix having the third prefix length.
Claim 9
Dependent Claim
148 words
The method as defined in claim 7 , wherein the step of searching the content addressable memory comprises the steps of: generating a compare array having a plurality of compare array entries corresponding to the plurality of entries in the content addressable memory, each of the plurality of compare array entries having a compare array prefix and an associated index identifier corresponding to the index identifier of a respective entry in the content addressable memory; extending the third prefix length of the third prefix to obtain an extended third prefix with an extended third prefix length; and comparing the extended third prefix to the plurality of compare array prefixes so as to identify index identifiers associated with compare array prefixes which match the extended third prefix, each identified index identifier corresponding to a respective entry in the content addressable memory that is a member of the prefix chain.
Claim 10
Dependent Claim
164 words
The method as defined in claim 4 , wherein the plurality of entries in the content addressable memory are bounded by a minimum index identifier (INDEXMIN) and a maximum index identifier (INDEXMAX), wherein the plurality of entries in the content addressable memory comprise a plurality of free space entries each having an unused prefix field and an unused prefix length field, wherein the plurality of free space entries are located in a middle portion of the content addressable memory bounded by a low free space index identifier (FREELOW) and a high free space index identifier (FREEHIGH), wherein entries in the content addressable memory having prefixes with prefix lengths that are greater than a threshold prefix length (THRESHOLD) have associated index identifiers that are greater than INDEXMIN and less than FREELOW, and wherein entries in the content addressable memory having prefixes with prefix lengths that are less than or equal to THRESHOLD have associated index identifiers that are greater than FREEHIGH and less than INDEXMAX.
Claim 11
Dependent Claim
76 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying FREELOW as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is equal to INDEXMIN; the second index identifier is equal to INDEXMAX; and the third prefix length is greater than THRESHOLD.
Claim 12
Dependent Claim
79 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying FREEHIGH as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is equal to INDEXMIN; the second index identifier is equal to INDEXMAX; and the third prefix length is less than or equal to THRESHOLD.
Claim 13
Dependent Claim
87 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying FREELOW as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is equal to INDEXMIN; the second index identifier is less than INDEXMAX; the second prefix length is less than or equal to THRESHOLD; and the third prefix length is greater than THRESHOLD.
Claim 14
Dependent Claim
90 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying FREEHIGH as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is equal to INDEXMIN; the second index identifier is less than INDEXMAX; the second prefix length is less than or equal to THRESHOLD; and the third prefix length is less than or equal to THRESHOLD.
Claim 15
Dependent Claim
79 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying the second index identifier as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is equal to INDEXMIN; the second index identifier is less than INDEXMAX; and the second prefix length is greater than THRESHOLD.
Claim 16
Dependent Claim
82 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying the first index identifier as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is greater than INDEXMIN; the second index identifier is equal to INDEXMAX; and the first prefix length is less than or equal to THRESHOLD.
Claim 17
Dependent Claim
87 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying FREEHIGH as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is greater than INDEXMIN; the second index identifier is equal to INDEXMAX; the first prefix length is greater than THRESHOLD; and the third prefix length is less than or equal to THRESHOLD.
Claim 18
Dependent Claim
87 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying the first index identifier+1 as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is greater than INDEXMIN; the second index identifier is equal to INDEXMAX; the first prefix length is greater than THRESHOLD; and the third prefix length is greater than THRESHOLD.
Claim 19
Dependent Claim
93 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying the first index identifier as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is greater than INDEXMIN; the second index identifier is less than INDEXMAX; the first prefix length is less than or equal to THRESHOLD; and the second prefix length is less than or equal to THRESHOLD.
Claim 20
Dependent Claim
98 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying FREEHIGH as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is greater than INDEXMIN; the second index identifier is less than INDEXMAX; the first prefix length is greater than THRESHOLD; the second prefix length is less than or equal to THRESHOLD; and the third prefix length is less than or equal to THRESHOLD.
Claim 21
Dependent Claim
95 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying FREELOW as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is greater than INDEXMIN; the second index identifier is less than INDEXMAX; the first prefix length is greater than THRESHOLD; the second prefix length is less than or equal to THRESHOLD; and the third prefix length is greater than THRESHOLD.
Claim 22
Dependent Claim
87 words
The method as defined in claim 9 , wherein the step of determining the third index identifier comprises the step of: identifying the second index identifier as the third index identifier associated with the third entry where the third prefix with the third prefix length may be added to the content addressable memory if: the first index identifier is greater than INDEXMIN; the second index identifier is less than INDEXMAX; the first prefix length is greater than THRESHOLD; and the second prefix length is greater than THRESHOLD.
Claim 23
Dependent Claim
32 words
The method as defined in claim 9 , further comprising the step of: adding the third prefix with the third prefix length in the third entry associated with the third index identifier.
Claim 24
Dependent Claim
58 words
The method as defined in claim 9 , further comprising the step of: moving a block of entries up by one into the plurality of free space entries to create the third entry into which the third prefix with the third prefix length may be added if the third index identifier is determined to be less than FREELOW.
Claim 25
Dependent Claim
29 words
The method as defined in claim 23 , further comprising the step of: incrementing FREELOW by one if the third index identifier is determined to be less than FREELOW.
Claim 26
Dependent Claim
58 words
The method as defined in claim 9 , further comprising the step of: moving a block of entries down by one into the plurality of free space entries to create the third entry into which the third prefix with the third prefix length may be added if the third index identifier is determined to be greater than FREEHIGH.
Claim 27
Dependent Claim
29 words
The method as defined in claim 25 , further comprising the step of: decrementing FREEHIGH by one if the third index identifier is determined to be greater than FREEHIGH.
Claim 28
Dependent Claim
32 words
The method as defined in claim 9 , further comprising the step of: deleting a fourth prefix with a fourth prefix length from a fourth entry having an associated fourth index identifier.
Claim 29
Dependent Claim
35 words
The method as defined in claim 27 , wherein each of the plurality of entries also has a free space indicator, further comprising the step of: setting the free space indicator in the fourth entry.
Claim 30
Dependent Claim
41 words
The method as defined in claim 27 , further comprising the step of: moving a block of entries down by one from the plurality of free space entries into the fourth entry if the fourth index identifier is less than FREELOW.
Claim 31
Dependent Claim
26 words
The method as defined in claim 29 , further comprising the step of: decrementing FREELOW by one if the fourth index identifier is less than FREELOW.
Claim 32
Dependent Claim
44 words
The method as defined in claim 30 , wherein each of the plurality of entries also has a free space indicator, further comprising the step of: setting the free space indicator in the entry associated with index identifier FREELOW−1 after decrementing FREELOW by one.
Claim 33
Dependent Claim
41 words
The method as defined in claim 27 , further comprising the step of: moving a block of entries up by one from the plurality of free space entries into the fourth entry if the fourth index identifier is greater than FREEHIGH.
Claim 34
Dependent Claim
26 words
The method as defined in claim 32 , further comprising the step of: incrementing FREEHIGH by one if the fourth index identifier is greater than FREEHIGH.
Claim 35
Dependent Claim
44 words
The method as defined in claim 33 , wherein each of the plurality of entries also has a free space indicator, further comprising the step of: setting the free space indicator in the entry associated with index identifier FREEHIGH+1 after incrementing FREEHIGH by one.
Claim 36
Dependent Claim
39 words
A signal embodied in a carrier wave representing one or more sequences of processor readable instructions which, when executed by at least one processor, cause the at least one processor to perform the method recited in claim 1 .
Claim 37
Independent Claim
227 words
An apparatus for updating a content addressable memory having a plurality of entries, each of the plurality of entries having a prefix field, a prefix length field, and an associated index identifier, the apparatus comprising: at least one processor readable media for storing processor readable instructions; and at least one processor for executing the instructions stored on the at least one processor readable media, thereby causing the at least one processor to: determine a first index identifier associated with a first of the plurality of entries, the first entry having a first prefix with a first prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory; determine a second index identifier associated with a second of the plurality of entries, the second entry having a second prefix with a second prefix length that is less than the third prefix length of the third prefix to be added to the content addressable memory; and determine a third index identifier, based upon the first index identifier and the second index identifier, associated with a third of the plurality of entries where the third prefix with the third prefix length may be added to the content addressable memory, the third index identifier being located at one of or between the first index identifier and the second index identifier.
Claim 38
Independent Claim
227 words
An apparatus for updating a content addressable memory having a plurality of entries, each of the plurality of entries having a prefix field, a prefix length field, and an associated index identifier, the apparatus comprising: at least one processor readable media for storing processor readable instructions; and at least one processor for executing the instructions stored on the at least one processor readable media, thereby causing the at least one processor to: determine a first index identifier associated with a first of the plurality of entries, the first entry having a first prefix with a first prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory; determine a second index identifier associated with a second of the plurality of entries, the second entry having a second prefix with a second prefix length that is less than the third prefix length of the third prefix to be added to the content addressable memory; and determine a third index identifier, based upon the first index identifier and the second index identifier, associated with a third of the plurality of entries where the third prefix with the third prefix length may be added to the content addressable memory, the third index identifier being located at one of or between the first index identifier and the second index identifier.
Claim 39
Dependent Claim
241 words
An article of manufacture for updating a content addressable memory having a plurality of entries, each of the plurality of entries having a prefix field, a prefix length field, and an associated index identifier, the article of manufacture comprising: at least one processor readable carrier; and instructions carried on the at least one carrier; wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to: determine a first index identifier associated with a first of the plurality of entries, the first entry having a first prefix with a first prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory; determine a second index identifier associated with a second of the plurality of entries, the second entry having a second prefix with a second prefix length that is less than the third prefix length of the third prefix to be added to the content addressable memory; and determine a third index identifier, based upon the first index identifier and the second index identifier, associated with a third of the plurality of entries where the third prefix with the third prefix length may be added to the content addressable memory, the third index identifier being located at one of or between the first index identifier and the second index identifier.
Claim 40
Dependent Claim
241 words
An article of manufacture for updating a content addressable memory having a plurality of entries, each of the plurality of entries having a prefix field, a prefix length field, and an associated index identifier, the article of manufacture comprising: at least one processor readable carrier; and instructions carried on the at least one carrier; wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to: determine a first index identifier associated with a first of the plurality of entries, the first entry having a first prefix with a first prefix length that is greater than a third prefix length of a third prefix to be added to the content addressable memory; determine a second index identifier associated with a second of the plurality of entries, the second entry having a second prefix with a second prefix length that is less than the third prefix length of the third prefix to be added to the content addressable memory; and determine a third index identifier, based upon the first index identifier and the second index identifier, associated with a third of the plurality of entries where the third prefix with the third prefix length may be added to the content addressable memory, the third index identifier being located at one of or between the first index identifier and the second index identifier.
References Cited (Backward Citations)
US6181698B1
Cited
US6081440A
Cited
US6175514B1
Cited
US6181592B1
Cited
US6137707A
Cited
US6154384A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-06-02 | 2006-12-02 | 2007-06-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-06-02 | 2010-12-02 | 2011-06-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-06-02 | 2014-12-02 | 2015-06-03 | $7700.00 | Window Closed / Lapsed |