Scheduling method for wireless packet data channel

• US 20060153216A1
• Filed: 10/13/2005
• Published: 07/13/2006
• Est. Priority Date: 11/19/2004
• Status: Active Grant

• Current Assignee: Unwired Planet LLC (JP Morgan Chase & Co)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Hosein, Patrick A., Makhijani, Mahesh A.
• Granted Patent: US 7,742,455 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 1/0002 by adapting the transmission rate
• CPC Class Codes: H04L 1/0018 based on latency requirement
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/52 by attributing bandwidth to queues
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/562 Attaching a time tag to queues
• CPC Class Codes: H04L 47/566 Deadline varies as a function of time spent in the queue
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/626 channel conditions
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 28/22 Negotiating communication rate
• CPC Class Codes: H04W 72/1221 based on age of data to be sent
• CPC Class Codes: H04W 72/1273 of downlink data flows
• CPC Class Codes: H04W 72/52 based on load
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A scheduler at a base station may schedule packet data traffic based on a ranking metric that varies directly with the mobile station'"'"'s scheduling downlink transmission rate and a delay factor indicative of the staleness of the corresponding queued data. The ranking metric may advantageously vary in a direct non-linear fashion with the delay factor to allow for delay sensitive data, such as VoIP data, to be scheduled with increased urgency when quality of service is about to be compromised. The scheduler may attempt to pack a multi-user downlink physical layer packet by selecting a tentative rate and determining if an aggregate amount of data in the packet may be increased by transmitting the packet at a lower rate. If so, additional queued data is added to the packet and the transmission rate for the packet is lowered. Such an approach allows for greater link efficiency to be achieved.

Claims

1. A method of scheduling use of a downlink packet data traffic channel shared by a plurality of mobile stations, comprising:

calculating a ranking metric for a mobile station that varies directly with the mobile station'"'"'s scheduling downlink transmission rate and a delay factor indicative of the staleness of data queued for the mobile station; and

scheduling one or more downlink transmissions to the mobile station on the downlink packet data traffic channel based on said ranking metric.

2. The method of claim 1 wherein said calculating said ranking metric comprises calculating said ranking metric as a function of the scheduling rate divided by the difference between a threshold and the delay factor.

3. The method of claim 2 wherein said threshold represents the maximum allowed delay.

4. The method of claim 1 wherein said ranking metric varies in a direct non-linear fashion with the delay factor.

5. The method of claim 1 further comprising determining said delay factor based on an amount of elapsed time associated with the oldest of the data queued for said mobile station.

6. The method of claim 1 wherein said ranking metric RANK varies according to the formula RANK=R/(d_max−

d)^k, where R represents the mobile station'"'"'s scheduling downlink transmission rate, d_max represents the threshold value of the maximum allowed delay, d represents the current delay factor, and k is a sensitivity exponent.

7. The method of claim 6 wherein k equals one.

8. The method of claim 6 further comprising modifying the value of k upward to increase an effective capacity of the downlink packet data traffic channel.

9. The method of claim 6 further comprising modifying the value of k downward to increase quality of service to said mobile station.

10. The method of claim 1 further comprising determining said delay factor based on an amount of buffer consumed by said queued data.

11. The method of claim 1 wherein said ranking metric RANK varies according to the formula RANK=R/(q_max−

q)^k, where R represents the mobile station'"'"'s scheduling downlink transmission rate, q_max represents the threshold value of the maximum allowed buffer size, q represents the current amount of buffer consumed by said queued data, and k is a sensitivity exponent.

12. The method of claim 1:

wherein said ranking metric RANK varies according to the formula RANK=R/(d_max−

d)^k, where R represents the mobile station'"'"'s scheduling downlink transmission rate, d_max represents the threshold value of the maximum allowed delay, d represents the current delay factor, and k is a sensitivity exponent; and

further comprising transmitting data to said mobile station based on said scheduling in a multi-user downlink packet on the shared downlink packet data traffic channel.

13. A method of packing a multi-user wireless downlink physical layer packet with data queued for a plurality of mobile stations, comprising:

selecting as a tentative downlink transmission rate a scheduling downlink transmission rate associated with a primary mobile station identified based on a scheduling algorithm;

