How a packet finds its way

A packet leaving your laptop does not carry a route. Nobody plans its trip across the network in advance. Each router it meets makes one small decision, which neighbour to hand it to next, and the packet still arrives by the cheapest way. Inside one network run by one organisation, that works because every router has worked out the whole map, and then uses only one step of it.

What is being claimed

A router is a machine that joins several links and passes packets between them. Inside one network run by one organisation, one standard way to choose routes is OSPF, specified by J. Moy in RFC 2328. In OSPF each router keeps a database describing the network's layout: which routers exist, which links join them, and what each link costs. Within one region of the network, which the standard calls an area, every router has an identical copy. From that copy each router builds a routing table by constructing a tree of shortest paths with itself at the root. The RFC is plain about what happens next: the tree gives the entire path to every destination, “However, only the next hop to the destination is used in the forwarding process.”

Why it is worth knowing

This is why a network can lose a link and keep working without anyone steering traffic by hand. No router needs to agree with the others about a packet's full journey. It only needs to agree about the map. If every router holds the same map and computes honestly, their separate one-step choices fit together into whole cheapest paths.

Cost is a sum, and the tree grows from the nearest

Each link has a cost, a plain number with no units that is configured on the router interface sending onto it. The RFC requires it to be greater than zero. The cost of a path is the sum of the costs of its links, and one path is shorter than another if that sum is smaller. So the cheapest route need not be the one with the fewest links. In the network below, A reaches G by A→C→B→E→G for 2 + 1 + 2 + 2 = 7, even though A→B→E→G uses one link fewer: it costs 6 + 2 + 2 = 10.

The tree is built by a method E. W. Dijkstra published in 1959. He put it as finding the path of minimum total length between two nodes P and Q, with the minimal paths from P “constructed in order of increasing length until Q is reached.” He sorts the nodes into three sets: those whose shortest path is known, those connected to a known node but not yet known themselves, and the rest. At each step the node in the middle set with the smallest distance from P moves into the known set, and its neighbours are looked at again. RFC 2328 describes the same loop in its own words. Of the candidate routers, the one closest to the root is “guaranteed to be shortest”; it joins the tree, its neighbours are examined, and the loop stops when no candidates are left.

Why is the closest candidate safe to lock in? Any other way of reaching it would have to leave the known set through some other candidate, which is already at least as far away, and every link after that adds a positive cost. Nothing can undercut it.

Only the first step is used

Router A's tree says the path to G is A, C, B, E, G. But A only acts on the first step: it hands the packet to C. C then consults its own tree, rooted at C, and hands the packet to B. Because C holds the same map, the rest of A's path is also C's cheapest path to G, so the hops agree. Dijkstra's paper states the fact underneath this: if R lies on the minimal path from P to Q, then the part from P to R is itself minimal. The same argument, our step rather than his, shows the part from R to Q is minimal too.

When a link changes, OSPF does not patch the old answer. In the RFC's words, “The present routing table is invalidated. The routing table is built again from scratch.” Take the B–C link down in the figure and A's new cheapest path to G is A→C→F→G, at 2 + 1 + 6 = 9. If two paths tie, the RFC says traffic is shared equally among them.

The other family

Not every protocol works from a map. In RIP, specified by G. Malkin in RFC 2453, each router tells its neighbours only how far it thinks each destination is, every 30 seconds and also when something changes. Without a map, routers can mislead each other after a failure, each counting its distance upward through the other. RIP stops the count by treating 16 as infinity, so valid distances run from 1 to 15. Its main defence, split horizon with poisoned reverse, is described in the RFC as preventing loops that involve only two routers; with three, the mutual deception can still happen.

In short

Every router in an OSPF area holds the same map, builds its own shortest-path tree by adding the nearest remaining router first, and then throws away all of the path but the next hop. Because the maps agree, those single steps chain into the whole cheapest route.