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

Abstract

Abstruct-The stability of a queueing network with interde- pendent 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) pro- vide a motivation for the consideration of this system. We study the problem of scheduling the server activation under the con- straints imposed by the dependency among them. The perfor- mance criterion of a scheduling policy m is its throughput that is characterized by its stability region C,, that is, the set of vectors of arrival rates for which the system is stable. A policy m,, is obtained which is optimal in the sense that its stability region Cn0 is a superset of the stability region of every other scheduling policy. The stability region Cmo 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. I. INTRODUCTION E consider a queueing network model that is suit- able for communication networks with interde- pendent service components. The queueing network has arbitrary topology and multiple servers. The servers are interdependent in that they cannot provide service simul- taneously. The dependency among them is reflected on the constraints which specify exactly which subsets of servers may be active simultaneously. For example, when the constrained queueing system is used as a model of a radio network, the servers correspond to the links and the constraints disallow simultaneous transmissions for neigh- boring links. We consider slotted time. At each time slot, routing decisions are taken for the served customers and eligible sets of servers are selected for activation. We assume that these decisions are made in a centralized fashion and are based on global knowledge of the queue lengths in the entire network. We assume that buffering at each queue is infinite. We consider the system to be