Link-State Routing and Dijkstra's Algorithm

A link-state routing algorithm is built from two logically separate mechanisms: topology dissemination and path computation. Every router first constructs a link-state packet (LSP), sometimes called a link-state advertisement, describing itself: its identifier, the identifiers of its directly attached neighbors, and the cost (weight) of each attached link, together with a monotonically increasing sequence number. Every router then floods its LSP to all other routers in the domain using a reliable flooding protocol, so that in steady state every router holds an identical link-state database (LSDB) — a complete, weighted graph of the network. Once a router has the full graph, it treats itself as the source vertex and runs Dijkstra's shortest-path algorithm on the LSDB to compute a shortest-path tree rooted at itself, giving the least-cost path (and hence the next hop) to every other router. Because all routers compute from the same graph, and because Dijkstra's algorithm is deterministic given a graph and a source, all routers agree — modulo tie-breaking rules — on a globally consistent set of paths, which is precisely what prevents persistent forwarding loops. This is fundamentally different from distance-vector routing, where each router knows only its neighbors' reported distances, not the topology itself, and computes paths via a distributed, iterative relaxation (Bellman–Ford in disguise). Link-state trades a larger amount of flooded state — the entire topology, held by every router — for faster, more predictable convergence and freedom from the "count-to-infinity" failure mode. The two philosophies (link-state vs. distance-vector) are the two archetypal answers to the routing problem, which itself is precisely the shortest-path problem on the graph abstraction of a network, where routers are vertices and links are weighted edges.

Link-state routing operates in two phases: flooding to build the LSDB, then per-router shortest-path computation.

Phase 1 — Reliable flooding

Each router periodically (or on a topology change) generates an LSP describing its local link state. Flooding must guarantee that every router in the domain eventually receives every router's latest LSP exactly once, even though the underlying links can drop, duplicate, or reorder packets. This is achieved with:

• A sequence number in each LSP, incremented every time the originating router issues a new one. Routers discard any LSP whose sequence number is not newer than the copy already stored.
• An age field (time-to-live) that decrements over time or hops, so that stale LSPs from routers that have crashed or been removed eventually get purged from every LSDB even without an explicit withdrawal.
• Flood-and-acknowledge on every link: when a router receives a new LSP on one interface, it immediately forwards ("floods") a copy out every other interface, and acknowledges receipt back to the sender. This guarantees an LSP originating anywhere reaches every router, since the network graph is connected.

``` function ON_RECEIVE_LSP(lsp, incoming_link): stored = LSDB.lookup(lsp.origin) if stored is None or lsp.seq_num > stored.seq_num: LSDB.update(lsp.origin, lsp) # accept newer information for link in ROUTER.links: if link != incoming_link: SEND(lsp, link) # flood outward, not back ACK(lsp, incoming_link) SCHEDULE_DIJKSTRA() # topology changed, recompute else if lsp.seq_num == stored.seq_num: ACK(lsp, incoming_link) # duplicate, just acknowledge else:

# lsp is older than what we have — tell the sender the truth SEND(stored, incoming_link) ``` This flood terminates: each router forwards a given (origin, sequence-number) pair at most once per interface, because the second time it arrives the stored copy is no longer strictly older. On a graph with $V$ routers and $E$ bidirectional links, the total number of LSP transmissions for one flooded update is $O(E)$, since every link is traversed a bounded number of times in each direction.

Phase 2 — Dijkstra's shortest-path computation

