Method of packet scheduling, with improved delay performance, for wireless networks

• US 6,590,890 B1
• Filed: 03/03/2000
• Issued: 07/08/2003
• Est. Priority Date: 03/03/2000
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Stolyar, Aleksandr, Vijayakumar, Rajiv
• Primary Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US09/517,659
• Time in Patent Office: 1,222 Days
• Field of Search: 370/349, 370/335, 370/342, 370/395.32, 370/411-418, 370/468, 370/331, 370/437, 455/67.1, 455/522
• US Class Current: 370/349
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 72/1221 based on age of data to be sent
• CPC Class Codes: H04W 72/54 based on quality criteria

Abstract

A new scheduling discipline is disclosed for the forward link of a wireless network such as a CDMA network. The new discipline, which we denominate Modified LWDF (M-LWDF), resembles the known LWDF discipline in that only one queue is served at a time, and the queue to be served is that having the largest weighted delay. According to M-LWDF, the weighted delay of the i'"'"'th queue is defined as $\frac{{\gamma }_iW_i\left(t\right)}{c_i\left(t\right)},$

wherein W_i(t) is a packet delay, a queue length, or an increasing function of packet delay or queue length for the i'"'"'th queue, c_i(t) is a weight coefficient descriptive of channel conditions for the i'"'"'th user, and γ_i is a fixed constant that can be chosen arbitrarily. We have found that if any scheduling discipline can yield stable queues for a given traffic pattern of arriving packets, then M-LWDF can, even under changing channel conditions. Moreover, we have found that M-LWDF can provide favorable QoS in terms of delay bounds.

Claims

1. A method for scheduling queued packets for service by a wireless base station, wherein there is a queue of packets destined for each of a plurality of users, the method comprising:

periodically identifying a queue having a largest weighted delay; and

scheduling the identified queue for service, during a scheduling interval, at the greatest transmission rate available for serving said queue;

wherein;

(a) each queue i has, at a given time t, a delay W_i(t) determined by one of the following;

the age of the oldest packet in said queue;

a total amount of data in said queue;

in a system in which service of said queue is regulated by a virtual queue that receives tokens at a constant rate, the age of the oldest token in the virtual queue;

or the number of tokens in a corresponding virtual queue; and

(b) at time t, the weighted delay of each queue i is expressed by $\frac{{\mathrm{\gamma <br><br>}}_i}{c_i<br><br>\left(t\right)}$

 

times W_i(t), or by $\frac{{\mathrm{\gamma <br><br>}}_i}{c_i<br><br>\left(t\right)}$

 

times an increasing function of W_i(t), wherein γ

_i is a constant, and c_i(t) is a weight coefficient that represents the transmission power required per unit data rate to transmit data, at time t, to the user whose destined queue is queue i.

2. The method of claim 1, wherein only the queue having the largest weighted delay is scheduled for service during each scheduling interval.

3. The method of claim 1, wherein the queues are ranked according to weighted delay, and for each scheduling interval, the maximum available rate is allocated first to the queue having the largest weighted delay, and the remaining transmission capacity is allocated to the remaining queues in descending rank order such that the maximum available rate is allocated to each queue until all available transmission capacity is exhausted.

4. The method of claim 1, wherein:

each constant γ

_i is proportional to $-\frac{\ln <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_i}{T_i};<br><br>$

T_i is a specified delay threshold for queue i; and

δ

_i is a specified maximum probability that the delay of queue i exceeds T_i.

5. The method of claim 4, wherein each constant γ

_i is equal to $-\frac{\ln <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_i}{T_i}.$

6. The method of claim 4, wherein each constant γ

_i is proportional to $-{\stackrel{\_}{c}}_i<br><br>\frac{\ln <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_i}{T_i},$

wherein {overscore (c)}_i represents a measured short-term average or short-term median value of the weight coefficient c_i(t).

7. The method of claim 6, wherein each constant γ

_i is equal to $-{\stackrel{\_}{c}}_i<br><br>\frac{\ln <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_i}{T_i}.$

8. The method of claim 1, wherein:

the weighted delay of each queue i is expressed by $\frac{{\mathrm{\gamma <br><br>}}_i}{c_i<br><br>\left(t\right)}$

 

times an increasing function of W_i(t);

said increasing function has the form $F<br><br>\left(\frac{a_i<br><br>W_i<br><br>\left(t\right)}{G<br><br>\left(\stackrel{\_}{\mathrm{aW}}\right)}\right);<br><br>$

F( . . . ) and G( . . . ) are increasing functions;

a_i is a positive scaling coefficient;

a_iW_i is a scaled delay of queue i; and

{overscore (aW)} is a scaled delay averaged over all queues.

9. The method of claim 8, wherein each scaling coefficient a_i is derived from a specified delay threshold T_i for queue i and a specified maximum probability δ

_i that the delay of queue i exceeds T_i.

10. The method of claim 9, wherein each scaling coefficient a_i is proportional to $-\frac{\ln }{}$

 



δ

iTi.

11. The method of claim 9, wherein each scaling coefficient a_i is equal to $-\frac{\ln }{}$

 



δ

iTi.

12. The method of claim 9, wherein {overscore (aW)} is the mean value of a_iW_i over all queues i.

13. The method of claim 8, wherein G ( . . . ) is a sub-linear function.

14. The method of claim 13, wherein G({overscore (aW)}) is equal to {square root over ({overscore (aW)})}+b, b a positive constant.

15. The method of claim 13, wherein $F$

(ai

Wi

(t)G

(aW_))

is equal to $\exp <br><br>\left(\frac{a_i<br><br>W_i<br><br>\left(t\right)}{G<br><br>\left(\stackrel{\_}{\mathrm{aW}}\right)}\right).$