language: en

Real-time Communication in Multi-hop Networks

Dilip D. Kandlur, Kang G. Shin
Real-Time Computing Laboratory Department of Elec. Engr. and Computer Science The University of Michigan
Ann Arbor, Michigan 48109-2122.
email: kgshin@alps.eecs.umich.edu
Domenico Ferrari
Computer Science Division EE & CS Department University of California
Berkeley, CA 94720.

ABSTRACT Communication in real-time systems has to be predictable, because unpredictable delays in the delivery of messages can adversely affect the execution of tasks dependent on these messages. In this paper, we develop a scheme for providing predictable inter-process communication in real-time systems with (partially connected) point-to-point interconnection networks, which provides guarantees on the maximum delivery time for messages. This scheme is based on the concept of a real-time channel, a unidirectional connection between source and destination. A real-time channel has parameters which describe the performance requirements of the source-destination communication, e.g., from a sensor station to a control site. Once such a channel is established, the communications subsystem guarantees that these performance requirements will be met. In this paper, we concentrate on methods to compute guarantees for the delivery time of messages belonging to real-time channels. We also address problems associated with allocating buffers for these messages and develop a scheme which preserves delivery time guarantees.

Index Terms | Real-time systems, communication, scheduling, guaranteed delay, point-to-point networks.

[The work reported here is supported in part by an IBM Graduate Fellowship and by the Office of Naval Research under Contract N00014-85-K-0122. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.]