Fast convergence: BFD & fast reroute

If the words "convergence" and "microloop" are new, start with dynamic routing on networks.jelia.nyc, whose section "Convergence: how fast is fast?" is the on-ramp to this chapter. Here we take the same four steps apart with a stopwatch.

The IETF's framework for IP fast reroute, RFC 5714, lists what happens after a failure in a link-state network such as OSPF or IS-IS, with rough numbers for each step. First the routers next to the failure have to detect it: a few milliseconds if the physical layer reports it, "up to several tens of seconds when a routing protocol Hello is employed." Then they originate new link-state advertisements, often after a deliberate hold-down. The news is flooded to every other router, which the RFC puts at 10 to 100 milliseconds per hop. Each router recomputes its shortest-path tree, typically a few milliseconds of Dijkstra. Finally each router installs the changed routes into its forwarding hardware, which RFC 5714 calls "very implementation dependent" and which "may be several hundred milliseconds."

Traffic is lost for the whole of that chain, and the chain is only as fast as its slowest link. Two parts dominate in practice. Detection dominates when it relies on hellos, because a protocol hello timer is measured in seconds. Once detection is fast, installation tends to dominate, because a router may have to rewrite tens or hundreds of thousands of forwarding entries one by one, and the last prefix in the queue waits for all the others.

That last problem has a structural fix. In a flat forwarding table, each of a hundred thousand prefixes stores its own next hop, so a failure means a hundred thousand writes. In a hierarchical table, the prefixes all point at one shared "path list" entry, and only that entry holds the next hop. A failure then means one write, whatever the number of prefixes. This is called prefix-independent convergence (PIC): the recovery time no longer grows with the size of the table.

The cheapest detection is the one the hardware gives you for free. When a fiber is cut between two routers that are directly connected, the receiving optics lose light and the interface goes down within milliseconds; the routing protocol hears about it at once. This is carrier loss, and when it works, nothing beats it.

It often does not work. Two routers may be joined through a switch, a transport system or a provider's Ethernet service. If the far router crashes, or a line card stops forwarding while its laser stays lit, every light on the near router stays green. The only way to find out is to notice that the neighbor has stopped talking. OSPF and IS-IS do this with their own hellos, but those are designed for adjacency, not for speed: RFC 2328 gives 10 seconds as a sample hello interval and suggests declaring a neighbor dead after "some multiple of the HelloInterval (say 4)." That is 40 seconds of black hole.

Bidirectional Forwarding Detection (BFD, RFC 5880) is a protocol that does nothing but this. Two routers agree to send each other small control packets at a fixed interval. In the usual asynchronous mode, each side simply expects to keep hearing from the other. If a router hears nothing for a whole detection time, it declares the session down and tells every protocol that registered an interest (RFC 5882 describes how OSPF, IS-IS, BGP and static routes use it). Because BFD is so simple, it can run on a line card or in hardware, far away from the busy routing process, which is what lets it run at intervals of tens of milliseconds.

The detection time is not sent in the packet. Each receiver works it out from two negotiated numbers: the interval, the greater of what the sender wants to send and what the receiver is willing to receive, and the sender's detect multiplier, roughly the number of packets that may be missed in a row.

For a session between directly connected routers, RFC 5881 puts the control packets in UDP to destination port 3784 and requires the IP TTL (or IPv6 hop limit) to be exactly 255 on sending and receiving. Any packet that has crossed even one router arrives with 254 or less and is thrown away, so a spoofer elsewhere on the internet cannot keep a dead session alive or kill a live one; this is the same trick as the Generalized TTL Security Mechanism in RFC 5082. The packet itself is small and fixed, 24 bytes before any authentication:

A session comes up with a three-way handshake through the states Down, Init and Up, and while it is not Up the RFC requires sending no faster than once a second, so a misconfigured peer cannot be flooded. In echo mode, a router sends packets addressed to itself to UDP port 3785 across the link; the neighbor forwards them straight back in its data plane, testing the real forwarding path without the neighbor's software doing any work.

If fast is good, why would a router ever wait before running SPF? Because one failure is rarely one event. When a router dies, every one of its neighbors detects a link loss, each a few milliseconds apart, and each floods its own LSA. A router that ran SPF on the first LSA would compute a picture that is wrong a moment later, install it, then do it all again. During a flapping link it might do this many times a second, burning CPU and churning the forwarding tables of the entire area.

So implementations throttle with an exponential back-off. The first event after a quiet period triggers SPF after a short delay. If more events keep arriving, the next run is held off longer, and longer, up to a ceiling. Once the network has been quiet for a while, the delay snaps back to the short value. FRRouting's OSPF documentation gives the example timers throttle spf 200 400 10000: wait 200 ms after an event, then keep runs at least 400 ms apart, growing by 400 ms each time another event lands inside the hold time, never more than 10 seconds.

Different vendors' algorithms used to differ, and if two neighbors run SPF at different moments their forwarding tables disagree for longer, which breeds the microloops later in this chapter. RFC 8405 therefore standardizes one back-off algorithm for link-state IGPs, with an INITIAL delay for a single isolated event (its example is 0 ms), a SHORT delay while the rest of one component failure arrives (50 to 100 ms), and a LONG delay when the network is unstable (2 seconds), returning to INITIAL after a HOLDDOWN interval of quiet (3 seconds in its example).

