§5.2.2The Distance-Vector (DV) Algorithm

Three words: iterative, asynchronous, distributed

The book describes the algorithm with three adjectives, and each one is a real property, not decoration.

Distributed. Each node receives information from its directly attached neighbours, performs a calculation, and sends the result back to those neighbours. No node collects everything.

Iterative. The exchange repeats until no more information passes between neighbours. Nobody counts the rounds in advance.

Asynchronous. The nodes do not have to move in step. One router may compute and send while another is still waiting.

There is a fourth property the book mentions in brackets, and it is the strange one. The algorithm is self-terminating. No signal says the computation is finished. It simply stops, because there is nothing left to send. That final silence is the quiescent state quiescent state Simple Nothing left to send, so the algorithm has quietly stopped. Precise The state a distance-vector computation reaches when no node's distance vector has changed, so no update messages are sent and no further calculation occurs. The algorithm is self-terminating: nothing signals that it is finished. introduced in ch. 5 — open in glossary .

The Bellman-Ford equation

Before the algorithm, one piece of arithmetic. Let d_x(y) be the cost of the least-cost path least-cost path Simple The cheapest way from one node to another. Precise The path between two nodes with the smallest sum of edge costs. When every cost is 1 it is also the shortest path. introduced in ch. 5 — open in glossary from node x to node y. Then the least costs are related by the Bellman-Ford equation:

where the minimum is taken over all of x’s neighbours.

The book’s own check

The book verifies the equation by hand on Figure 5.3, the six-node graph from section 5.2.1. Source u, destination z.

Node u has three neighbours: v, x and w. Walking the graph gives d_v(z) = 5, d_x(z) = 3 and d_w(z) = 3. The link costs are c(u,v) = 2, c(u,x) = 1 and c(u,w) = 5. So:

Four is exactly what Dijkstra’s algorithm produced for the same graph in the previous section. Two completely different methods, one answer.

d_x(y) = min over v of { c(x,v) + d_v(y) }
  through the first neighbour: 2 + 5 = 7
  through the second neighbour: 1 + 3 = 4   <- smallest
  through the third neighbour: 5 + 3 = 8
d_x(y) = 4
so v* is the second neighbour: that is the next hop this destination gets in the forwarding table

Why the equation is more than a curiosity

The book makes two practical points, and both matter more than the equation itself.

The solution fills in the forwarding table. Let v* be the neighbour that achieves the minimum. If x wants to send a packet to y along a least-cost path, it should forward that packet to v*. So x’s forwarding table forwarding table Simple A table in a router that says which outgoing link to use for each destination address. Precise A table in a router that maps destination addresses, or portions of destination addresses, to that router's outbound links. On arrival, the router examines the packet's destination address and searches this table to find the appropriate outbound link. introduced in ch. 1 — open in glossary lists v* as the next-hop router next-hop router Simple The one neighbour a packet is handed to next. Precise v*(y), the neighbouring node that achieves the minimum in the Bellman-Ford equation for destination y. It is the value node x records in its forwarding table for that destination. introduced in ch. 5 — open in glossary for destination y. The whole computation collapses into one neighbour per destination, exactly as it did for link-state routing.

The equation suggests what neighbours should say to each other. Node x needs d_v(y) — its neighbour’s distance to y. So that is what neighbours send.

What one node stores

Each node x keeps an estimate D_x(y) for every destination y in N, the set of nodes. The whole list is x’s distance vector distance vector Simple One router's list of guessed costs, one number for every destination. Precise D_x = [D_x(y): y in N] — node x's vector of cost estimates from itself to every other node in N. It is the only thing a node ever sends to its neighbours. introduced in ch. 5 — open in glossary , written D_x = [D_x(y): y in N].

Three things live in each node, and only one of them ever leaves.

The algorithm

Here is the book’s own pseudocode, page 389, running at every node x.

Initialization:
  for all destinations y in N:
      Dx(y) = c(x,y)      /* if y is not a neighbour then c(x,y) = ∞ */
  for each neighbour w
      Dw(y) = ? for all destinations y in N
  for each neighbour w
      send distance vector Dx = [Dx(y): y in N] to w

loop
    wait (until I see a link cost change to some neighbour w or
              until I receive a distance vector from some neighbour w)

    for each y in N:
        Dx(y) = minv{c(x,v) + Dv(y)}

    if Dx(y) changed for any destination y
        send distance vector Dx = [Dx(y): y in N] to all neighbours

forever

Two details are easy to read past.

Line 14 also produces the next hop. For each destination y, the neighbour v that achieves the minimum is v*(y), and x writes it into its forwarding table. If several neighbours tie, any of them will do.

Nothing is sent unless something changed. That is the test on line 16, and it is what makes the algorithm stop.

Figure 5.6: watching it converge

Three nodes, three links, costs 2, 1 and 7. Each node’s routing table holds three rows: its own distance vector, and the last vector received from each neighbour. At the start, the neighbour rows are all ∞, because nothing has arrived.

Follow node x through the first round. It has just received Dy = [2, 0, 1] and Dz = [7, 1, 0]. It applies line 14:

Its estimate for z falls from 7 to 3. Node y won the minimum for both destinations, so at this point v*(y) = y and v*(z) = y: everything leaves x over the link to y.

