A distributed scheduling algorithm for real-time communication on slotted shared medium

Algorithms for arbitrating and scheduling transmissions from different tran smitters sharing a common access medium arise often in the design of many s hared and distributed systems. In this paper we present a distributed algor ithm for arbitrating time-constrained transmissions on slotted shared acces s media. The two most important distinguishing features of our algorithm ar e: (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 comm on pitfalls of all slotted systems, that is, allocation in integral multipl es of full slots. We derive sufficient conditions for schedulability and sh ow 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 ac hievable utilization. We present a distributed slot access protocol to real ize the proposed algorithm for ring architecture. The protocol can be easil y modified for other topologies, such as bus and dual-bus networks. Using i llustrative examples we demonstrate the effectiveness of the algorithm. (C) 1999 Academic Press.