Scheduler and method for scheduling transmissions in a communication network

• US 7,349,338 B2
• Filed: 04/15/2003
• Issued: 03/25/2008
• Est. Priority Date: 04/15/2003
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Parulekar, Minothi, Das, Arnab, Balachandran, Krishna, Budka, Kenneth C., Medapalli, Kameswara Rao
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Hyun; Soon D.
• Application Number:
  US10/413,382
• Publication Number:
  US 20040208183A1
• Time in Patent Office: 1,806 Days
• Field of Search: None
• US Class Current: 370/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/626 channel conditions
• CPC Class Codes: H04W 28/0205 at the air interface dynamic wireless traffic scheduling H04W72/12
• CPC Class Codes: H04W 28/0284 detecting congestion or overload during communication monitoring arrangements H04L43/00
• CPC Class Codes: H04W 28/24 Negotiating SLA [Service Level Agreement]; Negotiating QoS [Quality of Service]
• CPC Class Codes: H04W 72/54 based on quality criteria
• CPC Class Codes: H04W 72/543 based on requested quality, e.g. QoS
• CPC Class Codes: H04W 72/566 of the information or information source or recipient
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A scheduler and a method for scheduling transmissions to a plurality of users in a communication network assigns a higher target minimum throughput for receiving a next transmission to a user based on a quality of service (QoS) class of the user. A token count that tracks the user'"'"'s achieved performance relative to a target minimum throughput Is determined for each user in given timeslot, and a weight is determined for each user based on one or more of the token count and a current rate requested by the user. A user having the highest weight as determined by a weight function is scheduled to be served the next transmission. User priority for scheduling may be downgraded if an average data rate requested by the user is less than the target minimum throughput.

Claims

1. A method for scheduling transmissions to a plurality of users in a communication network, comprising:

assigning a first target minimum throughput for receiving a next transmission to at least one of the plurality of users based on a quality of service (QoS) class of the user, the first target minimum throughput being greater than a second target minimum throughput assigned to another of the plurality of users, and the quality of service class of the user being-specified by the network;

prioritizing the plurality of users for transmission in the communication network;

assigning, to the user, a data rate for receiving the next transmission based on the prioritizing step, the assigned data rate being between the first target minimum throughput and a target maximum throughput, the target maximum throughput being associated with the quality of service class of the first user; and

downgrading a priority for scheduling the user if the average data rate reported by the user is less than the target minimum throughput.

2. The method of claim 1, wherein a QoS class of a user is represented by how much a user pays for a particular service offered by the communication network.

3. The method of claim 2, wherein said assigning further includes allocating residual airlink bandwidth to users that subscribe to a higher class of service.

4. The method of claim 3, wherein said allocating is performed based on the average user throughput of the user and the revenue generated for the network by carrying traffic for the user.

5. The method of claim 4, wherein said prioritizing further includes scheduling the users in order of the user having the highest total expected revenue per average user throughput in a given time instant to receive said residual airlink bandwidth, until there is no more data to transmit to the user.

6. The method of claim 1, wherein said assigning further includes:

determining, for each user in at least one timeslot, a token count that tracks the user'"'"'s achieved performance relative to a target minimum throughput,

determining a weight for each user based on one or more of the token count and a current rate requested by the user; and

selecting a user with a highest weight as the user to be served the next transmission.

7. The method of claim 6, further comprising:

updating, at least once, the token count of one or more of the users.

8. The method of claim 7, wherein said updating a token count further includes incrementing or decrementing the token count based on a target minimum throughput (Rⁱ_min) guaranteed by the network to an i^th user.

9. The method of claim 8, wherein a current token count value for the i^th user in an n^th timeslot, (T_i(n)), is incremented or decremented in accordance with:

T_i(n)=T_i(n−

1)+X_i(n)−

b_i(n), with X_i(n)=<sup>α

imin</sup>/₆₀₀(bits/slot);

where X_i(n) is a token rate that represents a product of the target minimum throughput for user i and the timeslot duration, a is a tunable parameter that permits the token rate to be set at a value higher than the target minimum throughput for a given period, and b_i(n) represents the number of bits transmitted to the user i in timeslot n.

10. The method of claim 6, further comprising:

restricting token counts for each user to a given range.

11. The method of claim 6, wherein

said determining a weight function further includes determining, for an i^th user in an n^th timeslot, a weight function (w_i(n)) defined by:

w_i(n)=max{[DRC_i(n)]^1+δ

·

e<sup>α

Ti(n)</sup>, DRC_i(n)},

