A link-state protocol makes every router hold the same map of the network, built by flooding each router’s list of its own links, and each router then computes the shortest path to every destination from that map with Dijkstra’s algorithm. In a network of 5 routers and 7 links, flooding one announcement takes 2 x 7 - (5 - 1) = 10 transmissions, and when one link fails the recomputed route changes at once, with no counting to infinity. The price is memory for the map and a burst of traffic at every change, which matters on slow radio links.
Part of Networking
The OSPF family of routing protocols: flooding, the shortest-path calculation worked by hand, equal-cost paths, and the arithmetic of the traffic a change causes.
Every Router Computes From The Same Map
Routing Basics describes the principle: each router learns the complete topology by exchanging link state advertisements with all the others and computes shortest paths independently using Dijkstra’s algorithm, converging typically in seconds. This article does the arithmetic that the other articles only state. The calculation below is original to this article and was checked by program as well as by hand; it uses an invented network and invented costs, and no timers or packet sizes, which are not sourced here.
A router’s advertisement lists its own links and their costs. Every router that receives a new advertisement stores it and forwards it out all its other interfaces, so the whole network ends up with the same database. Advertisements carry a sequence number so a router can tell a new one from a copy it already has, and only forwards the new one (general knowledge about how such protocols avoid loops). Each router then runs the same algorithm on the same data, so they agree about the paths without ever exchanging distances.
What You Need
- A cost for every link — set from the link speed so that fast links are preferred (Dynamic Routing); here the costs are small invented integers
- A diagram — a paper graph is enough to check any result
- A pencil — Dijkstra by hand is a table
The Example Network
Routers A, B, C, D, E and links with costs: A-B 2, A-C 3, B-C 5, B-D 6, C-D 2, C-E 4, D-E 1. That is 5 routers and 7 links.
Method: Dijkstra From Router A
Keep a set of settled routers. Start with A at cost 0. Repeat: settle the unsettled router with the smallest tentative cost, then relax its neighbours (set a neighbour’s cost to settled cost + link cost if that is smaller).
| Step | Settle (cost) | Relaxations |
|---|---|---|
| 1 | A (0) | B = 2 via B, C = 3 via C |
| 2 | B (2) | D = 2 + 6 = 8 via B; C via B would be 2 + 5 = 7, worse than 3, keep 3 |
| 3 | C (3) | D = 3 + 2 = 5 via C (better than 8); E = 3 + 4 = 7 via C |
| 4 | D (5) | E = 5 + 1 = 6 (better than 7), still reached through C |
| 5 | E (6) | nothing left |
The routing table at A, with the first hop for each destination:
| Destination | Cost | First hop |
|---|---|---|
| B | 2 | B |
| C | 3 | C |
| D | 5 | C |
| E | 6 | C |
Worked Example 1: A Link Fails
Link C-D fails. Both ends announce the change, every router updates its map and reruns the calculation. From A: B stays at 2 and C at 3. E is now reached A-C-E for 3 + 4 = 7. D is reached A-B-D for 2 + 6 = 8, but also A-C-E-D for 3 + 4 + 1 = 8. The two paths tie, so A may use either or share traffic between them. A tie is not an error, but it matters: you cannot say “the” path unless the protocol breaks ties in a documented way. The new table at A: B 2 via B, C 3 via C, D 8 via B (or via C), E 7 via C. No router counted upward, because every one recomputed from a map that already showed the link gone (Distance Vector shows the contrast).
Worked Example 2: What Flooding Costs
Model: the originating router sends its announcement on every link; every other router, on first receipt, forwards it on every link except the one it arrived on; later copies are discarded. Count transmissions. The originator with degree d sends d. Every other router v sends deg(v) - 1. Summing the degrees over all routers gives 2L, where L is the number of links (each link counts at both ends). So total = deg(origin) + (2L - deg(origin)) - (R - 1) = 2L - (R - 1).
For L = 7 and R = 5: 2 x 7 - (5 - 1) = 14 - 4 = 10 transmissions per announcement. A program simulating the flood from each router in turn gave 10 for every one, as the formula predicts.
Initial start-up: each of the 5 routers floods its own announcement, 5 x 10 = 50 transmissions in this model. One link failure: the 2 routers at its ends each announce, 2 x 10 = 20 transmissions. A link that flaps repeatedly costs 20 transmissions each time, which is why a flapping radio link is damaging to the whole network and not just to itself. Real protocols also acknowledge announcements, which adds to these counts (general knowledge; no figure is given).
Common Mistakes
- Mismatched costs on the two ends of a link — each end advertises its own cost and the routers then disagree about which way is cheaper
- Assuming one best path — equal-cost ties are normal in regular layouts
- Ignoring a flapping link — every flap makes the whole network recompute; fix or disable the link
- Using it on a tree — Routing Protocols explains why static routes serve a network with no loops
What’s Next
- Learn next: Routing Tables — how the result is stored and looked up
- Combine with: BGP Basics — what the old internet used between independent networks