Optimal Construction of Redundant Multicast Trees in Directed Graphs

In this paper, we consider the problem of protection of multicast connections against single link or node failures using redundant multicast trees (RMTs). RMTs connect the source node of a 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 source node in at least one of the two trees. Construction of RMTs has been studied extensively for undirected graphs, but not for directed graphs. Computing RMTs 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) RMTs 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 RMTs in directed graphs. We present a novel efficient scheme for construction of optimal RMTs in networks modeled as weighted undirected as well as directed graphs.