About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Parallel and Distributed Computing
Paper
A Distributed Scheduling Algorithm for Real-Time Communication on Slotted Shared Medium
Abstract
Algorithms for arbitrating and scheduling transmissions from different transmitters sharing a common access medium arise often in the design of many shared and distributed systems. In this paper we present a distributed algorithm for arbitrating time-constrained transmissions on slotted shared access media. The two most important distinguishing features of our algorithm are: (1) unlike most of the other schemes that guarantee on-time transmission over shared media by centralized preallocation of slots, our algorithm is fully distributed and completely on-line; (2) it eliminates one of the common pitfalls of all slotted systems, that is, allocation in integral multiples of full slots. We derive sufficient conditions for schedulability and show that the proposed scheme achieves high levels of schedulable utilization. We also show that the schedulable utilization increases as the length of the allocation cycle increases and asymptotically approaches the maximum achievable utilization. We present a distributed slot access protocol to realize the proposed algorithm for ring architecture. The protocol can be easily modified for other topologies, such as bus and dual-bus networks. Using illustrative examples we demonstrate the effectiveness of the algorithm. © 1999 Academic Press.