Link-State Routing: short notes (Computer Networks)

Revision mode

Introduction

In link-state (LS) routing every router learns the complete topology of its routing domain and computes shortest paths itself. Each router describes only its own links, the neighbours and the cost to each, in a link-state packet (LSP; OSPF calls it a link-state advertisement, LSA) and floods that packet to every other router. Once a router holds every router's LSP, it has the whole weighted graph in its link-state database, runs Dijkstra's algorithm with itself as the source, and derives its forwarding table from the resulting shortest-path tree.

This is the opposite division of labour from Distance-Vector Routing: LS sends local facts to everyone, DV sends global estimates to neighbours only. LS converges faster and does not count to infinity, at the price of more messages, more memory and a full shortest-path computation at every router. OSPF and IS-IS are LS protocols.

Dijkstra's algorithm itself (correctness, the priority-queue versions and their costs) is in Single-Source Shortest Paths; what remains is how the graph reaches each router and how the result becomes a forwarding table.

Prerequisites

IPv4 Addressing and Header: routers, destination networks, forwarding tables.
Single-Source Shortest Paths: Dijkstra's algorithm.

Core concepts

The five steps at each router

Discover neighbours. Send HELLO packets on each link; learn who is at the other end.
Set link costs. Configured by the operator, or derived from bandwidth or delay.
Build an LSP: the sender's identity, a sequence number, an age, and the list of (neighbour, cost) pairs.
Flood the LSP reliably to all routers.
Compute shortest paths from itself with Dijkstra and install the first hop of each path in the forwarding table.

Steps 3 to 5 are repeated when a link changes, and LSPs are also refreshed periodically.

Flooding with sequence numbers

A router receiving an LSP compares its sequence number with the one it has stored for that source:

Arriving sequence number	Action
Higher than stored (or none stored)	Store it, forward it on every link except the one it arrived on, acknowledge it
Equal to stored	Duplicate: discard (acknowledge)
Lower than stored	Obsolete: discard

Cost of one flood. With duplicate suppression, the originator sends one copy on each of its links and every other router forwards the first copy it receives on every link except the arrival link. For a connected graph with $n$ routers and $E$ links one LSP therefore costs

\deg(s) + \sum_{v \neq s} \big(\deg(v) - 1\big) = 2E - (n - 1)

link transmissions, and a full exchange of all $n$ LSPs costs $n\,(2E - n + 1)$ , before acknowledgements.

Age. Each stored LSP carries an age that advances while it sits in the database; an LSP that reaches the limit (in OSPF, MaxAge, 1 hour) is discarded, so a crashed router's information eventually disappears. Ageing also guards against a corrupted or wrapped sequence number keeping a stale LSP alive.

Dijkstra at one router

With itself as the source $s$ , the router keeps a set $N'$ of nodes whose least cost is final, a tentative cost $D(v)$ and a predecessor $p(v)$ for every other node:

Text

DIJKSTRA-LS(s)
    N' <- {s}
    for each node v: D(v) <- c(s, v) if v is a neighbour of s, else infinity;  p(v) <- s for neighbours
    while N' does not contain every node
        w <- the node not in N' with least D(w)
        add w to N'
        for each neighbour v of w not in N'
            if D(w) + c(w, v) < D(v) then D(v) <- D(w) + c(w, v);  p(v) <- w

The forwarding table needs the first hop to each destination, not the predecessor: follow $p(\cdot)$ back from the destination until the node whose predecessor is $s$ .

For $V$ vertices and $E$ edges, a full array-scan Dijkstra implementation takes $\Theta(V^2)$ time; a binary heap gives $O((V+E)\lg V)$ under logarithmic heap-operation costs. Auxiliary distance, predecessor and visited arrays need $O(V)$ ; adjacency storage needs $O(V+E)$ separately. A decrease-key heap has $O(V)$ entries; a lazy duplicate-entry heap may instead hold $O(E)$ entries. An average-time claim requires a graph distribution.

How it works: one router's computation

Six routers with links S-A 4, S-B 1, A-B 2, A-C 5, B-C 8, B-D 10, C-D 2, C-E 6, D-E 2. Router S has received all six LSPs and runs Dijkstra. Each row shows the state after the node in the first column is added; entries are $D(v), p(v)$ , and a dash means the node is already final.

Step	$N'$	A	B	C	D	E
0	S	4, S	1, S	$\infty$	$\infty$	$\infty$
1	S B	3, B	-	9, B	11, B	$\infty$
2	S B A	-	-	8, A	11, B	$\infty$
3	S B A C	-	-	-	10, C	14, C
4	S B A C D	-	-	-	-	12, D
5	S B A C D E	-	-	-	-	-

Final costs from S: A 3, B 1, C 8, D 10, E 12. The shortest-path tree is S-B, B-A, A-C, C-D, D-E, a single chain, so every destination's first hop is B, including A: the direct S-A link (cost 4) loses to S-B-A (cost 3).

Destination	Cost	Path	Next hop
A	3	S B A	B
B	1	S B	B
C	8	S B A C	B
D	10	S B A C D	B
E	12	S B A C D E	B

