Recall warm-up
- In Link State routing, what algorithm does each router run after collecting all LSPs?
Stuck? Peek at 3.4.4 Link State routing: LSP flooding & Dijkstra’s algorithm
- LSP contents:
(Router ID, Direct Neighbours & Costs, Sequence #, Age)— distributed to all routers via controlled flooding. - Dijkstra: Greedily add min-D(u) node to permanent set N', then relax neighbours:
D(v) = min(D(v), D(u) + c(u, v)); time O(V²) or O((V+E) log V). - Next hop from source s to d = first node after s on the path traced backwards via
prev[].
- LSP contents:
- In Distance Vector routing, what equation does each router use to update its distances from neighbours’ vectors?
Stuck? Peek at 3.4.2 Distance Vector routing & the Bellman-Ford equation
- Bellman-Ford:
Dₓ(y) = min_{v ∈ N(x)} { c(x, v) + D_v(y) }. - DV message: contains
[(y, Dₓ(y))]for all destinations y; sent only to immediate neighbours. - If the current next-hop's distance increases, recompute that branch before taking the minimum.
- Bellman-Ford:
- Which routing family suffers from the Count-to-Infinity problem?
Stuck? Peek at 3.4.3 Count-to-infinity, Split Horizon & Poison Reverse
- Count-to-infinity: Bad news (link failure) causes neighbours to bounce increasing costs back and forth; RIP caps this with infinity = 16 (max valid hops = 15).
- Split Horizon: Do not advertise a route back to the next-hop neighbour v*.
- Poison Reverse: Advertise
Dₓ(y) = ∞to the next-hop neighbour v* (fixes 2-node loops, not 3+ node loops).
The Hook
Every couple of years, GATE asks a conceptual MCQ or MSQ pitting Distance Vector (DV) against Link State (LS): Which one floods small packets to everyone? Which one sends big tables only to neighbours? What happens if one buggy router claims it has cost 0 to everywhere?
Let's put both algorithms side by side so you can answer any comparison question in 10 seconds flat.
Predict First
Suppose a single router R_bad has a software bug and advertises that its link cost is 0. In which routing family (Distance Vector or Link State) can R_bad trick the entire network into sending ALL traffic for every destination into R_bad (a "black hole")?
In Distance Vector! If R_bad advertises D_bad(y) = 0 for every destination y, its neighbours believe R_bad is sitting right next to y and route everything to R_bad. In Link State, R_bad can only lie about its own direct links inside its LSP — every other router computes shortest paths itself using Dijkstra, so R_bad cannot falsify paths between distant nodes!
Core Concept
The Master Comparison Table: Distance Vector vs Link State
Every contrast between DV and LS flows from one root difference: DV tells neighbours its rumours about the whole world; LS tells the whole world the truth about its neighbours.
| Feature | Distance Vector (DV) | Link State (LS) |
|---|---|---|
| Core motto | "Tell your neighbours about the world" | "Tell the world about your neighbours" |
| Topology knowledge at each router | Partial: knows only distances & next hops (no map) | Complete: knows the entire weighted graph G = (V, E) |
| What is sent in a routing message? | Vector of distances to ALL |V| destinations | LSP listing ONLY direct neighbours (degree d) |
| Who receives the message? | ONLY immediate (1-hop) neighbours | ALL routers in the network (via controlled flooding) |
| Algorithm & Per-Node Compute | Distributed Bellman-Ford (simple table addition) | Local Dijkstra: O(|V|²) or O(|E| log |V|) |
| Convergence & Loops | Slow on bad news; vulnerable to Count-to-Infinity | Fast convergence; loop-free once LSPs arrive |
| Robustness to a faulty router | Poor: a lying router can corrupt all routes (black hole) | High: each router computes its own tree; faults stay local |
| Classic Protocol Example | RIP (hop count, max 15, infinity = 16) | OSPF (arbitrary link costs, hierarchical areas) |
Route Oscillations under Load-Dependent Link Costs
Are Link State protocols immune to every problem? One subtle issue affects both DV and LS if link costs are set equal to current traffic load / queuing delay:
If all routers simultaneously see clockwise paths are lightly loaded, they all switch their traffic clockwise after running Dijkstra → clockwise links become congested and counter-clockwise links become empty → on the next LSP flood, everyone flips counter-clockwise! This back-and-forth swinging is called route oscillation (cured by not tying link weights directly to instantaneous load, or by randomising when routers send updates).
Protocol Mapping: RIP vs OSPF
- RIP (Routing Information Protocol): Distance Vector; metric = hop count (every link costs 1); infinity = 16 (max 15 hops); exchanges full routing table with neighbours every 30 seconds; uses Split Horizon with Poison Reverse.
- OSPF (Open Shortest Path First): Link State; metric = configurable link weight (often inversely proportional to bandwidth); floods LSPs when link state changes (plus periodic refresh); runs Dijkstra locally; supports hierarchical areas.
Putting it together
- Distance Vector sends full distance tables to immediate neighbours and runs distributed Bellman-Ford (used in RIP).
- Link State floods small neighbour-cost packets (LSPs) to all routers and runs Dijkstra locally on the full map (used in OSPF).
- Link State avoids count-to-infinity and converges faster, though both families can oscillate if link weights track live traffic load.
Visual
Worked Examples
In a network of 50 routers where Router A has 3 direct neighbours, how many destinations are listed in Router A's Distance Vector message versus how many link entries are listed in Router A's Link-State Packet?
Show the full solution
• Distance Vector message: lists distances to all 50 routers (destinations).
• Link-State Packet (LSP): lists only Router A's 3 direct neighbour links!
Why is Link State routing not vulnerable to the Count-to-Infinity problem when a link fails?
Show the full solution
When a link fails in Link State, the two adjacent routers immediately flood a new LSP reporting that edge's cost is ∞ (removed). Every router updates its local graph directly and re-runs Dijkstra from scratch on the true remaining edges — no router ever adds its own link cost to a neighbour's stale distance estimate!
State whether each statement describes Distance Vector (DV), Link State (LS), Both, or Neither:
(i) Sends small messages (containing only adjacent link costs) to all routers via flooding.
(ii) Vulnerable to the count-to-infinity problem.
(iii) Can experience route oscillations if link costs are proportional to carried traffic load.
(iv) Guarantees shortest paths even when some edges have negative weight cycles.
Show the full solution
(i) LS. (ii) DV. (iii) Both. (iv) Neither (negative cycles make shortest simple paths undefined/NP-hard, and physical network link costs are always positive).
GATE Traps
- Never say Link State floods the entire routing table! A router in Link State floods ONLY its own direct neighbour link costs (an LSP); the routing table is computed locally and never transmitted.
- Route oscillation ≠ Count-to-infinity: Link State is immune to count-to-infinity, but NOT immune to route oscillations if link costs depend on traffic load.
Memory Hook
DV tells neighbours about the world (big table, 1 hop); LS tells the world about neighbours (small LSP, flooded)!
Connect the Dots
That completes all four chapters of Phase 3! Next up: the Chapter 3.4 Lock-in to cement routing, followed by the 15-question timed Phase 3 Checkpoint (CP3) covering everything from IPv4 addressing and CIDR to fragmentation, NAT, and routing!
Self-Test
- MCQ
Which statement accurately contrasts message exchange in Distance Vector (DV) and Link State (LS) routing?
- DV floods small link-state packets to all routers; LS sends full routing tables only to neighbours.
- DV sends distances to all destinations only to direct neighbours; LS floods direct-neighbour link costs to all routers.
- Both DV and LS flood full routing tables to all routers.
- Both DV and LS send messages only to direct neighbours without flooding.
- MSQ
Which of the following are TRUE when comparing Distance Vector (DV) and Link State (LS) routing?
- LS converges faster than DV after a link failure and does not suffer from count-to-infinity.
- In LS, every router possesses a complete map of the network topology.
- In DV, a single malfunctioning router advertising distance 0 to all destinations can attract traffic from the entire network.
- LS is used by RIP, whereas DV is used by OSPF.
- NAT
In a network of 30 routers, Router R has 4 direct neighbours. How many neighbour-link cost entries does Router R place inside its Link-State Packet (LSP)?
Write your answer before opening the key.
- MCQ
What happens in a Link State network if link costs are set equal to the current traffic load carried on each link?
- The count-to-infinity problem occurs.
- Routers can experience route oscillations as all routers simultaneously shift traffic to lightly loaded paths and back.
- LSPs can no longer be flooded.
- Dijkstra’s algorithm takes exponential time.
Rule Card
- DV (Bellman-Ford, RIP): sends all |V| distances to neighbours only; partial topology; vulnerable to count-to-infinity (∞ = 16).
- LS (Dijkstra, OSPF): floods direct neighbour costs only (LSP) to all routers; full topology; O(V²) local compute; no count-to-infinity.
- Both can oscillate if link cost = traffic load.
Concept Ledger
- DV vs LS comparison
- route oscillation
- RIP ↔ DV
- OSPF ↔ LS
Answer Vault
Try the questions first. Open when you are ready to check.
Warm-up answers
- Dijkstra’s shortest-path algorithm.
- The Bellman-Ford equation: D_x(y) = min_v { c(x,v) + D_v(y) }.
- Distance Vector routing.
Self-test answers
- B — DV sends its full distance vector (all destinations) only to immediate neighbours; LS floods a small LSP (only its own attached links) to all routers.
- A: Reverses DV and LS.
- C: Neither floods a full routing table.
- D: LS floods LSPs across the whole routing area.
- ABC — LS has full topology, fast loop-free convergence, and better robustness; DV is used by RIP and LS is used by OSPF.
- D: Reversed: RIP uses Distance Vector, and OSPF uses Link State.
- 4 — An LSP contains only the originating router’s direct links to its immediate neighbours — here 4 entries (not 30).
- B — Load-dependent link weights cause all routers to simultaneously swing traffic onto the same path and then away on the next update (route oscillation).
- A: Count-to-infinity is a Distance Vector phenomenon.
- C: Flooding uses sequence numbers and is unaffected.
- D: Dijkstra still runs in O(V²) time.
Flashcards
- Motto of Distance Vector vs Link State?
Reveal answer
DV: "Tell your neighbours about the world." LS: "Tell the world about your neighbours." - Which routing family is used by RIP and which by OSPF?
Reveal answer
RIP uses Distance Vector (Bellman-Ford); OSPF uses Link State (Dijkstra). - Why is Link State more robust against a single misconfigured router than Distance Vector?
Reveal answer
Because an LS router only advertises its own attached links and every router computes shortest paths locally, whereas a DV router advertising 0 to all destinations can black-hole the whole network.
Exam shortcuts
- "Neighbours vs World" Mnemonic: DV = Big message (world) to small audience (neighbours); LS = Small message (neighbours) to big audience (world). — answering any DV vs LS message-passing question instantly.
- RIP = DV (15/16), OSPF = LS (Dijkstra). — protocol-matching questions.