STABILITY PROPERTIES OF CONSTRAINED QUEUING-SYSTEMS AND SCHEDULING POLICIES FOR MAXIMUM THROUGHPUT IN MULTIHOP RADIO NETWORKS

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 pi is its throughput that is characterized by its stability region C(pi), that is, the set of vectors of arrival rates for which the system is stable. A policy pi0 is obtained which is optimal in the sense that its stability region C(pi0) is a superset of the stability region of every other scheduling policy. The stability region C(pi0) 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.