One last look: the map versus the move
Before we compute anything, let us pin down the difference one final time, because it is the whole point of this rung. Forwarding is the fast, local move a router makes for one packet: read the destination, look it up in a table, shove the packet out the right interface, all in nanoseconds. Routing is the slow, thoughtful job that fills that table in the first place: deciding which path is actually best across the whole network. The earlier rung on IP showed you the move; this guide is about building the map that makes the move correct. If forwarding versus routing still feels blurry, picture a courier who already knows the streets (forwarding) versus the city planner who drew the road map (routing).
The previous guide handed us the planner's raw material: the network drawn as a graph. Each router is a node, each link between two routers is an edge, and every edge carries a number called its cost or weight — maybe it reflects distance, money, or a link's congestion, but to the algorithm it is just a number to add up. A network graph like this lets us ask a precise question instead of a vague one. Not 'what feels like a good route?' but 'of all the ways to walk from this router to that one, which one has the smallest total of edge costs?'
That precise question has a name: finding the least-cost path. And here is the subtlety worth saying out loud — the least-cost path is not always the one with the fewest hops. A two-hop route over two fast, lightly loaded links can easily beat a one-hop route over a single slow, congested link. The whole art of routing lives in choosing the costs sensibly; once the costs are set, the algorithm just does honest arithmetic.
Two ways to know the network
There are two great families of routing algorithm, and the difference between them is simply how much of the map each router gets to see. In link-state routing, every router ends up holding a complete map of the whole network — every node, every link, every cost — and then computes its own best paths privately. In distance-vector routing, no router ever sees the whole map; each one knows only its direct neighbours and trusts what those neighbours tell it about the rest, like asking the person next to you 'how far to the station from where you stand?' This guide is the link-state story; the next guide is the distance-vector story, and it has a famous bug we will meet there.
How does a router in a link-state network get the whole map when it can physically see only the links plugged into it? By a step called flooding. Each router measures the cost to each of its own directly attached neighbours, packs that little list into a message called a link-state advertisement, and floods it to every other router — each router that receives a fresh advertisement passes it on out all its other links, so the news spreads to the entire network like a rumour. Once every router has heard everyone else's advertisement, each one can reassemble the complete graph from the pieces. Now they all hold the same map.
Dijkstra's algorithm: greedy, but provably right
Now each router has the same complete graph. Turning it into a routing table is the job of Dijkstra's algorithm, named after Edsger Dijkstra, who sketched it in 1956. The idea is beautifully stubborn. The router keeps two groups of nodes: those whose true cheapest cost from the source is already settled and final, and those still tentative. It also keeps, for every node, the cheapest cost found to it so far and which neighbour you would arrive from. Then it repeats one move until done: among all the still-tentative nodes, pick the one with the smallest tentative cost, declare that cost final, and use it to relax its neighbours.
That word relax just means: check whether going through the node we just finalised gives a cheaper way to reach one of its neighbours than anything we had before, and if so, write down the lower cost. The reason this works is the greedy insight at the algorithm's heart: if the smallest tentative cost in the whole frontier is, say, 7, then 7 must be the true final cost for that node, because every other path to it would have to pass through some node that already costs at least 7 to reach — so it could never come out cheaper. (This relies on costs being non-negative, which for network link costs they always are; Dijkstra is not safe with negative edges, but no sane router assigns a negative cost to a link.)
- Start at your own router, the source. Set its cost to 0 and every other node's cost to infinity (meaning 'no path found yet'). Mark all nodes tentative.
- Among the tentative nodes, pick the one with the smallest cost. Declare that cost final and move the node into the finished set — its cheapest path is now known for good.
- Relax that node's neighbours: for each neighbour, compute (the node's final cost) plus (the cost of the link to that neighbour). If this beats the neighbour's current tentative cost, lower it and remember you would arrive via this node.
- Repeat the pick-and-relax move until every node is finished. The 'arrive via' pointers now trace the least-cost path to every destination, and the first hop of each becomes one row in the forwarding table.
A tiny worked example
Numbers make this concrete. Suppose our router is node A, and the graph has five nodes A, B, C, D, E with these link costs: A-B is 2, A-C is 5, B-C is 1, B-D is 4, C-E is 2, D-E is 1. We want A's least-cost path to everyone. Watch how the greedy pick keeps choosing the smallest frontier cost, and how relaxing B's cheap link to C quietly fixes the cost to C that the direct A-C link had set too high.
Links: A-B=2 A-C=5 B-C=1 B-D=4 C-E=2 D-E=1 (source = A) step finalize via | tentative costs from A (cost, via) ---- -------- ---- | B C D E 0 A (0) -- | 2,A 5,A inf inf 1 B (2) A | -- 3,B 6,B inf <- C drops 5->3 via B 2 C (3) B | -- -- 6,B 5,C 3 E (5) C | -- -- 6,B -- <- E=3+2 via C beats nothing yet 4 D (6) B | -- -- -- -- Final least-cost paths and FIRST HOP from A: to B : cost 2, path A-B, first hop B to C : cost 3, path A-B-C, first hop B to D : cost 6, path A-B-D, first hop B to E : cost 5, path A-B-C-E, first hop B
Look at the last column of the result: the forwarding table only ever stores the first hop, not the whole path. To reach E, A does not need to remember 'A then C then E'; it just needs to know 'send it to B and trust B to do the rest.' That is the deep reason routing and forwarding fit together so neatly — each router runs Dijkstra over the same agreed map, so their independently computed first hops chain into one consistent end-to-end path, with no router ever needing to dictate the full route.
From textbook to the real Internet
This is not just a classroom exercise. The most widely used link-state protocol inside real networks is OSPF (Open Shortest Path First), and the 'shortest path first' in its very name is Dijkstra's algorithm running on the map that OSPF's flooding builds. The fourth guide in this rung opens OSPF up properly; for now it is enough to know that when a fibre is cut or a new router comes online somewhere in a company or campus network, an OSPF router floods the news, everyone rebuilds the same updated map, and every router quietly re-runs Dijkstra to refresh its table. The theory you just traced by hand is, almost line for line, what production routers do.