METHOD AND APPARATUS FOR SCHEDULING TRAFFIC TO MEET QUALITY OF SERVICE REQUIREMENTS IN A COMMUNICATION NETWORK

• US 20030185224A1
• Filed: 09/10/1999
• Published: 10/02/2003
• Est. Priority Date: 09/10/1999
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: RAMANAN, KAVITA, STOYLAR, ALEKSANDR
• Granted Patent: US 7,054,267 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management

Abstract

Packets are scheduled for transmission over a communication link in a network, using a Largest Weighted Delay First (LWDF) scheduling policy. A delay measure W_i, i=1, 2, . . . N, is computed for each of N packets, each associated with a corresponding one of N data flows and located in a head position in a corresponding one of N data flow queues. The computed delay measures are then weighted using a set of positive weights α₁, α₂, . . . , α_N. The packet having the largest weighted delay W_i/α_i associated therewith is then selected for transmission. In an embodiment configured to meet a quality of service (QoS) requirement specified in terms of a deadline T_i and an allowed deadline violation probability δ_i, e.g., a requirement specified by P(W_i>T_i)≦δ_i, the weights α_i in the set of positive weights α₁, α₂, . . . , α_N may be given by α_i=−T_i/log δ_i. The invention can also be used to meet other types of QoS requirements, including, e.g., requirements based on packet loss probabilities. For example, the QoS guarantee may be defined for a delay measure in the form of queue length Q_i, i=1, 2, . . . N, and an allowed queue length violation probability δ_i. In such an embodiment, the QoS requirement is specified by P(Q_i>H_i)≦δ_i, and the weights α_i in the set of positive weights α₁, α₂, . . . , α_N may be given by α_i=−H_i/log δ_i, where H_i represents an upper bound on the length of the queue.

Claims

1. A processor-implemented method of scheduling data packets for transmission over a communication link in a network, the method comprising the steps of:

computing delay measures for a plurality of packets including at least one packet from each of a plurality of queues; and

selecting a given one of the plurality of packets for transmission based at least in part on a comparison of weighted versions of the computed delay measures, such that the selected packet is the packet having the largest weighted delay associated therewith.

2. The method of claim 1 wherein the step of computing delay measures for a plurality of packets includes computing the delay measure for a given one of the packets as a difference between a current time and an arrival time of the given packet in a node of the communication network.

3. The method of claim 1 wherein the plurality of packets comprise N packets, each associated with a corresponding one of N data flows and located in a head position in a corresponding one of N queues.

4. The method of claim 3 wherein the selecting step includes selecting a packet from a head position of a jth one of the N queues, such that a function of a given weight α

_j and a given delay measure W_j is maximal among all such functions for j=1, 2, . . . N, where α

_j is one of a set of positive weights α

₁, α

₂, . . . , α

_N.

5. The method of claim 4 wherein the function of the given weight and the given delay measure is W_j/α

_j.

6. The method of claim 4 wherein the computing and selecting steps are configured to meet a quality of service requirement specified in terms of a deadline T_i and an allowed deadline violation probability δ

_i.

7. The method of claim 6 wherein each of the weights α

_i in the set of positive weights α

₁, α

₂, . . . , α

_N is given by α

_i=−

T_i/log δ

_i.

8. The method of claim 6 wherein the quality of service requirement is specified by:

P(W_i>

T_i)≦

δ

_i for i=1, . . . , N.

9. The method of claim 3 wherein the selecting step includes selecting a packet from a head position of a jth one of the N queues, such that a function of a given weight α

_j and a given delay measure Q_j is maximal among all such functions for j=1, 2, . . . N, where α

_j is one of a set of positive weights α

₁, α

₂, . . . , α

_N, and Q_j is a queue length of the jth queue.

10. The method of claim 9 wherein the function of the given weight and the given delay measure is Q_j/α

_j.

11. The method of claim 10 wherein the computing and selecting steps are configured to meet a quality of service requirement specified in terms of a maximum queue length H_i, and an allowed queue length violation probability δ

_i.

