next up previous contents
Next: MPLS Unicast Fast Reroute Up: Resilience and protection in Previous: Protection at the MAC   Contents


Network layer protection

Packet switching networks like the Internet are inherently resilient to link failures. Routing protocols [35] [46] [49] [57] [60] [63] take account for topology changes such as a link failure and recompute routing tables accordingly using a shortest path algorithm. When all routing tables of the network are recomputed and have converged, all paths that were using a failed link are rerouted through other links. However, convergence is fairly slow and takes usually several tens of seconds. Part of the reason for this is that routing protocols use timers to detect link failure with coarse granularity (1 second) making the $T_{detect}$ term in Equation 2.2 large compared with lower layer rerouting mechanisms. Second, all routers in the network have to be notified of the failure. Propagating notification messages is done in an order of magnitude of tens of millisecond which makes $T_{notif}$ negligible compared with $T_{detect}$. Indeed routers only need to forward the messages with no additional processing. Finally routing tables have to be recomputed before paths are switched. Recomputing routing tables implies using CPU intensive shortest path algorithms which can take a time $T_{switchover}$ of several hundred milliseconds in large networks.

In [1], the authors argue that it is possible to perform IP rerouting in less than one second by shrinking the $T_{detect}$ and $T_{switchover}$ terms of Equation 2.2. First, they propose to use subsecond timers to detect failures and decrease the value of the $T_{detect}$ term. Second, they suggest that routing convergence is slow due to the obsolescence of the shortest path algorithms employed in current routing protocols which would be able to recompute routing tables at the millisecond scale if faster, more modern algorithms were used. In summary, expected rerouting times in networks using modified routing protocols are below one second, but the authors also argue that millisecond network layer rerouting is achievable. However, implementation of those guidelines requires major modifications in current routing algorithms and routers.


next up previous contents
Next: MPLS Unicast Fast Reroute Up: Resilience and protection in Previous: Protection at the MAC   Contents
Yvan Pointurier 2002-08-11