SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATES

TLDR

The paper studies a discrete‑time queuing model of a wireless link shared by a finite number of users, where each flow follows an irreducible Markov chain and the server’s state evolves as a finite‑state Markov chain, determining state‑dependent service rates. The scheduling rule selects, in each slot, the flow to serve based on the current server state and the queue lengths. The authors prove that the Modified Largest Weighted Delay First policy, and its generalizations, are throughput‑optimal, guaranteeing queue stability whenever the arrival rates lie within the system’s maximum stability region.

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