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.
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 . Node receives traffic from other networks (not represented) and sends this traffic over the multicast routing tree. Leaves of the tree, and , receive the multicast traffic sent by 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 receives packets that must be forwarded over the tree. Node pushes label ``1'' on the packets and forwards these packets to . Node is an ingress LER of the mLSP. Then, node duplicates the packets and swaps the label of one of the two copies first with label ``2'', then with label ``3''. Node forwards the packets labeled ``2'' to and the packets labeled ``3'' to . Node is therefore a LSR of the mLSP. Node pops labels from packets labeled ``2'' coming from and node pops labels from packets labeled ``3'' coming from . Nodes and 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 sources with unidirectional mLSPs. Each of the unidirectional mLSPs would map a tree rooted at one of the 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 is the core and nodes , , are the sources . This core based tree is mapped by the single bidirectional mLSP represented in Figure 4.1(d). Node pushes label ``1'' on packets bound to the multicast group. Node swaps label ``1'' against labels ``2'' and ``3'' and forwards packets labeled ``2'' to and packets labeled ``3'' to . Node pops label ``2'' and node pops label ``3''. If node is a source of the multicast group, then when node needs to send packets to the multicast group it pushes label ``4'' on the transmitted packets. Node swaps label ``4'' against labels ``5'' and ``3'', and node pops label ``5'' while pops ``3''. If node is a source of the multicast group, node pushes label ``6'' on packets bound to the group, node swaps label ``6'' against labels ``5'' and ``2'', node pops label ``6'' and node pops label ``2''. Since , and both push and pop labels for packets of the bidirectional mLSP, they are ingress and egress LERs at the same time. Node is a LSR of the bidirectional mLSP. In the remainder of this thesis, we only consider core based trees mapped by bidirectional mLSPs.
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 mapped by the bidirectional mLSP depicted in Figure 4.2(a). A backup path has been computed between nodes and and the protected path is constituted by links , , , and . Node is defined as the Least Common Ancestor of and with regards to . In this example, since belongs to the protected path between and , then . 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 in Figure 4.2(b), then both nodes and detect the failure of link . Then, both nodes and 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 and 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 forwards traffic coming from the LERs , and over the backup path, therefore is a PSL, and node forwards traffic coming from the LERs , and over the backup path, therefore is also a PSL.
When nodes and resume receiving probes over the previously failed link , they detect that the failed link has been repaired. Then and send link recovery notification messages which are propagated through the multicast routing tree (Figure 4.2(d)). When nodes and 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.