Distance Vector routing & the Bellman-Ford equation

1. In a weighted router graph, what two pieces of information does router X store in its routing table for each destination Y?
   Stuck? Peek at 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).

   Read lesson 3.4.1

2. What does a router do when a destination IP matches multiple rows in its forwarding table?
   Stuck? Peek at 3.1.5 Forwarding tables & Longest Prefix Match (LPM)

   • Match condition: Row N/n (mask M) matches destination D iff (D AND M) == N (i.e. D falls in [N .. N + 2³²⁻ⁿ − 1]).
   • Longest Prefix Match (LPM): Among all matching rows, pick the one with the largest prefix length n.
   • Default route 0.0.0.0/0: matches every address with n = 0 (used only if nothing else matches).

   Read lesson 3.1.5

3. What is a direct neighbour of a router?
   Stuck? Peek at 1.3.2 Propagation, queuing and processing delay; multi-hop pipelining

   • T_p = d / v, v = 2 × 10⁸ m/s default; independent of size and rate.
   • Nodal delay = d_proc + d_queue + T_t + T_p.
   • One packet, h equal links: h·T_t + h·T_p.
   • N packets, h equal links: (N + h − 1)·T_t + h·T_p (+ (h − 1)·d_proc).
   • Unequal links: first packet ΣT_t + ΣT_p, then + (N − 1) × max T_t.
   • Traffic intensity L·a/R → 1: queues explode.

   Read lesson 1.3.2

Imagine standing at a country crossroads with no map. You only know the distance to the two villages directly down the road from you: Village B is 2 km away, and Village C is 6 km away. Then a traveller from B tells you, "From B, I can reach City D in 5 km!" Instantly you add two numbers: 2 km (to B) + 5 km (B to D) = 7 km via B!

That simple idea — "my best distance to Y is the minimum over all my neighbours v of (cost to v + v's distance to Y)" — is the Bellman-Ford equation, the engine of Distance Vector (DV) routing.

Router A has two neighbours: B (at link cost 2) and C (at link cost 6). B reports its distance to D is 8, and C reports its distance to D is 2. What distance and next hop to D does Router A compute?

Via B: 2 + 8 = 10. Via C: 6 + 2 = 8. Since min(10, 8) = 8, Router A sets D_A(D) = 8 via next-hop C (until B learns a better route via C in the next round!).

The Bellman-Ford Equation

Let Dₓ(y) be router x's current estimate of the minimum cost from x to destination y, and let N(x) be the set of direct neighbours of x. Whenever x receives a distance vector D_v = [D_v(y) : y ∈ V] from each neighbour v ∈ N(x), it updates its table using:

What is in a Distance Vector Message?

Three critical facts tested on GATE:

• A distance vector from router v is a 1-D list of pairs (Destination y, Distance D_v(y)) for all destinations in the network.
• No next-hop or path is sent! Router v tells its neighbours how far y is, NOT which path v takes to get there.
• A router sends its distance vector ONLY to its immediate neighbours (never flooded across the whole network).

Round-by-Round Trace to Convergence

Let's trace synchronous DV rounds on our 4-router graph (A–B=2, A–C=6, B–C=3, B–D=8, C–D=2):

Putting it together

• Distance Vector routing uses the distributed Bellman-Ford equation D_x(y) = min_v { c(x,v) + D_v(y) }.
• Routers exchange vectors of distances (without path details) only with their immediate neighbours.
• Each synchronous round propagates shortest-path improvements one additional hop across the network.

• Keeping the old cost when the current next-hop worsens: A router does NOT take min(old_D_x(y), new_candidates) when the old route went through the very neighbour whose cost just increased!
• Distance Vector messages go ONLY to direct neighbours: Never say DV broadcasts/floods vectors to all routers.

Add your link cost to each neighbour's column, then pick the smallest number in each row!

Notice how blindly trusting a neighbour's distance worked great when costs decreased. Next question (3.4.3): What happens when the link to C breaks completely, and B asks A for a route to C without realising that A's route to C goes right back through B?

1. NAT

   Router A has neighbours B (link cost 3) and C (link cost 7). B advertises distance 9 to destination Z, and C advertises distance 4 to destination Z. What is Router A’s shortest distance to Z after applying the Bellman-Ford update?

   Write your answer before opening the key.

2. MCQ

   In Distance Vector routing, to which routers does a router send its distance vector, and what does the vector contain?

   1. To all routers in the network; it contains the full topology graph.
   2. Only to its immediate neighbours; it contains its current estimated shortest distance to every destination.
   3. Only to its immediate neighbours; it contains the complete list of routers along each shortest path.
   4. Only to the default router; it contains only its direct link costs.
3. NAT

   Router X has two neighbours M (link cost 2) and N (link cost 6). Initially M advertises distance 5 to D and N advertises distance 4 to D, so X routes to D via M with cost 7. Next, M sends an update that its distance to D has increased to 9 (while N still advertises 4). What is X’s new distance to D?

   Write your answer before opening the key.

4. MSQ

   Which of the following statements about Distance Vector (Bellman-Ford) routing are TRUE?

   1. It is a distributed, iterative algorithm where routers exchange information only with directly connected neighbours.
   2. In the absence of link failures, a k-hop shortest path takes at most k synchronous exchange rounds to be discovered.
   3. Each router knows the complete topology (all nodes and edges) of the entire network.
   4. RIP (Routing Information Protocol) is based on Distance Vector routing.

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

• distance vector
• Bellman-Ford equation
• neighbour
• DV exchange
• rounds
• convergence

1. Write the Bellman-Ford equation for Router x’s distance to y.
   Reveal answer

   D_x(y) = min over all neighbours v of { c(x, v) + D_v(y) }.
2. Who receives a router’s Distance Vector message, and is the next-hop included in the message?
   Reveal answer

   Only immediate (1-hop) neighbours receive it; the next-hop is NOT included (only destination and distance).
3. What must Router X do if its current next-hop neighbour V reports a LARGER distance to Y?
   Reveal answer

   Recompute the cost via V (c(X,V) + new D_V(Y)) and then take the minimum over all neighbours.

• Column-Shift Method for GATE DV Tables: Write each neighbour's advertised vector as a column, add the link cost c(x, v) to the entire column, and read the row-wise minimum across columns! — solving full-table GATE Bellman-Ford questions in 20 seconds without arithmetic slips.
• When current next-hop gets worse: If the update comes from your current next-hop v* and D_{v*}(y) increased, your old cost is GONE — replace it before taking the min! — GATE questions where a link cost increases.