US6687247B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Architecture for high speed class of service enabled linecard
Assignee: Cisco Technology Inc
•
Filing: 1999-10-27
•
Granted: 2004-02-03
•
Expires: 2019-10-27
Abstract
Abstract A linecard architecture for high speed routing of data in a communications device. This architecture provides low latency routing based on packet priority: packet routing and processing occurs at line rate (wire speed) for most operations. A packet data stream is input to the inbound receiver, which uses a small packet FIFO to rapidly accumulate packet bytes. Once the header portion of the packet is received, the header alone is used to perform a high speed routing lookup and packet header modification. The queue manager then uses the class of service information in the packet header to enqueue the packet according to the required priority. Enqueued packets are buffered in a large memory space holding multiple packets prior to transmission across the device's switch fabric to the outbound linecard. On arrival at the outbound linecard, the packet is enqueued in the outbound transmitter portion of the linecard architecture. Another large, multi-packet memory structure, as employed in the inbound queue manager, provides buffering prior to transmission onto the network.
Inventors
- 👤 Bruce Wilford
- 👤 Yie-Fong Dan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 17:31
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/302; H04L45/40; H04L45/50; H04L45/502; H04L45/58; H04L45/583; H04L47/00; H04L47/50
Claims Analysis
Total Claims: 50
Claim 1
Independent Claim
132 words
An apparatus for routing packets in a communications network device comprising: an inbound receiver comprising a first buffer that receives an inbound packet at a line rate, said inbound packet comprising a header and a tail; a lookup circuit connected to said inbound receiver that compares said header to a data structure and determines routing information; a first packet modifier circuit that modifies said header according to at least said routing information to form a modified packet; an inbound queue manager connected to said first packet modifier circuit that buffers said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer, wherein said inbound receiver, said lookup circuit, and said first packet modifier circuit each operate substantially at said line rate in said linecard.
Claim 2
Independent Claim
132 words
An apparatus for routing packets in a communications network device comprising: an inbound receiver comprising a first buffer that receives an inbound packet at a line rate, said inbound packet comprising a header and a tail; a lookup circuit connected to said inbound receiver that compares said header to a data structure and determines routing information; a first packet modifier circuit that modifies said header according to at least said routing information to form a modified packet; an inbound queue manager connected to said first packet modifier circuit that buffers said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer, wherein said inbound receiver, said lookup circuit, and said first packet modifier circuit each operate substantially at said line rate in said linecard.
Claim 3
Dependent Claim
95 words
The apparatus of claim 1 further comprising: an outbound receiver connected to and concurrently receiving at least one outbound packet into a third buffer; a second packet modifier circuit that modifies said outbound packet according to information contained in said outbound packet; and an outbound queue manager connected to said second packet modifier circuit that buffers said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer wherein said outbound receiver and said second packet modifier circuit each operate substantially at said line rate in said linecard.
Claim 4
Dependent Claim
15 words
The apparatus as recited in claim 1 , wherein said first buffer comprises a FIFO.
Claim 5
Dependent Claim
19 words
The apparatus as recited in claim 1 , wherein said data structure further comprises an M-way branching tree structure.
Claim 6
Dependent Claim
20 words
The apparatus as recited in claim 1 , wherein said first packet modifier circuit further comprises an inbound rate limiter.
Claim 7
Dependent Claim
19 words
The apparatus as recited in claim 1 , wherein said inbound queue manager further comprises a buffer usage manager.
Claim 8
Dependent Claim
28 words
The apparatus as recited in claim 1 , wherein said inbound queue manager further comprises a circuit that dequeues said packet using a modified deficit round robin algorithm.
Claim 9
Independent Claim
99 words
An apparatus for routing packets in a communications network device comprising: an outbound receiver connected to and concurrently receiving at least one outbound packet into a first buffer; a first packet modifier circuit that modifies said outbound packet according to information contained in said outbound packet; and an outbound queue manager connected to said first packet modifier circuit that buffers said outbound packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer wherein said outbound receiver and said first packet modifier circuit each operate substantially at said line rate in said linecard.
Claim 10
Independent Claim
99 words
An apparatus for routing packets in a communications network device comprising: an outbound receiver connected to and concurrently receiving at least one outbound packet into a first buffer; a first packet modifier circuit that modifies said outbound packet according to information contained in said outbound packet; and an outbound queue manager connected to said first packet modifier circuit that buffers said outbound packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer wherein said outbound receiver and said first packet modifier circuit each operate substantially at said line rate in said linecard.
Claim 11
Dependent Claim
17 words
The apparatus as recited in claim 8 , wherein said first buffer comprises one or more FIFOs.
Claim 12
Dependent Claim
20 words
The apparatus as recited in claim 8 , wherein said first packet modifier circuit further comprises an outbound rate pacer.
Claim 13
Dependent Claim
20 words
The apparatus as recited in claim 8 , wherein said first packet modifier circuit further comprises a buffer usage manager.
Claim 14
Dependent Claim
20 words
The apparatus as recited in claim 8 , wherein said first packet modifier circuit further comprises an outbound rate limiter.
Claim 15
Dependent Claim
28 words
The apparatus as recited in claim 8 , wherein said outbound queue manager further comprises a circuit that dequeues said packet using a modified deficit round robin algorithm.
Claim 16
Independent Claim
101 words
A method of routing packets in a communications network device, comprising the steps of: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) through d) are performed substantially at said line rate in said linecard.
Claim 17
Independent Claim
101 words
A method of routing packets in a communications network device, comprising the steps of: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) through d) are performed substantially at said line rate in said linecard.
Claim 18
Dependent Claim
73 words
The method of claim 14 further comprising the steps of: f) concurrently receiving at least one outbound packet into a third buffer; g) modifying said outbound packet according to information contained in said outbound packet; and h) buffering said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer; wherein said steps f) and g) are performed substantially at said line rate in said linecard.
Claim 19
Dependent Claim
16 words
The method of claim 14 wherein said data structure further comprises an M-way branching tree structure.
Claim 20
Dependent Claim
17 words
The method of claim 14 wherein the step of modifying said header further comprises inbound rate limiting.
Claim 21
Dependent Claim
18 words
The method of claim 14 wherein the step of buffering said modified packet further comprises managing buffer usage.
Claim 22
Dependent Claim
25 words
The method of claim 14 wherein the step of buffering said modified packet further comprises dequeuing said packet using a modified deficit round robin algorithm.
Claim 23
Independent Claim
77 words
A method of routing packets in a communications network device, comprising the steps of: a) concurrently receiving at least one outbound packet into a first buffer; b) modifying said outbound packet according to information contained in said outbound packet; and c) buffering said outbound packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) and b) are performed substantially at said line rate in said linecard.
Claim 24
Independent Claim
77 words
A method of routing packets in a communications network device, comprising the steps of: a) concurrently receiving at least one outbound packet into a first buffer; b) modifying said outbound packet according to information contained in said outbound packet; and c) buffering said outbound packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) and b) are performed substantially at said line rate in said linecard.
Claim 25
Dependent Claim
18 words
The method of claim 20 wherein the step of modifying said outbound packet further comprises outbound rate pacing.
Claim 26
Dependent Claim
18 words
The method of claim 20 wherein the step of modifying said outbound packet further comprises managing buffer usage.
Claim 27
Dependent Claim
18 words
The method of claim 20 wherein the step of modifying said outbound packet further comprises outbound rate limiting.
Claim 28
Dependent Claim
25 words
The method of claim 20 wherein the step of buffering said outbound packet further comprises dequeuing said packet using a modified deficit round robin algorithm.
Claim 29
Dependent Claim
100 words
A computer system for interfacing with a communications network, comprising computer instructions for: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) through d) are performed substantially at said line rate in said linecard.
Claim 30
Dependent Claim
100 words
A computer system for interfacing with a communications network, comprising computer instructions for: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) through d) are performed substantially at said line rate in said linecard.
Claim 31
Dependent Claim
17 words
The computer system of claim 25 wherein said data structure further comprises an M-way branching tree structure.
Claim 32
Dependent Claim
18 words
The computer system of claim 25 wherein the step of modifying said header further comprises inbound rate limiting.
Claim 33
Dependent Claim
19 words
The computer system of claim 25 wherein the step of buffering said modified packet further comprises managing buffer usage.
Claim 34
Dependent Claim
26 words
The computer system of claim 25 wherein the step of buffering said modified packet further comprises dequeuing said packet using a modified deficit round robin algorithm.
Claim 35
Dependent Claim
96 words
A computer readable storage medium, comprising computer instructions for: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) through d) are performed substantially at said line rate in said linecard.
Claim 36
Dependent Claim
96 words
A computer readable storage medium, comprising computer instructions for: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) through d) are performed substantially at said line rate in said linecard.
Claim 37
Dependent Claim
19 words
The computer readable storage medium of claim 30 wherein said data structure further comprises an M-way branching tree structure.
Claim 38
Dependent Claim
20 words
The computer readable storage medium of claim 30 wherein the step of modifying said header further comprises inbound rate limiting.
Claim 39
Dependent Claim
21 words
The computer readable storage medium of claim 30 wherein the step of buffering said modified packet further comprises managing buffer usage.
Claim 40
Dependent Claim
28 words
The computer readable storage medium of claim 30 wherein the step of buffering said modified packet further comprises dequeuing said packet using a modified deficit round robin algorithm.
Claim 41
Dependent Claim
96 words
A computer readable carrier wave, comprising computer instructions for: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) through d) are performed substantially at said line rate in said linecard.
Claim 42
Dependent Claim
96 words
A computer readable carrier wave, comprising computer instructions for: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; wherein said steps a) through d) are performed substantially at said line rate in said linecard.
Claim 43
Dependent Claim
19 words
The computer readable carrier wave of claim 35 wherein said data structure further comprises an M-way branching tree structure.
Claim 44
Dependent Claim
20 words
The computer readable carrier wave of claim 35 wherein the step of modifying said header further comprises inbound rate limiting.
Claim 45
Dependent Claim
21 words
The computer readable carrier wave of claim 35 wherein the step of buffering said modified packet further comprises managing buffer usage.
Claim 46
Dependent Claim
28 words
The computer readable carrier wave of claim 35 wherein the step of buffering said modified packet further comprises dequeuing said packet using a modified deficit round robin algorithm.
Claim 47
Independent Claim
208 words
An apparatus for routing packets in a communications network device comprising: an inbound receiver comprising a first buffer that receives an inbound packet at a line rate, said inbound packet comprising a header and a tail; a lookup circuit connected to said inbound receiver that compares said header to a data structure and determines routing information; a first packet modifier circuit that modifies said header according to at least said routing information to form a modified packet; an inbound queue manager connected to said first packet modifier circuit that buffers said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer, an outbound receiver connected to and concurrently receiving at least one outbound packet into a third buffer; a second packet modifier circuit that modifies said outbound packet according to information contained in said outbound packet; and an outbound queue manager connected to said second packet modifier circuit that buffers said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer, wherein said inbound receiver, said lookup circuit, said first packet modifier circuit, said outbound receiver, and said second packet modifier circuit each operate substantially at said line rate in said linecard.
Claim 48
Independent Claim
208 words
An apparatus for routing packets in a communications network device comprising: an inbound receiver comprising a first buffer that receives an inbound packet at a line rate, said inbound packet comprising a header and a tail; a lookup circuit connected to said inbound receiver that compares said header to a data structure and determines routing information; a first packet modifier circuit that modifies said header according to at least said routing information to form a modified packet; an inbound queue manager connected to said first packet modifier circuit that buffers said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer, an outbound receiver connected to and concurrently receiving at least one outbound packet into a third buffer; a second packet modifier circuit that modifies said outbound packet according to information contained in said outbound packet; and an outbound queue manager connected to said second packet modifier circuit that buffers said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer, wherein said inbound receiver, said lookup circuit, said first packet modifier circuit, said outbound receiver, and said second packet modifier circuit each operate substantially at said line rate in said linecard.
Claim 49
Independent Claim
148 words
A method of routing packets in a communications network device, said method comprising: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; f) concurrently receiving at least one outbound packet into a third buffer; g) modifying said outbound packet according to information contained in said outbound packet; and h) buffering said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer; wherein a) through d), f), and g) are performed substantially at said line rate in said linecard.
Claim 50
Independent Claim
148 words
A method of routing packets in a communications network device, said method comprising: a) receiving an inbound packet into a first buffer at a line rate, said inbound packet comprising a header and a tail; b) comparing said header to a data structure; c) determining routing information; d) modifying said header according to at least said routing information to form a modified packet; e) buffering said modified packet using a second buffer for transmission, said second buffer being substantially larger than said first buffer; f) concurrently receiving at least one outbound packet into a third buffer; g) modifying said outbound packet according to information contained in said outbound packet; and h) buffering said outbound packet using a fourth buffer for transmission, said fourth buffer being substantially larger than said third buffer; wherein a) through d), f), and g) are performed substantially at said line rate in said linecard.
References Cited (Backward Citations)
US5574910A
Cited
US5802287A
Cited
US5781532A
Cited
US5509006A
Cited
US5852655A
Cited
US5872783A
Cited
US6157641A
Cited
US6449271B1
Cited
US6259699B1
Cited
US6463067B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-02-02 | 2007-08-04 | 2008-02-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-02-02 | 2011-08-04 | 2012-02-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-02-02 | 2015-08-04 | 2016-02-03 | $7700.00 | Window Closed / Lapsed |