Real-Time Communications in FDDI Networks and Dual-Bus Networks
Graduate student: Kar Shun Tsoi
Faculty: Ching-Chih Han and Chao-Ju Jennifer Hou
Sponsors: Wisconsin Alumni Research Foundation
(WARF) under Grants 135-2080 and Vilas Fellowship Award
Local synchronous bandwidth allocation schemes use only information
available locally to each node,
and are thus preferred to global schemes in terms of their
lower network-management overhead.
If local schemes which give optimal bandwidth allocation
solutions (if any) can be devised, they will be
superior to their global counterparts both in the performance
and in the network management aspect.
We formally prove, using the technique of adversary argument,
that there does not exist any optimal local synchronous
bandwidth allocation scheme.
In conjunction with the proof of the non-existence of optimal local
schemes, we also derive several timing
properties that generalize the contemporary findings about the
cycle-time properties of the MAC protocol.
In particular, we derive the upper bound of the time
between the token's l-th departure from node b and
the token's (l+c)-th departure from node i.
(The previous results by Johnson et al.
and by Agrawal et al. become special cases of our result.)
Finally, complementary to the non-existence proof,
we devise an optimal global synchronous bandwidth allocation scheme
(of polynomial time complexity).
We establish a formal basis for allocating pre-arbitrated slots to a set of
isochronous message streams in dual-bus networks and devise an
effective static slot allocation scheme which
ensures that all isochronous messages are delivered before their
deadlines at system initialization as long as the message set
satisfies certain schedulability condition.
We then propose a dynamic slot allocation scheme to
dynamically establish/terminate a message stream and adjust
the slot allocation schedule, in response to call setup and clear
requests.
We also address on how to improve the performance of the proposed
slot allocation schemes (in terms of bandwidth utilization)
using the concept of slot reuse.
We devise several slot reuse schemes to assign spatially
non-intersecting message streams to share the same virtual connections
(i.e., the same set of pre-arbitrated slots identified by the VCI numbers).
The slot reuse schemes devised are simple, and can be easily
incorporated into the proposed slot allocation schemes.
Finally, we investigate the implementation details of the proposed
slot allocation schemes with the objective that the resulting
implementation shall be simple, feasible, and effective.
FDDI Networks
We consider how to tailor the timed-token medium
access control (MAC) protocol for real-time applications.
One of the key issues is to devise an effective synchronous bandwidth
allocation scheme to meet both the protocol and deadline constraints.
Either local or global information can be used in a synchronous
bandwidth allocation scheme to derive solutions.
Dual Bus Networks
We consider the issue of guaranteeing the timely
delivery of isochronous messages with hard deadlines in a
dual-bus network network.
The dual-bus network under consideration is general enough
to accommodate several MAC schemes suggested for this topology, e.g.,
DQDB, Fasnet, CRMA, and
Simple, to name a few.
Return
to Project Home Page
Date last modified -- September 15, 1996
Direct comments concerning this WWW site to:
jhou@ece.osu.edu