Distance Vector vs Link State Routing: Algorithms & Traps
“Bellman-Ford updates, count-to-infinity, split horizon, and Dijkstra SPF.”
1.Distance Vector Routing & Bellman-Ford Principle
§ 6.1.Distance Vector is a decentralized routing algorithm where each router maintains a table (vector) of minimum distances to all known destinations. Periodically (e.g., every 30s in RIP), each node sends its entire routing table ONLY to its immediate neighbors.
Bellman-Ford Equation: Let D_x(y) be the cost of the least-cost path from node x to node y. D_x(y) = min_v { c(x, v) + D_v(y) }, where the minimum is taken over all neighbors v of x, and c(x, v) is the direct link cost from x to v.
The Count-to-Infinity Problem: Good news travels fast, but bad news travels agonizingly slow. When a link breaks (cost increases to infinity), adjacent routers may exchange outdated mutual vectors, incrementing distance by 1 at each iteration until reaching infinity (RIP defines infinity as 16 hops).
Mitigations: Split Horizon (never advertise a route back out the same interface through which it was learned) and Poison Reverse (actively advertise a distance of infinity back to the next-hop neighbor).
2. Routing Paradigm Comparison: Distance Vector vs Link State
Core architectural differences between RIP (Distance Vector) and OSPF (Link State):
| Feature / Aspect | Dimension | Distance Vector (RIP) |
|---|---|---|
| Underlying Algorithm | Distributed Bellman-Ford equation | Dijkstra Shortest Path First (SPF) |
| Knowledge Scope | Tells neighbors about the entire world | Tells the entire world about its local neighbors |
| Topology Awareness | Has NO map of full network; routes on hearsay | Every router builds complete identical network graph |
| Convergence Speed | Slow (susceptible to routing loops) | Fast (no count-to-infinity issue) |
| Message Overhead | Periodic broadcasts of full routing tables | Triggered Link State Advertisements (LSA) |
| Metric | Hop count (maximum 15 hops; 16 = infinity) | Cost based on reference bandwidth (100 Mbps / Bandwidth) |
3. GATE Worked Numerical: Distance Vector Routing Table Update
When applying Bellman-Ford update from neighbor vector, don't forget to ADD the link cost to that neighbor before comparing against current known distance!
Problem: Node X is connected to neighbors A, B, and C with direct link costs: c(X, A) = 2, c(X, B) = 5, c(X, C) = 1.
Node X receives distance vectors from A, B, and C with costs to destination D:
D_A(D) = 6, D_B(D) = 2, D_C(D) = 8.
Compute X's new minimum distance to destination D and the next-hop router.
Step 1: Compute candidate costs through each neighbor:
Path via A: c(X, A) + D_A(D) = 2 + 6 = 8.
Path via B: c(X, B) + D_B(D) = 5 + 2 = 7.
Path via C: c(X, C) + D_C(D) = 1 + 8 = 9.
Step 2: D_X(D) = min(8, 7, 9) = 7.
Step 3: Minimum cost is 7 via neighbor B. Node X updates its routing table entry for destination D: Cost = 7, Next Hop = B.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-level numerical drilling and PYQ analysis.
Step-by-step conceptual walkthroughs with worked GATE numericals.
Clear whiteboard lectures for foundational and semester exam coverage.