Noesis
4.3.16Computer Networks

Link state routing — OSPF, Dijkstra

1,925 words9 min readdifficulty · medium3 backlinks
🇮🇳 Yeh note Hinglish mein padho →

OSPF (Open Shortest Path First) is the Internet's standard intra-domain (IGP) implementation of this idea: an open standard, runs directly over IP (protocol 89), supports areas, authentication, and equal-cost multipath.

HOW does flooding stay correct?

Dijkstra's algorithm — derived from scratch

The procedure:

  1. d[s]=0d[s]=0, d[others]=∞d[\text{others}]=\infty, S=∅S=\varnothing.
  2. Pick u∉Su \notin S with minimum d[u]d[u]; add uu to SS.
  3. Relax every edge out of uu.
  4. Repeat until SS = all nodes.

Complexity with a binary heap: O((V+E)log⁡V)O((V+E)\log V).

Figure — Link state routing — OSPF, Dijkstra

Worked Example 1 — small graph

Graph (undirected, costs): A–B = 2, A–C = 5, B–C = 1, B–D = 7, C–D = 3. Source = A.

Step Finalized d[A] d[B] d[C] d[D]
init {} 0 ∞ ∞ ∞
pick A {A} 0 2 5 ∞
pick B (min=2) {A,B} 0 2 3 (via B:2+1) 9 (2+7)
pick C (min=3) {A,B,C} 0 2 3 6 (3+3)
pick D (min=6) all 0 2 3 6
  • Why pick B first? Min tentative = 2 → finalized. Why this step? Greedy invariant guarantees no shorter path to B exists.
  • Why does C drop 5→3? Relaxing B's edge: d[B]+1=3<5d[B]+1 = 3 < 5. Why? Path A→B→C beats direct A→C.
  • Why D = 6 not 9? After C finalized, relax C→D: 3+3=6<93+3=6 < 9. Why? Going via C is cheaper than via B.

Final shortest paths from A: B(2), C(3, via B), D(6, via B,C).

Worked Example 2 — what OSPF stores

Suppose router A's table after Dijkstra: to reach D, the first hop is B (because the path is A→B→C→D).

  • Why store only next hop, not whole path? Why this step? Forwarding is hop-by-hop; A only needs to know which neighbor to hand the packet to. B will know its own next hop, etc. This is the destination → next-hop forwarding table.

Common mistakes

Active recall

Recall Test yourself (hide answers)
  • What 5 steps make up link state routing?
  • Why does Dijkstra need non-negative weights?
  • What does an LSP contain?
  • Why does flooding need sequence numbers?
  • What does OSPF run on top of (protocol)?
What information does each router flood in link state routing?
Its own Link State Packet (LSP): its ID and a list of (neighbor, link-cost) pairs.
Which algorithm does each router run on the assembled topology?
Dijkstra's shortest-path algorithm, from itself as source.
State the relaxation rule in Dijkstra.
d[v]=min⁡(d[v], d[u]+w(u,v))d[v] = \min(d[v],\, d[u]+w(u,v)).
Why must Dijkstra's edge weights be non-negative?
Because the greedy step assumes a finalized node's distance can never decrease; a negative edge could later shorten it, breaking correctness.
What problem of distance-vector does link state avoid?
Count-to-infinity / slow convergence and routing loops.
What does OSPF stand for and where does it run?
Open Shortest Path First; an intra-domain IGP running directly over IP (protocol number 89).
Why do LSPs carry sequence numbers and age?
To keep only the newest copy, stop infinite flooding loops, and expire stale topology info.
Time complexity of Dijkstra with a binary heap?
O((V+E)log⁡V)O((V+E)\log V).
In the forwarding table, what does each router actually store?
Destination → next-hop (first neighbor on the shortest path), not the entire path.
LS vs DV in one line each?
LS = share the full map, compute alone (Dijkstra); DV = share computed distances, trust neighbors (Bellman–Ford).
Recall Feynman: explain to a 12-year-old

