A network becomes a graph and a good path becomes the cheapest path. The link-state algorithm then finds every cheapest path from one node, by growing a set of solved nodes outward.
Words you will meet
-
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 — the path whose edge costs add up to the smallest total.
-
Centralized routing algorithm centralized routing algorithm Simple Compute the path knowing the whole network. Precise A routing algorithm that computes least-cost paths using complete, global knowledge of connectivity and all link costs. The calculation may run at one site or be replicated in every router; what defines it is the completeness of the information, not the location. introduced in ch. 5 — open in glossary — one that computes using complete knowledge of the whole network.
-
Decentralized routing algorithm decentralized routing algorithm Simple Compute the path knowing only your neighbours. Precise A routing algorithm in which the least-cost calculation is carried out iteratively and distributed across routers. No node has complete information about all link costs. Each begins knowing only the costs of its own attached links, then converges through repeated exchange with its neighbours. introduced in ch. 5 — open in glossary — one where no node knows the whole network, and the answer is reached by repeated exchange.
-
Link-state algorithm link-state algorithm Simple Every node knows the whole map and works the answer out itself. Precise A routing algorithm in which the network topology and all link costs are known to every node, typically by link-state broadcast. Each node then computes least-cost paths locally with Dijkstra’s algorithm. introduced in ch. 5 — open in glossary — written LS (Link-State) Link-State A routing algorithm in which every node knows the whole graph and runs Dijkstra locally. introduced in ch. 5 : a centralized algorithm, because every node knows every link cost.
-
Link-state broadcast link-state broadcast Simple Tell every other node about my own links. Precise The mechanism that gives a link-state algorithm its global view. Each node broadcasts a link-state packet, containing the identities and costs of its attached links, to all other nodes in the network — not only to its neighbours. The result is that every node holds an identical and complete view. introduced in ch. 5 — open in glossary — how every node comes to know every link cost.
-
Dijkstra’s algorithm dijkstra's algorithm Simple Grow a set of solved nodes outward from the source. Precise The link-state algorithm the book presents. It computes the least-cost path from one source node to all other nodes, iteratively: after the kth iteration the least-cost paths are known to k destinations, and those k paths are the k cheapest of all. Worst-case complexity O(n squared). introduced in ch. 5 — open in glossary — the particular link-state algorithm this section runs.
-
Route oscillation route oscillation Simple Everyone moves to the quiet path at once, so it stops being quiet. Precise The pathology that arises when link costs depend on the load the links carry. Routers all shift traffic onto whichever path is currently cheapest, which makes that path expensive and the abandoned one cheap, and the pattern repeats indefinitely. introduced in ch. 5 — open in glossary — what goes wrong when a link’s cost is the traffic it is carrying.
Why this matters
Section 5.1 said the control plane fills in the forwarding table. It did not say what the control plane is actually computing. This section says: the cheapest path through a graph.
That reduction is the useful part. Once a network is a graph with numbers on its edges, the routing problem stops being about cables and becomes a problem mathematicians solved in 1956. The book is honest that the reduction leaks — policy does not fit into a cost, and section 5.4 is about what happens when it will not fit. But everything inside one organisation runs on this.
The algorithm here is also the one running in 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 section 5.3 covers, so this is not preparation for the real thing. It is the real thing, on a six-node example.
A network becomes a graph
A graph G = (N, E) is a set N of nodes and a collection E of edges, where each edge is a pair of nodes from N.
N means something new here
N is now the set of nodes, and n is how many there are.
In section 4.2.2 the letter N was the number of ports on a
router. In section 4.2.4 it was the number of independent
TCP (Transmission Control Protocol) Transmission Control Protocol The Internet transport protocol that delivers data reliably and in order, with flow control and congestion control.
introduced in ch. 1 flows, in the buffer-sizing rule B = RTT·C/√N. This is a
third meaning, in a third chapter.
The clue that tells them apart: chapter 5’s N is a set, not a count. It never appears inside an arithmetic expression. When you see a number divided by N, you are in chapter 4.
One more warning, because it costs people marks. N and N′ are one apostrophe apart and are not the same set. N is every node. N′ is only the nodes whose least cost is already settled. This page writes N′ as “the solved set” every time.
In routing, the nodes are routers — the points at which forwarding decisions are made — and the edges are the physical links between them. Later, in 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 , the nodes will be whole networks and an edge will mean direct connectivity, known as peering.
Every edge carries a value representing its cost, written c(x, y). A cost
may reflect the physical length of the link, its speed, or the money it costs. A
transoceanic link might cost more than a short terrestrial one. The book takes
the costs as given and does not say how they are set.
Two rules about costs, both worth remembering:
- If the pair (x, y) is not an edge, then
c(x, y) = ∞. - The graphs here are undirected, so
c(x, y) = c(y, x). The algorithms extend to directed links with a different cost each way, but the examples do not use them.
A path is a sequence of nodes where every consecutive pair is an edge. Its cost is the sum of the edge costs along it. Between any two nodes there are usually many paths, and one or more of them is a least-cost path. If every edge costs the same, the least-cost path is also the shortest path — the one with fewest links.
The book’s own exercise, and what it is really asking
The book asks you to find the least-cost path from u to z in Figure 5.3, and then to notice how you did it.
Most people trace a few routes, compare them, and stop when one feels right. There are 17 possible paths from u to z. You almost certainly did not check all of them.
That is the point of the question. Whatever you did, you did it in one place, with the whole map in front of you. That is a centralized routing algorithm, run in your brain. The other kind — where nobody can see the map — is section 5.2.2.
(The 17 is verifiable, and this site verifies it: tools/check-graph-ch05.mjs
enumerates every simple path in the graph below and asserts the count. A single
wrong edge would change it, so the check also proves the graph was transcribed
correctly.)
Three ways to sort routing algorithms
The book classifies routing algorithms three times over, and the three classifications are independent of each other.
| Split | One side | The other side |
|---|---|---|
| What it knows | centralized — complete, global knowledge of connectivity and all link costs. Called a link-state algorithm, because it must know the state of every link. §5.2.1 | decentralized — no node has complete information. Each starts knowing only its own attached links and converges by exchanging with neighbours. Called a distance-vector algorithm. §5.2.2 |
| How fast it changes | static — routes change very slowly, often only when a human edits a link cost | dynamic — routes change as load or topology changes, either periodically or in response to an event. More responsive, but more prone to routing loops and oscillation |
| What it reacts to | load-sensitive — link costs vary with congestion, so the algorithm steers around busy links | load-insensitive — cost does not reflect congestion. RIP (Routing Information Protocol) Routing Information Protocol An early intra-AS distance-vector routing protocol. introduced in ch. 5 , OSPF and BGP are all load-insensitive |
In plain words
“Centralized” does not mean “runs in one place”.
The book is careful here and it is easy to miss. A centralized algorithm can be run at one site, such as the controller in Figure 5.2. It can equally be replicated in the routing component of every single router, as in Figure 5.1.
What makes it centralized is that the algorithm has complete information. Not where it runs. Every router in an OSPF network runs the same centralized algorithm on the same complete map, and arrives at the same answer.
How every node comes to know every link
A link-state algorithm needs the topology and all link costs as input. Where do they come from?
Each node broadcasts a link-state packet to all other nodes in the network. Each packet contains the identities and costs of that node’s own attached links. In practice this uses a link-state broadcast algorithm, and OSPF does exactly this in section 5.3.
The result: every node has an identical and complete view of the network. Each can then run the algorithm and compute the same set of least-cost paths as everyone else.
Broadcast to all nodes, not to neighbours
This one word is the whole difference between the two algorithms in section 5.2, and it is easy to read past.
A link-state node sends its information to every node in the network. A distance-vector node sends only to its directly attached neighbours, and never learns the map at all.
Everything else follows from that. Link state converges fast and needs a network-wide flood. Distance vector needs no flood and, as section 5.2.2 shows, can take a very long time to recover from bad news.
Dijkstra’s algorithm, and its three variables
Dijkstra’s algorithm computes the least-cost path from one node — the source, called u — to all other nodes. It is iterative, and it has a strong property:
After the kth iteration, the least-cost paths are known to k destination nodes, and among the least-cost paths to all destinations, these k paths have the k smallest costs.
Three variables carry all the state:
| Symbol | Meaning |
|---|---|
| D(v) | the cost of the least-cost path from the source to v as of this iteration — a running estimate, not the answer yet |
| p(v) | the previous node, a neighbour of v, along that current least-cost path |
| N′ | the solved set: v is in N′ if the least-cost path from the source to v is definitively known |
Link-State (LS) Algorithm for Source Node u
1 Initialization:
2 N' = {u}
3 for all nodes v
4 if v is a neighbor of u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in N' such that D(w) is a minimum
10 add w to N'
11 update D(v) for each neighbor v of w and not in N':
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 least path cost to w plus cost from w to v */
15 until N' = NThe loop runs once per node in the network. When it stops, every least-cost path from u is known.
Run it
Initialization. N′, the solved set, holds only the source u. Every neighbour of u gets D = the cost of the direct link. Every other node gets ∞.
| step | N′ | D(v), p(v) | D(w), p(w) | D(x), p(x) | D(y), p(y) | D(z), p(z) |
|---|---|---|---|---|---|---|
| 0 | u | 2, u | 5, u | 1, u | ∞ | ∞ |
This run contains a tie. Tick break ties the other way and step through again: the order the nodes enter N′ changes, and every final least cost stays the same.
Green nodes are in N′, the solved set. The green edges are the least-cost tree so far; a gold edge is a current best guess that may still be beaten. Change the source to run the algorithm from any node, and tick the tie box to break the one tie the other way.
The first three steps, in the book’s own words
Initialization. The paths from u to its directly attached neighbours v, x and w are set to 2, 1 and 5. Note that the cost to w is set to 5 even though a cheaper path exists — 5 is simply the cost of the direct one-hop link. y and z are set to ∞ because they are not attached to u.
Iteration 1. Among the nodes not yet in the solved set, x has the least cost, 1, so x joins. Now line 12 runs. The cost to v is unchanged at 2. The cost to w through x is 4, cheaper than 5, so w’s estimate drops to 4 and p(w) becomes x. The cost to y through x is 2.
Iteration 2. v and y are both at 2. The book breaks the tie arbitrarily and adds y. The estimate for w now drops again, to 3 through y, and z becomes 4 through y.
Tick break ties the other way above and step through again. v enters the solved set before y, the table looks different — and every final cost is identical. That is what “arbitrarily” is allowed to mean.
From p(v) to a forwarding table
When the algorithm terminates, each node has its predecessor along the least-cost path from the source. That predecessor has a predecessor, and so on, so the entire path can be reconstructed backwards.
The forwarding table at u is then built by storing, for each destination, the next-hop node on the least-cost path to it. Step the widget above to the end and the third table appears: it is Figure 5.4, and every destination except v leaves u by the link (u, x).
In plain words
Look at how little survives.
The algorithm computed five complete paths, each with a cost and a chain of predecessors. The forwarding table keeps one letter per destination: the first hop.
Everything else is thrown away, because a router never needs it. It is the same point section 4.1 made about the data plane. The router does not think, and the entire result of the thinking is one column of a table.
What it costs to run
Given n nodes, not counting the source, how much work is this in the worst case?
The first iteration searches all n nodes to find the minimum. The second searches n − 1, the third n − 2, and so on. The total is
n(n + 1) / 2
which grows as n squared, so the algorithm as written is O(n²).
The book adds the standard caveat: a more sophisticated implementation using a heap finds the minimum in line 9 in logarithmic rather than linear time, which reduces the complexity.
The pathology: costs that depend on traffic
Before leaving the link-state algorithm, the book shows one way it can misbehave.
Suppose link costs are equal to the load carried on the link — a reasonable
idea, since a busy link really does delay packets. In this example, costs are not
symmetric: c(u,v) equals c(v,u) only when both directions carry the same
load.
Three nodes are sending to w. z sends one unit, x sends one unit, and y sends a tiny amount called e.
z sends its unit straight to w. x sends its unit straight to w. y sends its e to x, which forwards it, so the x-to-w link carries 1+e. Cost equals load on every link.
The book labels both directions of every link. This drawing labels only the direction that carries traffic, and names it, because in each panel the other direction carries nothing. Gold means the link is in use; the number beside it is both its load and its cost.
Read all steps as text
- a — the initial routing — z sends its unit straight to w. x sends its unit straight to w. y sends its e to x, which forwards it, so the x-to-w link carries 1+e. Cost equals load on every link.
- b — x and y switch clockwise — y compares: clockwise through z costs 0+1 = 1; its current path through x costs more. x compares: its direct link now costs 1+e, while going clockwise through y and z costs 0+0+1 = 1. Both switch.
- c — all three switch counterclockwise — Everything piled onto the clockwise route, so the clockwise links are now expensive and the counterclockwise links cost 0. x, y and z all find a zero-cost counterclockwise path to w, and all take it.
- d — and back to clockwise — Now the counterclockwise links are loaded and the clockwise ones are free. Panel d is identical to panel b. The network has completed one full cycle.
- e — it never settles — Step forward again and you get panel c. The routing flips between these two states for as long as the algorithm keeps running. Nothing is broken and no router is at fault; each one is doing exactly what the algorithm says.
One printed number does not match its own figure
Describing the move from panel a to panel b, the book gives two numbers for y. It says the clockwise path to w costs 1, and that the counterclockwise path y had been using costs 1 + e.
The first number is right: y’s clockwise path is y→z→w, costing 0 + 1 = 1.
The second does not match Figure 5.5(a). y’s counterclockwise path is y→x→w,
and the figure’s own labels give c(y,x) = e and c(x,w) = 1 + e. The sum is
1 + 2e, not 1 + e.
Nothing in the argument changes. e is tiny and positive, so 1 is smaller either way, and y still switches. Every other number in all four panels is exactly consistent — this site checked each panel’s loads against each panel’s costs. It is a slip in one sentence, not a fault in the example.
Everyday picture — the empty motorway
A traffic app tells every driver which route is fastest right now.
The motorway is jammed, the back road is empty, so the app sends everyone to the back road. A minute later the back road is jammed and the motorway is empty, so the app sends everyone back. Nobody gets anywhere quickly, and every driver was following correct advice at the moment they received it.
Where the picture stops. Drivers arrive and leave, so real traffic partly self-corrects. In Figure 5.5 the traffic never leaves — the same three flows are present in every panel, which is why it cycles forever instead of settling.
What can be done about it
The book offers two fixes and rejects the first.
Mandate that link costs not depend on the traffic carried. This works, and the book calls it unacceptable: one goal of routing is to avoid congested, high-delay links, and this forbids noticing them.
Ensure not all routers run the algorithm at the same time. More reasonable. Even routers running with the same period should not run at the same instant.
Except that they do. Researchers have found that routers in the Internet can self-synchronize. Even when they start out running the algorithm at different instants, the execution can drift into step and stay there.
The fix for the fix: each router randomizes the time it sends out its link advertisement.
In plain words
Oscillation is not a bug in Dijkstra’s algorithm.
The book is explicit that it can arise in any algorithm using a congestion- or delay-based metric, not only a link-state one. The trouble is the feedback loop: the measurement changes the thing being measured.
This is why today’s Internet routing protocols — RIP, OSPF and BGP — are all load-insensitive. A link’s cost does not reflect how busy it is. Routing around congestion sounds obviously good, was tried in the early ARPAnet, and was abandoned.
Check yourself
Check yourself
0 of 7 answered1.What makes a routing algorithm "centralized" in the book's classification?
2.A link-state node broadcasts its link-state packet to whom?
3.predictIn the initialization, D(w) is set to 5, even though the algorithm will later find a path to w costing 3. Why is that not a bug?
What does D(v) actually mean at each stage?
4.predictAt step 2 the book finds v and y both at cost 2, and breaks the tie in favour of y. Run the widget with the tie broken the other way. What changes?
Compare the last row of the table, and then the forwarding table.
5.Why does Figure 5.5's network oscillate forever?
6.The book rejects one of the two fixes for oscillation. Which, and why?
7.What does the forwarding table at u keep, out of everything Dijkstra computed?
What to remember
- A link-state node broadcasts to all nodes, not to its neighbours. That is the single word separating this section from the next one.
- Dijkstra keeps three things: D(v) the running cost estimate, p(v) the predecessor, N′ the solved set. Each round moves the cheapest unsolved node into N′ and updates its neighbours.
- Costs that depend on load make routes oscillate, in any algorithm, not just this one. Today’s Internet protocols are all load-insensitive because of it.