Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

The stability of a queuing network with interdependent servers is considered. The dependency among the servers is described by defining subsets of servers that can be activated simultaneously. Packet radio networks provide the motivation for the consideration of these systems. The problem of scheduling server activation under the constraints imposed by the dependency among them is studied. The stability region of the network under a specific scheduling policy is the set of vectors of arrival rates in the queues of the system for which the stochastic process of the queue lengths is ergodic. The 'supremum' (i.e., union) of the stability regions over all the policies is characterized. Then a scheduling policy is specified, the stability region of which is equal to the union of the stability regions over all the policies. Finally, the behavior of the network for arrival rates outside the stability region is studied.>