Six routers S, A, B, C, D, E with links S-A cost 4, S-B cost 1, A-B cost 2, A-C cost 5, B-C cost 8, B-D cost 10, C-D cost 2, C-E cost 6, D-E cost 2. Each router has a small LSP card listing its own links. The shortest-path tree from S is drawn in bold: S-B, B-A, A-C, C-D, D-E, with final costs A 3, B 1, C 8, D 10, E 12 written beside the nodes. A side table gives S's forwarding table: next hop B for every destination. — Figure 1. Link-state routing at router S: the flooded LSPs give the whole graph, Dijkstra gives the bold shortest-path tree (costs A 3, B 1, C 8, D 10, E 12), and the forwarding table sends everything to B.

Flood cost in this network. $n = 6$ , $E = 9$ : one LSP costs $2 \cdot 9 - 5 = 13$ transmissions, and all six cost 78.

Mathematical explanation: why LS converges without counting

Every router computes from the same database, so once flooding has delivered the new LSPs all routers hold the same graph and compute consistent trees. A failed link is reported directly by the routers at its ends; no router ever builds on another router's estimate, so there is no route through itself to count up. Transient loops can still occur in the short time while some routers have the new LSP and others do not.

Oscillation with load-dependent costs. If a link's cost is set to the traffic it currently carries, all routers may move their traffic to the currently cheap path at once, making it expensive, and then all move back. Using fixed costs or desynchronising the times at which routers recompute avoids this.

Worked examples

Example 1: first hop from predecessors

Dijkstra at router R ends with $p(Z) = Y$ , $p(Y) = X$ , $p(X) = R$ . The forwarding entry for Z is next hop X (walk back Z, Y, X; X's predecessor is R). The next hop is X, not Z's predecessor Y.

Example 2: flood count

A network of 10 routers and 15 links: one LSP flood costs $2 \cdot 15 - 9 = 21$ transmissions; all ten LSPs cost 210.

Example 3: which LSP is kept

A router has stored the LSP from router K with sequence number 41. Copies arrive with sequence numbers 41, 43 and 42 in that order. It discards 41 as a duplicate, stores and forwards 43, and discards 42 as obsolete.

Example 4: the same network after the S-B link fails

S and B each flood a new LSP without the failed link, and every router reruns Dijkstra on the corrected graph. From S, nodes become final in the order A (4, direct), B (6, via A), C (9, path S A C), D (11, via C) and E (13, via D; the route through C to E would cost 15). Every first hop at S changes from B to A in one recomputation, with no counting: no router builds on another router's old estimate.

OSPF version 2 runs directly over IP as protocol number 89 (no UDP or TCP), originates a fresh copy of each LSA at least every 30 minutes (LSRefreshTime), and stops using an LSA whose age reaches MaxAge, 1 hour. Large OSPF domains are split into areas, confining area-scoped router/network-LSA floods. AS-external type-5 LSAs have AS-wide flooding scope, except into stub areas.

Important properties and observations

Property	Link state	Distance vector
Information sent	Own links only	Estimated costs to all destinations
Sent to	Every router (flooding)	Neighbours only
Computation	Dijkstra over the whole graph	One Bellman-Ford step per update
Bad news	Fast; no counting to infinity	Slow; count to infinity possible
Fault spread	A router lies only about its own links	A wrong cost propagates through everyone
Example protocol	OSPF, IS-IS	RIP

Common misconceptions.

"Each router floods its routing table." It floods its own links; tables are computed locally.
"The forwarding table entry is the predecessor in the Dijkstra tree." It is the first hop.
"A direct link is always the route to that neighbour." Only if no cheaper path exists, as with S-A above.
"Link-state routing never loops." It can loop briefly while LSPs are still spreading.

GATE examination perspective

Dijkstra trace tables. Write $N'$ , $D(v)$ and $p(v)$ per step; state the tie rule if two nodes have equal $D$ .
Forwarding table. Convert predecessors to first hops.
Flooding counts. Use $2E - (n - 1)$ per LSP under "forward on all links except the arrival link".
LS versus DV. Message scope, computation, convergence and robustness, as in the table above.
Sequence numbers. Higher is newer; equal is a duplicate; lower is obsolete.

Summary

Sources

A. S. Tanenbaum, D. J. Wetherall, Computer Networks, 5th ed., Pearson, 2011: Section 5.2.5 (Link State Routing) and Section 5.6.6 (OSPF).
J. F. Kurose, K. W. Ross, Computer Networking: A Top-Down Approach, 8th ed., Pearson, 2021: Section 5.2.1 (The Link-State (LS) Routing Algorithm) and Section 5.3 (Intra-AS Routing in the Internet: OSPF).
B. A. Forouzan, Data Communications and Networking, 5th ed., McGraw-Hill, 2013: Chapter 20 (Unicast Routing).
J. Moy, RFC 2328, OSPF Version 2, 1998, Appendix A.1 (IP protocol 89) and Appendix B (LSRefreshTime 30 minutes, MaxAge 1 hour), (consulted 2026-11-11).