Link State Routing

In link state routing every router has a complete map of the network (the whole topology and all link costs) and computes the shortest path itself, instead of trusting the partial, second-hand information passed hop-by-hop as in distance vector routing. It is a global algorithm implemented by OSPF and IS-IS.

How it works

1. Link discovery — each router finds its neighbours and the cost of each link (hello packets).
2. Link-state advertisement (LSA) — the router creates an LSA containing its ID, every neighbour ID and the cost of each link.
3. Reliable flooding — the LSA is flooded to every router in the autonomous system. Each router re-broadcasts it on all links except the one it arrived on, using sequence numbers and an age (lifetime) field so duplicates are discarded and stale LSAs expire. Flooding repeats periodically (e.g. every 30 min in OSPF) to keep the database fresh.
4. Link-state database (LSDB) — after convergence every router holds an identical copy of all LSAs, i.e. an identical graph of the network.
5. SPF computation — each router runs Dijkstra's shortest-path algorithm with itself as the root, producing a shortest-path tree and hence a forwarding table (destination → next hop).

Example

           4                5
     A --------- B ---------------- D
      \         /
       \       /
    3   \     /  2
         \   /
           C

Dijkstra's SPF run at A (cost from A):

Step	Visited set	Newly updated neighbours
Init	{A}	D(B) = 4 via A, D(C) = 3 via A, D(D) = ∞
1	pick min → C (3)	B: min(4, 3+2=5) = 4 (unchanged, via A)
2	pick min → B (4)	D: 4 + 5 = 9 via B
3	pick min → D (9)	—

Resulting forwarding table at A:

Destination	Cost	Next hop
A	0	—
B	4	B
C	3	C
D	9	B

Every other router runs the same algorithm with itself as root, so each has its own tree but shares the same LSDB.

Evaluation

Aspect	Link state	Distance vector
Knowledge	Full global topology	Only neighbours' vectors
Computation	Dijkstra at each router	Bellman-Ford, distributed
Convergence	Fast	Slow
Loops	No count-to-infinity	Count-to-infinity, transient loops
Overhead	High (flooding of LSAs)	Low (periodic small vectors)
Resources	More memory & CPU	Minimal

Merits: loop-free, fast convergence, each router is independent. Demerits: flooding cost grows with network size, every router must store the whole topology, and SPF must be re-run on every change.