Delivery of time-critical messages using a multiple copy approach

Reviewer: Steven K. Andrianoff

The reliable and timely delivery of time-critical messages in a distributed real-time system is addressed. Ramanathan and Shin propose a scheme that sends multiple copies of messages along disjoint routes in the network. In particular, their scheme addresses the problem of messages missing their delivery deadlines due to congestion in a point-to-point interconnection topology. The problem with a multiple copy approach is that the additional messages increase the network load, which in turn increases the likelihood that critical messages will miss their deadlines. The authors develop a heuristic for determining the number of copies of a message to be sent that depends on how critical the message is, the number of hops the message must traverse, and the deadline of the message. This number is determined in such a way as to minimize the expected cost of messages missing their deadlines. The authors describe the results of applying their method in a C-wrapped hexagonal mesh. They compare analytic results obtained using their heuristic with results of simulation runs that avoid some of the simplifying assumptions. Both the analytic and the simulation results show a substantial decrease in the expected cost compared to the single-copy approach. The details of the authors' technique are presented clearly. The paper includes a valuable discussion of the assumptions made in the development of their system model. Finally, they provide enough supporting evidence for their claims about the benefits of their method.