Once a router's LSDB stabilizes, it runs Dijkstra's algorithm with itself as the source vertex $s$. The algorithm maintains a set $S$ of vertices whose shortest distance from $s$ is already finalized ("settled"), and a tentative distance array $d[\cdot]$ for all others. ``` function DIJKSTRA(Graph G, source s): for each vertex v in G: d[v] = INFINITY prev[v] = UNDEFINED d[s] = 0 S = empty set # settled vertices Q = min-priority-queue of all vertices, keyed by d[] while Q is not empty: u = Q.extract_min() # vertex with smallest tentative distance if u in S: continue # stale entry, already settled add u to S for each edge (u, v) with weight w(u, v): if v not in S and d[u] + w(u, v) < d[v]: d[v] = d[u] + w(u, v) prev[v] = u Q.decrease_key(v, d[v]) # or insert a new entry, if lazy deletion return d, prev # d[v] = shortest distance, prev[v] = predecessor ``` At termination, `prev[]` encodes a shortest-path tree rooted at `s`; the router walks this tree back one hop from each destination to itself to determine the correct next hop, which is the only thing it actually needs to populate its forwarding table.

Flooding complexity. Let $V$ be the number of routers and $E$ the number of bidirectional links. Each router's LSP is forwarded across every link it did not arrive on, and duplicate-suppression via sequence numbers guarantees each link carries a bounded number of copies (in practice one per direction, plus retransmissions on loss). Total message complexity for propagating one LSP update is $O(E)$. Since each router stores one LSP per origin, the space required for the LSDB is $O(V + E)$ per router — the entire topology, replicated at every router. This is the structural price of link-state routing: it trades memory and flooding bandwidth for computational independence and fast convergence.

Dijkstra's time complexity. The algorithm performs exactly $V$ `extract_min` operations (each vertex is settled once) and, across the whole run, at most $E$ relaxation steps, since each edge is examined exactly once, from its tail endpoint when that endpoint is settled.

• With an unsorted array holding tentative distances, `extract_min` costs $O(V)$ (linear scan) and `decrease_key` costs $O(1)$. Total: $O(V \cdot V + E \cdot 1) = O(V^2)$.
• With a binary min-heap, `extract_min` costs $O(\log V)$ and `decrease_key` costs $O(\log V)$ (or, with lazy deletion and re-insertion, an `insert` at $O(\log V)$, tolerating stale duplicate entries by skipping them, as the pseudocode above does). Total: $O((V + E)\log V)$.
• With a Fibonacci heap, `decrease_key` is $O(1)$ amortized and `extract_min` is $O(\log V)$ amortized, giving $O(E + V\log V)$ — the asymptotically optimal bound for comparison-based Dijkstra, though the large constant factors make it rarely used in practice.

For router-scale graphs (hundreds to low thousands of vertices, sparse, $E = O(V)$), the binary-heap bound $O((V+E)\log V) \approx O(V \log V)$ is what real implementations use; the $O(V^2)$ array version is only preferable when the graph is dense ($E$ close to $V^2$), which router topologies never are.

Why the greedy strategy is correct. Dijkstra's correctness rests on one crucial precondition: all edge weights are non-negative. The proof is by induction on the order in which vertices are added to the settled set $S$. Invariant: whenever a vertex $u$ is extracted from the priority queue and added to $S$, its tentative distance $d[u]$ equals the true shortest-path distance $\delta(s, u)$. Base case: the source $s$ is settled first with $d[s] = 0 = \delta(s,s)$, trivially correct. Inductive step: suppose the invariant holds for every vertex already in $S$. Let $u$ be the next vertex extracted, so $d[u]$ is minimal among all vertices outside $S$. Consider any path from $s$ to $u$. It must leave $S$ at some point, crossing an edge $(x, y)$ where $x \in S$ and $y \notin S$. Because edge weights are non-negative, the distance to $y$ along this path is at most the distance to $u$ along it, and by the time $x$ was settled, $d[y]$ was already updated to at most $\delta(s, x) + w(x,y)$ via relaxation. Since $u$ was chosen as the minimum tentative-distance vertex remaining, $d[u] \le d[y] \le$ (length of any path through the boundary) $\le$ (length of the path to $u$). Since this holds for every path to $u$, in particular the true shortest one, $d[u] \le \delta(s,u)$. But $d[u]$ is always an upper bound on $\delta(s,u)$ by construction (it is the cost of some actual path found via relaxation), so $d[u] = \delta(s,u)$, completing the induction. This argument fails with negative edge weights: a vertex could be settled with a tentative distance that a later, negative-weight edge would have improved, but by then it is no longer reconsidered. Network link costs (OSPF metrics, IS-IS metrics) are configured to be strictly positive precisely so that this precondition always holds.

