Scheduling in a queuing system with asynchronously varying service rates

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

Research output: Contribution to journalArticle

Abstract

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 (US)
Pages (from-to)191-217
Number of pages27
JournalProbability in the Engineering and Informational Sciences
Volume18
Issue number2
DOIs
StatePublished - May 7 2004
Externally publishedYes

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

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

  • Cite this