Networking in distributed real-time systems.

Abstract

Distributed computing systems are increasingly being used for many critical real-time applications. In these systems, large or unpredictable delays in the delivery of messages can adversely affect the execution of tasks dependent on these messages. Consequently, there are usually deadlines associated with messages between cooperating processes. The goal of this dissertation is to design and develop a communication scheme for a distributed real-time system which guarantees the delivery of messages within certain deadline constraints. We are particularly interested in systems with partially connected point-to-point interconnection networks, mainly due to their potential for high performance and fault tolerance. This dissertation also presents solutions to several other important problems related to communication in systems with this type of interconnection. We first present an abstraction called a real-time channel which provides a mechanism for expressing the timing constraints and other requirements for inter-process communication. We develop methods to compute worst-case delays and buffer space requirements for messages belonging to real-time channels, so that their delivery time can be guaranteed. Following this, we deal with the problem of routing in networks with virtual cut-through switching. In this mode of switching, the message delivery delay depends upon the number of times that a message gets buffered at intermediate nodes on the route. We develop algorithms to select routes that balance the network load and minimize the number of times that a message gets buffered. To increase the efficiency of broadcasting, which is an important issue in point-to-point networks, we develop a broadcast primitive that can be easily integrated into the switching hardware. Using this primitive, we then develop a family of algorithms for broadcasting in mesh-connected networks. These algorithms ensure reliable delivery in the presence of possibly unknown network failures. Finally, we present the design and implementation of a communication subsystem for HARTS, which is an experimental distributed real-time system being developed in the Real-Time Computing Laboratory. This subsystem makes use of a communication coprocessor to offload communication overheads from the main processors. Among other things, it supports real-time channels and provides a global time-base for the system.