Why link-state avoids routing loops. Because every router computes shortest paths from an identical LSDB using a deterministic algorithm, the derived next-hop choices are mutually consistent: if router A's shortest path to destination Z goes through B, then B's own shortest path to Z (computed independently on the same graph) cannot loop back through A, since that would contradict A's path being shortest. Transient loops can still occur for a few milliseconds while different routers hold momentarily different, not-yet-converged LSDBs, but these self-heal as soon as flooding completes — unlike distance-vector protocols, where inconsistent partial information can cause the persistent count-to-infinity problem.

Consider the five-router network below (undirected, weighted), and trace Dijkstra's algorithm from source $A$. Edges: $A$–$B$ (4), $A$–$C$ (1), $C$–$B$ (2), $C$–$D$ (5), $B$–$E$ (1), $D$–$E$ (3), $D$–$B$ (8).

The final shortest-path tree rooted at $A$: $A\!\to\!C$ (1), $A\!\to\!C\!\to\!B$ (3), $A\!\to\!C\!\to\!B\!\to\!E$ (4), $A\!\to\!C\!\to\!D$ (6). Router $A$'s forwarding table now reads: to reach $B$, $C$, $D$, or $E$, send first to $C$ (the next hop shared by every one of those routes, since $C$ is the sole neighbor of $A$ on all of them here) — a small but real illustration of how a multi-hop shortest-path tree collapses into simple one-hop forwarding decisions at the source. Notice the tie at step 4: both the direct path $A$–$C$–$D$ (cost 6) and the alternate $A$–$C$–$B$–$E$–$D$ (cost $1+2+1+3=7$) were considered, and Dijkstra correctly rejected the longer one — the greedy invariant guarantees this without ever having to reconsider a settled vertex.

Link-state routing and Dijkstra's algorithm come from two different, later-merged, threads: theoretical graph algorithms, and practical internet engineering under the ARPANET program.

The ARPANET's original routing protocol used a distributed Bellman–Ford-style distance-vector scheme, which suffered severe oscillations and slow convergence under congestion and topology changes in the late 1970s. The 1979 redesign, led by engineers including John McQuillan, replaced it with a link-state approach: full topology flooding plus local Dijkstra computation, directly inspired by the theoretical shortest-path algorithm developed two decades earlier. This redesign became the direct ancestor of both OSPF and IS-IS, the two link-state protocols that dominate enterprise and carrier routing today.

Link-state routing runs the interior of almost every large IP network. OSPF (Open Shortest Path First) and IS-IS (Intermediate System to Intermediate System) are the two production link-state protocols; both flood LSPs (called Router-LSAs in OSPF, LSPs in IS-IS) within an administrative area, and both run Dijkstra locally at every router to build the shortest-path tree that populates the forwarding table. ISPs use IS-IS or OSPF as the "interior gateway protocol" that finds paths within their own network, while BGP handles routing between independently administered networks — a boundary that reflects the practical limit of how far full-topology flooding can scale before the LSDB becomes too large to flood and store everywhere. Beyond wide-area networking, the same idea appears in data-center fabrics (some use link-state-like designs at Layer 3), in wireless mesh routing protocols such as OLSR (Optimized Link State Routing), and conceptually in any distributed system where nodes need a globally consistent view before making a local decision — a pattern echoed in consensus and state-machine replication, though those solve a different (stronger) consistency problem. Dijkstra's algorithm itself, independent of networking, underlies GPS navigation systems, game AI pathfinding, and any application computing shortest paths on a weighted graph, making it one of the most reused algorithmic primitives in computer science.

Ask the tutor: Can you walk me through why Dijkstra's algorithm fails on a graph with a negative-weight edge, using a concrete 3-vertex counterexample?