Full Protection Made Easy: The DisPath IP Fast Reroute Scheme

A major concern in IP networks is to ensure that any topology changes, whether planned or unplanned, do not disrupt network performance. IP Fast Reroute (IP FRR) is a general approach to address this issue, by promptly forwarding an IP packet to some predetermined alternate next hop as soon as the usual next hop to its destination is known to have become unavailable due to a topology change. However, all IP FRR schemes proposed to date are unsatisfactory in some way: either they cannot guarantee protection against all single link or node failures, which are the most common topology changes, or they are hard to implement because of inherent complexities. In this work, we present a novel scheme for IP FRR called DisPath. Our scheme determines the alternate next hop towards a given destination by computing two shortest node-disjoint paths to that destination. This makes DisPath only slightly more complex than Loop-Free Alternate (LFA) and U-turn Alternate, which are among the simplest and most popular IP FRR schemes. Moreover, we prove that DisPath ensures protection against all single link or node failures, a property not enjoyed by the other two schemes. Finally, we compare LFA and U-turn to DisPath in terms of stretch, i.e. the ratio of the length of a rerouted packet's trajectory to the length of the shortest path that avoids the failed network component. Simulations on several realistic instances reveal that DisPath usually exhibits lower--and never much higher--stretch than both LFA and U-turn.