A multiple copy approach for delivering messages under deadline constraints

Abstract

A scheme to minimize the expected recovery cost incurred by a distributed real-time system as a result of messages failing to meet their deadline is proposed. The scheme is intended for distributed systems with point-to-point interconnection topology. The goal of minimizing the expected cost is achieved by sending multiple copies of a message through disjoint routes, thus increasing the probability of successful message delivery within the deadline. The number of copies of each message to be sent is determined by optimizing the tradeoff between the increase in the message traffic due to additional copies and the decrease in the probability of a message missing its deadline. The objective used to determine the optimal number of copies is formalized, and a numerical example is presented, showing that reductions of more than 70% can be achieved at low to moderate loads. At high loads the reductions are in the range of 10-40%.