next up previous contents
Next: A multicast routing tree Up: Resilience and protection in Previous: MPLS Unicast Fast Reroute   Contents


Multicast fault recovery


Unicast rerouting mechanisms can protect multicast routing trees from link failures by setting up a backup path from each group member to the core of a core based tree or the source of a shortest path tree. Protecting multicast routing trees from link failures requires to compute, advertise and reserve bandwidth for many unicast backup paths, some of them possibly having links in common and therefore leading to link capacity wastes if bandwidth is reserved on the backup paths. A few rerouting mechanisms applicable to ATM or MPLS that take multicasting into account have been proposed in the literature.


In [43], an algorithm that builds a primary and a backup tree at the same time is presented. The algorithm minimizes the bandwidth that is used by the primary and the backup paths. The algorithm selects in turn every member of the group, starting with the source (in the case of shortest path trees) or center (in the case of center-based trees). For each member, two disjoint paths from the source or center to this member that respect certain resource availability properties are computed. One path is inserted in the primary tree and the other in the backup tree. Bandwidth used by the trees is minimized. However, since a backup path protects the tree for all possible link failures, the total bandwidth that should be reserved for the backup tree is the same as the bandwidth reserved for the primary tree. Similar algorithms that do not take bandwidth utilization into consideration but also build a primary and a backup tree simultaneously are discussed in [40] and [47].

In [69], the authors introduce an online mechanism able to repair ATM multicast routing trees. When a failure occurs in an ATM multicast routing tree, the multicast routing tree is split into two smaller trees, $T_1$ and $T_2$. One of these smaller trees $T_1$ contains the source or center of the tree, and the other $T_2$ is the tree rooted at the switch $S$ downstream of the failed link with regards to the source or center of the tree. When $S$ detects the link failure, $S$ sends a failure notification message that contains its unique switch identifier to all of its neighbors. Each neighbor forwards in turn the notification message to its own neighbors and so on, thus flooding the network with the notification message. The first switch $S'$ of $T_1$ that receives the notification message replies to $S$ in order to set up a backup path between itself and $S$. A candidate backup path is the path taken by the notification message from $S$ to $S'$, but any other path between $S$ and $S'$ can be chosen as a backup path. This backup path is inserted in the multicast routing tree such that $S$ becomes a downstream node or child of $S'$ in the reconfigured multicast routing tree. As expected, this mechanism compares well compared with IP rerouting but poorly compared with SONET, since the backup path is computed online instead of being pre-planned. According to the simulations in [69], this mechanism can repair multicast routing trees in 400 ms. The advantage of this ATM multicast routing tree rerouting mechanism is that it repairs a tree with a single backup path.

Current multicast rerouting mechanisms protect multicast groups from any link failure. As a result many backup paths must be computed, advertised and bandwidth must be allocated for the backup traffic which will use the backup paths only on a link failure. In this thesis, we consider the case where CPU and bandwidth resources are sparse, and assume that only one backup path is deployed in a multicast routing tree. In the next section, we develop an algorithm that computes this backup path.


next up previous contents
Next: A multicast routing tree Up: Resilience and protection in Previous: MPLS Unicast Fast Reroute   Contents
Yvan Pointurier 2002-08-11