A scheduling policy with maximal stability region for ring networks with spatial reuse

Abstract

A slotted ring that allows simultaneous transmissions of messages by different users is considered. Such a ring network is commonly called ring with spatial reuse. It can achieve significantly higher throughput than standard token rings but it also raises the issue of fairness since some nodes may be prevented from accessing the ring for long time intervals. Policies that operate in cycles and guarantee that a certain number (quota) of packets will be transmitted by every node in every cycle have been considered before to deal with the fairness issue. In this paper we address the problem of designing a policy that results in a stable system whenever the end-to-end arrival rates are within the stability region of the ring with spatial reuse (the stability region of the ring is defined as the set of end-to-end arrival rates for which there is a policy that makes the ring stable). We provide such a policy, which does not require knowledge of end-to-end arrival rates. The policy is an adaptive version of the quota policies and can be implemented with the same distributed mechanism. We use the Lyapunov test function technique together with methods from the theory of regenerative processes to derive our main results. © 1995 J.C. Baltzer AG, Science Publishers.