Optimal Construction of Redundant Multicast Trees in Directed Graphs

In this paper, we consider the problem of protection of multi- cast connections against single link or node failures using redundant trees. Redundant trees connect the root of the multicast connection to all its destinations in such a way that in the event of a single link or node failure in the network, every destination node is still connected to the root node in at least one of the two trees. Construction of redundant trees has been studied extensively for undirected graphs, but not for directed graphs. Computing redundant trees in directed graphs can be important in networks, for instance, where link capacity is available in one direction, but not the other. Also, none of the schemes proposed in previous work provide a solution for finding optimal (minimal-cost) redundant trees even for weighted undirected graphs. We show that a whole class of earlier schemes that are based on the concept of ear-decomposition cannot find optimal redundant trees in certain network topologies. To our knowledge, we are the first to consider the problem of finding optimal redundant trees in directed graphs. We present a novel efficient scheme for construction of optimal redundant trees in networks modeled as weighted undirected as well as directed graphs.