Consider an MPLS network over which a multicast routing tree has been established, as shown in Figure 1.12. An MPLS network receives traffic directly from multicast hosts attached to MPLS routers, or from networks which simply relay multicast traffic from other multicast hosts. When a link of the multicast routing tree fails, a certain number of multicast hosts accessing the tree directly or through other networks are dropped from the communication. In this thesis, we present an algorithm which aims at selecting one backup path in a given multicast routing tree to improve the resilience of the tree for a single link failure. The backup path selected by the algorithm minimizes the number of group members dropped from a multicast communication on a single link failure. We provide a specification, complexity analysis and implementation of the algorithm.
Our second contribution is the addition of multicast support to the Linux implementation of MPLS. A unicast implementation of MPLS is available for the Linux operating system, but MPLS multicast is barely standardized and no implementation is available at the time of this writing. We also provide the definition and implementation of the signaling protocol needed to establish multicast LSPs in an MPLS network. Our signaling protocol implements Explicit Routing to establish multicast LSPs. Any MPLS router or alternatively a dedicated server can establish mLSPs.
Our third contribution is the design and implementation of an MPLS multicast rerouting mechanism, MPLS multicast Fast Reroute. MPLS multicast Fast Reroute is an extension to MPLS Fast Reroute , a unicast MPLS unicast rerouting mechanism. We provide a description and the implementation of both the MPLS multicast Fast Reroute mechanism itself and the signaling protocol extensions necessary to support the rerouting mechanisms. Although our implementation of MPLS multicast Fast Reroute runs over off-the-shelf Linux PC-routers, it can reroute multicast traffic in less than 50 ms (without propagation delay) depending on the size of the tree, thus making link failures unnoticeable to users of multicast applications like teleconferencing.
The remainder of this thesis is structured as follows. In Chapter 2, we present techniques to protect networks from link failures. These techniques range from mechanisms implemented in the physical layer to a traffic engineering mechanism specific to MPLS unicast. In Chapter 3, we propose a graph algorithm that builds a particular backup path that minimizes the number of group members dropped from a multicast communication on a single link failure. In Chapter 4, we present MPLS Multicast Fast Reroute, an extension to MPLS that implements rerouting in multicast routing trees and makes use of the backup path computed in Chapter 3. In Chapter 5, we show how to add multicast support to a unicast implementation of MPLS using PC hardware and the Linux operating system. Then, we define the signaling protocol required to implement MPLS Fast Reroute, and describe our implementation of MPLS Multicast Fast Reroute. In Chapter 6, we present experiments which show how MPLS Multicast Fast Reroute compares with traditional rerouting techniques.