determining if an aggregate amount of data in said packet may be increased by transmitting said packet at a downlink transmission rate lower than said tentative rate; and

selecting a downlink transmission rate for said packet based on said determining;

said packet including data queued for said primary mobile station.

14. The method of claim 13 further comprising selectively adding, based on said determining, data queued for at least one additional mobile station to said packet;

said at least one additional mobile station having an associated scheduling downlink transmission rate that is lower than said tentative rate.

15. The method of claim 14 further comprising adding data queued for at least one supplemental mobile station to said packet, said at least one supplemental mobile station having an associated scheduling downlink transmission rate that is equal to or higher than said tentative rate.

16. The method of claim 15 wherein said adding data queued for at least one supplemental mobile station to said packet occurs prior to said determining.

17. The method of claim 13 wherein said determining comprises calculating a first amount of data to be transmitted in said packet at said tentative rate and comparing said first amount against a threshold.

18. The method of claim 17 wherein failing to satisfy said threshold indicates that an aggregate amount of data in said packet may be increased if the downlink transmission rate associated with said packet is lowered.

19. The method of claim 17 wherein said threshold is a ratio with respect to a data payload capacity of said packet if transmitted at said tentative rate.

20. The method of claim 13:

wherein said determining comprises calculating a first amount of data to be transmitted in said packet at said tentative rate and comparing said first amount against a threshold;

wherein said threshold is a ratio with respect to a data payload capacity of said packet if transmitted at said tentative rate; and

further comprising selectively adding, based on said determining, data queued for at least one additional mobile station to said packet;

said at least one additional mobile station having an associated scheduling downlink transmission rate that is lower than said tentative rate.

21. The method of claim 13 further comprising adding data queued for at least one supplemental mobile station to said packet, said at least one supplemental mobile station having an associated scheduling downlink transmission rate that is equal to or higher than said tentative rate;

wherein said adding data queued for at least one supplemental mobile station to said packet occurs prior to said determining.

22. A method of packing a multi-user wireless downlink physical layer packet with data queued for a plurality of mobile stations, comprising:

selecting a tentative downlink transmission rate and primary mobile station to be transmitted to for the packet;

wherein all of the queued data for said primary mobile station fails to fill said packet at said tentative downlink transmission rate;

determining if data queued for one or more additional mobile stations could be added to said packet if the downlink transmission rate was lowered from said tentative downlink transmission rate to a second downlink transmission rate; and

selecting a downlink transmission rate for said packet based on said determining.

23. The method of claim 22 further comprising selectively adding queued data for said one or more additional mobile stations to said packet based on said determining.

24. The method of claim 22 wherein said determining comprises identifying one or more candidate mobile stations having an associated scheduling downlink transmission rate lower than said tentative downlink transmission rate.

25. The method of claim 24 wherein said candidate mobile stations have an associated scheduling downlink transmission rate that is one step lower than said tentative downlink transmission rate.

26. The method of claim 22 wherein said determining comprises comparing an aggregate amount of queued data allocated to said packet to a capacity of said packet at said tentative downlink transmission rate.

27. The method of claim 22 further comprising, prior to said determining:

adding data queued for a second mobile station to said packet;

said second mobile station having an associated scheduling downlink transmission rate of at least said tentative downlink transmission rate.

28. The method of claim 22 wherein said determining further comprises determining if further data queued for other mobile stations could be added to said packet if the downlink transmission rate for said packet was lowered from said second downlink transmission rate to a third downlink transmission rate lower than said second downlink transmission rate.

29. The method of claim 22:

wherein said determining comprises identifying one or more candidate mobile stations having an associated scheduling downlink transmission rate lower than said tentative downlink transmission rate;

wherein said candidate mobile stations have an associated scheduling downlink transmission rate that is one step lower than said tentative downlink transmission rate;

wherein said determining further comprises comparing an aggregate amount of queued data allocated to said packet to a capacity of said packet at said tentative downlink transmission rate; and

further comprising selectively adding queued data for said one or more additional mobile stations to said packet based on said determining.

30. The method of claim 29 further comprising, prior to said determining, adding data queued for a second mobile station to said packet;

said second mobile station having an associated scheduling downlink transmission rate of at least said tentative downlink transmission rate.