Even with BFD and short throttles, the routers far from a failure need flooding, SPF and FIB writes before they move. The routers right beside the failure are the ones that know first, and they are also the ones dropping traffic. RFC 5714 calls such a router the point of local repair, and IP fast reroute (IPFRR) is the idea of giving it a backup next hop, computed and installed before anything fails. When BFD fires, it switches to the backup in the data plane, in milliseconds, while normal convergence carries on behind it.

The catch is that the backup neighbor will forward the packet using its own routing table, which still describes the network before the failure. If that neighbor's best path to the destination runs back through the repairing router, the packet comes straight back and loops. RFC 5286 gives the test a neighbor must pass to be a safe backup, a loop-free alternate (LFA). Write S for the repairing router, D for the destination, N for a candidate neighbor and Distance(X, Y) for the shortest-path cost from X to Y before the failure:

A worked example. S reaches D through E: S to E costs 1, E to D costs 1, so Distance(S, D) = 2. S has another neighbor N, with S to N costing 1 and N to D costing 2. Then Distance(N, D) = 2, Distance(N, S) = 1, and the test reads 2 < 1 + 2, which is true: N is an LFA. Now raise the N to D cost to 4. N's best route to D is now back through S and E, cost 3, and the test reads 3 < 1 + 2, which is false. Hand N a packet for D and it returns it to S. The same neighbor, with one cost changed, stops being safe.

RFC 5286 adds two stronger conditions. A downstream path (Inequality 2) requires Distance(N, D) < Distance(S, D): N is strictly closer to the destination than S is, a stricter test that also rules out loops when neighboring routers are repairing at the same time. A node-protecting LFA (Inequality 3) requires Distance(N, D) < Distance(N, E) + Distance(E, D), where E is the primary next hop: N's path avoids E itself, so the backup survives if the whole router E died rather than just the link to it. A neighbor that passes only Inequality 1 protects the link.

Whether an LFA exists depends entirely on the shape of the network and its costs. Meshes and triangles are generous. Rings are hostile: in a ring with equal costs, the neighbor on the other side of S usually reaches the far part of the ring through S, so it fails the test. That is not a curiosity; many metro and access networks are rings.

If no direct neighbor is safe, perhaps a router further away is. That is the idea of remote LFA (RFC 7490): S sends the packet through a tunnel to a distant router that, from where it sits, will forward it to the destination without being drawn back towards the failure. The tunnel makes the distant router behave like a neighbor.

The tunnel endpoint has to satisfy two conditions, and RFC 7490 names them as two sets of routers. The P-space of S, with respect to the protected link S–E, is every router S can reach on its normal shortest paths without any of them (equal-cost splits included) crossing S–E. Packets tunnelled to a router in P-space will get there despite the failure. Because S can also use its neighbors' views, the RFC defines an extended P-space: the union of the P-spaces of S's other neighbors. The Q-space of E is every router from which E can be reached without crossing S–E. Packets released at a router in Q-space travel on normally without needing the broken link. A router in both is a PQ node, and it is where the tunnel ends.

RFC 7490's own example is a ring of six routers, S, E, D, C, B and A, all links costing 1. When S–E fails, traffic to D and E cannot be protected by plain LFAs. S can reach A and B without the link, and through its neighbor A it can also reach C: that is the extended P-space. D and C can reach E without the link; B cannot, because one of its two equal-cost paths to E runs through S. The only router in both sets is C, so S tunnels to C and C delivers to D and E. The LFA finder above reproduces exactly this when you load the ring.

Remote LFA still leaves gaps: in some topologies P-space and Q-space do not touch. Topology-independent LFA (TI-LFA, RFC 9855, published October 2025) closes them by using segment routing, which lets the source write a short list of waypoints, and even specific links, into the packet header. With that, S can steer a packet from the last router in P-space across the gap to the first router in Q-space. TI-LFA also chooses its repair along the post-convergence path, the path the network will settle on once it has converged, so traffic moves once to its final route rather than twice. The RFC states the result plainly: guaranteed coverage "in any two-connected networks using a link-state IGP." If the network is still connected after the failure, TI-LFA can protect it.

Convergence is not one event but many, scattered over a few hundred milliseconds. Each router finishes detecting, flooding, computing and installing at its own moment, and RFC 5714 points out that the install step varies the most from one router to another. In between, some routers forward by the new topology and some by the old. If a router with the new picture sends a packet to a router with the old picture, and the old picture says "send it back," the packet bounces between them. That is a microloop: a forwarding loop that exists only during convergence.

A microloop is not harmless just because it is brief. Each looping packet crosses the same link again and again until its TTL runs out, so a loop at line rate fills that link with copies, and traffic that was never affected by the failure gets caught in the congestion. Fast reroute does not help either, unless it is held in place: the moment the repairing router installs its new route, it stops using its carefully loop-free backup and may point straight into a neighbor that has not caught up.

RFC 5715 is the framework for loop-free convergence and surveys the cures. One family controls the order in which routers update: in an ordered FIB scheme, routers update in a sequence chosen so that no router ever points at one that still points back. A simpler, widely used case is RFC 8333's local convergence delay. Its observation is that many microloops involve the router right next to the failure, which detects first and updates first. So that router deliberately waits: it keeps forwarding on its fast-reroute repair, which is loop-free, while the rest of the network converges, and only then installs its own new route. RFC 8333 limits this to link-down events and says it may only be used when fast reroute protects the traffic during the wait, or for planned maintenance. Its simulations on real topologies found that these local loops were more than half of all forwarding loops.