A multicast routing tree repair algorithm

In this chapter, we propose an algorithm for rerouting multicast communications. The presented algorithm presents a trade-off between resource requirements and the level of protection when pre-planning rerouting. Given a network and a multicast group, we compute a single, pre-planned backup path for the multicast routing tree corresponding to the multicast group. The backup path is selected so that the number of group members dropped from the multicast communication if a single link of the network fails is minimized.

In Section 3.1, we model the network as a graph and the multicast group as a tree. In Section 3.2, we propose a graph algorithm that aims at computing the aforementioned backup path. Then, we propose extensions to our algorithm in order to update a backup path computed prior to changes in the multicast group, e.g. joining and leaving members. Finally, in Section 3.3, we determine the time complexity of the algorithms in the average case and the worst case.