Method for leaky bucket traffic shaping using fair queueing collision arbitration

• US 5,831,971 A
• Filed: 08/22/1996
• Issued: 11/03/1998
• Est. Priority Date: 08/22/1996
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Bonomi, Flavio Giovanni, Rexford, Jennifer Lynn, Greenberg, Albert Gordon
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US08/701,341
• Time in Patent Office: 803 Days
• Field of Search: 370/229, 370/230, 370/232, 370/235, 370/412, 370/418, 370/395, 370/231, 370/413, 370/415, 370/428, 370/429
• US Class Current: 370/230
• CPC Class Codes: H04L 2012/5637 Leaky Buckets
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

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.

Claims

1. 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.

3. 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.

5. 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.

2. 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.

13. 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.

14. 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.

4. 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.

15. 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.

16. 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.

6. 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.

8. 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.

9. The method of claim 6 wherein the virtual finishing time assigned to the incoming cell is determined based on weighted fair queuing.

10. The method of claim 6 wherein the virtual finishing time assigned to the incoming cell is determined based on self-clocked fair queuing.

7. 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.

17. 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.

18. The method of claim 7 wherein the virtual finishing time assigned to the incoming cell is determined based on weighted fair queuing.

19. The method of claim 7 wherein the virtual finishing time assigned to the incoming cell is determined based on self-clocked fair queuing.

11. 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.

12. 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.