SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATES
Autor: | Kavita Ramanan, Phil Whiting, Rajiv Vijayakumar, Krishnan Kumaran, Alexander L. Stolyar, Matthew Andrews |
---|---|
Rok vydání: | 2004 |
Předmět: |
Statistics and Probability
Markov chain Queue management system business.industry Computer science Management Science and Operations Research Industrial and Manufacturing Engineering Scheduling (computing) Discrete time and continuous time Countable set Wireless Statistics Probability and Uncertainty business Finite set Queue Computer network |
Zdroj: | Probability in the Engineering and Informational Sciences. 18:191-217 |
ISSN: | 1469-8951 0269-9648 |
Popis: | 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 μim customers of flow i (in one time slot).The scheduling discipline is a rule 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. |
Databáze: | OpenAIRE |
Externí odkaz: |