In my last installment on the topic of fast convergence, I said I’d be discussing the calculation stage of fast convergence next. Orhan tried to scoop me in the comments, but that’s okay –I’m working at this through the process switched path, rather than interrupt context. 🙂
In parallel with flooding information about the topology change to all the other routers within the same failure domain, each router must also calculate and switch to an alternate route so traffic can continue being forwarded to the destination. There are a lot of really complex algorithms for finding this alternate path, but I’m going to let you in on a little secret: all these complex algorithms actually represent one of two cases, both involving rings in the network topology.
Begin here: all networks with alternate paths must have a ring or loop in the network topology someplace. The point of a routing protocol is to find these loops, and eliminate them from the forwarding path. The key to fast reroute is finding the alternate path through each loop – the “back side of the ring,” if you want to think of it that way – and using it in case the primary path goes down. The figure embedded here might help you visualize this rather graph oriented way of thinking about the problem of fast reroute.
Let’s take this from E’s perspective. Whatever method (or routing protocol) is used, assumed E will choose the path through C to reach the destination, which is connected to the ring through A. If the link between E and C fails, then E must find some new route to the destination – or rather, to A, which provides the connection between the ring and the destination.
The first fast reroute case is this: E can calculate, based on already existing information, that the path through D is not, in fact, a loop – that traffic forwarded to D will not be forwarded back to E itself, and D can reach the destination. How can E calculate this? In EIGRP this is done through the feasibility condition: if D’s metric to reach the destination is lower than E’s metric to reach the destination, then D’s metric cannot, by definition, include the path through E itself, so D’s path must represent an independent path to the destination. In other words, if the D’s cost is less than E’s cost, then D’s path is the “back side of the ring,” the other way to reach the same exit point from the ring, which is A.
In a link state protocol, there are several ways to calculate this same thing, but Loop Free Alternates (LFAs), in the real world, use essentially the same mechanism that EIGRP does – because it’s the simplest and easiest solution to the problem at hand.
I’m going to leave you hanging on the second case until the next installment.