Link-State Routing and Dijkstra’s Algorithm, Step by Step

The picture: everyone gets the same map#

Picture six friends in six towns. Each friend gets the same printed road map, showing every road and how many minutes it takes. Nobody asks for directions. Each friend works out the fastest way from their own town to every other town.

That is link-state routing. The towns are routers, the roads are links, and the minutes are link costs. First everyone gets the same complete map. Then each router works out its own best routes from it.

The method each friend uses is Dijkstra’s algorithm. Like a ripple in a pond, it settles the nearest town first, then the next nearest, until every town is settled.

Vocabulary, before anything uses it#

Routing as a graph problem, and the kinds of routing algorithm#

A routing algorithm is a method for finding good paths through the network. Underneath, every one solves the same problem: find the least-cost path in a graph. The cost of a path is the sum of the link costs along it. If every link costs 1, the least-cost path is simply the one with the fewest hops.

Here is the network this guide uses. It has six routers (A, B, C, E, F and G) and nine links. There is no router D, so the letter D only ever means a cost. All costs are the same in both directions.

Three ways to classify a routing algorithm

How every router gets the map: link-state broadcast#

Dijkstra needs the whole map, so the routers must build it first. Each router knows only the links attached to it and their costs. It packs that list into a link-state packet (also called a link-state advertisement, LSA) and sends it to every other router in the network. Each router passes these packets on to its neighbors, a process called flooding, until every router has a copy from every other router.

When the flooding is done, every router holds an identical map. Each one then runs Dijkstra with itself as the source. Because the maps match, their answers fit together.

Dijkstra’s algorithm, worked in full#

The source here is A. The algorithm has a start and a loop.

Start. N′ = {A}. For each other node v, set D(v) = c(A, v) if v is a neighbor of A, and D(v) = ∞ if not. Set p(v) = A for each neighbor.

Loop, until every node is in N′:

1. Among the nodes not yet in N′, pick the one with the smallest D. Call it w. Add w to N′. Its D(w) is now final.
2. For every neighbor v of w that is not in N′, check whether going through w is cheaper:

D(v) = min( D(v), D(w) + c(w, v) )

In words: keep the old cost, or reach w and then take the link to v, whichever is smaller. If going through w wins, also set p(v) = w.

Here is the whole run from A. Each cell shows D(v), p(v). A blank cell means that node is already in N′, so its value is final and no longer changes.

The bold entry in each row is the smallest unsettled D: the node added in the next step.

From the table to a forwarding table

To read the path to any node, follow the predecessors backwards. For F: p(F) = E, p(E) = G, p(G) = B, p(B) = A. So the path is A → B → G → E → F, with cost 2 + 5 + 2 + 3 = 12. Doing this for every node gives the shortest-path tree: the links A–B, A–C, B–G, E–G and E–F.

A router only needs the first hop of each path, because the next router makes its own decision. So A’s forwarding table is:

How much work it takes, and the oscillation problem#

The cost: O(n²)

Say there are n nodes besides the source. To find the smallest D, the first step looks through all n of them, the next step n − 1, and so on down to 1. The total is n(n + 1) / 2. That grows like n², so the worst case is written O(n²), read “order n squared”.

The oscillation problem

Trouble starts when link costs are load-sensitive, meaning a link’s cost equals how much traffic it is carrying. Picture two routes from S to T: a top route and a bottom route. S sends 10 units of traffic.

1. Both routes start empty, so both cost 0, and the tie is broken toward the top route. Now the top costs 10 and the bottom costs 0.
2. Every router reruns Dijkstra. The bottom is cheaper, so all the traffic moves there. Now the bottom costs 10 and the top costs 0.
3. Every router reruns Dijkstra again, and all the traffic swings back to the top.

The routes flip back and forth and never settle. That is oscillation. One fix is not to make costs depend on load, though the textbook rejects this because routers then cannot steer around congestion. The better fix is to stop routers all rerunning at once, by having each send its link-state packets at a slightly random time.

Practice#

Write out the whole Dijkstra table whenever a question involves one. The rows earn the marks.

1. Classify Dijkstra’s algorithm as used in link-state routing: centralized or decentralized? Then say what information a router must have before it can start.
2. Using the six-router network in this guide, run Dijkstra with G as the source. Give the final least cost to every other node and G’s forwarding table (which neighbor each destination is sent to).
3. In the worked table from A, D(E) was 11 after step 1 and 9 after step 3. Which node caused the change, and what was the calculation?
4. The cost of link E–G rises from 2 to 6, and A reruns Dijkstra. What are A’s new least costs to E and to F, and which link does A now use for E?
5. A network has 21 routers. Using the simple version of Dijkstra, how many nodes in total does one router look at to find the smallest D across the whole run?
6. Explain why link costs that follow traffic load can make routes oscillate, and give one fix.

Solutions#

1. Centralized (global). Each router runs it itself, but only after link-state broadcast has given it the complete map: every link and its cost.
2. A 7, B 5, C 7, E 2, F 5. Forwarding: A, B and C go to B; E and F go to E. Start: D(B) = 5, D(C) = 8, D(E) = 2, D(F) = 6, D(A) = ∞. Settle E (2): F improves to 2 + 3 = 5 through E; C through E would be 12, worse than 8. B and F now tie at 5; either order gives the same answer. Settle B (5): A becomes 5 + 2 = 7 through B, and C improves to 5 + 2 = 7 through B. Settling F, A and C improves nothing. Paths: G→B→A, G→B, G→B→C, G→E, G→E→F.
3. Node G, when it joined N′ in step 3. D(G) + c(G, E) = 7 + 2 = 9, which beats the old 11 (through C, 1 + 10), so D(E) became 9 and p(E) became G.
4. E costs 11, F costs 13, and E is reached over link (A, C). Through B and G, E would now cost 7 + 6 = 13, so the route A → C → E at 1 + 10 = 11 wins. F is now best as A → B → G → F at 2 + 5 + 6 = 13.
5. 210. There are n = 20 nodes besides the source, so the total is n(n + 1) / 2 = 20 × 21 / 2 = 210.
6. Moving traffic changes the costs that chose the route. All routers move onto the cheaper path together, which makes it the expensive one, so they all move back next run. Fixes: do not make link costs depend on load, or make routers run (and send link-state packets) at randomized times so they do not all switch together (the preferred fix).

Test-readiness checklist#

• ☐  I can describe a network as a graph with link costs c(x, y), and say what c(x, y) = ∞ means.
• ☐  I can sort a routing algorithm by the three classifications: centralized or decentralized, static or dynamic, load-sensitive or not.
• ☐  I can explain how link-state broadcast gives every router the same map.
• ☐  I can fill in a full Dijkstra table with N′, D(v) and p(v), one row per step.
• ☐  I can read paths from the predecessors and turn them into a forwarding table.
• ☐  I can state the O(n²) cost and compute n(n + 1) / 2 for a given network.
• ☐  I can explain the oscillation problem and one way to avoid it.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written.