US6038217A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Rate shaping in per-flow output queued routing mechanisms for available bit rate (ABR) service in networks having segmented ABR control loops
Assignee: Xerox Corp
•
Filing: 1997-06-03
•
Granted: 2000-03-14
•
Expires: 2017-06-03
Abstract
Abstract This invention provides rate shaping in per-flow output queued routing mechanisms for available bit rate (ABR) service in networks having segmented ABR control loops.
Inventors
- 👤 J. Bryan Lyles
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 19:55
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5635
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
273 words
A method for shaping each of a plurality of time multiplexed serial flow of packets to corresponding available bit rate network traffic contracts in a network having at least one segmented control loop each of which is configured to provide segment-by-segment congestion control for the network where each of the traffic contracts defines a minimum packet emission rate and a first peak packet emission rate, the method comprising the steps of: analyzing congestion control activity within each of a plurality of control segments comprising each segmented control loop for computing an available bandwidth estimate for each control segment; computing an allowed packet rate for each control segment using the bandwidth estimate; refining the first peak packet emission rate to create a second peak packet emission rate for each flow of packets and setting the second peak packet emission rate within an upper bound and a lower bound, the upper bound being substantially equal to the lesser of the first peak packet emission rate and the allowed Packet rate and the lower bound being substantially equal to the minimum packet emission rate: and controlling the rates at which packets of the given flow are emitted into the corresponding control segment by selectively enqueuing the packets (i) on a first non-work conserving calendar queue when the rate at which the packets flowing into the control segment is non-compliant with the traffic contract for the given flow as modified by the second peak packet emission rate and (ii) on a work conserving calendar queue when the rate at which the packets flowing into the control segment is compliant with the traffic contract for the given flow.
Claim 2
Independent Claim
273 words
A method for shaping each of a plurality of time multiplexed serial flow of packets to corresponding available bit rate network traffic contracts in a network having at least one segmented control loop each of which is configured to provide segment-by-segment congestion control for the network where each of the traffic contracts defines a minimum packet emission rate and a first peak packet emission rate, the method comprising the steps of: analyzing congestion control activity within each of a plurality of control segments comprising each segmented control loop for computing an available bandwidth estimate for each control segment; computing an allowed packet rate for each control segment using the bandwidth estimate; refining the first peak packet emission rate to create a second peak packet emission rate for each flow of packets and setting the second peak packet emission rate within an upper bound and a lower bound, the upper bound being substantially equal to the lesser of the first peak packet emission rate and the allowed Packet rate and the lower bound being substantially equal to the minimum packet emission rate: and controlling the rates at which packets of the given flow are emitted into the corresponding control segment by selectively enqueuing the packets (i) on a first non-work conserving calendar queue when the rate at which the packets flowing into the control segment is non-compliant with the traffic contract for the given flow as modified by the second peak packet emission rate and (ii) on a work conserving calendar queue when the rate at which the packets flowing into the control segment is compliant with the traffic contract for the given flow.
Claim 3
Dependent Claim
135 words
The method of claim 1, further comprising the steps of: controlling the rates at which packets of the given flow are emitted into the corresponding control segment by selectively enqueuing the packets (i) on a second non-work conserving calendar queue at a rate substantially equal to the minimum packet emission rate when the rate at which the packets flowing into the control segment is compliant with the minimum packet emission rate, and (ii) on the first non-work conserving calendar queue at a rate substantially equal to the second peak packet emission rate when the rate at which the packets flowing into the control segment is non-compliant with the second peak packet emission rate, wherein the first non-work conserving calendar queue has a higher priority than the work conserving calendar queue for resolving scheduling conflicts therebetween.
Claim 4
Dependent Claim
78 words
The method of claim 2, wherein: packets of the given flow also are enqueued on the work conserving calendar queue when the rate at which the packets flowing into the control segment is non-compliant with the minimum packet emission rate, and packets enqueued on both the second non-work conserving calendar queue and the work conserving calendar queue are delinked from one queue when dequeued from the other queue, thereby resolving a race condition established by such dual enqueuing.
Claim 5
Independent Claim
23 words
The method of claims 2 or 3, wherein the first and second non-work conserving calendar queues are linked, real time indexed data structures.
Claim 6
Dependent Claim
53 words
The method of claim 4, wherein the second non-work conserving calendar queue and the work conserving calendar queue are dynamically reallocated segments of one of the data structures, where the reallocation of such data structure segments is controlled by a pointer which cyclically traverses the data structure as a function of real time.
Claim 7
Dependent Claim
18 words
The method of claim 5, wherein packets of the given flow each have a uniform, fixed bit length.
Claim 8
Dependent Claim
39 words
The method of claim 6, wherein packets of the given flow are dequeued from said work conserving calendar queue in accordance with a strategy which provides approximate round robin service for packets enqueued on the work conserving calendar queue.
Claim 9
Dependent Claim
21 words
The method of claim 7, wherein packets of the given flow are fixed byte length cells for asynchronous transfer mode communications.
References Cited (Backward Citations)
EP0625101A1
Cited
US5278828A
Cited
US5677906A
Cited
EP0710046A2
Cited
US5629928A
Cited
US5675576A
Cited
US5732078A
Cited
US5754530A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-14 | 2003-09-13 | 2004-03-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-14 | 2007-09-13 | 2008-03-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-14 | 2011-09-13 | 2012-03-14 | $7700.00 | Window Closed / Lapsed |