(A) splitting multiaccess protocol and its application to time-constrained message communication

Abstract

A class of real-time multiaccess protocol is investigated in order to achieve the basic goal of fault-free and timely transmission for distributed hard realtime applications. Traditional time window protocol has desirable features such as channel access control based on message arrival times and the best throughput among known contention algorithms. However, the time window protocol is unfortunately subject to deadlock which is a serious drawback for hard real-time communication. In this thesis, a deadlock free window protocol, called limited splitting algorithm, is proposed and generalized to real-time multiaccess scheduling with static and dynamic priority scheduling policies. The limited splitting algorithm limits total number of window splitting and uses a probabilistic retransmission scheme for deadlock resolution. In this way, the limited splitting algorithm can be deadlock free from various deadlock conditions, either noisy feedback or a simultaneous arrival of messages, with little degradation of maximally achievable throughput. The performance of the limited splitting algorithm is evaluated according to the maximal throughput under a Poisson infinite-user model. In addition to its traditional role as a channel access protocol, the limited splitting algorithm is generalized for distributed real-time scheduling by explicitly imposing a network-wide transmission order on all message according to their time constraints. The real-time multiaccess scheduling problem arises messages with hard deadlines must communicate over a single multiaccess channel. The desirable features of our real-time multiaccess protocol are the usage of the time constraint of messages to determine channel access right and correct operation in spite of those deadlock conditions. The performances of the real-time scheduling policies have been studied by simulation method and the results show that, the real-time multiaccess protocol performs well according to the well known real-time s...