link-state routing

Imagine every person in a city is handed the same complete city map, with the length of every street marked. Once you have the whole map, you can privately plan the best route to anywhere yourself, without asking anyone for directions. Link-state routing works the same way: every router learns the entire network map, then computes its own paths.

It works in two phases. First, flooding: each router measures the cost to each of its directly attached neighbors and broadcasts that small fact — its 'link state' — to every other router in the network, in a packet called a link-state advertisement (LSA). Because everyone floods their LSAs, every router eventually holds an identical, complete picture of the graph: all nodes, all links, all costs. Second, computation: each router runs Dijkstra's algorithm on that graph, rooted at itself, to find the least-cost path to every destination, and installs the first hop of each path into its forwarding table.

The big advantage is fast, predictable convergence and immunity to most routing loops, because every router decides based on the same global map rather than on second-hand rumors. The famous real protocol in this family is OSPF, used inside countless company and ISP networks. Link-state is what most large, performance-sensitive networks run.

An honest caveat: knowing the whole map costs memory and bandwidth, and flooding LSAs across thousands of routers does not scale on its own. The fix is hierarchy — OSPF splits a network into areas so routers keep a detailed map only of their own area and a summary of the rest. Also, all routers must agree on the same Dijkstra rules; if they disagree, transient loops can still appear during convergence.