Multiplex communications – Communication over free space – Combining or distributing information via time channels
Reexamination Certificate
2000-03-03
2003-07-08
Nguyen, Steven (Department: 2665)
Multiplex communications
Communication over free space
Combining or distributing information via time channels
C370S342000, C370S395400
Reexamination Certificate
active
06590890
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to scheduling disciplines for packet transmissions in a wireless network, and more particularly to the downlink scheduling in a CDMA network.
ART BACKGROUND
Within the base station of a wireless network such as a CDMA network, packets destined for individual mobile stations accumulate in a buffer until they can be served by the base station and transmitted to their destinations. A queue of waiting packets can be identified for each mobile station served by the base station.
An important area of current study is how best to devise a rate scheduling rule (also referred to as a scheduling discipline or queueing discipline) that directs the base station, at a given time, how to allocate its total capacity among individual data transmission rates to the respective mobile stations. Desirably, the rate scheduling rule is devised such that all the queues are stable; that is, in such a way that each queue reaches a steady-state delay that on average does not increase with time. Moreover, it is desirable to devise the rate scheduling rule such that no queue experiences excessive delay as measured, e.g., by the age of the oldest packet in the queue. The age of a packet is typically measured from the arrival timestamp of the packet.
A scheduling rule known to those skilled in the art as Largest Weighted Delay First (LWDF) was described in U.S. patent application Ser. No. 09/393,949, filed on Sep. 10, 1999 by K. Ramanan et al. under the title “Method And Apparatus For Scheduling Traffic To Meet Quality Of Service Requirements In A Communication Network” and commonly assigned herewith. Under the LWDF scheduling rule, only one mobile station (more generally, only one “user”) is served at a time, and transmission to that user is made at the greatest available mobile data transmission rate. Within a scheduling interval identified, e.g., by its initial time t, the LWDF rule directs that the base station should serve that queue which has the greatest weighted delay a
i
W
i
(t), where the number of distinct queues is N, i=1, . . . , N, W
i
(t) is the delay of the longest-waiting packet in the i'th queue, and {a
i
} are a set of constants, described in more detail below.
The LWDF discipline is useful, under at least certain conditions, for maintaining packet delays within certain bounds, which we refer to as probabilistic delay bounds. (A probabilistic delay bound is a requirement that with at least a specified probability, packet delays must be less than a specified threshold.) However, LWDF generally provides the best results when channel conditions are constant. Channel conditions are typically characterized by a set of weights {c
i
}, each weight expressing the transmission power required per unit data rate to transmit data to a respective mobile station. Because in many cases there are significant fluctuations in the channel conditions, a need has remained for a scheduling discipline that will dependably provide queue stability and probabilistically bounded delay even in the presence of such fluctuations.
SUMMARY OF THE INVENTION
We have devised a new scheduling discipline, which we denominate Modified LWDF (M-LWDF). We have mathematically proven that if any scheduling discipline can yield stable queues for a given traffic pattern of arriving packets, then M-LWDF can. We have proven that this is so even under changing channel conditions. Moreover, we have found that M-LWDF can provide favorable probabilistic delay bounds. That is, M-LWDF can lead to a low probability that the delay of any queue will exceed a threshold. This probability is also low compared to those delay-violation probabilities typically achieved by, e.g., the known LWDF discipline.
Like LWDF, the M-LWDF discipline directs that only one mobile station should be served at a time. It is generally desirable, although not essential, to serve that one mobile station at the greatest available mobile data transmission rate. Moreover, as will be explained below, certain extensions of pure M-LWDF in which multiple mobile stations may be served at one time also fall within the scope of the invention.
In certain exemplary embodiments of M-LWDF, the queue to be served in each scheduling interval is the queue having a maximum weighted delay. However, the weighted delay is defined differently from the weighted delay of the LWDF discipline. One example of a weighted delay suitable for M-LWDF is
γ
i
W
i
(
t
)
c
i
(
t
)
,
where W
i
(t) is defined as above, the time-dependence of the weights c
i
(t) (which, as noted, reflect channel conditions) is now explicitly indicated, and {&ggr;
i
} is a fixed set of positive constants that can be chosen arbitrarily.
Significantly, each weighted delay now grows larger as the corresponding weight c
i
(t) grows smaller. Smaller weights signify better signal-propagation channels, because less power is required for transmission at a given data rate. Thus, the new weighted delay presented above represents a trade-off between two possibly competing effects. On the one hand, the weighted delay tends to grow, and thus the likelihood of serving the corresponding queue tends to grow, as W
i
(t) grows, i.e., as the packets of the queue grow older. On the other hand, the weighted delay tends to grow as the weight c
i
(t) falls, but tends to fall as the weight c
i
(t) rises. Thus, increases in either packet age or channel quality can increase the likelihood of serving the pertinent queue.
The M-LWDF discipline, as we envisage it, is broad enough to encompass other definitions of the weighted delay that also take into account the possibly competing effects of packet age and channel quality. For example, the weight c
i
(t) may be normalized by a statistically calculated variable such as its own average or median value {overscore (c)}
i
over an appropriate time interval. According to still other alternate definitions of the weighted delay, the ratio
γ
i
c
i
(
t
)
multiplies, not W
i
(t), but instead an increasing function of W
i
(t). Advantageously, such a function gives preferential weight to queues whose delays (possibly adjusted by a scaling coefficient) exceed by a threshold quantity an average scaled delay, i.e., the scaled delay averaged over all queues. Such a threshold quantity is desirably an increasing function of the average scaled delay.
Although W
i
(t) has been described above as representing the age of the oldest packet in the i'th queue, it can also represent the length of the i'the queue, i.e., the amount of data waiting in the queue. Thus, without deviating from the scope and spirit of the invention, queues can be selected on the basis of weighted delay for all queues, weighted queue length for all queues, or weighted delay for some queues and weighted queue length for others.
As noted, pure M-LWDF demands that in each scheduling interval, only one queue should be served. However, the base station in some wireless systems will be prohibited from allocating its full transmission capacity to a single mobile station. In such a case, the maximum transmission rate that is “available” to serve a given queue may not account for the full transmission capacity of the base station. In such cases, for example, it will be advantageous to rank the queues in descending order of their respective weighted delays. The maximum transmission rate available for serving the first queue is allocated for that purpose. Of the transmission capacity that remains, the maximum available rate is then allocated to the next queue, and so on, down through the rank ordering until the total transmission capacity is exhausted. We consider such a scheduling method, in which the weighted delay is defined as in pure M-LWDF, to also fall within the scope of the present invention.
REFERENCES:
patent: 5914950 (1999-06-01), Tiedemann et al.
patent: 6091717 (2000-07-01), Honkasalo et al.
patent: 6335922 (2002-01-01), Tiedemann, Jr. et al.
patent: 6393012 (2002-05-01), Pankaj
N. Kahale, et al., “Dynamic Global Pac
Stolyar Aleksandr
Vijayakumar Rajiv
Finston Martin I.
Lucent Technologies - Inc.
Nguyen Steven
LandOfFree
Method of packet scheduling, with improved delay... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of packet scheduling, with improved delay..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of packet scheduling, with improved delay... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3007605