6.2Link state routing
The idea
In link state routing every router floods its link costs, so all routers hold the same map, and each one runs Dijkstra on it to get shortest paths.
Think of it like this: Everyone gets the same road map and plans their own route from it.
Why it exists
GATE compares overhead, convergence and loops, and asks which algorithm OSPF uses.
How it works
- Each router floods a link-state packet with its links and costs.
- Every router builds the full topology.
- Run Dijkstra from yourself: finalise the closest unfinished node, relax its edges.
- The first hop of each shortest path becomes the forwarding entry.
Worked example: Run Dijkstra from A in the lab graph.
The order of finalisation is A, B (7), C (9), F (11), D (20), E (20); the next hop to F is C.
Now play with it
- →Click Next step and watch the finalised vertex and updated distances.
- →Read the forwarding table below the animation.
Every router floods its link costs, so everyone holds the same full map and runs Dijkstra on it. Source: A.
- Finalise A (distance 0); improves B → 7, C → 9, F → 14
- Finalise B (distance 7); improves D → 22
- Finalise C (distance 9); improves D → 20, F → 11
- Finalise F (distance 11); improves E → 20
- Finalise D (distance 20); no improvements
- Finalise E (distance 20); no improvements
| dest | cost | next hop |
|---|---|---|
| B | 7 | B |
| C | 9 | C |
| D | 20 | C |
| E | 20 | C |
| F | 11 | C |
Check yourself
Compared with distance vector, link state
Exam notes (the dense version)
Each router floods link-state packets describing its direct links; everyone builds the same map and runs Dijkstra. It converges faster, is loop-free in steady state and supports per-link metrics, but costs more CPU and memory (O(E log V) per run) and more flooding traffic. A distance vector protocol with split horizon still does not avoid all loops, whereas link-state converges after a topology change in one flooding round plus a computation.
Previous year questions: Routing & Congestion Control (3)
PYQs are grouped by topic, so this is the full set for Routing & Congestion Control; try the ones that match this subtopic. Open all 3 on the topic page.