next up previous contents
Next: Implementation Up: MPLS Multicast Fast Reroute Previous: Failure and recovery notification   Contents


Switchover and switchback

Switchover consists in merging the backup path with the mLSP that maps the original multicast routing tree (before link failure). After switchover is performed, traffic flows on a new mLSP. On the other hand, switchback restores the original mLSP by ceasing to send traffic over the backup path.
Figure 4.8: Backup label mappings.
\includegraphics[width=\textwidth]{figures/mc_fast_reroute_bakmappings}

Let us consider the backup label mappings that need to be advertised before a multicast routing tree can be repaired. Consider a multicast routing tree and the mLSP that has been established for the multicast routing tree. In the following, we will refer to the label mappings that define this mLSP as ``original label mappings''. We establish two series of new mappings for the backup path as follows. First, label mappings are established on the path between $A$ and $S'$ via $B$. Second, label mappings are established on the path between $B$ and $S'$ via $A$. Therefore, backup mappings are established on all links of the backup path in both directions, and on all links of the protected path in a single direction. Consider the example network in Figure 4.8(a). We show these additional backup mappings for this network in Figure 4.8(b). With both mappings from the original mLSP and these additional mappings, two new unidirectional mLSPs are defined (Figure 4.8(c)). For instance, suppose $B$ sends a packet on the backup path using the new backup label mapping. Node $K$ forwards the packet to $A$ which forwards the packet to $D$, still using backup label mappings. Node $D$ duplicates the packet and sends a copy to $C$ using a backup label mapping, one copy to $F$ and one copy to $G$ using original label mappings. When $C$ receives the packet, it forwards the packet to both $S'$ using a backup label mapping and to $E$ using an original label mapping. Node $S'$ does not forward packets that use backup label mappings and come from a link of the protected path to another link of the protected path. We will explain why when we focus on switchback.

Figure 4.9: Path followed by packets sent by $J$ after switchover.
\includegraphics[width=0.9\textwidth]{figures/mc_fast_reroute_switchover_ex}

Switchover is performed as follows: when a PSL is notified of a link failure, it forwards all the packets it receives on the backup path using the backup mapping. Suppose for instance that link $CD$ fails. The PSLs $A$ and $B$ perform switchover and the backup path is merged with the original multicast routing tree, yielding a new, repaired multicast routing tree. Suppose $J$ sends a packet on the new multicast routing tree. The packet reaches nodes $H$, $S'$, $C$, $E$ and $B$ using original label mappings. When $B$ receives the packet, it forwards the packet on the backup path as described above, except that $D$ does not forward the packet to $C$. We show the path followed by packets sent by $J$ after switchover in Figure 4.9.

If a second link of the protected path fails, then the PSLs are notified of the second link failure and ignore it. The repaired multicast routing tree is split into two trees and the multicast group is partitioned. We do not consider the case where only one direction of a link fails, since links are assumed to be bidirectional and a failure generally affects both directions.

Both PSLs do not perform switchover simultaneously. When a link fails, a multicast routing tree is split into two smaller subtrees $T_A$ and $T_B$. Suppose $T_A$ is the subtree that contains PSL $A$ and $T_B$ is the subtree which contains PSL $T_B$ (see Figure 4.9). After the link failure and before $A$ and $B$ are notified of the failure, traffic sent by nodes from $T_A$ cannot reach nodes of $T_B$ and traffic sent by nodes from $T_B$ cannot reach nodes of $T_A$. Suppose $A$ is notified of the failure and performs switchover before $B$. After $A$ has performed switchover and before $B$ has performed switchover, traffic sent by nodes of $T_A$ can reach nodes of $T_B$ but conversely traffic sent by nodes of $T_B$ cannot reach nodes of $T_A$. After both PSLs have performed switchover, no node is dropped from the multicast routing tree. Switchover consists in a change in the MPLS forwarding table of the LSRs, thus switchover is almost instantaneous. The total time to repair the tree is therefore $T_{repair} = T_{fdetect} + T_{notif} \approx T_{fdetect}$. The order of magnitude of $T_{repair}$ is a few tens of milliseconds.

