Efficient construction of directed Redundant Steiner trees

Multicast is getting increasingly popular to support critical business services such as IPTV, video conferencing and content distribution. To meet the stringent availability requirements, a highly fault resilient multicast infrastructure is critically important. Redundant Steiner trees (RST) are one mechanism for realizing such infrastructure. RSTs are a pair of Steiner trees that ensure that for any single link or node failure in the network, every destination node of a multicast connection is reachable from the source on at least one of these two trees. In this paper, we consider the problem of constructing optimal RSTs in a directed graph, which is NP-complete. In light of this, we propose a simple and efficient scheme to construct near-optimal RSTs. The scheme ensures an approximation ratio of 2k for general directed graphs, where k denotes the number of destination nodes. We compare the performance of our scheme with an linear program (LP) formulation of the problem that provides a lower bound on the optimal solution. Our simulations illustrate that our scheme constructs near optimal RSTs independent of the number of destination nodes and significantly outperforms other approaches proposed in prior literature.