In 1956, a 26-year-old Edsger Dijkstra worked out a shortest-path algorithm in about twenty minutes, sitting at a café, no pencil, no paper. He didn’t know it yet, but he’d just written the logic that keeps the internet from falling apart.
Here’s where it lives today.
Every network inside a single organization, a campus, a data center, an ISP backbone, etc. runs an Interior Gateway Protocol (IGP) to decide how a packet gets from A to B.
The two that run the serious networks, OSPF and IS-IS, are “link-state,” and the way they work is quietly elegant:
1. Each router says hello to its neighbours and forms adjacencies.
2. Each one floods a description of its own links to everyone else (Link-State Advertisements).
3. Now every router holds an identical map of the whole network.
4. Each router runs Dijkstra’s algorithm on that map to compute its own shortest path to every destination.
Then a fibre gets cut (a real scenario).
The two routers on the broken link flood a fresh advertisement. Every router updates its map, reruns Dijkstra, and traffic shifts onto the next-best path, often before anyone notices. No central controller. No human in the loop. Just every router, independently, recomputing the same map.
That’s the contrast with BGP, which I posted about recently: BGP routes between autonomous systems and trusts policy over distance. An IGP routes inside one and trusts math.
Below is a simulation of it, with the actual SPF code running right beside it and highlighting line-by-line in sync: adjacencies form, the map floods out, the shortest-path tree grows node by node, a link fails, and the network reconverges onto a costlier backup path, cost 20 down to a cost-22 detour, automatically.
And the question I always get “what language is OSPF written in?” has the same answer BGP did: there isn’t one. OSPF is a protocol (RFC 2328), not a program. The routers that speak it run daemons written overwhelmingly in C/C , FRRouting, BIRD, OpenBSD’s OpenOSPFD, Cisco IOS, Juniper Junos.
The C in the video is a faithful model of the SPF computation itself, which is just Dijkstra, run over the link-state database.
One algorithm, sketched in a café in twenty minutes, now runs a few hundred times a second across the planet every time something breaks.
#Networking #OSPF #ISIS #RoutingProtocols #NetworkEngineering #Dijkstra #SystemsThinking