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

A slotted ring that allows simultaneous transmissions of messages by different users is considered. Such a ring network is commonly called ring withspatial 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.This research was primarily done while the author was visiting INRIA in Rocquencourt, France. The author wishes to thank INRIA (projects ALGO, MEVAL and REFLECS) for a generous support. Additional support was provided by NSF Grants NCR-9206315 and CCR-9201078 and INT-8912631, and by Grant AFOSR-90-0107, and in part by NATO Grant 0057/89.The research of this author was supported in part by NSF under Grants NCR-9211417 and NCR-9406415, and by the New York State Center for Advanced Technology in Telecommunications, Polytechnic University.