12. The method of claim 11 wherein each of the weights α

_i in the set of positive weights α

₁, α

₂, . . . , α

_N is given by α

_i=−

H_i/log δ

_i.

13. The method of claim 11 wherein the quality of service requirement is specified by:

P(Q_i>

H_i)≦

δ

_i for i=1, . . . , N.

14. An apparatus for use in scheduling data packets for transmission over a communication link in a network, the apparatus comprising:

a set of queues, each of at least a subset of the queues including at least one packet; and

a link scheduler having inputs coupled to corresponding outputs of the queues, the link scheduler being operative to compute delay measures for a plurality of packets including at least one packet from each of the at least a subset of the queues, and to select a given one of the plurality of packets for transmission based at least in part on a comparison of weighted versions of the computed delay measures, such that the selected packet is the packet having the largest weighted delay associated therewith.

16. The apparatus of claim 14 wherein the plurality of packets comprise N packets, each associated with a corresponding one of N data flows and located in a head position in a corresponding one of N queues.

17. The apparatus of claim 16 wherein the link scheduler is further operative to select a packet from a head position of a jth one of the N queues, such that a function of a given weight α

_j and a given delay measure W_j is maximal among all such functions for j=1, 2, . . . , N, where α

_j is one of a set of positive weights α

₁, α

₂, . . . , α

_N.

18. The apparatus of claim 17 wherein the function of the given weight and the given delay measure is W_j/α

_j.

19. The apparatus of claim 17 wherein the link scheduler is configured to meet a quality of service requirement specified in terms of a deadline T_i and an allowed deadline violation probability δ

_i.

20. The apparatus of claim 19 wherein each of the weights α

_i in the set of positive weights α

₁, α

₂, . . . , α

_N is given by α

_i=−

T_i/log δ

_i.

21. The apparatus of claim 19 wherein the quality of service requirement is specified by:

P(W_i>

T_i)≦

δ

_i for i=1, . . . , N.

22. The apparatus of claim 16 wherein the link scheduler is further operative to select a packet from a head position of a jth one of the N queues, such that a function of a given weight try α

_j and a given delay measure Q_j is maximal among all such functions for j=1, 2, . . . N, where α

_j is one of a set of positive weights α

₁, α

₂, . . . , α

_N, and Q_j is a queue length of the jth queue.

23. The apparatus of claim 22 wherein the function of the given weight and the given delay measure is Q_j/α

_j.

24. The apparatus of claim 22 wherein the link scheduler is configured to meet a quality of service requirement specified in terms of a maximum queue length H_i and an allowed queue length violation probability δ

_i.

25. The apparatus of claim 19 wherein each of the weights α

_i in the set of positive weights α

₁, α

₂, . . . , α

_N is given by a α

_i=−

H_i/log δ

_i.

26. The apparatus of claim 19 wherein the quality of service requirement is specified by:

P(Q_i>

H_i)≦

δ

_i for i=1, . . . , N.

15. The apparatus of 14 wherein the link scheduler is further operative to compute delay measures for a plurality of packets includes computing the delay measure for a given one of the packets as a difference between a current time and an arrival time of the given packet in a node of the communication network.

27. An apparatus for use in scheduling data packets for transmission over a communication link in a network, the apparatus comprising:

a memory implementing a set of queues, each of at least a subset of the queues including at least one packet; and

a processor coupled to the memory and operative to compute delay measures for a plurality of packets including at least one packet from each of the at least a subset of the queues, and to select a given one of the plurality of packets for transmission based at least in part on a comparison of weighted versions of the computed delay measures, such that the selected packet is the packet having the largest weighted delay associated therewith.

28. A machine-readable medium storing one or more software programs for scheduling data packets for transmission over a communication link in a network, wherein the one or more programs when executed by a processor include:

a step for computing delay measures for a plurality of packets including at least one packet from each of a plurality of queues; and

a step for selecting a given one of the plurality of packets for transmission based at least in part on a comparison of weighted versions of the computed delay measures, such that the selected packet is the packet having the largest weighted delay associated therewith.