page 1  (34 pages)
2to next section

An Efficient and Practical Synchronous Bandwidth

Allocation Scheme for Deadline Guarantees of

Synchronous Messages in an FDDI Network

Sijing Zhang

(Email: [email protected])

Real-Time Systems Research Group

Department of Computer Science, University of York

Heslington, York YO1 5DD, UK


This report addresses issues related to guaranteeing synchronous message

sets with message deadlines equal to periods, in an FDDI network where the

timed token protocol is used. FDDI guarantees a bounded access time and an

average bandwidth for synchronous traffic, and therefore the timed token protocol

is well suited for real-time applications. However, this guarantee alone, though

necessary, is insufficient for guaranteeing the transmission of synchronous mes-

sages before their deadlines. To ensure the timely delivery of synchronous mes-

sages, the synchronous bandwidth (a key parameter in the control of synchronous

message transmission) must be carefully allocated to individual nodes.

In this report, we propose and analyse a new local synchronous bandwidth

allocation (SBA) scheme. Generally, our local scheme performs better than any of

previously-published local SBA schemes due to the fact that it calculates synchro-

nous bandwidths, with locally-available information, under the consideration of

fully using all synchronous bandwidths surely available during the period of the

message. Our new local scheme also differs significantly from previously

reported local SBA schemes by explicitly taking into account the synchronous

bandwidth allocation for the synchronous message sets with the minimum mes-

sage deadline ( D min ) less than twice the Target Token Rotation Time (TTRT),

and as a result can be applied to any of synchronous message sets (with

D min > TTRT). The feasibility of allocations produced by the proposed local

scheme as well as the worst case achievable utilisation of the scheme is also dis-

cussed in this report. Since local SBA schemes, unlike global SBA schemes, can

greatly simplify the run-time management of network with the advantage of being

flexible and suitable for use in dynamic environment, the proposed local scheme

can be used to effectively support synchronous traffic in practice.

1. Introduction

In a distributed system for hard real-time applications, communication through message

exchange between tasks residing on different nodes must happen in bounded time, in order to

ensure that end-to-end deadline requirements are met. This motivates the use of medium access

control (MAC) communication protocols which provide a guaranteed connection and a guaranteed

amount of channel bandwidth to support timely delivery of inter-task messages. With the impor-

tant property of bounded time between any two consecutive visits of the token to a node, the timed

token protocol becomes one of the most suitable and attractive candidates for hard real-time appli-

cations. This protocol has been incorporated into many network standards including the Fibre