Design and evaluation of routing schemes for dependable real-time connections

Dependability of service (DoS) has become an important requirement for real-time applications, such as remote medical services, business-critical network meetings and command-and-control applications. The Dependable Real-Time Protocol (DRTP), in which each dependable real-time connection is realized with one primary and one or more backup channels, has been shown to be an effective way of providing DoS. How to route both primary and backup channels for each dependable real-time connection is of vital importance to the success of failure recovery and to overhead reduction in providing DoS. In this paper, we propose and evaluate three different schemes for routing the primary and backup channels of each dependable real-time connection. Specifically, we present methods based on link-state information and bounded flooding to discover routes for the primary and backup channels while satisfying the required quality of service (QoS). The costs of the link-state and flooding algorithms are reduced significantly by using the fact that the probability of success in failure recovery can be estimated with simple link-state information, and by bounding the flooded region within an ellipse with the two communication end-points as loci. Our in-depth simulations have shown that the proposed routing schemes are highly effective, providing a fault tolerance of 87% or higher with a network capacity overhead of less than 85%.