US6775737B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for allocating and using range identifiers as input values to content-addressable memories
Assignee: Cisco Technology Inc
•
Filing: 2001-10-09
•
Granted: 2004-08-10
•
Expires: 2021-10-09
Abstract
Abstract Methods and apparatus are disclosed for allocating and using range identifiers as input values to associative memories, especially binary content-addressable memories (CAMs) and ternary content-addressable memories (TCAMs). In one implementation, each of multiple non-overlapping intervals are identified with one of multiple unique identifiers. An indication of a mapping between the multiple non-overlapping intervals and the multiple unique identifiers is maintained. A particular unique identifier is determined from said multiple unique identifiers based on a value and said multiple non-overlapping intervals. A lookup operation is performed on an associative memory using the particular unique identifier to generate a result. One implementation uses a trie representation of a range tree of the intervals to derive the unique identifiers. Moreover, one implementation evaluates and selects among various possible trie representations, especially to determine identifiers such that a TCAM prefix may match multiple intervals corresponding to a desired range.
Inventors
- 👤 Priyank Ramesh Warkhede
- 👤 William N. Eatherton
- 👤 Shyamsundar N. Maniyar
- 👤 Peram Marimuthu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 20:18
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/48; H04L69/00; H04L69/22
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
76 words
A method comprising: identifying each of a plurality of non-overlapping intervals with one of a plurality of unique identifiers; maintaining an indication of a mapping between the plurality of non-overlapping intervals and the plurality of unique identifiers; determining a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and performing a lookup operation on an associative memory using the particular unique identifier to generate a result.
Claim 2
Independent Claim
76 words
A method comprising: identifying each of a plurality of non-overlapping intervals with one of a plurality of unique identifiers; maintaining an indication of a mapping between the plurality of non-overlapping intervals and the plurality of unique identifiers; determining a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and performing a lookup operation on an associative memory using the particular unique identifier to generate a result.
Claim 3
Dependent Claim
19 words
The method of claim 1 , further comprising partitioning a plurality of ranges into the plurality of non-overlapping intervals.
Claim 4
Dependent Claim
57 words
The method of claim 1 , wherein said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes: determining at least two different sets of values for the plurality of unique identifiers; and selecting one of said at least two different sets of values for the plurality of unique identifiers.
Claim 5
Dependent Claim
42 words
The method of claim 3 , wherein said one of said at least two different sets of values for the plurality of unique identifiers is associated with a minimal cost, wherein said cost is defined as a number of ternary content-addressable entries.
Claim 6
Dependent Claim
65 words
The method of claim 1 , wherein said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes: determining at least two different mappings between the plurality of non-overlapping intervals and the plurality of unique identifiers; and selecting one of said at least two different mappings between the plurality of non-overlapping intervals and the plurality of unique identifiers.
Claim 7
Dependent Claim
34 words
The method of claim 1 , said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes determining a trie representation of the plurality of non-overlapping intervals.
Claim 8
Dependent Claim
49 words
The method of claim 1 , wherein said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes: determining at least two different trie representations of the plurality of non-overlapping intervals; and selecting one of said at least two different trie representations.
Claim 9
Dependent Claim
43 words
The method of claim 7 , wherein said selecting one of said at least two different trie representations includes evaluating each of said at least two different trie representations for prefixes that would match two or more of the plurality of non-overlapping intervals.
Claim 10
Dependent Claim
28 words
The method of claim 1 , further comprising programming the associative memory with an entry that matches at least two unique identifiers of said plurality of unique identifiers.
Claim 11
Dependent Claim
12 words
The method of claim 9 , wherein the entry includes a prefix.
Claim 12
Dependent Claim
17 words
The method of claim 1 , wherein the associative memory includes a binary or ternary content-addressable memory.
Claim 13
Dependent Claim
19 words
The method of claim 1 , wherein the value includes a port number, an address, or a service characteristic.
Claim 14
Dependent Claim
21 words
The method of claim 12 , further comprising receiving a packet including the port number, the address, or the service characteristic.
Claim 15
Dependent Claim
43 words
The method of claim 1 , wherein said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes performing a tree analysis on at least two different sets or mappings of the plurality of unique identifiers.
Claim 16
Dependent Claim
33 words
The method of claim 14 , wherein said tree analysis includes analyzing a resultant set of trie representations of said at least two different sets or mappings of the plurality of unique identifiers.
Claim 17
Dependent Claim
14 words
A computer-readable medium containing computer-executable instructions for performing the method of claim 15 .
Claim 18
Dependent Claim
44 words
The method of claim 1 , wherein said performing a lookup operation on an associative memory using the particular unique identifier to generate a result includes performing a lookup operation in the associative memory based on a lookup word including the particular unique identifier.
Claim 19
Dependent Claim
46 words
The method of claim 17 , wherein the associative memory is a ternary content-addressable memory such that each particular entry of the associative memory matches the lookup word if each bit of the lookup word is equal to each corresponding non-masked bit of said particular entry.
Claim 20
Dependent Claim
45 words
The method of claim 17 , wherein the associative memory is a binary content-addressable memory such that each particular entry of the associative memory matches the lookup word if each bit of the lookup word is equal to each corresponding bit of said particular entry.
Claim 21
Independent Claim
69 words
An apparatus comprising: a storage mechanism configured to maintain an indication of a mapping between a plurality of non-overlapping intervals and a plurality of unique identifiers; a range logic to determine a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and an associative memory to perform a lookup operation using the particular unique identifier to generate a result.
Claim 22
Independent Claim
69 words
An apparatus comprising: a storage mechanism configured to maintain an indication of a mapping between a plurality of non-overlapping intervals and a plurality of unique identifiers; a range logic to determine a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and an associative memory to perform a lookup operation using the particular unique identifier to generate a result.
Claim 23
Dependent Claim
27 words
The apparatus of claim 20 , further comprising a programming engine for determining the mapping between the plurality of non-overlapping intervals and the plurality of unique identifiers.
Claim 24
Dependent Claim
20 words
The apparatus of claim 21 , wherein the programming engine includes an associative memory programmer to program the associative memory.
Claim 25
Dependent Claim
31 words
The apparatus of claim 21 , wherein the programming engine includes an analyzer for performing an analysis on at least two different sets or mappings of the plurality of unique identifiers.
Claim 26
Dependent Claim
32 words
The apparatus of claim 23 , wherein the programming engine includes a selection mechanism for selecting one of said at least two different sets or mappings of the plurality of unique identifiers.
Claim 27
Dependent Claim
27 words
The apparatus of claim 23 , wherein the analyzer performs a tree analysis on at least two different sets or mappings of the plurality of unique identifiers.
Claim 28
Dependent Claim
33 words
The apparatus of claim 25 , wherein said tree analysis includes analyzing a resultant set of trie representations of said at least two different sets or mappings of the plurality of unique identifiers.
Claim 29
Dependent Claim
33 words
The apparatus of claim 20 , wherein said to perform a lookup operation using the particular unique identifier includes to perform a lookup operation using a lookup word including the particular unique identifier.
Claim 30
Independent Claim
84 words
An apparatus comprising: means for identifying each of a plurality of non-overlapping intervals with one of a plurality of unique identifiers; means for maintaining an indication of a mapping between the plurality of non-overlapping intervals and the plurality of unique identifiers; means for determining a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and means for performing a lookup operation on an associative memory using the particular unique identifier to generate a result.
Claim 31
Independent Claim
84 words
An apparatus comprising: means for identifying each of a plurality of non-overlapping intervals with one of a plurality of unique identifiers; means for maintaining an indication of a mapping between the plurality of non-overlapping intervals and the plurality of unique identifiers; means for determining a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and means for performing a lookup operation on an associative memory using the particular unique identifier to generate a result.
Claim 32
Dependent Claim
21 words
The apparatus of claim 28 , further comprising means for partitioning a plurality of ranges into the plurality of non-overlapping intervals.
Claim 33
Dependent Claim
63 words
The apparatus of claim 28 , wherein said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes: means for determining at least two different sets of values for the plurality of unique identifiers; and means for selecting one of said at least two different sets of values for the plurality of unique identifiers.
Claim 34
Dependent Claim
71 words
The apparatus of claim 28 , wherein said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes: means for determining at least two different mappings between the plurality of non-overlapping intervals and the plurality of unique identifiers; and means for selecting one of said at least two different mappings between the plurality of non-overlapping intervals and the plurality of unique identifiers.
Claim 35
Dependent Claim
38 words
The apparatus of claim 28 , said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes means for determining a trie representation of the plurality of non-overlapping intervals.
Claim 36
Dependent Claim
55 words
The apparatus of claim 28 , wherein said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes: means for determining at least two different trie representations of the plurality of non-overlapping intervals; and means for selecting one of said at least two different trie representations.
Claim 37
Dependent Claim
47 words
The apparatus of claim 33 , wherein said means for selecting one of said at least two different trie representations includes means for evaluating each of said at least two different trie representations for prefixes that would match two or more of the plurality of non-overlapping intervals.
Claim 38
Dependent Claim
30 words
The apparatus of claim 28 , further comprising means for programming the associative memory with an entry that matches at least two unique identifiers of said plurality of unique identifiers.
Claim 39
Dependent Claim
12 words
The apparatus of claim 35 , wherein the entry includes a prefix.
Claim 40
Dependent Claim
17 words
The apparatus of claim 28 , wherein the associative memory includes a binary or ternary content-addressable memory.
Claim 41
Dependent Claim
19 words
The apparatus of claim 28 , wherein the value includes a port number, an address, or a service characteristic.
Claim 42
Dependent Claim
23 words
The apparatus of claim 38 , further comprising means for receiving a packet including the port number, the address, or the service characteristic.
Claim 43
Dependent Claim
47 words
The apparatus of claim 28 , wherein said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes means for performing a tree analysis on at least two different sets or mappings of the plurality of unique identifiers.
Claim 44
Dependent Claim
37 words
The apparatus of claim 40 , wherein said means for tree analysis includes means for analyzing a resultant set of trie representations of said at least two different sets or mappings of the plurality of unique identifiers.
Claim 45
Dependent Claim
48 words
The apparatus of claim 28 , wherein said means for performing a lookup operation on an associative memory using the particular unique identifier to generate a result includes means for performing a lookup operation in the associative memory based on a lookup word including the particular unique identifier.
References Cited (Backward Citations)
US5088032A
Cited
US5781772A
Cited
US5481540A
Cited
US5319763A
Cited
US5898689A
Cited
US6000008A
Cited
US5515370A
Cited
US5848416A
Cited
US5528701A
Cited
US5721899A
Cited
US5651099A
Cited
US6091725A
Cited
US5809501A
Cited
US5884297A
Cited
US5740171A
Cited
US5829004A
Cited
US6243667B1
Cited
US5842040A
Cited
US5930359A
Cited
US5956336A
Cited
US6115716A
Cited
US5920886A
Cited
US6181698B1
Cited
US6307855B1
Cited
US6097724A
Cited
US6295576B1
Cited
US6018524A
Cited
US6061368A
Cited
US6236658B1
Cited
US6298339B1
Cited
US6148364A
Cited
US6067574A
Cited
US6141738A
Cited
US6289414B1
Cited
US6237061B1
Cited
US6633953B2
Cited
US6532516B1
Cited
US6574701B2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-08-10 | 2008-02-09 | 2008-08-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-08-10 | 2012-02-09 | 2012-08-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-08-10 | 2016-02-09 | 2016-08-10 | $7700.00 | Window Closed / Lapsed |