Scheduling in a Queuing System With Asynchronously Varying Service Rates

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 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.