Overview of rerouting

Figure 2.1: Rerouting overview and terminology. Traffic between $A$ and $B$ on the primary path is rerouted over the backup path when link $(CD)$ fails.

We present here general concepts and terminology concerning rerouting. Rerouting is a technique that can be used in both Circuit Switching and Packet Switching networks. When a link in a network fails, traffic that was using the failed link must change its path in order to reach its destination: it is rerouted from a primary path to a backup path. The primary and the backup path can be totally disjoint or partially merged. Figure 2.1 presents an example where a source node $A$ sends traffic to a destination node $F$, and where a link on the primary path fails. In the remainder of this section, we will refer to this example to illustrate rerouting. A complete rerouting technique consists in seven steps. The first four concern rerouting after a link has failed to switch traffic from the primary to the backup path, while the last three concern rerouting after the failed link has been repaired to bring back traffic to the primary path.

First, the network must be able to detect link failures. Link failure detection can be performed by dedicated hardware or software by the end nodes $C$ and $D$ of the failed link. Second, nodes that detect the link failure must notify certain nodes in the network of the failure. Which nodes are actually notified of the failure depends on the rerouting technique. Third, a backup path must be computed. In pre-planned rerouting schemes however, this step is performed before link failure detection. Fourth, instead of sending traffic on the primary, failed path, a node called Path Switching Node must send traffic on the backup path. This step in the rerouting process is called switchover. Switchover completes the repairing of the network after a link failure.

When the failed link is physically repaired, traffic can be rerouted to the primary path, or keep being sent on the backup path. In the latter case, no further mechanism is necessary to reroute traffic to the primary path while three additional steps are needed to complete rerouting in the former case. First, a mechanism must detect the link repair. Second, nodes of the network must be notified of the recovery, and third the Path Switching Node must send traffic back on the primary path in the so-called switchback step.

Consider a unicast communication. When a link of the path between the sender and the receiver fails, users experience service interruption until the path is repaired. The length of the interruption is the time between the instant the last bit that went through the failed link before the failure is received, and the instant when the first bit of the data that uses the backup path after the failure arrives at the receiver. Let $T_{detect}$ denote the time to detect the failure, $T_{notif}$ the notification time, $T_{switchover}$ the switchover time, and $d_{ij}$ the sum of the queuing, transmission and propagation delay needed to send a bit of data between two nodes $i$ and $j$. Then, for the example given in Figure 2.1, the total service interruption time for the communication $T_{service}$ is given by:

$$T_{service} = T_{detect} + T_{notif} + T_{switchover} + (d_{BE}+d_{EF}) - (d_{DE}+d_{EF}) .$$ (1)

The quantity $(d_{BE} - d_{EF}) - (d_{DE} - d_{EF})$ does not depend on the rerouting technique but rather on the location of the failure. Therefore, we define the total repair time $T_{repair}$ which only depends on the rerouting mechanism by

$$T_{repair} = T_{detect} + T_{notif} + T_{switchover} .$$ (2)

The total repair time is the part of the service interruption time that is actually spent by a rerouting mechanism to restore a communication after a link has failed.