OSPF Shortest Path First

Dijkstra's algorithm step by step on OSPF area 1 — the network turned into a graph of nodes and costed edges, a shortest-path tree grown from any root you pick, and the tree turned back into a routing table.

Every router in an OSPF area holds the same database, and runs Shortest Path First (SPF) on it to find the cheapest path to everywhere in the area. This demo takes area 1 of the network from the Hello and Database Exchange demos, strips it down to a graph, and runs Dijkstra's algorithm on it one decision at a time.

From network to graph

The router LSAs in area 1's database already describe a graph, so SPF needs nothing else:

Each router is a node: R1A to R1D become A to D, and the two ABRs E and F.
Each link is an edge with a cost, e0 to e6. The costs are set so that the fewest hops is not always the cheapest path: e2, the direct A–D link, costs 30.
Addresses, LANs and Hellos play no part. A LAN hangs off the end of a path and never lies along one, so it is added only when the routing table is built.
SPF runs per area, on that area's database alone: everything outside area 1 drops out.

Next (or →) moves one step. Click any node, or a letter in the Root row, to run the calculation from there instead.

Dijkstra's algorithm, one step at a time

The root starts on the candidate list at cost 0, and the list grows from there:

The cheapest candidate becomes final. Every other candidate already costs at least as much, and costs only add up along a path, so no route found later can reach it for less.
Each edge of the new final node is then checked:
- a node with no cost yet goes on the candidate list at the new node's cost plus the edge's;
- a candidate reached more cheaply this way takes the new, lower cost, and the edge of its old path drops out;
- a candidate already reached as cheaply stays as it is, and this edge drops out.
The calculation ends when every node is final. The edges left form a tree: exactly one path from the root to every other node, five edges for six nodes.

From A, B is final first at 5; then D drops from 30 (the direct e2) to 10 through B, and e2 drops out. The candidate list, the running cost on each node and the paths found so far sit beside the drawing.

One tree per router

Every router runs the same calculation on the same graph, each with itself as the root, so each gets a different tree. The trees agree with each other, because a piece of a shortest path is itself a shortest path: A reaches F through B and D, and D's own tree reaches F directly.

Loop-free forwarding from different trees

Different trees never send a packet round in a loop, as long as every router holds the same database: each hop takes the packet strictly closer to its destination, so no router can see it twice.

Each hop is on the next router's own shortest path. A's cheapest path to F costs 20, and its first hop, B, is 5 away. So B's cheapest path to F costs exactly 20 − 5 = 15: if B knew a cheaper one, A could reach F more cheaply through it; if B's best cost more, A's 20 could not exist.
The cost still to go shrinks at every hop, since every cost is positive. A packet back at a router it already passed would need that router's cost-to-go again, which a shrinking number never reaches. Equal-cost next hops keep this: each of them is on a shortest path too.
A loop needs two routers working from different databases. SPF cannot create one; a database out of date can.

That happens, briefly, while the network converges. Suppose e3, the B–D link, fails:

R1B notices first, reruns SPF, and now reaches R1D back through R1A: B → A → C → D, cost 30.
R1A gets the new LSA a hop later, and runs its own SPF later too. Until it does, its tree still says D is via R1B, so it hands the packet straight back.
The packet bounces between R1A and R1B — a micro-loop — until R1A reruns SPF and switches to A → C → D at 25.

The micro-loop lasts as long as flooding and the next SPF run take, usually well under a second. A packet caught in it is not stuck for ever: each router it crosses lowers its TTL, and it is dropped at zero. That is why OSPF floods a change before it does anything else. The Flooding demo runs this failure, packet by packet.

From the tree to the routing table

The last step puts the tree back on the network as the root's routing table for area 1:

Each network's cost is the path to the router it hangs off, plus the cost of that router's link to it. R1A reaches R1C's LAN, 10.1.110.0/24, at 10 + 10 = 20.
A router keeps only the first hop of each path, as a next-hop address and an outgoing interface. The next router along picks its own next hop, from its own tree.
Two paths of equal cost give two next hops. From A, the C–D link (10.1.4.0/30) costs 25 through R1C and 25 through R1B; OSPF keeps both and shares the traffic between them.

Simplifications in the demo

Ties between candidates go alphabetically here; a real router may take either.
The routing table covers area 1 only. The routes to other areas come from the ABRs' summary LSAs, the subject of the next demo in the series, OSPF Inter-Area Routing .