Network Packet Routing: Dijkstra, OSPF and BGP in Miniature

Shortest path first: Dijkstra's algorithm

Every router on the internet is, at bottom, solving a single-source shortest-path problem on a graph: nodes are routers, edges are links, and edge weight is a cost (often related to bandwidth or a configured metric). Dijkstra's algorithm, published by Edsger Dijkstra in 1959, finds the cheapest path from one router to every other router in a network with non-negative weights, and it does it without ever having to look at a path that's already provably worse than one already found.

dist[source] = 0;  dist[all others] = infinity
visited = {}
while unvisited nodes remain:
    u = unvisited node with the smallest dist[u]
    mark u visited
    for each neighbour v of u:
        if dist[u] + weight(u,v) < dist[v]:
            dist[v] = dist[u] + weight(u,v)
            prev[v] = u                       // for path reconstruction

The greedy step — always expand the closest unvisited node next — is provably correct only because weights are non-negative: once a node is settled, no later relaxation through an unvisited (necessarily farther) node can ever produce a shorter path to it. Implemented with a binary or Fibonacci heap for the priority queue, it runs in O((V+E) log V), fast enough to recompute routes for networks with thousands of routers on every topology change.

OSPF: Dijkstra inside a single network

OSPF (Open Shortest Path First) is Dijkstra's algorithm running for real, inside a single autonomous system (a company, university or ISP's own network). Every router floods the others with its local link states — which neighbours it has and at what cost — so that every router ends up with an identical map of the whole topology, then independently runs Dijkstra on that map to compute its own routing table. Cost is typically inverse to bandwidth, so OSPF naturally prefers a 10 Gbps link over a 100 Mbps one even if the 100 Mbps path has fewer hops.

BGP: routing between networks, not just the cheapest path

Between autonomous systems — between ISPs, essentially the routing of the internet itself — pure shortest-path routing is replaced by BGP (Border Gateway Protocol), because ISPs don't want the technically shortest path, they want a path that respects business relationships: a transit customer's traffic is preferred over a settlement-free peer's, which is preferred over a competitor's paid transit path. BGP is path-vector rather than link-state: each router advertises the full AS-path it would use, and every other router applies local policy to choose among competing advertisements, not a shared cost function.

What happens when a link fails

Fail a link inside an OSPF domain and every router refloods the new link-state, reruns Dijkstra and converges on a new shortest-path tree — typically in well under a second on modern hardware, though the flooding and recomputation is not instantaneous, which is exactly the window where transient routing loops can appear, because different routers can briefly hold inconsistent views of the topology. BGP convergence after a failure is much slower and can take minutes, because AS-path withdrawals have to propagate hop by hop across the entire internet, and routers apply damping to avoid amplifying route flaps into global instability.

Frequently asked questions

Try it live

Everything above runs in your browser — open Network Packet Routing and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.