where DRC_i(n) denotes the rate requested by the i^th user in slot n, δ

represents a rate request exponent, α

denotes a tunable parameter and T_i(n) denotes the current token count value for the i^th user in slot n; and

said selecting further includes selecting the user having the maximum positive-valued weight function (w_i(n)) to be served the next transmission in the n^th timeslot.

12. The method of claim 1, further comprising periodically comparing the average data rate requested by a user to the user'"'"'s target minimum throughput.

13. The method of claim 12, further comprising:

determining, for an i^th user in an n^th timeslot, a token rate that is based on the i^th user'"'"'s achieved performance relative to a target minimum throughput; and

said downgrading further including temporarily setting the token rate so as to downgrade the i^th user'"'"'s priority for being scheduled to receive a next transmission, if said comparing indicates the average data rate requested by the i^th user is less than the i^th user'"'"'s target minimum throughput.

14. A scheduler scheduling a plurality of users in a communication network to receive a transmission in accordance with the method of claim 1.

15. A method for scheduling transmissions to a plurality of users in a communication network, comprising:

determining, for an i^th user in an n^th timelsot, a token count that tracks a user'"'"'s achieved performance relative to a target minimum throughput guaranteed by the network;

prioritizing the users based on one or more of the token count and a current rate requested by the user;

assigning a higher target minimum throughput for receiving a next transmission to the highest priority i^th user.

16. The method of claim 15, wherein the token count is a measure of the i^th user'"'"'s dissatisfaction level at being served data by the network.

17. The method of claim 15, wherein the highest priority i^th user is the user scheduled to receive the next transmission at said assigned higher target minimum throughput.

18. The method of claim 17, further comprising:

initializing a token count for a new user entering the network based on one of a specified interval spanning m timeslots arid the priority of the scheduled user currently receiving the next transmission.

19. The method of claim 18, said initializing further includes setting a token count so that the new user is served within said m slots, else scheduling the user with a priority that equals the currently served scheduled user.

20. The method of claim 17, wherein the scheduled user maintains a token pool of tokens, the method further comprising:

depleting the scheduled user'"'"'s token pool by a number of tokens corresponding to the bits transmitted to the scheduled user in the n^th slot.

21. The method of claim 20, wherein said depleting further includes updating, by an entire number of bits transmitted to the scheduled user at the start of the transmission, a rate at which the scheduled user'"'"'s token pool is decremented in the n^th slot.

22. The method of claim 20, wherein said depleting further includes updating, by an entire number of bits transmitted to the scheduled user at the end of the transmission, a rate at which the scheduled user'"'"'s token pool is decremented in the n^th slot.

23. The method of claim 20, wherein said depleting further includes:

determining the number of bits transmitted to the scheduled user per slot at an expected rate;

decrementing the token pool by a number of token corresponding to the determined number of bits transmitted in each slot until the transmission is complete; and

decrementing the token pool by any remaining number of bits transmitted to the scheduled user at the end of the transmission.

24. The method of claim 15, wherein a current token count value for the i^th user in an n^th timeslot, (T_i(n)), is incremented or decremented in accordance with:

T_i(n)=T_i(n−

1)+X_i(n)−

b_i(n), with X_i(n)=<sup>α

Rimin</sup>/₆₀₀(bits/slot);

where X_i(n) is a token rate that represents a product of the target minimum throughput R_i^min for the i^th user and the timeslot duration, α

is a tunable parameter that permits the token rate to be set at a value higher than the target minimum throughput for a given period, and b_i(n) represents the number of bits transmitted to the i^th user in the n^th timeslot.

25. The method of claim 24, wherein the token rate X_i(n) is dependent on how much the i^th user pays for a particular service offered by the network.

26. The method of claim 24, further comprising:

freezing the incrementing or decrementing of a current token count value for the i^th user if one of a network-related or user-initiated delay causes an idle period.

27. The method of claim 15, further comprising:

restricting token counts for each user to a given range.

28. A scheduler scheduling a plurality of users in a communication network to receive a transmission in accordance with the method of claim 15.

29. A method for scheduling transmissions to a plurality of users in a communication network, comprising:

determining, for each user in at least one timeslot, a token count that tracks the user'"'"'s achieved performance relative to a target minimum throughput;

determining a weight for each user based on one or more of the token count and a current rate requested by the user; and

selecting a user with a highest weight function as the user to be served the next transmission.

30. A scheduler scheduling a plurality of users in a communication network to receive a transmission in accordance with the method of claim 29.