Distance vector in depth

If distance vector and link state are new to you, start with dynamic routing on networks.jelia.nyc, which introduces both. This chapter assumes that introduction and goes into the machinery.

A distance-vector router knows three things: the networks it is directly attached to, the cost of each of its own links, and whatever its neighbors last told it. Every so often each router sends every neighbor a list of destinations with one number beside each, its current distance. That list is the distance vector. A router receiving it adds the cost of the link it arrived on, compares the totals with what it already has, and keeps the smallest. It never learns which routers lie beyond its neighbor, only how far away the neighbor says the destination is.

That is the Bellman-Ford shortest-path method, run in pieces. Richard Bellman and Lester Ford described the centralized version in the 1950s; the distributed version, where each router computes only its own row and passes it on, is the oldest routing algorithm on the internet. The ARPANET used it from the start, which the history chapter tells.

Here is the rule at work on four routers. R1 is attached to network 192.0.2.0/24 at cost 1. The links are R1–R2 cost 1, R1–R3 cost 4, R2–R3 cost 1 and R3–R4 cost 1. In each round, every router hears every neighbor's distance from the round before and applies the rule.

Two things are worth noticing. R3 first takes the expensive direct link to R1, then switches when R2's cheaper news reaches it; R4 inherits the expensive figure for one round and then corrects it. And the whole network settles in three rounds, round 4 being the round in which nothing changes. Good news travels fast: a newly reachable destination, or a cheaper path, needs at most one round per hop of the longest shortest path. Bad news is a different story, and it is most of this chapter.

RIP is distance vector written down as plainly as possible. Version 1 (RFC 1058, 1988) documented a protocol that was already widely deployed through BSD Unix's routed. Version 2 (RFC 2453, 1998) is the one still in use. Its metric is a hop count: every network usually costs 1, a route's metric is the number of networks crossed, and 16 means unreachable. That choice caps any RIP network at a diameter of 15 hops, a limit the RFC calls deliberate: the designers considered the basic protocol unsuitable for anything larger.

Every 30 seconds each router sends its full table to every neighbor as UDP datagrams on port 520. RIP-2 sends them to the multicast group 224.0.0.9, so hosts that are not listening do not have to process them. The receiving rules are short. A route from the neighbor you already use is always believed, whether it got better or worse. A route from anyone else is adopted only if it is strictly better. Each route has a 180-second timeout, refreshed whenever the current next hop mentions it; if the timeout expires, the route's metric is set to 16 and a 120-second garbage-collection timer starts, during which the router keeps advertising the route as unreachable so its neighbors hear the bad news before it is deleted.

The message is as plain as the rules. A 4-byte header carries a command (1 for a request, 2 for a response) and a version, and is followed by between 1 and 25 route entries of 20 bytes each. That makes the largest message 504 bytes of RIP data, which keeps it inside the 512-byte datagram limit that RIP-1 set. A full table that needs more than 25 entries goes out as several messages.

Take the simplest network that can fail: three routers in a line, R1–R2–R3, each link costing 1, with 192.0.2.0/24 attached to R1. Before anything breaks, R1 is at 1, R2 at 2 through R1, and R3 at 3 through R2. Now the R1–R2 link fails. R2 notices at once, because the interface went down, and marks the route unreachable. R3 has not heard yet, and its routine update happens to arrive first.

For the whole of that exchange, R2 thinks the destination is through R3 and R3 thinks it is through R2. A packet for 192.0.2.0/24 that reaches either one bounces between them, losing one from its TTL at every hop, until the TTL reaches zero and the packet is dropped. (How TTL works is covered in troubleshooting on networks.jelia.nyc.) That is a forwarding loop, and the slow climb of the metric is counting to infinity.

Nothing stops the count except the ceiling. If infinity were a million, the routers would count to a million. That is why RIP's infinity is a modest 16: it is not a property of networks, it is how long you are prepared to wait. Without triggered updates, each step can wait for the next 30-second update, so the thirteen or so steps above can take several minutes. With triggered updates each step takes a few seconds, but the loop still exists for as long as the count lasts.

The root of it is that a distance vector carries no information about the path. When R3 says "3", R2 cannot tell that R3's 3 was computed through R2 itself. Every fix below either withholds information that might be circular, or adds information that proves it is not.

The classic distance-vector protocols collected a set of rules to make counting to infinity rarer and shorter. Each one is cheap and each one helps. None of them makes loops impossible.

Split horizon: never advertise a route back out of the interface you learned it from. R3 learned its route from R2, so it says nothing about that destination to R2, and R2 can never be fooled by its own echo. Poison reverse is the stronger form RIP recommends: instead of saying nothing, R3 tells R2 the route is at 16. Silence leaves R2 to wait for a timeout before it forgets an old claim; poison kills the claim at once. The price is bigger updates, since every route is mentioned on every interface, in many cases as unreachable.

Triggered updates: when a metric changes, send an update within a few seconds instead of waiting for the next 30-second cycle. Bad news then outruns most stale news. RFC 2453 notes that if the network sat still while the cascade ran, counting to infinity could not happen; but regular updates keep firing during the cascade, and one that leaves a router just before the bad news arrives restarts the trouble.

Hold-down: after a route gets worse or goes unreachable, refuse any offer that is no better than the route you just lost, for a fixed time. The stale offers that drive the count are refused, and by the time the timer ends the bad news has usually reached everyone. Hold-down is not in RFC 2453; it came from vendor implementations. Its cost is that it refuses good news too: a genuine new path is ignored until the timer ends, so traffic is dropped when it could have been rerouted.

