Failure-Inference-Based Fast Reroute with Progressive Link Metric Increments

摘要

This paper is focused on providing fast reroute and loop-free convergence in traditional IP networks, without making any modifications to the IP datagram and without requiring any coordination between routers for FIB updates. Failure inference based fast route (FIFR) is an approach in which routers adjacent to a failed link or router perform local rerouting around the failure, without notifying non-adjacent routers about the failure. The non-adjacent routers utilize interface-specific forwarding tables, which are precomputed based on potential inferred failures that could cause a packet for a given destination to arrive through that unusual interface, to ensure loop-free forwarding towards the destination. However, as long as the failure lasts, packets that were to be forwarded over the failed link traverse suboptimal paths, as they reach the router adjacent to the failure and then are rerouted along a detour. Therefore, in case of a long-lasting failure, it is desirable to trigger a network-wide link state update, so that all routers can converge to new optimal forwarding tables. But, without some coordination between routers to install their forwarding entries in a specific order, there may be transient forwarding loops during the convergence period. As we are interested in a mechanism that does not require any such coordination between routers, we consider the possibility of employing progressive link state updates. In this paper, we show that FIFR with progressive link metric increments can guarantee loop-free forwarding not only before/after but during convergence too and protect against non-partitioning single link failures.