Questions: Bellman-Ford Algorithm and Distance-Vector Routing

Question 1

Router A reaches network X through router B (cost 2). The direct link from B to X then fails. Before B can propagate the failure, A sends B its distance vector saying it can reach X at cost 3. What happens next?

• A. B correctly detects the loop and immediately removes X from its routing table
• B. B updates its route to X via A at cost 4, and A may then update again via B, creating a counting loop
• C. A's advertisement is ignored because B originally told A about X, and split horizon prevents A from advertising it back
• D. The count-to-infinity cannot start because triggered updates will propagate the failure instantly

Answer: (B)

This is the count-to-infinity problem. B's direct link to X has failed, so its cost to X is now infinite. But before that failure propagates, A tells B: 'I can reach X at cost 3 (via you!).' B doesn't know A's route loops back through itself, so it updates to reach X via A at cost 4. Next round, A hears B's update (cost 4 to X) and updates to cost 5, then B to cost 6, and so on — the cost increments indefinitely until it reaches 16 (RIP's infinity). Split horizon (option C) would only prevent this if A had a simple two-router topology with B, not in more complex network configurations.

Question 2

Why is RIP (which uses distance-vector routing) limited to networks with a maximum diameter of 15 hops?

• A. Hardware limitations prevent RIP routers from storing routing tables larger than 15 entries
• B. RIP uses 16 as 'infinity' to bound the count-to-infinity problem, making any route with cost 16 unreachable
• C. The 30-second update timer means a 15-hop network takes 7.5 minutes to converge, which is the maximum allowed
• D. TCP/IP protocol headers can only encode hop counts up to 15 bits

Answer: (B)

RIP defines cost 16 as 'infinity' (unreachable). During count-to-infinity, costs increment until they hit 16, at which point the route is poisoned. This design choice bounds the counting loop at the cost of limiting usable network diameter to 15 hops — any legitimate route with more than 15 hops would appear unreachable. This trade-off is why RIP is unsuitable for large networks and why link-state protocols (OSPF) are used instead when networks grow beyond a few dozen routers.

Question 3

Split horizon substantially eliminates the count-to-infinity problem in distance-vector routing protocols.

• T. True
• F. False

Answer: False

Split horizon prevents a router from advertising a route back to the neighbor it learned it from, which stops simple two-router counting loops. However, it does not eliminate count-to-infinity in networks with three or more routers arranged in a topology where routes can loop through intermediate routers. In a triangle topology (A-B-C-A), if the link between A and the destination fails, B and C can still form a counting loop with each other because neither is advertising the route back to the specific neighbor it learned from. Poison reverse strengthens split horizon but still cannot guarantee loop-freedom in all topologies.

Question 4

In distance-vector routing, each router requires knowledge of the full network topology to compute its routing table.

• T. True
• F. False

Answer: False

This is the key distinction between distance-vector and link-state routing. In distance-vector routing, each router only knows its own distance vector (estimated costs to all destinations) and its direct neighbors' distance vectors. It has no knowledge of the overall network topology — which routers connect to which. Global shortest-path routing emerges from purely local exchanges: routers share costs, not topology. This simplicity is both the elegance (less information to store) and the weakness (counts to infinity, slow convergence) of the approach.

Question 5

Why does the count-to-infinity problem not occur in link-state routing protocols like OSPF?

Model answer: In link-state routing, every router floods the network with its local link-state information, so each router builds a complete, consistent map of the entire network topology. When a link fails, all routers update their maps and recompute shortest paths independently — there is no iterative exchange of distance estimates that can create counting loops.

Count-to-infinity arises because distance-vector routers only know costs, not topology — they cannot detect that an advertised route loops through themselves. Link-state protocols share raw topology (who is connected to whom with what cost), not computed distances. With a full topology map, Dijkstra's algorithm computes correct shortest paths in one shot per router, and link-failure updates propagate as topology changes rather than as incrementing cost estimates.