Network-layer routing (DV, Count-to-Infinity & Link State)

Chapter 3.4 completed our journey through the Network Layer by showing how routers automatically populate the forwarding tables we used in Chapter 3.1. We contrasted data-plane forwarding with control-plane routing, traced Bellman-Ford Distance Vector exchanges, saw how bad news triggers Count-to-Infinity (and how RIP's ∞=16, Split Horizon, and Poison Reverse fight it), traced LSP flooding and Dijkstra's algorithm step by step, and compared DV and LS head-to-head.

From 3.4.1 Routing vs forwarding, weighted-graph model & shortest paths

• Forwarding = local per-packet lookup (data plane); Routing = network-wide shortest-path computation (control plane).
• Graph model: routers = vertices V, links = edges E with positive cost c(u, v).
• Routing table entry at u for d: stores (Destination d, Cost D_u(d), Next Hop = first neighbour along shortest path).

From 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.

From 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).

From 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[].

From 3.4.5 Distance Vector vs Link State: full comparison, RIP & OSPF

• 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.

1. NAT · 2 marks

   Router R has three neighbours A, B, and C with link costs c(R,A)=2, c(R,B)=5, c(R,C)=1. For destination D, the neighbours advertise D_A(D)=7, D_B(D)=3, D_C(D)=9. What is R’s Bellman-Ford shortest distance to D?

   Write your answer before opening the key.

2. MCQ · 2 marks

   In the previous question (c(R,A)=2, c(R,B)=5, c(R,C)=1; D_A=7, D_B=3, D_C=9), suppose B now sends an update that D_B(D) has increased from 3 to 6. What are R’s new distance and next hop to D?

   1. 8 via B
   2. 9 via A
   3. 11 via B
   4. 10 via C
3. MCQ · 2 marks

   In network A —(2)— B —(3)— C, after convergence, what distance to C does Router A advertise to Router B when Split Horizon with Poison Reverse is enabled?

   1. 5
   2. 2
   3. 3
   4. ∞ (16)
4. NAT · 2 marks

   In A —(2)— B —(2)— C without Split Horizon (infinity = 16), initially D_B(C) = 2 and D_A(C) = 4. Link B–C fails. In synchronous rounds where both A and B exchange vectors simultaneously using the previous round’s values, what is D_B(C) after Round 1 (the very first update after link failure)?

   Write your answer before opening the key.

5. NAT · 2 marks

   Consider a 4-node graph with edges (A,B)=1, (A,C)=4, (B,C)=2, (B,D)=6, (C,D)=3. Running Dijkstra from source A, what is the shortest-path distance to D?

   Write your answer before opening the key.

6. MCQ · 1 mark

   When a router in a Link State network receives a new (unseen) Link-State Packet on interface I, out of which interfaces does it forward the packet?

   1. Only interface I
   2. All of its interfaces including I
   3. All of its interfaces except I
   4. Only the interface toward the default route
7. MSQ · 2 marks

   Which of the following statements are TRUE?

   1. In Distance Vector routing, the size of each routing message grows with the total number of destinations |V| in the network.
   2. In Link State routing, the size of a router’s LSP grows only with the number of its direct neighbours.
   3. Split Horizon completely prevents 3-router routing loops in Distance Vector routing.
   4. Dijkstra’s algorithm adds exactly one vertex to the permanent set in each iteration.
8. MCQ · 1 mark

   Which plane of a router operates on a per-packet timescale (nanoseconds) using hardware lookup tables?

   1. The Control Plane (Routing)
   2. The Data Plane (Forwarding)
   3. The Management Plane
   4. The Link-State Plane