31. The method of claim 30 further comprising determining if further data queued for other mobile stations could be added to said packet if the downlink transmission rate for said packet was lowered from said second downlink transmission rate to a third downlink transmission rate lower than said second downlink transmission rate.

32. A base station for a wireless communications system comprising a scheduler to schedule use of a downlink packet data traffic channel shared by a plurality of mobile stations, said scheduler comprising one or more processing circuits configured to:

calculate a ranking metric for a mobile station that varies directly with the mobile station'"'"'s scheduling downlink transmission rate and a delay factor indicative of the staleness data queued for the mobile station; and

schedule one or more downlink transmissions to the mobile station on the packet data traffic channel based on said ranking metric.

33. The base station of claim 32 wherein said scheduler is further configured to calculate said ranking metric as a function of the scheduling rate divided by the difference between a threshold and the delay factor.

34. The base station of claim 33 wherein said threshold represents the maximum allowed delay.

35. The base station of claim 32 wherein said scheduler is further configured to calculate said ranking metric such that said ranking metric varies in a direct non-linear fashion with the delay factor.

36. The base station of claim 33 wherein said scheduler is further configured to determine said delay factor based on an amount of elapsed time associated with the oldest of the data queued for said mobile station.

37. The base station of claim 32 wherein said scheduler is further configured to calculate said ranking metric RANK according to the formula RANK=R/(d_max−

d)^k, where R represents the mobile station'"'"'s scheduling downlink transmission rate, d_max represents the threshold value of the maximum allowed delay, d represents the current delay factor, and k is a sensitivity exponent.

38. The base station of claim 37 wherein k equals one.

39. The base station of claim 37 wherein said scheduler is further configured to modify the value of k upward to increase an effective capacity of the downlink packet data channel.

40. The base station of claim 37 wherein said scheduler is further configured to modify the value of k downward to increase quality of service to said mobile station.

41. The base station of claim 32 wherein said scheduler is further configured to determine said delay factor based on an amount of buffer consumed by said queued data.

42. The base station of claim 32 wherein said scheduler is further configured to calculate said ranking metric RANK according to the formula RANK=R/(q_max−

q)^k, where R represents the mobile station'"'"'s scheduling downlink transmission rate, q_max represents the threshold value of the maximum allowed buffer size, q represents the current amount of buffer consumed by said queued data, and k is a sensitivity exponent.

43. The base station of claim 32:

wherein said scheduler is further configured to calculate said ranking metric RANK according to the formula RANK=R/(d_max−

d)^k, where R represents the mobile station'"'"'s scheduling downlink transmission rate, d_max represents the threshold value of the maximum allowed delay, d represents the current delay factor, and k is a sensitivity exponent; and

further comprising a transmitter that transmits data packets to said mobile station based on said scheduling in a multi-user downlink packet on the shared downlink packet data traffic channel.

44. A base station for a wireless communications system comprising a scheduler to pack a downlink physical layer packet with data queued for a plurality of mobile stations, said scheduler comprising one or more processing circuits configured to:

selecting as a tentative downlink transmission rate a scheduling downlink transmission rate associated with a primary mobile station identified based on a scheduling algorithm;

determine if an aggregate amount of data in said packet may be increased by transmitting said packet at a downlink transmission rate lower than said tentative rate; and

select a downlink transmission rate for said packet based on said determination;

wherein said packet includes data queued for said primary mobile station.

45. The base station of claim 44 wherein said scheduler is further configured to selectively add, based on said determination, data queued for at least one additional mobile station to said packet;

said at least one additional mobile station having an associated scheduling downlink transmission rate lower than said tentative rate.

46. The base station of claim 45 wherein said scheduler is further configured to selectively add data queued for at least one supplemental mobile station to said packet, said at least one supplemental mobile station having an associated scheduling downlink transmission rate that is equal to or higher than said tentative rate.

47. The base station of claim 46 wherein scheduler is further configured to selectively add said data queued for at least one supplemental mobile station to said packet prior to said determination.

48. The base station of claim 44 wherein scheduler is further configured to calculate, during said determination, a first amount of data to be transmitted in said packet at said tentative rate and compare said first amount against a threshold.