Cycle-Time Properties of the Timed Token Medium Access Control Protocol.
AbstractWe investigate the timing properties of the timed token protocol that are necessary to guarantee synchronous message deadlines. A tighter upper bound on the elapse time between the token's lth arrival at any node i and its (l+v)th arrival at any node k is found. A formal proof to this generalized bound is presented.
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 that end-to-end deadline requirements are met. This motivates the use of medium
access control (MAC) communication protocols suitable 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 special timing property of bounded
time between any number of consecutive visits of the token to a node, which is necessary for
real-time communication, the timed token protocol becomes one of the most suitable and
attractive candidates for hard real-time applications. The timed token protocol has been
incorporated into many network standards including the Fiber Distributed Data Interface
IEEE 802.4, the High-Speed Data Bus (HSDB), the High-Speed Ring Bus (HSRB)
and the Survivable Adaptable Fiber Optic Enbedded Networks (SAFENET), which are used
as backbone networks in many embedded real-time applications [1].
The important concept of the timed token protocol was first proposed by Grow in [2] where
the framework (the basic idea) of the timed token protocol, adaptable to either a physical
or a logical ring, was described. Ulm [3] then studied the protocol proposed by Grow and
its performance characteristics. The timing properties of the timed token protocol were first
formally analyzed by Johnson and Sevcik in [4, 5] where it is shown that the average token
rotation time is bounded by the Target Token Rotation Time (TTRT ) and the maximum
token rotation time cannot exceed twice the TTRT . Chen et al [1, 6, 7, 8] made a detailed
study on the timing behavior of the timed token protocol and generalized the upper bound
derived by Johnson and Sevcik on the maximum token rotation time. That is, they extended
the upper bound on the time possibly elapsed between any two successive token's arrivals at a
node (i.e., the maximum token rotation time) to between any v (v is a positive integer no less
than two) successive token's arrivals at a node. Their general result is important for studies
on real-time communications in any network where the timed token protocol is employed,
and has already been used extensively by many researchers [1, 8, 9, 10, 11, 12, 13, 14, 15, 16]
in studying (analyzing) various kinds of synchronous bandwidth allocation (SBA) schemes.
Unfortunately, this general upper bound derived by Chen et al, although very important,
may not keep tight when v grows large enough, and consequently the SBA schemes previously
developed and analyzed based upon this general upper bound may not be as satisfactory as
they should be. Han et al [17] also derived a generalized Johnson and Sevcik's result, which
makes the previous results by Johnson and Sevcik and by Chen et al become special cases.
But, the result given by Han et al is almost the same, in nature, as (but not tighter than)
that first derived by Chen et al, for the upper bound on any number of successive token
arrivals to a particular node of the ring. Zhang and Burns [18, 19] investigated the inherent
timing properties of the timed token protocol and found, as a result, that the upper bound
derived by Chen et al can be replaced by a tighter one. Their generalized upper bound
expression, which is more complex than either of those derived by Chen et al and Han et al,
may produce a tighter upper bound when the number of successive token rotations becomes
large.
It should be noticed that exploring the inherent cycle-time properties of the timed token
MAC protocol is particularly important for research on hard real-time communication in any
timed token ring network. For example, a tighter upper bound on the time possibly elapsed
in the worst case between any given number of successive token's arrivals at a particular
node will lead to a derivation of a tighter (or larger) lower bound on the minimum available
time (that can be used by that node for transmission of real-time messages)
for any given length of time, which in turn brings a better chance (i.e., a larger possibility)
for real-time messages to be transmitted before their deadlines. Also, a generalized upper
bound on elapse time during any number of successive token visits between any two nodes
(say, the source node and the destination node) helps guarantee the end-to-end deadlines of
time-constrained messages to be transmitted between two network nodes.
In this report the derivation of a more generalized result on the cycle-time properties
of the timed token protocol is presented. Specifically, an upper bound on the elapse time
between the token's l th arrival at any node i and the token's (l th arrival at any node k
(where v can be any non-negative integer) is derived. The derived new result generalizes all
the previous findings on the cycle-time properties and is better than any previously published
result in the sense that it is more general and/or tighter.
The rest of this report is organized as follows: In Section 2 a description of the network
model is given. The timed token protocol is then briefly introduced in Section 3. The previous
results of related protocol timing properties is formally described in Section 4. In Section 5,
a concise formal proof to a new generalized result on the cycle-time properties is presented.
In Section 6 it is shown how the generalized result generalizes all the previous findings on
the cycle-time properties and why it is better than any of the existing results. An example
is given in Section 7 to show the importance of the generalized cycle-time property for hard
real-time communication with the timed token protocol. Finally, the report concludes with
Section 8.
Network Model
The network is assumed to consist of n nodes connected to form a logical ring and be free
from any hardware or software failures. A special bit pattern called the token, which grants
permission/right to its holder to transmit among the contending nodes, rotates around the
ring in a pre-determined order. The message transmission is controlled by the timed token
protocol. The node holding the token transmits its frames for as long as the protocol allows
then passes the token to its downstream neighbor 1 .
Let  i denote the maximum portion of the time which is unavailable for message transmission
between the token's arrival at node i and the token's immediately subsequent arrival
at node i's downstream neighbor (i.e., node i 1). That is,  i represents the sum of various
overheads possibly incurred during the above-mentioned time interval (between node i and
its downstream neighbor), which includes node bit delay, node latency buffer delay, media
propagation delay, and various protocol dependent overheads 2 . Then, the maximum fraction
of the time unavailable for message transmission during one complete token rotation,
denoted as  , can be expressed by the sum total of all above portions of time between every
two neighboring nodes, i.e.,
1 The downstream neighbor of node i is node i similarly, the upstream
neighbor of node i is node
Various overheads possibly involved have been identified by Johnson and Sevcik in [4, 5]. For example,
protocol dependent overheads include token capture delay, token transmission delay, etc.
3 Timed Token MAC Protocol
The basic ideas of the timed token protocol were first presented by Grow [2]. With this
protocol [20], messages are distinguished into two types: synchronous and asynchronous.
Synchronous messages, such as voice or video traffic, are periodic messages which come to
the system at regular intervals and have delivery time constraints. Asynchronous messages
are nonperiodic messages which have no time constraints.
In network initialization time, all nodes negotiate a common value for the TTRT , an
important protocol parameter which gives the expected token rotation time, since each node
has different synchronous transmission requirements to be satisfied. The TTRT should be
chosen small enough to meet responsiveness requirements of all nodes, i.e., the negotiated
value for TTRT should be fast enough to satisfy the most stringent response time requirements
of all nodes. Each node is assigned a fraction of the TTRT , known as its synchronous
bandwidth (denoted as H i for node i), which is the maximum amount of time for which the
node is allowed to transmit its synchronous messages every time it receives the token [1, 8].
Whenever a node receives the token, it first transmits its synchronous messages, if any, for
a time period up to its allocated synchronous bandwidth. The asynchronous messages can
then be sent (if any), but only if the token has rotated sufficiently fast that it arrives earlier
than expected since the token's last arrival at the same node. That is, synchronous traffic
is assigned a guaranteed bandwidth while the leftover bandwidth (unallocated, unused or
both) is dynamically shared among all the nodes for the asynchronous traffic.
Each node has two timers and one counter:
ffl Token Rotation Timer of node i (TRT i This timer is initialized to TTRT and is
always enabled. TRT i counts down until it either expires (i.e., TRT or the
token is received early (i.e., earlier than expected since the token's last arrival at node
i). In either situation, the TRT i is reinitialized to TTRT and enabled again (starting
the counting down process ).
ffl Late Counter of node i (LC i This counter is initialized to zero and used to record
the number of times that TRT i has expired since the token last arrived at node i. LC i
is incremented each time TRT i expires and is reset to zero whenever node i receives
the token. The token is said to arrive early at node i if LC i is zero when the token
arrives at node i. Otherwise, if LC i is one, the token is considered to be late 3 .
ffl Token Holding Timer of node i (THT i This timer is set to the current value of TRT i
on token's arrival at node i (only if the token arrives early). This timer also counts
down, but is enabled only during asynchronous transmission in order to control the
amount of time for which the node i can transmit asynchronous messages.
When the token arrives early at node i, the current value of TRT i is placed in THT i and
TRT i is then reset to TTRT . Synchronous frames, if any, can be transmitted for a time
not to exceed its allocated synchronous bandwidth (H i ). The node may then transmit its
asynchronous frames (if any) until THT i or TRT i expires (i.e., as long as both THT i and
TRT i are both greater than zero). On the other hand, when the token is late on its arrival
at node i (i.e., LC 1), the LC i is reset to zero. In this case, node i is still permitted to
synchronous frames for a time no more than H i but no asynchronous frames are
allowed to transmit. Refer to [2, 20, 21, 22] for a more detailed description of the timed
token protocol.
Due to inevitable overheads involved, the total bandwidth available for synchronous message
transmission during one complete traversal of the token around the ring is less than the
actual token rotation time. Because  forms part of the token rotation time which is unavailable
for message transmission and synchronous transmission with the guaranteed bandwidth
allocated precedes asynchronous transmission, it is clear that as a protocol constraint on the
allocation of synchronous bandwidth, the sum total of the synchronous bandwidths allocated
to all nodes in the ring should not exceed the available portion of the expected token rotation
time (i.e., TTRT ). That is,
The protocol constraint (1) is assumed to hold in the rest of this report.
3 To be exact, the token should be considered to be "not early" (which includes the case that the token
arrives on time) since the token could arrive at a node exactly when the Token Rotation Timer expires (for
the first time). But, for convenience/simplicity of presentation, "late" will be used instead of "not early" in
the situation that the token arrives when LC i
that no asynchronous transmission is allowed).
Timing Properties
In this section, a formal statement and a brief review of the previous relevant work on the
protocol timing property are given. In particular, the previous related results are presented
on the cycle-time properties of the timed token protocol, derived respectively by Johnson
and Sevcik [4, 5], Chen et al [1, 6], Han et al [17] and Zhang and Burns [19]. The following
notations are needed for a formal description of the related results.
t c;i the time when the token makes its c th arrival at node i.
d i (l) the time when the token makes its l th departure from node i, i.e., the time
when node i finishes the transmission of its synchronous and/or asynchronous
messages, if any, in the token's l th visit to node i and starts the transmission of
the token to its downstream neighbor [17].
c) the time difference between a reference time point d b (l) and the time when the
token departs from node i the c th time after d b (l) [17]. That is,
(2)
Theorem 1: (Johnson and Sevcik's Theorem [4, 5])
For any positive integer l and any node i (1  i  n), under the protocol constraint (1),
The above theorem was first formally proved by Johnson and Sevcik in [4, 5]. This
theorem shows a well-known fact that the maximum time that could possibly elapse between
any two successive token arrivals to a node is bounded by 2 \Delta TTRT . This result can be used
to obtain a lower bound on the minimum number of token visits to a node within any given
time interval. Unfortunately, the lower bound is not tight when the time interval is longer
than 3 \Delta TTRT [1]. Chen et al [6] made a detailed study on timing behavior of the timed
token protocol. As a result, they extended the previous result by Johnson and Sevcik on the
bounded token rotation time to a general one. In particular, they generalized the analysis
by Johnson and Sevcik to give an upper bound on the time possibly elapsed between any v
(v is a positive integer no less than two) consecutive token's arrivals at a particular node, in
which the previous result by Johnson and Sevcik becomes a special case when 2. Their
generalized theorem is re-stated as follows:
Theorem 2: (Generalised Johnson and Sevcik's Theorem by Chen et al [1, 6])
For any integer l  and any node i (1  i  n), under the protocol constraint (1),
The above general result is very important and has been extensively used by many
researchers [1, 8, 9, 10, 11, 12, 13, 14, 15, 16] in their studies on SBA schemes. However,
the generalized upper bound (on the time possibly elapsed in the worst case between any
successive token arrivals at a particular node) may not be tight when v
is absolutely true when
To obtain a protocol-parameter-based
upper bound (i.e., an upper bound that is a function of protocol parameters only) which
keep tight even when v  n+ 2 and
Zhang and Burns[19] enhanced
the previous work by Chen et al and derived another generalized upper bound expression
(as shown in Theorem 3 below) which is better than either of the upper bound expressions
first given by Chen et al and later derived by Han et al in the sense that their expression
may produce a tighter upper bound when v grows large. Their tighter upper bound can be
used to derive a better lower bound on the available transmission time for any given time
interval [19].
Theorem 3: (Generalised Johnson and Sevcik's Theorem by Zhang and Burns [19])
For any integer l  and any node i (1  i  n), under the protocol constraint (1),
al [17] also studied the cycle-time properties of the timed token MAC protocol,
and consequently derived a generalized upper bound on the elapse time between the token's
l th departure from node b and the token's (l th departure from node i, which makes the
previous results by Johnson and Sevcik [4, 5] and by Chen et al [1, 6] become special cases
of their result. But, for the elapse time of any given number of successive token arrivals to
a particular node, their more generalized upper bound is almost the same as (but no tighter
than) that first derived by Chen et al, although they are different in form of the derived upper
bound expressions. The following theorem shows their generalized upper bound expression.
Theorem 4: (Generalised Johnson and Sevcik's Theorem by Han et al [17])
For the timed-token MAC protocol, under the protocol constraint (1), for any l  1 and
c  1,
where
is subject to the definition of
shown below:
f
proof on the above generalized result can be found in [17] where it is shown how the
previous results by Johnson and Sevcik and by Chen et al become special cases of their result.
Although the upper bound expression derived by Han et al is more general, it may produce
an upper bound that is not as tight as that produced using the upper bound expression
given by Zhang and Burns (as shown in Theorem 3) on the elapse time between successive
token arrivals to a particular node, due to the fact that their upper-bound is the same as
that first derived by Chen et al on the time elapsed during any certain number of successive
token rotations. In this report a generalized result on the cycle-time properties of the timed
token MAC protocol will be derived. The generalized result is better than any previously
published (i.e., any of Theorems 1, 2, 3 and 4 above) in the sense that the upper bound
expression derived in this report is more general and/or tighter. This new generalized result
is shown by the following theorem whose formal proof is presented in the next section.
Theorem 5: (Generalised Johnson and Sevcik's Theorem)
For any integers l and v (l  nodes i and k (1  i  n; 1  k  n), if
under the protocol constraint (1),
\Delta@ n
where
is subject to the definition 4 of
shown below (where e and f are
f
Before formally proving Theorem 5, we need to define some terms and to show a lemma, as
given in the following subsection.
5.1 Preliminaries
The definitions of all the terms to be used later on are summarized in Table 1. For the
convenience of an easy comparison with and an easy understanding of similar studies, Some
of the notations adopted by Chen et al [6] and by Sevcik and Johnson [5] in their proofs on
the related timing properties are retained and quoted. Notes to some of the notations are
given below:
Token visits to nodes are indexed by a pair of subscripts, say, "c; i", where c and
indicate respectively the token cycle and the node being visited. That is, visit c; i
denotes the token's c th visit to node i. The following natural ordering will be frequently
used in the proofs later on: visit c; i is followed by visit c; or by visit
when the subscript pair c; used to denote the visit
before c; should be taken to be c \Gamma 1; n. Similarly, if
should be taken to be c + 1; 1. These pairs of index visits will also be used
in summations. For instance, the sum total of the quantity q for all the visits starting
with the token's j th visit to node k, and ending with the token's w th visit to node z,
4 Note that the definition of
in Theorem 5 is not exactly the same as that (defined by Han et
al [17]) in Theorem 4.

Table

1: Glossary of Terms
n The number of nodes on the ring.
TTRT The Target Token Rotation Time.
Synchronous bandwidth allocated to node i.
i The maximum amount of the time unavailable for message transmission between
the token's arrival at node i and the token's immediately subsequent arrival at
node i's downstream neighbor (i.e., node (i+1) ), i.e.,
The maximum amount of the time unavailable for message transmission (i.e., the
tightest upper bound on the sum total of various overheads possibly involved) in
one complete token rotation.
of subscripts used to index token's visit to nodes, c indicating the token
cycle and i indicating the node being visited. That is, c; i indexes the token's c th
visit to node i.
h c;i The time spent transmitting synchronous messages on the token's c th visit to node
a c;i The time spent transmitting asynchronous messages on the token's c th visit to
node i. 0  a c;i  TTRT \Gamma  .
c;i The overheads involved (which is unavailable for message transmission) between
the token's c th arrival at node i and the token's immediately subsequent arrival at
node i's downstream neighbor (i.e., node (i+1) ).
c;i The duration of the token's c th visit to node i, i.e., the sum of h c;i , a c;i and  c;i .
c;i The time spent in one complete token rotation ending with the token's c th visit to
node i, i.e., B
t c;i The time when the token makes its c th arrival at node i.
can be expressed as follows:
w;z
ffl Signs "=", "!", "", "?" and "" can be used to link two visits. "x; means
that visit x; y is the same as visit c; i (i.e., means that
visit x; y is earlier than visit c; i (in this case we also say visit x; y is before visit c; i).
"x; y  c; i" means that visit x; y is no later than visit c; i (i.e., either x;
Similarly, "x; y ? c; i" means that visit x; y is later than visit c; i; and
"x; y  c; i" means that visit x; y is no earlier than visit c; i.
ffl Let h c;i and a c;i respectively represent the times spent in transmitting synchronous
and asynchronous traffic on the token c th visit to node i, and let  c;i denote the various
overheads possibly involved (which is unavailable for message transmission) between
the token's c th arrival at node i and its immediately subsequent arrival at node i's
downstream neighbor (i.e., c th arrival at node i 1). Then the duration of the token's
c th visit to node i, denoted as v c;i , can be expressed as the sum of h c;i , a c;i and  c;i , i.e.,
Further, let B c;i be the length of a complete token rotation ending with its c th visit to
node i, we have,
c;i
Note that according to the timed token MAC protocol described in Section 3, each
node i can transmit its synchronous messages for a time interval at most up to its
assigned synchronous bandwidth H i , and can transmit its asynchronous messages only
up to the amount of time by which the token arrived early. So, for c  1 and 1  i  n,
a c;i  max(0;
Further, with this protocol, any node is not allowed to keep holding the token for more
than TTRT units of time. So, we have
a c;i
Combining (5) and (6) into one, we get
a c;i  min f
Because no nodes have messages, either synchronous or asynchronous,
to send during the immediately preceding token rotation ending with the visit
the maximum bandwidth possibly available for transmit asynchronous mes-
sages, according to (5) is bounded by TTRT \Gamma  .
ffl Similar to the definition of
shown in Theorem 5 (which represents the sum
of the allocated synchronous bandwidths of less than n successive nodes), we define
as the sum of various overheads incurred during less than n successive token
visits to nodes, as follows:
f
The following lemma is needed for the proof of Theorem 5.
Lemma 1: If the token is early on visit c; i (i.e., early on its c th arrival at node i), then
c;i
Proof: Since the token arrives at node i early on visit c; i, we have
Suppose that the token makes its c th arrival at node i earlier than expected by ffi
according to the timed token protocol, that
With (7) we obtain that
a c;i  minf
Thus, we get,
c;i
5.2 Proof of Theorem 5
Theorem 5: (Generalised Johnson and Sevcik's Theorem)
For any integers l and v (l  nodes i and k (1  i  n; 1  k  n), if
under the protocol constraint (1),
\Delta@ n
where
calculated according to the definition of
shown below (where
e and f are integers and " mod n" represents "modulo n" operation):
f
Proof: The time interval of t exactly corresponds visits from l; i inclusive to l +v; k
exclusive. There are two cases to consider:
1: The token is late on all visits from visit l; i inclusive to visit l
As the token is late on every visit, there is no asynchronous transmission. Thus, the time
elapsed during any complete token rotation, if any, is bounded by
. Since there
are totally (v inclusive and visit l +v; k exclusive (i.e., from
time t l;i to time t l+v;k ) and each token rotation consists of n successive visits, the number of
complete token rotations incurred in the above interval is given by
The remaining visits (which starts with node i and ends with node (k \Gamma 1), if any, is bounded
by
should be calculated according to the
definition of
shown in Theorem 5). Based on the above analysis, we have,
because  x;y   y ,
On the other hand, from the generalized upper-bound given in Theorem 5, we get the
following derivations:
\Delta@ n
\Delta@ n
\Delta@ n
(by the protocol constraint (1))
Clearly, Theorem 5 follows in this case with Inequalities (11) and (12).
2: There is at least one early visit from visit l; i inclusive to visit l
early visits in between visit l; i inclusive and visit l exclusive, subject to the following
conditions:
(a) for all s (1  s ! m),
(b) is the last early visit before visit l
(c) visit m) is the last early visit before visit p any.
The following observations can be made from the above definitions:
(A) From (a) above, we see that for 1  s ! m, between visit exclusive and visit
inclusive, there are at least (n+1) successive visits. It is easy to check
that there are totally v inclusive and visit l
exclusive, therefore, the maximum possible number of m is bounded by
From (b) above, we know that any visit between visit
if exists, is a late visit. That is, if any visit x; y, under
, is a late visit. Thus, asynchronous message transmission is
not allowed on visit x; y. So we have v
x;y=pm ;q m+1
x;y=pm ;q m+1
(C) Similar to (B) above, from (c) above, we know that any visit between visit
(l  s ! m) and visit p exclusive, if exists, is a late visit. Thus we
have, for l  s ! m,
x;y=ps ;q s+1
x;y=ps ;q s+1
(D) From the above definitions we see that if then there are no early visits
between visit l; i and visit inclusive. Hence, no asynchronous messages
are allowed to transmit on all these visits (if exist). So, if
(E) By Lemma 1 we see that whenever there is an early visit, the time possibly elapsed
during the (n visits ending with the early visit is bounded by TTRT
plus the synchronous bandwidth used and the amount of various overheads incurred
in this early visit. For the convenience of proof, this upper bound (on the elapse time
of (n successive visits) can be easily formed by supposing that the time elapsed
during the first n successive visits (that form one complete token rotation) is upper
bounded by TTRT and there is only synchronous transmission in the (n th visit.
Note that this is just a supposed equivalent situation (scenario) (and therefore it may
not match what happens in reality mostly), but it leads to the same upper-bound
as theoretically derived and help simplify the proof and help follow derivations to be
presented later.
It should be stressed here that we are interested in obtaining an upper bound on
the elapse time of (n visits ending with an early visit, and one such
upper bound can be obtained by using TTRT instead of the first n successive visits
(i.e., one complete token rotation) plus the synchronous bandwidth consumed and the
overhead incurred in the (n th (early) visit.
Note that replacing (removing) any n successive visits does not break the neighboring
relationship between nodes because any n successive visits make up one complete
token rotation. That is, the node corresponding to the visit immediately before these
visits and the node corresponding to the visit immediately after these n visits neighbor
each other (the latter is the immediately subsequent node of the former) although
these two corresponding visits are one-token-rotation apart. Realizing this is important
for understanding well the later derivations. In particular, according to the above
analysis and with the above definitions (a)-(c), we see that for any early visit
m), the node corresponding to visit and the
node corresponding to visit p s ; q s (i.e., node q s ) neighbor each other (since node q s is
the immediately subsequent node of node (q s \Gamma 1)). Here the removed n visits (that
are replaced by TTRT ) are visits between
Based upon how far the visit 1 is from the visit l; i, several different cases are
considered in the later derivations. The following analysis helps follow derivations in
different cases:
In this case, all (n successive token visits connected with all m early visits
(subject to the above definitions (a)-(c)), i.e., totally m \Theta (n+1) visits, fall within
the visits from l; i inclusive to l exclusive. According to (E) above, we see
that each one early visit
one replacement of n successive visits (i.e., one rotation)
by TTRT ". So, the final derived upper bound (on the elapse time from visit l; i
inclusive to visit l exclusive), for this case, should include "m \Delta TTRT ".
Further, since each early visit p s ; q s causes a removal of n visits (i.e., one
rotation) which is replaced by TTRT , the total number of the remaining visits
will be total number of all visits minus the number of removed visits, i.e., (v:n
that when seeking an upper bound for all these remaining
visits, we should only consider transmission of synchronous messages in any of
these remaining visits because any of these visits is either a late visit x; y (if x; y 6=
m) or has been assumed/supposed (in the imaginary equivalent
scenario where only synchronous transmission is considered (accounted for) in
the (n th visit of (n visits ending with an early visit (i.e., visit
analyzed in (E) above), for convenience of proof, (if x;
to the unbroken feature of neighboring relationship between nodes (whenever the
removal of n successive nodes happens) as analyzed in (E) above, these remaining
visits, if any, can be treated as q imaginary equivalent token rotations and r
remaining visits (where 0  r ! n) where
(v
Thus, the elapse time during the q equivalent token rotations (during either the
first or the last q visits of the remaining visits) is bounded by
because only synchronous transmission happens (or only the transmission of synchronous
messages is accounted) on any of these visits, as indicated in (E) above,
and the synchronous bandwidth actually used in any visit never exceeds the allocated
amount. Clearly, the above bound given in (17) should also be part of the
final derived upper-bound expression.
As for the r remaining visits, with the unbroken feature of neighboring relationship
between nodes, it is easy to check that the elapse time during r remaining
visits is bounded by
should also appear in the final expression

In this case, to simplify derivations of the proof, all the (n (from
inclusive to l are divided into the following two groups:
Group 1: visits from "
Group 2: visits from " l; i" to "
We now discuss the upper-bounds for visits in these two groups respectively.
For visits in Group 1, we can do exactly the same analysis as that adopted in
above. Since there are totally (m \Gamma 1) early visits (i.e., "p
and each of them is related to (n successive visits that fall into the
visits in Group 1, the final upper-bound expression (for Group 1) should include
". Because there are totally [(l visits in
Group 1 and among all these visits, (m\Gamma1) \Delta n visits are replaced by (m\Gamma1) \Delta TTRT ,
the number of remaining visits is
to above, we can now calculate q (the number of (imaginary) equivalent
rotations from the remaining visits) and r as follows:
ng \Gamma
(l
Similarly, the time possibly elapsed during the q equivalent rotations (i.e., q \Delta n
visits) is upper bounded by
(l
\Delta@ n
and r remaining visits can never exceed
Also, both of these
two bounds, together with " should appear in the final upper
bound expression for Group 1.
For visits in Group 2, by Lemma 1, we can easily find an upper bound on
the elapse time during all [(p visits (in this group) between
inclusive, as follows:
We further notice that visit l; i becomes the only visit in Group 2 when
According to the timed-token MAC protocol we see that the band-width
consumed in any single visit (say, visit x; y) for transmission of synchronous
and/or asynchronous messages, can never exceed TTRT (because by (7) we have
a x;y  TTRT \Gamma h x;y ). So the time elapsed in visit l; i (when
bounded by TTRT (and therefore by "T TRT
With the above definitions (a)-(c) and observations (A)-(F), we can now formally derive
the upper bound given in the above Theorem 5 as follows:
x;y=pm ;q m+1
x;y=pm ;q m+1
( by (14) and (15) of the observations [B] and [C] above )
since
( by (15) of the observation [C] above )
x;y=pm ;q m+1
m)
(by observation [E] above) if
(by observation [F] above) if l \Gamma
(by observation [F] above) if
because  x;y   y ,
\Delta@ n
( by (13) of the observation [A] above and the fact that the above
upper bound is an increasing function of m
From the above proof process, we see that the derived upper bound is independent of
the actual synchronous bandwidth used by each node, as long
as the protocol constraint (1) holds. That is, the bound still works even when h
some x; y. Realizing this fact is important for real-time communication with the timed token
protocol.
The generalized upper-bound expression (given in Theorem 5) is useful for determining
the worst-case delivery time of a real-time message (i.e., from its arrival at the source node
till its arrival at the destination node) and is therefore helpful for guaranteeing end-to-
end (application-to-application) deadline constraints (say, a synchronous message produced
by an application at the source node i will be sent to another application running at the
destination node k).
6 Comparison with Previous Results
In this section we shall show how the generalized result given in Theorem 5 generalizes all
the previous findings on the cycle-time properties of the timed token MAC protocol and why
the upper bound derived in this report is more general and/or tighter than any of existing
results (upper bounds) shown in Theorems 1-4.
To achieve an effective comparison of related results, we shall only compare the generalized
upper bound expression with that derived by Zhang and Burns (see Theorem
the case of successive token arrivals to a particular node) and with that derived by Han et
al (see Theorem 4) for a more generalized case of any number of successive visits in between
any two network nodes. This approach is taken because in [18, 19] Zhang and Burns have
demonstrated how the previous findings by Johnson and Sevcik (see Theorem 1) becomes a
special case of their generalized result and why their generalized upper bound is tighter than
that derived by Chen et al (see Theorem 2) when the number of consecutive token rotations
grows large enough under
in [17] Han et al have shown how their
result generalizes the previous results by Johnson and Sevcik and by Chen et al.
(1) Comparing Theorem 5 with Theorem 3
It is easy to show that Theorem 5 becomes Theorem 3 when Theorem 5 we
get, when the following derivations:
\Delta@ n
(since d v \Deltan
c)
That is,
This is the same result as that shown in Theorem 3 and can be re-stated in exactly the same
form as the upper bound expression of Theorem 3 where it is assumed that v  2.
(2) Comparing Theorem 5 with Theorem 4
The following lemma is needed for comparison of Theorems 4 and 5.
Lemma 2 For any two visits "l (where l and v are
any integers subject to l  1 and v  0; and i and k are any two nodes, 1  i  n and
So we get
0 and
Consider the following two cases:
Case 1: if since in this case, we have 1  k  i  n)
In this case, Lemma 2 follows under the following facts:
d
Case 2: if since in this case, we have 1
In this case we have:
and
Clearly, Lemma 2 also follows in this case. 2
To show that the generalized upper bound given in Theorem 5 is tighter than that derived
by Han et al (given in Theorem 4), we can relax the generalized upper bound (of Theorem
as follows:
\Delta@ n
(by (18) of Lemma 2 and
That is,
As will be shown below, even the above relaxed upper bound (given by (20)) is still
tighter than that derived by Han et al. To enable comparison, we need to represent
(exactly according to the definition of \Delta b;i (l; c), given by Han et al [17]) using the notation
t c;i defined in this report. For simplicity, let ' be the delay between the departure of the
token from any node i and its immediate arrival to the downstream neighbor of node i (i.e.,
node (i 1)). So we have
Further, with (21) and from the definition of \Delta b;i (l; c) (see (2) in Section 4), we can do the
following conversions:
From the above converted equivalent result and with the relaxed upper bound (20), we
can go on to obtain an upper bound for \Delta b;i (l; c) as follows:
(b
(b
(b
(b
(b
(by (20))
c
c
c
(by using
defined in Theorem 5)
On the other hand, according to Theorem 4, we have,
Comparing the each upper bound (obtained from Theorem 4) of each case with those of
its corresponding cases (obtained from the relaxed upper bound (20)), we see clearly that
Theorem 5 can produce a tighter upper bound (for \Delta b;i (l; c)) than that given by Theorem 4.
7 An Example
In this section a simple example is given to show the importance of the new generalized
cycle-time property for distributed real-time applications.
Consider a network (that supports the timed token protocol) with three nodes (numbered
1,2,3). Assume that each node i n) has a periodic/synchronous message stream S i
characterized by a period P i , a maximum transmission time C i and a relative deadline D i .
Messages from stream S i arrive at regular intervals with period P i and have deadlines D i
by which they must be received by the destination node (i.e., if a message from S i of source
node i arrives at time t, it must completely be received by the destination node k (k 6= i)
Assume that the token circulates around the ring from node 1 to nodes 2,
3, and then back to node 1 again to repeat the order, and that messages from source nodes
are sent respectively to destination nodes 3, 3 and 1. Parameters of synchronous
messages (for all three message streams), together with the synchronous bandwidth (H i )
allocated to each node i on the network, are listed in Table 2. To simplify calculation we
also assume that

Table

2: Message and Network Parameters
Clearly, the given allocation of synchronous bandwidths satisfies the protocol constraint
(1) (since
We shall check below if
the given setting of network parameters (i.e., H 1 , H 2 , H 3 , TTRT and ) can ensure that
all synchronous messages will arrive at their destination nodes before their deadlines, by
respectively using the new generalized cycle-time property (Theorem 5) and that previously
derived by Han et al (Theorem 4). As will be clear, all message deadlines, which can be
guaranteed when judged with Theorem 5, are wrongly judged with Theorem 4 as failing to
be guaranteed. The reason for this is the worst-case message response time for a message
in source node i to reach destination node k (defined as the longest possible time from
the instant of the message being available for transmission at source node i till the instant
when the whole message arrives at the destination node k), denoted as R(i; k), could be
much different when calculated with Theorems 4 and 5 respectively. The value of R(i;
calculated with Theorem 5 could be much shorter than that obtained with Theorem 4.
(v; be the time difference between a reference time point t l;i (the token's l th
arrival at node i) and the time when the token arrives at node k the v th time after t l;i . Assume
a synchronous message from S i comes to the transmitting buffer of node i immediately after
some time t l;i . That is, at time t l;i , there is not a synchronous message waiting to be
sent in the transmitting buffer of node i and thus the transmission right (token) is either
internally passed to asynchronous transmission at the same node i (if the token is early on
visit l; i and there is asynchronous traffic waiting to be sent) or externally forwarded to the
subsequent node (i.e., node i 1). But just at that moment when the transmission right
(token) is internally passed or externally forwarded, the message arrives and becomes ready
for transmission. This is actually the worst case situation for transmission of a message from
because the message misses the first chance of being transmitted on visit l; i. Because C i
units of time are needed for transmission of a whole message from S i and node i can use at
most H i time units for transmitting synchronous messages whenever it receives the token, a
total of dC i =H i e times' token arrivals is expected in order to finish transmission of the whole
message that is divided into dC i =H i e frames (to be transmitted separately on each of token
arrivals). Since the message misses the first chance at time t l;i in the worst case, we can
estimate R(i; k) by calculating the time difference between t l;i and the token's (dC i =H i e+1) th
arrival at the destination node k (because the token is appended to all transmitted and/or
forwarded messages, according to the timed token MAC protocol), as follows:
(d C i
To facilitate the calculation of R(i; Theorems 4 and 5, we convert T t l;i
(v;
(exactly according to its definition) to the following equivalent forms:
(for use with Theorem 5) (23)
use with Theorem
With (22), (23), (24), and message and network parameters shown in Table 2, we can
now calculate R(1; 3) according to Theorems 4 and 5 respectively as follows:
ffl Based upon Theorem 4,
(d C1
Theorem
Thus, i.e., the time possibly elapsed in the worst case
before the last frame of a whole message from S i reaches the destination node k is
larger than the required deadline. That is, the message deadline (of stream
when judged with Theorem 4. However, as will be shown next, this is not the case.
ffl Based upon Theorem 5,
(d
d
d C1
(b
e
e
(by Theorem 5)
d
d 150
Thus, That is, the message deadline (of stream S 1 ) can be
guaranteed when judged with Theorem 5.
Similar to the calculation of R(1; above, we can calculate R(2; 3) and R(3; 1), and
otain the following results (interested readers can check this themselves):
ffl Based on Theorem 4: R(2;
ffl Based on Theorem 5: R(2;
From the above analysis we see that message deadlines are misjudged as failing to be
guaranteed (for every synchronous message stream examined) when based upon Theorem
4 although in fact no synchronous messages will miss their deadlines when judged with
Theorem 5.
Because R(i; calculated with Theorem 5 could be much shorter than that calculated
with Theorem 4, using the new generalized result (Theorem 5) instead of the previous one
(Theorem substantially increase the chance for synchronous message deadlines to be
guaranteed.
8 Conclusion
The key to success in using a distributed system for real-time application is the timely execution
of computational tasks that usually reside on different nodes and communicate with
one another to accomplish a common goal. End-to-end deadline guarantees are impossible
without a communication network that supports the timely delivery of inter-task messages.
The timed token ring networks such as FDDI are suitable for distributed real-time application
due to its inherent timing property of bounded elapse time between any number of
successive token rotations.
In this report a concise formal proof to a generalized result on the cycle-time properties of
the timed token MAC protocol has been presented for the first time. In particular, an upper
bound on the elapse time from the token's l th arrival at any node i till the token's (l th
arrival at any node k (where v is a non-negative integer), is derived. The generalized upper
bound expression, which is particularly important for studies on real-time communications
in any timed token ring network, is better than any of previous related findings on the cycle-time
properties due to the fact that it is more general and may produce a tighter upper
bound.



--R

"Guaranteeing synchronous message deadlines with the timed token medium access control protocol,"
"A Timed Token Protocol for Local Area Networks,"
"A Timed Token Ring Local Area Network and its Performance Characteristics,"
"Proof that Timing Requirements of the FDDI Token Ring Protocol are Satisfied,"
"Cycle Time Properties of the FDDI Token Ring Protocol,"
"Properties of the Timed Token Protocol,"
"Guaranteeing Synchronous Message Deadlines with the Timed Token Protocol,"
"Optimal synchronous capacity allocation for hard real-time communications with the timed token protocol,"
"Local synchronous capacity allocation schemes for guaranteeing message deadlines with the timed token protocol,"
"Selection of timed token parameters to guarantee message deadlines,"
"Deferring Real-Time Traffic for Improved Non-Real-Time Communication in FDDI Networks,"
"Performance Evaluation of a Bandwidth Allocation Scheme for Guaranteeing Synchronous Messages with Arbitrary Deadlines in an FDDI Net- work,"
"Transmitting time-dependent multimedia data in FDDI net- works,"
"Guaranteeing Synchronous Messages with Arbitrary Deadline Constraints in an FDDI Network,"
"The Timed-Token Protocol for Real-Time Communications,"
"Synchronous Bandwidth Allocation in FDDI Networks,"
"On non-existence of optimal local synchronous bandwidth allocation schemes,"
"Timing Properties of the Timed Token Protocol,"
"An optimal synchronous bandwidth allocation scheme for guaranteeing synchronous message deadlines with the timed-token MAC protocol,"
Fibre Distributed Data Interface Ring Media Access Control (MAC)
FDDI Handbook - High-Speed Networking Using Fiber and Other Media
--TR

--CTR
Sijing Zhang , Alan Burns , Jing Chen , E. Stewart Lee, Hard Real-Time Communication with the Timed Token Protocol: Current State and Challenging Problems, Real-Time Systems, v.27 n.3, p.271-295, September 2004
timed token medium access control MAC protocol;real-time communications;FDDI networks;protocol timing properties;timed token networks