We now discuss the switchback mechanism. When a node detects a link failure, it stops forwarding traffic over the failed link. When this node detects the link repair, it sends out notification messages as explained in Section 4.3 and resumes forwarding traffic over the repaired link. When a PSL is notified that a failed link is repaired, it stops forwarding traffic over the backup path. Like switchover, switchback is not performed simultaneously by both PSLs. After the link repair detection and before $A$ and $B$ are notified of the link recovery, when a node sends a packet then all other nodes receive two copies of this packet. Consider for example Figure 4.10 and suppose that nodes $C$ and $D$ have detected the repair of link $CD$ and that neither $A$ nor $B$ have performed switchback. When $J$ sends a packet to the multicast group, node $H$ duplicates the packet and sends one copy to $S'$ (Figure 4.10(a)) and the other copy to $B$ (Figure 4.10(b)). We now follow the path of the first copy. Node $S'$ forwards it to $C$ which forwards the packet to both node $E$ and, since the repair of link $CD$ has been detected, node $D$. Node $D$ forwards the packet to $F$, $G$ and $A$. Node $A$ has not performed switchback thus it forwards the packet to $K$. The packet then reaches $B$. Node $B$ forwards the packet to $H$, which forwards the packet to $J$ and $S'$. Node $S'$ does not forward the packet coming from a link of the protected path (link $S'H$) to another link of the protected path (link $S'C$), thus the packet is not forwarded to $C$. If the packet was forwarded to $C$, then it would loop on the path formed by the protected and the backup paths. Now consider the second copy of the packet made by $H$ after $H$ receives the packet from $J$. Node $H$ forwards the packet to $B$ which forwards the packet over the backup path to $A$ via $K$. Node $A$ sends the packet to $D$ which forwards the packet to $F$ and $G$. Since the repair of link $CD$ has been detected, $D$ also sends the packet to $C$, $C$ forwards the packet to $E$ and $S'$. Node $S'$ does not forward the packet to $H$ and breaks the loop. Therefore, during this transient period, all nodes receive duplicate copies of all packets. When only one PSL, for instance $A$, has performed switchback then traffic from nodes of $T_A$ is delivered twice to the nodes of $T_A$ and only once to the nodes of $T_B$, and traffic from nodes of $T_B$ is delivered twice to the nodes of $T_A$ and only once to the nodes of $T_B$. When the second PSL performs switchback then no node is forwarded on the backup path anymore and traffic is forwarded on the original mLSP as before the link failure.

Figure 4.10: Duplicate packets during switchback. When a failed link is repaired and switchback has not been performed, all nodes receive two copies of the packets sent by any node. In this example, all nodes receive two copies of a packet sent by $J$.
\includegraphics[width=0.99\textwidth]{figures/mc_fast_reroute_switchback_ex}


We define the time $T_{repairback}$ to switch traffic back on the original tree as the time between the instant at which the failed link is repaired and the instant at which both PSLs have performed switchback. Therefore $T_{repairback} = T_{rdetect}+T_{notif}$. During the time $T_{repairback}$, certain links must carry twice the same data, possibly leading to congestion. If the traffic that uses the mLSP before switchback represents less than 50% of the capacity of the links that is allocated to the mLSP then no congestion will occur and nodes will simply receive the same packets twice. It is up to the application layer to drop the redundant packets. On the other hand if traffic that flows on the mLSP before switchback represents more than 50% of the capacity of the links that is allocated to the mLSP then the mLSP will be congested and packets will be dropped. However, since $T_{rdetect} < T_{fdetect}$ the time during which congestion may occur is smaller than the interruption of service due to link failure. Moreover congestion that may be caused by switchback is very limited in time (a few milliseconds) and therefore does not prevent the network from functioning properly.

In this chapter, we have exposed the principles of MPLS multicast Fast Reroute. Implementing this mechanism requires the ability to advertise a mLSP and the backup path mappings. Second, the probing and notification mechanisms must be implemented. Finally, nodes must perform switchover or switchback when they are notified to. In the next chapter, we present an implementation of all these mechanisms.


next up previous contents
Next: Implementation Up: MPLS Multicast Fast Reroute Previous: Failure and recovery notification   Contents
Yvan Pointurier 2002-08-11