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.