US5831971A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for leaky bucket traffic shaping using fair queueing collision arbitration
Assignee: Nokia of America Corp
•
Filing: 1996-08-22
•
Granted: 1998-11-03
•
Expires: 2016-08-22
Abstract
Abstract A method shapes traffic using leaky bucket shaping and fair queueing techniques to shape conforming and nonconforming incoming traffic into a compliant output stream on an outgoing link connected to a node. An admitted or arriving cell is assigned to one queue in a set of queues. When a cell reaches the head of its assigned queue, a virtual finishing time is assigned to the cell, even if the cell has not reached its conformance time. A server then selects for transmission on the outgoing link, the head-of-line cell form among the queues with the smallest virtual finishing time. If the server selects a nonconforming cell for transmission, the selected nonconforming cell is rescheduled for transmission. If the selected cell is conforming, it is transmitted on the outgoing link.
Inventors
- 👤 Flavio Giovanni Bonomi
- 👤 Albert Gordon Greenberg
- 👤 Jennifer Lynn Rexford
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 08:51
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/5636; H04L2012/5637; H04L2012/5678; H04L2012/568; H04L2012/5681
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
180 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, wherein an incoming cell received from a connection in the set of connections has an associated conformance time, wherein an incoming cell received from a connection is assigned to a queue in a set of queues, and wherein each head-of-line cell in each queue in the set of queues has a virtual finishing time, the method comprising the steps of: selecting the cell having the smallest assigned virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming based on its associated conformance time, and otherwise, rescheduling the selected cell for transmission, wherein the step of transmitting the selected cell further comprises the step of: assigning a virtual finishing time to the new head-of-line cell in the queue assigned to the transmitted selected cell if the queue assigned to the transmitted selected cell is not empty.
Claim 2
Independent Claim
180 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, wherein an incoming cell received from a connection in the set of connections has an associated conformance time, wherein an incoming cell received from a connection is assigned to a queue in a set of queues, and wherein each head-of-line cell in each queue in the set of queues has a virtual finishing time, the method comprising the steps of: selecting the cell having the smallest assigned virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming based on its associated conformance time, and otherwise, rescheduling the selected cell for transmission, wherein the step of transmitting the selected cell further comprises the step of: assigning a virtual finishing time to the new head-of-line cell in the queue assigned to the transmitted selected cell if the queue assigned to the transmitted selected cell is not empty.
Claim 3
Independent Claim
155 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, wherein an incoming cell received from a connection in the set of connections has an associated conformance time, wherein an incoming cell received from a connection is assigned to a queue in a set of queues, and wherein each head-of-line cell in each queue in the set of queues has a virtual finishing time, the method comprising the steps of: selecting the cell having the smallest assigned virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming based on its associated conformance time, and otherwise, rescheduling the selected cell for transmission, wherein the step of rescheduling comprises the step of: assigning a new virtual finishing time to the selected cell.
Claim 4
Independent Claim
155 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, wherein an incoming cell received from a connection in the set of connections has an associated conformance time, wherein an incoming cell received from a connection is assigned to a queue in a set of queues, and wherein each head-of-line cell in each queue in the set of queues has a virtual finishing time, the method comprising the steps of: selecting the cell having the smallest assigned virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming based on its associated conformance time, and otherwise, rescheduling the selected cell for transmission, wherein the step of rescheduling comprises the step of: assigning a new virtual finishing time to the selected cell.
Claim 5
Dependent Claim
27 words
The method of claim 1 wherein the number of queues in the set of queues is equal to the number of connections in the set of connections.
Claim 6
Independent Claim
156 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, wherein an incoming cell received from a connection in the set of connections has an associated conformance time, wherein an incoming cell received from a connection is assigned to a queue in a set of queues, and wherein each head-of-line cell in each queue in the set of queues has a virtual finishing time, the method comprising the steps of: selecting the cell having the smallest assigned virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming based on its associated conformance time, and otherwise, rescheduling the selected cell for transmission, wherein the virtual finishing time assigned to each head-of-line cell in each queue is determined based on weighted fair queuing.
Claim 7
Independent Claim
156 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, wherein an incoming cell received from a connection in the set of connections has an associated conformance time, wherein an incoming cell received from a connection is assigned to a queue in a set of queues, and wherein each head-of-line cell in each queue in the set of queues has a virtual finishing time, the method comprising the steps of: selecting the cell having the smallest assigned virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming based on its associated conformance time, and otherwise, rescheduling the selected cell for transmission, wherein the virtual finishing time assigned to each head-of-line cell in each queue is determined based on weighted fair queuing.
Claim 8
Dependent Claim
25 words
The method of claim 1 wherein the virtual finishing time assigned to each head-of-line cell in each queue is determined based on self-clocked fair queuing.
Claim 9
Independent Claim
166 words
A method of regulating traffic in a network having at least one node which node is a part of a path for a set of connections, the method comprising the steps of: receiving an incoming cell from a connection in the set of connections, determining a conformance time for the incoming cell, determining if a particular queue in the set of queues is empty, and if so, assigning a virtual finishing time to the incoming cell, adding the incoming cell to the particular queue, selecting the cell having the smallest virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming, and otherwise, rescheduling the selected cell for transmission if the selected cell is not conforming, wherein the step of transmitting the selected cell further comprises the step of: assigning a virtual finishing time to the new head-of-line cell in the particular queue if the particular queue is not empty.
Claim 10
Independent Claim
166 words
A method of regulating traffic in a network having at least one node which node is a part of a path for a set of connections, the method comprising the steps of: receiving an incoming cell from a connection in the set of connections, determining a conformance time for the incoming cell, determining if a particular queue in the set of queues is empty, and if so, assigning a virtual finishing time to the incoming cell, adding the incoming cell to the particular queue, selecting the cell having the smallest virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming, and otherwise, rescheduling the selected cell for transmission if the selected cell is not conforming, wherein the step of transmitting the selected cell further comprises the step of: assigning a virtual finishing time to the new head-of-line cell in the particular queue if the particular queue is not empty.
Claim 11
Independent Claim
151 words
A method of regulating traffic in a network having at least one node which node is a part of a path for a set of connections, the method comprising the steps of: receiving an incoming cell from a connection in the set of connections, determining a conformance time for the incoming cell, determining if a particular queue in the set of queues is empty, and if so, assigning a virtual finishing time to the incoming cell, adding the incoming cell to the particular queue, selecting the cell having the smallest virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming, and otherwise, rescheduling the selected cell for transmission if the selected cell is not conforming, wherein the step of rescheduling comprises the step of: assigning a new virtual finishing time to the selected cell.
Claim 12
Independent Claim
151 words
A method of regulating traffic in a network having at least one node which node is a part of a path for a set of connections, the method comprising the steps of: receiving an incoming cell from a connection in the set of connections, determining a conformance time for the incoming cell, determining if a particular queue in the set of queues is empty, and if so, assigning a virtual finishing time to the incoming cell, adding the incoming cell to the particular queue, selecting the cell having the smallest virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell from the node if the selected cell is conforming, and otherwise, rescheduling the selected cell for transmission if the selected cell is not conforming, wherein the step of rescheduling comprises the step of: assigning a new virtual finishing time to the selected cell.
Claim 13
Dependent Claim
27 words
The method of claim 6 wherein the number of queues in the set of queues is equal to the number of connections in the set of connections.
Claim 14
Dependent Claim
22 words
The method of claim 6 wherein the virtual finishing time assigned to the incoming cell is determined based on weighted fair queuing.
Claim 15
Dependent Claim
22 words
The method of claim 6 wherein the virtual finishing time assigned to the incoming cell is determined based on self-clocked fair queuing.
Claim 16
Independent Claim
191 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, each connection in the set of connections having an associated queue, the method comprising the steps of: receiving an incoming cell from a particular connection in the set of connections, determining a conformance time for the incoming cell, determining if the queue associated with the particular connection is empty, and if the queue is empty, assigning a virtual finishing time to the incoming cell, adding the incoming cell to the queue associated with the particular connection, selecting the cell having the smallest virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell form the node if selected cell is conforming, and otherwise, rescheduling the selected cell for transmission if the selected cell is not conforming, wherein the step of transmitting the selected cell further comprises the step of: assigning a virtual finishing time to a new head of line cell in the queue associated with the transmitted selected cell if the queue is not empty.
Claim 17
Independent Claim
191 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, each connection in the set of connections having an associated queue, the method comprising the steps of: receiving an incoming cell from a particular connection in the set of connections, determining a conformance time for the incoming cell, determining if the queue associated with the particular connection is empty, and if the queue is empty, assigning a virtual finishing time to the incoming cell, adding the incoming cell to the queue associated with the particular connection, selecting the cell having the smallest virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell form the node if selected cell is conforming, and otherwise, rescheduling the selected cell for transmission if the selected cell is not conforming, wherein the step of transmitting the selected cell further comprises the step of: assigning a virtual finishing time to a new head of line cell in the queue associated with the transmitted selected cell if the queue is not empty.
Claim 18
Independent Claim
171 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, each connection in the set of connections having an associated queue, the method comprising the steps of: receiving an incoming cell from a particular connection in the set of connections, determining a conformance time for the incoming cell, determining if the queue associated with the particular connection is empty, and if the queue is empty, assigning a virtual finishing time to the incoming cell, adding the incoming cell to the queue associated with the particular connection, selecting the cell having the smallest virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell form the node if selected cell is conforming, and otherwise, rescheduling the selected cell for transmission if the selected cell is not conforming, wherein the step of rescheduling further comprises the step of: assigning a new virtual finishing time to the selected cell.
Claim 19
Independent Claim
171 words
A method of regulating traffic in a network, wherein the network comprises a node, wherein the node is a part of a path for a set of connections, each connection in the set of connections having an associated queue, the method comprising the steps of: receiving an incoming cell from a particular connection in the set of connections, determining a conformance time for the incoming cell, determining if the queue associated with the particular connection is empty, and if the queue is empty, assigning a virtual finishing time to the incoming cell, adding the incoming cell to the queue associated with the particular connection, selecting the cell having the smallest virtual finishing time from among all the head-of-line cells in the set of queues, transmitting the selected cell form the node if selected cell is conforming, and otherwise, rescheduling the selected cell for transmission if the selected cell is not conforming, wherein the step of rescheduling further comprises the step of: assigning a new virtual finishing time to the selected cell.
Claim 20
Dependent Claim
27 words
The method of claim 2 wherein the number of queues in the set of queues is equal to the number of connections in the set of connections.
Claim 21
Dependent Claim
25 words
The method of claim 2 wherein the virtual finishing time assigned to each head-of-line cell in each queue is determined based on self-clocked fair queuing.
Claim 22
Dependent Claim
27 words
The method of claim 4 wherein the number of queues in the set of queues is equal to the number of connections in the set of connections.
Claim 23
Dependent Claim
25 words
The method of claim 4 wherein the virtual finishing time assigned to each head-of-line cell in each queue is determined based on self-clocked fair queuing.
Claim 24
Dependent Claim
27 words
The method of claim 7 wherein the number of queues in the set of queues is equal to the number of connections in the set of connections.
Claim 25
Dependent Claim
22 words
The method of claim 7 wherein the virtual finishing time assigned to the incoming cell is determined based on weighted fair queuing.
Claim 26
Dependent Claim
22 words
The method of claim 7 wherein the virtual finishing time assigned to the incoming cell is determined based on self-clocked fair queuing.
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) | 2001-11-02 | 2002-05-04 | 2002-11-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-02 | 2006-05-04 | 2006-11-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-02 | 2010-05-04 | 2010-11-03 | $7700.00 | Window Closed / Lapsed |