Three things in that run are worth naming.

Silence is meaningful. After the first round, y’s vector did not change, so y sends nothing. Only x and z send. A node that has nothing new to say says nothing.

It stops without being told to. After the second round no node’s vector changed, so no messages are sent, so no calculation happens, so nothing will ever change again. Every node sits in the wait on lines 10–11. That is the quiescent state quiescent state Simple Nothing left to send, so the algorithm has quietly stopped. Precise The state a distance-vector computation reaches when no node's distance vector has changed, so no update messages are sent and no further calculation occurs. The algorithm is self-terminating: nothing signals that it is finished. introduced in ch. 5 — open in glossary .

The example is synchronous, the algorithm is not. The book draws every node computing at the same moment because it is easier to follow. The real algorithm allows a node to compute and send at any time, and it still converges.

When a link cost changes

The algorithm sits quiet until a link cost changes. Figure 5.7 shows the same three nodes with different costs: c(x,y) = 4, c(y,z) = 1, c(x,z) = 50.

Before anything happens the estimates have settled: D_y(x) = 4, D_y(z) = 1, D_z(y) = 1, D_z(x) = 5. Both scenarios below follow only the estimates for destination x, which is what the book does.

A cost that falls spreads quickly

The cost of the link from y to x drops from 4 to 1.

Three moments, and then it is over.

• At t₀, y detects the change, recomputes D_y(x) = 1, and tells its neighbours.
• At t₁, z receives the update and recomputes. Its cost to x falls from 5 to 2, so it tells its neighbours.
• At t₂, y receives z’s update. Its own least cost does not move, so y sends nothing. The algorithm is quiescent.

Two iterations. A cost that falls travels through the network fast.

A cost that rises spreads very slowly

Now the same link goes the other way: c(x,y) rises from 4 to 60.

At t₀, y detects it and recomputes:

We can see that 6 is wrong, because we can see the whole network. Node y cannot. All y knows is that its own link to x now costs 60, and that z last said it could reach x for 5. So y decides to route through z.

And z routes to x through y. That is a routing loop routing loop Simple Two routers each send the packet to the other, so it never arrives. Precise A state in which the forwarding decisions of two or more routers point at each other for the same destination, so a datagram for that destination is passed between them until the forwarding tables change or its time-to-live runs out. introduced in ch. 5 — open in glossary . A packet for x that arrives at either node is passed to the other, and then back, and never leaves.

Watch the two numbers climb. z hears that y can reach x for 6, so z computes min{50 + 0, 1 + 6} = 7. y hears 7 and computes min{60, 1 + 7} = 8. Then 9, then 10, and so on, one step per message.

The loop ends only when z’s path through y finally costs more than z’s own direct 50-cost link. The book says this takes 44 iterations, and the trace above agrees: exactly 44 messages carry an estimate below 50. Three more messages follow — y announces 50, z switches to its direct link and announces 50, and y settles at 51 — and then the algorithm goes quiet.

This is the count-to-infinity problem. The name comes from how bad it can get. Had c(y,x) changed from 4 to 10,000 with c(z,x) at 9,999, the two nodes would have counted upward for thousands of messages.

Poisoned reverse

The specific loop above can be avoided, and the trick is small.

If z routes through y to reach destination x, then z tells y that its distance to x is ∞. Not 5, which is the truth. ∞. And z keeps saying it for as long as it routes to x through y.

Since y believes z has no path to x at all, y will never try to route to x via z. The loop cannot form.

The same rise from 4 to 60, replayed with the lie switched on:

• At t₀, y updates and keeps routing directly to x, at the higher cost of 60. It tells z that D_y(x) = 60.
• At t₁, z receives it. Going through y would now cost 61, so z immediately switches to its own direct link, at cost 50.
• At t₂, this is a new least-cost path that no longer passes through y, so z tells y the truth: D_z(x) = 50.
• At t₃, y updates to D_y(x) = 51. Now z is on y’s least-cost path, so y poisons the reverse in turn and tells z that D_y(x) = ∞, although y knows it is 51.

Three messages instead of 47, and the same final answer.

Link-state and distance-vector compared

Both algorithms compute least-cost paths and neither one wins. The book’s own summary is a short list of trade-offs, and the opening sentence of that comparison is the cleanest statement of the difference:

In the DV algorithm, each node talks to only its directly connected neighbors, but it provides its neighbors with least-cost estimates from itself to all the nodes in the network. The LS algorithm requires global information — each node would need to communicate with all other nodes, but it tells them only the costs of its directly connected links.

The book’s verdict is that neither algorithm is an obvious winner, and that both are used in the Internet. Section 5.3 covers OSPF (Open Shortest Path First) Open Shortest Path First The Internet’s intra-AS link-state routing protocol. Each router builds a complete map of its autonomous system and runs Dijkstra locally. introduced in ch. 5 , which is link-state. Section 5.4 covers BGP (Border Gateway Protocol) Border Gateway Protocol The protocol ISPs use to tell each other which destinations they can reach; its rules follow the customer-provider and peering relationships. introduced in ch. 5 , which is distance-vector at heart.

Check yourself