An efficient and practical local synchronous bandwidth allocation scheme for the timed-token MAC protocol

This paper is concerned with deadline guarantees of synchronous messages with deadlines equal to periods, in a timed token ring network such as FDDI where the timed token medium access control (MAC) protocol is used. The timed token protocol guarantees a bounded access time and an average bandwidth for synchronous traffic. However, this guarantee alone, though necessary, is insufficient for guaranteeing the transmission of synchronous messages before their deadlines. To ensure timely delivery, the synchronous bandwidth must be carefully allocated to individual nodes. We propose and analyse an efficient and practical local synchronous bandwidth allocation (SBA) scheme. The new scheme performs better than any previously published as it calculates the synchronous bandwidth such that during the message period, the total synchronous transmission time definitely available (when judged only by local information) is exactly equal to the transmission time required. Our scheme also differs significantly from previously reported ones by explicitly taking into account the synchronous bandwidth allocation for message sets whose minimum message deadlines (D_min) are less than twice the target token rotation time (TTRT), and consequently can apply to any synchronous message set (with D_min>TTRT). The feasibility of the allocations produced by the proposed scheme and the worst case achievable utilisation of the scheme are also discussed