Overview

Before we give an overview of the multicast extensions to MPLS Fast Reroute, we introduce multicast LSPs (mLSPs), which are the multicast counterpart to unicast Label Switching Paths. Different from other virtual circuit switching techniques like ATM, MPLS is able to create virtual circuits that map multicast routing trees without the need of establishing a distinct virtual circuit between a particular node and all multicast hosts of a multicast group.

A multicast LSP (mLSP) is a point-to-multipoint MPLS virtual circuit. Packets are forwarded on mLSPs the same way as they are forwarded on unicast LSPs, except that they can be duplicated by MPLS routers and forwarded on several links. Like unicast LSPs, mLSPs are virtual circuits. Therefore, a mLSP must be established before a multicast communication can actually take place and terminated when the communication is over. Such tasks are performed by a signaling protocol. In MPLS networks, LSPs are associated with FECs. Packets that enter an MPLS network are assigned to a FEC and all packets from the same FEC entering in the network via the same ingress LER are forwarded on the same LSP. The FEC associated to a multicast LSP is the IP address of the multicast group whose traffic is carried by the mLSP.

Figure 4.1: Multicast Label Switching Path examples.

In Section 1.3, we introduced the notion of shortest path tree and core based tree. Consider Figure 4.1(a) which depicts a shortest path tree spanning over an MPLS network. The source of the tree is $A$. Node $A$ receives traffic from other networks (not represented) and sends this traffic over the multicast routing tree. Leaves of the tree, $B$ and $C$, receive the multicast traffic sent by $A$ over the tree. A shortest path tree is mapped by a unidirectional LSP where label mappings are established on each link of the tree in a single direction. For instance, the mLSP represented in Figure 4.1(b) maps the shortest path tree. Suppose that node $A$ receives packets that must be forwarded over the tree. Node $A$ pushes label ``1'' on the packets and forwards these packets to $D$. Node $A$ is an ingress LER of the mLSP. Then, node $D$ duplicates the packets and swaps the label of one of the two copies first with label ``2'', then with label ``3''. Node $D$ forwards the packets labeled ``2'' to $B$ and the packets labeled ``3'' to $C$. Node $D$ is therefore a LSR of the mLSP. Node $B$ pops labels from packets labeled ``2'' coming from $D$ and node $C$ pops labels from packets labeled ``3'' coming from $D$. Nodes $B$ and $C$ are egress LERs of the mLSP.

On the other hand, core based trees allow any multiple sources to send data to the members of a multicast group. It is possible to map a core based tree of $n$ sources with $n$ unidirectional mLSPs. Each of the unidirectional mLSPs would map a tree rooted at one of the $n$ different sources. However, the main advantage of core based trees is that a single tree is shared by all sources. We introduce the notion of bidirectional mLSP where label mappings are established on each link of the tree in both directions, assuming that all links of the tree are bidirectional. For instance, consider the core based tree represented in Figure 4.1(c), where node $D$ is the core and nodes $A$, $B$, $C$ are the sources . This core based tree is mapped by the single bidirectional mLSP represented in Figure 4.1(d). Node $A$ pushes label ``1'' on packets bound to the multicast group. Node $D$ swaps label ``1'' against labels ``2'' and ``3'' and forwards packets labeled ``2'' to $B$ and packets labeled ``3'' to $C$. Node $B$ pops label ``2'' and node $C$ pops label ``3''. If node $B$ is a source of the multicast group, then when node $B$ needs to send packets to the multicast group it pushes label ``4'' on the transmitted packets. Node $D$ swaps label ``4'' against labels ``5'' and ``3'', and node $A$ pops label ``5'' while $C$ pops ``3''. If node $C$ is a source of the multicast group, node $C$ pushes label ``6'' on packets bound to the group, node $D$ swaps label ``6'' against labels ``5'' and ``2'', node $A$ pops label ``6'' and node $B$ pops label ``2''. Since $A$, $B$ and $C$ both push and pop labels for packets of the bidirectional mLSP, they are ingress and egress LERs at the same time. Node $D$ is a LSR of the bidirectional mLSP. In the remainder of this thesis, we only consider core based trees mapped by bidirectional mLSPs.

Figure 4.2: Overview of MPLS multicast Fast Reroute.

We now give an overview of MPLS Multicast Fast Reroute, the multicast extension to the MPLS Fast Reroute mechanism described in Section 2.4. We discuss an example that illustrates each step of MPLS Multicast Fast Reroute. The example is illustrated in Figure 4.2.

MPLS multicast Fast Reroute is a pre-planned rerouting mechanism. This means that a backup path is computed and advertised before rerouting is performed. A backup path is computed with Algorithm 1 presented in Chapter 3. However, the choice of the algorithm and the rerouting mechanism are orthogonal. In the following, we do not make any assumption on how the backup path is computed. We continue to use here the notations introduced in Chapter 3.

Consider the tree rooted at $S$ mapped by the bidirectional mLSP depicted in Figure 4.2(a). A backup path $BP_{A, B}$ has been computed between nodes $A$ and $B$ and the protected path $PP_{A, B}$ is constituted by links $AD$, $DC$, $CS'$, $S'H$ and $HB$. Node $S'$ is defined as the Least Common Ancestor of $A$ and $B$ with regards to $S$. In this example, since $S$ belongs to the protected path between $A$ and $B$, then $S'=S$. MPLS multicast Fast Reroute can repair the multicast routing tree if any of these five links fails. Failure is detected by the end nodes of the failed link. All nodes of a multicast routing tree regularly send probe messages on each of their outgoing links. Each node also listens to such probe messages. If a node stops receiving probe messages on a link, then this node considers that the link has failed.

If a link fails, such as link $CD$ in Figure 4.2(b), then both nodes $C$ and $D$ detect the failure of link $CD$. Then, both nodes $C$ and $D$ send failure notification messages which are propagated through the tree (Figure 4.2(b)). All nodes of the tree are notified of the link failure. When the end nodes $A$ and $B$ of the backup path receive failure notification messages, they perform switchover by merging the backup path in the mLSP (Figure 4.2(c)). A new mLSP results from the merging of the backup path and the mLSP that mapped the multicast routing tree before the failure. This new mLSP maps the multicast routing tree described in Claim 1 of Chapter 3. Nodes now forward packets over the new mLSP and no LER is dropped from the tree. We introduced the notion of Path Switching LSR (PSL) in Section 2.4 in the context of MPLS unicast Fast Reroute. In MPLS multicast Fast Reroute, since mLSPs are bidirectional, both nodes at the end of the backup path are PSLs. Indeed, node $A$ forwards traffic coming from the LERs $A$, $F$ and $G$ over the backup path, therefore $A$ is a PSL, and node $B$ forwards traffic coming from the LERs $B$, $E$ and $J$ over the backup path, therefore $B$ is also a PSL.

When nodes $C$ and $D$ resume receiving probes over the previously failed link $CD$, they detect that the failed link has been repaired. Then $C$ and $D$ send link recovery notification messages which are propagated through the multicast routing tree (Figure 4.2(d)). When nodes $A$ and $B$ receive those messages, they perform switchback by stopping forwarding packets over the backup path (Figure 4.2(e)). After switchback is completed, the multicast routing tree is exactly the same as the original multicast routing tree that was in use before the failure occurred (Figure 4.2(a)).

In the next sections, we describe the steps of MPLS multicast Fast Reroute: link failure and recovery detection, link failure and recovery notification, and switchover and switchback.