Every router sends a tiny note to all the others saying "here are the roads next to me and how long they are." After everyone reads everyone's notes, each one draws the whole map of the town. Then, using a clever rule, each router figures out the shortest way to every place — always picking the closest unfinished spot next, like exploring a maze by always stepping to the nearest unexplored room first. Because everyone uses the same map, nobody sends packets in circles.

Connections

  • Distance Vector Routing — the alternative (Bellman–Ford, count-to-infinity)
  • Dijkstra's Algorithm — the graph algorithm reused here
  • Bellman–Ford Algorithm — needed when weights can be negative
  • Flooding — the reliable LSP distribution mechanism
  • OSPF Areas — scaling link state to large networks
  • BGP — inter-domain routing (path-vector, contrasts with intra-domain OSPF)
  • Routing Table vs Forwarding Table

Concept Map

suffers

motivates

step 1-2

step 3

step 4

uses

keeps newest, expires stale

assembled into

step 5, run

core operation

greedy invariant needs

produces

standard implementation

Distance-Vector RIP

Count-to-Infinity

Link State Routing

Discover neighbors and costs

Build Link State Packet

Reliable Flooding

Sequence numbers and age

Full Topology Map

Dijkstra's Algorithm

Relaxation rule

Non-negative weights

Routing Table

OSPF over IP 89

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, link state routing ka core idea simple hai: har router apne aas-paas ke neighbours aur unke link ka cost ek chhoti packet (LSP) mein likh kar poore network mein flood kar deta hai. Matlab har router ke paas ek hi jaise complete map aa jaata hai. Iske baad har router khud, akele, Dijkstra algorithm chala kar har destination tak ka shortest path nikaal leta hai. Ye distance-vector se alag hai — wahan routers sirf apne "best distance" gossip karte hain aur count-to-infinity ka problem aata hai. Yahan sab ke paas raw map hota hai, isliye convergence fast aur loop-free.

Dijkstra ki asli baat: tum source se start karte ho, sabki tentative distance infinity, source ki 0. Phir baar-baar sabse closest unfinished node ko "lock" (finalize) karte ho, aur uske edges ko relax karte ho — yaani check karte ho ki uske through jaana sasta hai kya: d[v]=min⁡(d[v],d[u]+w)d[v] = \min(d[v], d[u]+w). Ye greedy step sirf isliye kaam karta hai kyunki saare weights non-negative hain. Agar negative weight ho toh Dijkstra galat answer dega — tab Bellman–Ford use karo.

OSPF (Open Shortest Path First) yahi link state idea ka real-world protocol hai, jo Internet ke andar (intra-domain) chalta hai, directly IP ke upar (protocol 89). HELLO packets se neighbours dhoondho, LSP banao, flood karo, phir Dijkstra. Exam aur interview dono mein ye sequence aur "kyun non-negative weights chahiye" wala point bahut puchha jaata hai, toh ye yaad rakhna.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 2,072 wordsD2Visual walkthroughThe derivation in pictures · 1,936 wordsD3Worked examplesEvery scenario covered · 2,291 wordsD4ExercisesGraded, full solutions · 2,189 wordsD5Question bankConcept traps, quick reveals · 1,979 words

Test yourself — Computer Networks

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Distance vector routing — RIP, Bellman-Ford, count-to-infinityCoding · 4.3.15Dijkstra's algorithm — greedy, priority queue, O((V+E) log V) — no negative edgesCoding · 3.5.10Bellman-Ford algorithm — DP approach, negative cycles detection, O(VE)Coding · 3.5.11BGP — path vector, AS, policy routingCoding · 4.3.17Routing — forwarding table, routing tableCoding · 4.3.13Distance vector routing — RIP, Bellman-Ford, count-to-infinityCoding · 4.3.15BGP — path vector, AS, policy routingCoding · 4.3.17