Scheduling in a queuing system with asynchronously varying service rates

Matthew Andrews*, Krishnan Kumaran, Kavita Ramanan, Alexander Stolyar, Rajiv Vijayakumar, Phil Whiting

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

227 Citations (Scopus)


We consider the following queuing system which arises as a model of a wireless link shared by multiple users. There is a finite number N of input flows served by a server. The system operates in discrete time t = 0,1,2,.... Each input flow can be described as an irreducible countable Markov chain; waiting customers of each flow are placed in a queue. The sequence of server states m(t),t = 0,1,2,..., is a Markov chain with finite number of states M. When the server is in state m, it can serve μ i m customers of flow i (in one time slot). The scheduling discipline is a rale that in each time slot chooses the flow to serve based on the server state and the state of the queues. Our main result is that a simple online scheduling discipline, Modified Largest Weighted Delay First, along with its generalizations, is throughput optimal; namely, it ensures that the queues are stable as long as the vector of average arrival rates is within the system maximum stability region.

Original languageEnglish
Pages (from-to)191-217
Number of pages27
JournalProbability in the Engineering and Informational Sciences
Issue number2
Publication statusPublished - 2004
Externally publishedYes


Dive into the research topics of 'Scheduling in a queuing system with asynchronously varying service rates'. Together they form a unique fingerprint.

Cite this