Distributed priority algorithms under one-bit-delay constraint

Abstract

The paper deals with the issue of station delay in token-ring networks. It explains why one-bit-delay is the minimum possible delay at every station and shows that the station delay depends on the distributed computations performed in the ring. Then, the paper introduces the distributed priority mechanism for token-rings, as approved by the IEEE-802.5 standard. This mechanism attaches to the token, that circulates around the ring and controls the access to the shared medium, a priority field P and a reservation field R. These two fields work together in an attempt to match the service priority of the ring to the highest priority message that is waiting to be sent. It is shown that due to the computation restrictions imposed by the one-bit-delay requirements, this priority mechanism has a grave deficiency as follows. When the token priority is higher than the maximum reservation (P>R), the token should make up to P round-trips, where P is the number of priority levels, before P is reduced to R. During this time period, no station may seize the token and send a message. This leads to loss of bandwidth. The paper presents a new priority mechanism that retains the desired properties of the standard. However, in the new protocol when P>R holds, P is reduced to R in at most 1 round-trip rather than in up to P round-trips.