US5864540A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for integrated traffic shaping in a packet-switched network
Assignee: Riverstone Networks Inc
•
Filing: 1997-04-04
•
Granted: 1999-01-26
•
Expires: 2017-04-04
Abstract
Abstract A scalable integrated traffic shaper for a use in a packet-switched network that regulates multiple connections and prevents lost data by integrating link scheduling and traffic shaping to fairly arbitrate between incoming connections.
Inventors
- 👤 Flavio Giovanni Bonomi
- 👤 Albert Gordon Greenberg
- 👤 Jennifer Lynn Rexford
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 14:07
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5678; H04L2012/5679; H04L2012/568
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
127 words
A method of shaping traffic in a packet switched network having at least one incoming connection and at least one outgoing connection, comprising the steps of: enqueing packets received from an incoming connection on a queue associated with said incoming connection; determining the conformance time of each packet received from an incoming connection; transferring a packet at the head of said queue associated with said incoming connection to an output queue or to one of a plurality of sorting bins if said packet's conformance time is later than the current time; transferring a packet from one of said plurality of sorting bins to said output queue when said current time precedes or is simultaneous with said packet's conformance time; and transmitting a packet from said output queue.
Claim 2
Independent Claim
127 words
A method of shaping traffic in a packet switched network having at least one incoming connection and at least one outgoing connection, comprising the steps of: enqueing packets received from an incoming connection on a queue associated with said incoming connection; determining the conformance time of each packet received from an incoming connection; transferring a packet at the head of said queue associated with said incoming connection to an output queue or to one of a plurality of sorting bins if said packet's conformance time is later than the current time; transferring a packet from one of said plurality of sorting bins to said output queue when said current time precedes or is simultaneous with said packet's conformance time; and transmitting a packet from said output queue.
Claim 3
Dependent Claim
25 words
The method of shaping traffic in claim 1 wherein each said queue associated with said incoming connection is uniquely associated with a single incoming connection.
Claim 4
Dependent Claim
24 words
The method of shaping traffic in claim 1 wherein each said queue associated with said incoming connection is a first in first out queue.
Claim 5
Dependent Claim
87 words
The method of shaping traffic in claim 1 wherein a shaping rate and a burst tolerance is associated with each said incoming connection and said step of determining the conformance time of a packet received from an incoming connection comprises the steps of: estimating said packet's arrival time; evaluating the chronological relationship between said packet's estimated arrival time and said packet's actual arrival time; and determining said packet's conformance time based on said evaluation of said packet's estimated arrival time relative to said packet's actual arrival time.
Claim 6
Dependent Claim
97 words
The method of shaping traffic in claim 4 wherein said step of determining said packet's conformance time based on said evaluation of said packet's estimated arrival time relative to said packet's actual arrival time comprises the steps of: determining said packet's conformance time is equal to said actual arrival time when said estimated arrival time precedes or is simultaneous with said actual arrival time; and determining said packet's conformance time precedes said estimated arrival time by an interval corresponding to said burst tolerance and said shaping rate when said actual arrival time precedes said estimated arrival time.
Claim 7
Dependent Claim
63 words
The method of shaping traffic in claim 4 wherein a shaping rate and a burst tolerance is associated with each said incoming connection and said step of estimating said packet's arrival comprises estimating said arrival time as a function of the shaping rate and burst tolerance of said incoming connection and the arrival time of the last packet received from said incoming connection.
Claim 8
Dependent Claim
54 words
The method of shaping traffic in claim 1 wherein said step of transferring a packet at the head of said queue associated with said incoming connection to an output queue or to one of said plurality of sorting bins occurs when a packet associated with said incoming connection is transmitted from said output queue.
Claim 9
Dependent Claim
40 words
The method of shaping traffic in claim 1 further comprising the step of transferring a plurality of packets from said queue associated with said incoming connection to at least one of said plurality of sorting bins or said output queue.
Claim 10
Dependent Claim
73 words
The method of shaping traffic in claim 8 wherein a shaping rate is associated with each said incoming connection and the maximum number of packets associated with one of said incoming connections in said plurality of said sorting bins and said output queue is a function of the shaping rate of the incoming connection having the slowest shaping rate and the shaping rate of said one of incoming connections associated with said packets.
Claim 11
Dependent Claim
18 words
The method of shaping traffic in claim 1 wherein each of said sorting bins is a linked list.
Claim 12
Dependent Claim
19 words
The method of shaping traffic in claim 1 wherein said output queue is a first in first out queue.
Claim 13
Dependent Claim
17 words
The method of shaping traffic in claim 1 wherein each of said packets has a fixed size.
Claim 14
Dependent Claim
27 words
The method of shaping traffic in claim 1 wherein each said sorting bin corresponds to a single delay period between said conformance time and said current time.
Claim 15
Dependent Claim
28 words
The method of shaping traffic in claim 1 wherein each said sorting bin corresponds to a range of delay periods between said conformance time and said current times.
Claim 16
Independent Claim
161 words
A method of shaping traffic in a packet switched network having a plurality of incoming connections and at least one outgoing connection, comprising the steps of: enqueuing packets received from an incoming connection on a queue associated with said incoming connection; determining the conformance time of each packet received from an incoming connection; transferring a packet at the head of said queue associated with said incoming connection to one of a plurality of sorting units, each of said sorting units comprising at least one sorting bin and an output queue, wherein said packet is transferred to one of said sorting bins if said packet's conformance time is later than the current time; transferring a packet from one of said sorting bins to one of said output queues when said current time precedes or is simultaneous with said packet's conformance time; transferring a packet from one of said output queues to a group arbiter; and transmitting a packet from said group arbiter.
Claim 17
Independent Claim
161 words
A method of shaping traffic in a packet switched network having a plurality of incoming connections and at least one outgoing connection, comprising the steps of: enqueuing packets received from an incoming connection on a queue associated with said incoming connection; determining the conformance time of each packet received from an incoming connection; transferring a packet at the head of said queue associated with said incoming connection to one of a plurality of sorting units, each of said sorting units comprising at least one sorting bin and an output queue, wherein said packet is transferred to one of said sorting bins if said packet's conformance time is later than the current time; transferring a packet from one of said sorting bins to one of said output queues when said current time precedes or is simultaneous with said packet's conformance time; transferring a packet from one of said output queues to a group arbiter; and transmitting a packet from said group arbiter.
Claim 18
Dependent Claim
36 words
The method of shaping traffic in claim 15 wherein said step of transferring a packet from one of said output queues to said group arbiter occurs at a frequency determined by a fair, rate-based scheduling algorithm.
Claim 19
Dependent Claim
43 words
The method of shaping traffic in claim 15 wherein said step of transferring a packet at the head of said queue associated with said incoming connection to one of a plurality of sorting units occurs at a frequency determined by a round-robin arbitration.
Claim 20
Dependent Claim
44 words
The method of shaping traffic in claim 15 wherein said step of transferring a packet at the head of said queue associated with said incoming connection to one of a plurality of sorting units occurs at a frequency determined by a weighted round-robin arbitration.
References Cited (Backward Citations)
US5260935A
Cited
US5268900A
Cited
US5499238A
Cited
US5629937A
Cited
US5515363A
Cited
US5602830A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-25 | 2002-07-27 | 2003-01-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-25 | 2006-07-27 | 2007-01-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-25 | 2010-07-27 | 2011-01-26 | $7700.00 | Window Closed / Lapsed |