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

Alexander L. Stolyar ()
Additional contact information
Alexander L. Stolyar: Bell Laboratories, Lucent Technologies, 600 Mountain Ave., 2C-322, Murray Hill, New Jersey 07974

Operations Research, 2005, vol. 53, issue 1, 12-25

Abstract: 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 1 ,…, u N ), where u n s 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.

Keywords: communications; queues:algorithms; networks; optimization; networks:stochastic (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0156 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:53:y:2005:i:1:p:12-25

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().