A STUDY OF TIMING PROPERTIES WITH THE TIMED

TOKEN PROTOCOL

Sijing Zhang
Alan Burns

Department of Computer Science
University of York
Heslington
York YO1 5DD

ABSTRACT

We investigate the timing properties necessary to guarantee synchronous

message deadlines in a token ring network such as FDDI (Fibre Distributed

Data Interface) where the timed token medium access control protocol (MCA)

is employed. We present a tighter upper bound, than previously published, for

the worst case achievable utilisation of the MCA scheme. We also found that,

under the condition that the total channel bandwidth available for message

transmission is fully/exhaustively allocated among all synchronous message

streams, the lower bound of the worst case achievable utilisation with the MCA

scheme is a function of the number of nodes in the network. As a result, a

tighter lower bound is derived. In addition we propose a similar optimal syn-

chronous capacity allocation scheme named IMCA (Improved MCA) which

performs better than the MCA scheme in the sense that it can guarantee not

only all synchronous message sets which can be guaranteed by the MCA

scheme but also some other synchronous message sets for which the MCA

scheme cannot apply. In general the report enhances the results obtained by

Zhao et al[Mal93, Che92b, Agr92b].

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

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

control (MAC) communication protocols proposed for hard real-time communications, which

provide the guaranteed connection and guaranteed amount of channel bandwidth to support

timely delivery of inter-task messages. With the important property of bounded time between

any two consecutive visits of the token to a node, which is necessary for real-time communica-

tion, the timed token protocol becomes one of the most suitable and attractive candidates for

(hard) real-time application.

The important concept of "timed token" protocol was first proposed in 1982 by

Grow[Gro82] where the framework (the basic idea) of the timed token protocol, adaptable to

either a physical or a logical ring, was described in detail. Since then, extensive research has

been done on the timed token protocol. Ulm[Ulm82] studied the protocol proposed by Grow

and its performance characteristics. The effect of overheads was investigated and the perfor-

mance analysis was conducted with respect to various parameters, such as channel capacity,

network cable length and the number of nodes. Most of the research reported on the timed

token protocols was concerned with the FDDI token ring medium access control protocol since

the FDDI protocol was developed from the ideas of the timed token protocol proposed by