This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Stolyar, A. L. Search for Related Content

On the Asymptotic Optimality of the Gradient Scheduling Algorithm for Multiuser Throughput Allocation

Bell Laboratories, Lucent Technologies, 600 Mountain Ave., 2C-322, Murray Hill, New Jersey 07974
stolyar{at}research.bell-labs.com

We consider the model where N queues (users) are served in discrete time by a generalized switch. The switch state is random, and it determines the set of possible service rate choices (scheduling decisions) in each time slot. This model is primarily motivated by the problem of scheduling transmissions of N data users in a shared time-varying wireless environment, but also includes other applications such as input-queued cross-bar switches and parallel flexible server systems.

The objective is to find a scheduling strategy maximizing a concave utility function H(u₁,...,u_N), where u_ns are long-term average service rates (data throughputs) of the users, assuming users always have data to be served.

We prove asymptotic optimality of the gradient scheduling algorithm (which generalizes the well-known proportional fair algorithm) for our model, which, in particular, allows for simultaneous service of multiple users and for discrete sets of scheduling decisions. Analysis of the transient dynamics of user throughputs is the key part of this work.

Subject classifications: communications; queues:algorithms; networks; optimization; networks:stochastic.
History: Received January 2003; accepted June 2003.

This article has been cited by other articles:

				S. Borst Flow-level performance and user mobility in wireless data networks Phil Trans R Soc A, June 13, 2008; 366(1872): 2047 - 2058. [Abstract] [Full Text] [PDF]

				H.-Q. Ye and D. D. Yao Heavy-Traffic Optimality of a Stochastic Network Under Utility-Maximizing Resource Allocation Operations Research, March 1, 2008; 56(2): 453 - 470. [Abstract] [PDF]