US6181698B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Network routing table using content addressable memory
Assignee: Individual
•
Filing: 1997-07-09
•
Granted: 2001-01-30
•
Expires: 2017-07-09
Abstract
Abstract A routing table comprises routing table entries [230], a word line driver [92], prioritizer [100], and memory [106]. Each routing table entry [230] comprises content addressable memory (CAM) cells [220] and an entry masking circuit. The routing table looks up in parallel an entry matching an input network address, and outputs the search result in deterministic time. Only the bits specified by the masking circuit in each entry are compared when searching. If multiple entries match the input, the prioritizer [100] uses mask information from the masking circuits of the matching entries to select the best entry, e.g. the entry having the most matching bits.
Inventors
- 👤 Yoichi Hariguchi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 06:42
CPC Classifications
H; H04; H04L; H04L45/00; G; G11; G11C; G11C15/00; G11C15/04; H04L45/74; H04L45/745; H04L45/7453
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
127 words
A routing table circuit for determining from a destination address an associated table entry, the circuit comprising: a plurality of routing table entries for determining in parallel a set of routing table entry hit addresses from the destination address, a prioritizer for selecting a single routing entry address from the set of routing table entry hit addresses, and a memory for producing the associated table entry from the single routing entry address, wherein each entry in the routing table comprises: a collection of CAM cells for storing stored address bits; a masking circuit for masking a portion of the stored address bits in accordance with an address prefix associated with the stored address bits; and a mask output circuit for providing the address prefix to the prioritizer.
Claim 2
Dependent Claim
127 words
A routing table circuit for determining from a destination address an associated table entry, the circuit comprising: a plurality of routing table entries for determining in parallel a set of routing table entry hit addresses from the destination address, a prioritizer for selecting a single routing entry address from the set of routing table entry hit addresses, and a memory for producing the associated table entry from the single routing entry address, wherein each entry in the routing table comprises: a collection of CAM cells for storing stored address bits; a masking circuit for masking a portion of the stored address bits in accordance with an address prefix associated with the stored address bits; and a mask output circuit for providing the address prefix to the prioritizer.
Claim 3
Independent Claim
109 words
A method for routing a data packet having a packet destination address, the method comprising: determining from the packet destination address an associated table entry; and routing the packet in accordance with the associated table entry; wherein the step of determining the associated table entry from the packet destination address comprises: determining a set of table entry hit addresses by applying the packet destination address to a collection of CAM cells that store a stored address and store an address prefix of the stored address; selecting a single entry address from the set of table entry hit addresses, and producing the associated table entry from the single entry address.
Claim 4
Independent Claim
109 words
A method for routing a data packet having a packet destination address, the method comprising: determining from the packet destination address an associated table entry; and routing the packet in accordance with the associated table entry; wherein the step of determining the associated table entry from the packet destination address comprises: determining a set of table entry hit addresses by applying the packet destination address to a collection of CAM cells that store a stored address and store an address prefix of the stored address; selecting a single entry address from the set of table entry hit addresses, and producing the associated table entry from the single entry address.
Claim 5
Independent Claim
143 words
An apparatus for routing a data packet having a packet destination address, the apparatus comprising: a routing table circuit for determining from the packet destination address a next device identifier; and a switching fabric for routing the packet in accordance with the next device identifier; wherein the routing table circuit comprises: a plurality of routing table entries for determining in parallel a set of table entry hit addresses from the destination address, a prioritizer for selecting a single entry address from the set of table entry hit addresses, and a memory for producing the next device identifier from the single entry address, wherein each entry in the routing table comprises: a collection of CAM cells for storing stored address bits; and a masking circuit for masking a portion of the stored address bits in accordance with an address prefix for the destination address.
Claim 6
Independent Claim
143 words
An apparatus for routing a data packet having a packet destination address, the apparatus comprising: a routing table circuit for determining from the packet destination address a next device identifier; and a switching fabric for routing the packet in accordance with the next device identifier; wherein the routing table circuit comprises: a plurality of routing table entries for determining in parallel a set of table entry hit addresses from the destination address, a prioritizer for selecting a single entry address from the set of table entry hit addresses, and a memory for producing the next device identifier from the single entry address, wherein each entry in the routing table comprises: a collection of CAM cells for storing stored address bits; and a masking circuit for masking a portion of the stored address bits in accordance with an address prefix for the destination address.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-30 | 2004-07-31 | 2005-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-30 | 2008-07-31 | 2009-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-30 | 2012-07-31 | 2013-01-30 | $7700.00 | Window Closed / Lapsed |