Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks

Abstract

The stability of a queueing network with interdependent servers is considered. The dependency of servers is described by the definition of their subsets that can be activated simultaneously. Multihop packet radio networks (PRN's) provide a motivation for the consideration of this system. We study the problem of scheduling the server activation under the constraints imposed by the dependency among them. The performance criterion of a scheduling policy p is its throughput that is characterized by its stability region Cp, that is, the set of vectors of arrival rates for which the system is stable. A policy po is obtained which is optimal in the sense that its stability region Cpo is a superset of the stability region of every other scheduling policy. The stability region Cpo is characterized. Finally, we study the behavior of the network for arrival rates that lie outside the stability region. Implications of the results in certain types of concurrent database and parallel processing systems are discussed.