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.