In the late 1980s and early 1990s J. J. Garcia-Luna-Aceves, working at SRI International, published the Diffusing Update Algorithm, DUAL. Cisco built it into EIGRP, its Enhanced Interior Gateway Routing Protocol, and in 2016 published EIGRP as an informational RFC, RFC 7868. DUAL keeps the distance-vector exchange but adds one memory and one test, and with them it never forms a loop, even for an instant.

The memory is the feasible distance (FD): the lowest distance this router has had to the destination since the destination last settled. Note "lowest since": if the current route gets worse, the FD does not rise with it. The test is the feasibility condition. Each neighbor advertises its own distance, called its reported distance (RD). A neighbor is safe to use only if its reported distance is strictly less than our feasible distance.

Why it works fits in three sentences. Suppose neighbor n's route ran back through me. Then n's distance would be my distance plus at least one positive link cost, so it would be larger than my current distance, which can never be smaller than my FD. So a neighbor whose RD is below my FD cannot be routing through me, and choosing it cannot close a loop. Apply that at every router and every next-hop pointer leads strictly downhill toward the destination; a chain that always goes downhill cannot come back to where it started.

DUAL names the results. The successor is the neighbor on the least-cost path, and it must satisfy the condition. Any other neighbor that satisfies it is a feasible successor: a backup that is already proven loop-free. When the successor's link fails and the cheapest remaining path comes from a feasible successor, the router switches to it immediately, with no messages and no waiting. RFC 7868 calls the route PASSIVE in this state.

A worked example. Router A reaches 192.0.2.0/24 through three neighbors. B has link cost 1 and reports 1, total 2. C has link cost 4 and reports 1, total 5. D has link cost 3 and reports 3, total 6. A's best total is 2, through B, so its FD is 2. C reports 1, which is less than 2: C is a feasible successor. D reports 3, which is not less than 2, so D fails. D's path might run through A: A's 2 plus one more hop of cost 1 would be exactly D's 3. When B fails, the cheapest remaining total is C's 5, and C is feasible, so A moves to C at once.

Change one number and the protocols part ways. If D's link cost were 1, D's total would be 4, cheaper than C's 5 but still not feasible. RFC 7868 requires the least-cost path to come from a feasible neighbor before a route may stay PASSIVE, so EIGRP would not settle for C: it would go ACTIVE and ask. Babel simply ignores routes that fail the condition and would take C. Instrument 2 lets you try both.

The condition is sufficient but not necessary, as RFC 7868 puts it: every path that passes is loop-free, but some loop-free paths fail. When the successor is lost and no neighbor passes, the route goes ACTIVE. The router freezes its route, sends a QUERY to every neighbor, and waits for every REPLY before choosing again and resetting its FD. Neighbors with no feasible successor of their own pass the query on, so the computation spreads out from the failure and then collapses back, which is why it is called diffusing. A query that is not answered in time leaves the route stuck in active; Cisco's implementation allows 3 minutes, with a check-up query at the halfway mark.

Babel, designed by Juliusz Chroboczek and standardized as RFC 8966 in 2021, uses the same kind of feasibility condition, which its RFC says is derived from EIGRP's. A Babel router remembers, for each source, the smallest metric it has ever advertised, and accepts an update only if the advertised metric is strictly smaller. The condition has the same weakness too. A router can find that every route it hears fails the test even though a perfectly good path exists, because the test is only sufficient. RFC 8966 calls this starvation.

EIGRP answers starvation by stopping everyone involved and asking. Babel adds a second number instead. Every route carries a sequence number, set by the router that originates the prefix and passed along unchanged by everyone else. The pair of sequence number and metric is the route's distance, and the feasibility test compares pairs: an update is feasible if its sequence number is newer than the one in the feasible distance, or if it is the same and the metric is strictly smaller.

A starving router sends a seqno request toward the source. Requests are forwarded without regard to feasibility, so they get through even along routes that cannot yet be used. The source answers by incrementing its sequence number and announcing again. The new number spreads outward, and every router that hears it may take the route at whatever metric it now costs, because no router anywhere can have a feasible distance with a sequence number that has only just been invented. Only the routers that need help are involved; there is no network-wide freeze.

A newer sequence number cannot create a loop, for a simple reason: it is only ever created by the source and travels away from it, so a router holding it already lies on a path that came from the source. Babel also keeps feasible distances per source, a pair of router-id and prefix, so two routers announcing the same prefix do not confuse each other's sequence numbers. The sequence number is 16 bits and wraps around, compared with the same kind of modular arithmetic TCP uses.

In most enterprise and provider networks the interior protocol is now link state, OSPF or IS-IS (chapter 5, chapter 6), because every router can see the whole map and recompute quickly. Distance vector has kept three niches. RIP survives in small and older networks and in equipment where its simplicity is the point. EIGRP runs in many networks built on Cisco equipment, where its fast switch to a feasible successor is the main attraction. Babel is used in community mesh networks and small networks, especially where wireless links of varying quality carry traffic between routers.

And the protocol that holds the internet together is a close relative. BGP is a path-vector protocol: instead of a single distance, each route carries the list of autonomous systems it has passed through, and a router rejects any route whose list already contains its own number. Babel's RFC describes that as BGP's feasibility condition, a drastic but effective one. Chapter 8 starts there.