Tutorial 5: Distance-Vector Routing and Bellman-Ford Algorithm Expanded

Learning Objectives
Overview
Detailed Technical Content
Quiz
Exercises
Homework
Summary

Learning Objectives

Explain the distance-vector routing principle and the information each router maintains.
Derive and apply the Bellman-Ford equation for shortest path computation.
Describe the distributed, iterative, and asynchronous nature of distance-vector route updates.
Analyze the convergence behavior of distance-vector routing and identify the count-to-infinity problem.
Evaluate loop prevention mechanisms: split horizon, poison reverse, triggered updates, and hold-down timers.
Perform mathematical analysis of convergence time and routing loop duration.
Compare and contrast distance-vector with link-state routing in terms of overhead, convergence, and complexity.
Discuss the applicability of distance-vector in modern networks and its limitations.

Overview

Distance-vector (DV) routing is a distributed algorithm used in early routing protocols such as RIP (Routing Information Protocol). Each router maintains a vector of distances (costs) to all known destinations, along with the next hop on the best path. Routers periodically exchange their distance vectors with directly connected neighbours. Using the Bellman-Ford equation, each router updates its own vector to find the least-cost paths. DV is simple and requires little computation, but it suffers from slow convergence and the well-known count-to-infinity problem when link costs increase or links fail. Various enhancements such as split horizon, poison reverse, triggered updates, and hold-down timers mitigate these issues. This tutorial provides an in-depth exploration of DV routing, including the mathematical foundations, convergence analysis, loop prevention techniques, and a thorough comparison with link-state routing.

Detailed Technical and Theoretical Content

1. Distance-Vector Principles

In distance-vector routing, each router x maintains:

A vector D_x = [D_x(y)] for all destinations y in the network, representing its current estimate of the least cost to reach y.
A next-hop vector next_x(y) indicating the neighbour on the best path to y.
The cost to each neighbour c(x,v).

Routers exchange their distance vectors with neighbours periodically (e.g., every 30 seconds in RIP) or when the vector changes (triggered updates). Upon receiving a vector from neighbour v, router x updates its own vector using the Bellman-Ford equation:

D_x(y) = \min_{v \in N(x)} \{ c(x,v) + D_v(y) \}

where N(x) is the set of neighbours of x. This equation is applied iteratively until convergence.

2. The Bellman-Ford Equation and Algorithm

The Bellman-Ford algorithm is a dynamic programming solution to the shortest path problem in a graph with no negative cycles. For a graph with n vertices, it computes shortest paths from a source by relaxing all edges repeatedly. In a distributed setting, each router runs the Bellman-Ford iteration using vectors from neighbours.

Centralised Bellman-Ford algorithm:

Initialize dist[s]=0, dist[v]=INF for all v≠s
for i = 1 to |V|-1:
    for each edge (u,v):
        if dist[u] + w(u,v) < dist[v]:
            dist[v] = dist[u] + w(u,v)

In DV routing, the algorithm is distributed: each node computes its own distances based on neighbours' distances, and the process is asynchronous. The algorithm converges to the true shortest paths if the network is static and no updates are lost.

3. Distributed Route Computation and Periodic Updates

Routers send their entire distance vector (or only changes) to neighbours. When a router receives an update, it recalculates its distances. If any distance decreases, it may trigger an immediate update (triggered update). However, if a distance increases, the router must wait for a while (hold-down) to avoid flapping. The periodic exchange ensures that all routers eventually learn about changes, but the propagation of information is slow—one hop per update interval.

4. Convergence and the Count-to-Infinity Problem

Convergence is the process of all routers having consistent, accurate distance vectors. In DV, convergence can be slow, especially when a link fails and the cost to a destination increases. The count-to-infinity problem arises when routers gradually increase the cost to an unreachable destination, each advertising a path through the other, until the cost reaches a maximum (e.g., 16 in RIP, which is considered infinity).

Example: A, B, C in a line. A is connected to B, B to C, and C to a destination. If the link between A and B fails, B may think it can reach A via C (if C has a route to A through B), and C may think it can reach A via B, leading to increasing costs until infinity.

5. Loop Prevention Mechanisms

To mitigate count-to-infinity and routing loops, distance-vector protocols employ several techniques:

Split horizon: A router does not advertise a route back to the neighbour from which it learned that route. This prevents some loops in two-node topologies.
Poison reverse: A router advertises a route with an infinite metric (e.g., 16) back to the neighbour that supplied it, actively breaking loops. This is stronger than split horizon.
Triggered updates: When a route's metric changes (especially when it increases), the router sends an update immediately, rather than waiting for the next periodic update, speeding up convergence.
Hold-down timers: After a route becomes unreachable or its metric increases significantly, the router ignores any updates about that route (except from the same neighbour) for a period (e.g., 180 seconds in RIP). This prevents the acceptance of stale information that could cause loops.

6. Mathematical Analysis of Convergence

The convergence time of DV can be bounded based on the network diameter and the update interval. In the worst case, the count-to-infinity problem can cause convergence to take O(n) update cycles, where n is the number of routers, because each hop may increase the cost by 1 per cycle until infinity is reached. With infinity set to a small number (e.g., 16), convergence is limited but may still take up to 16 cycles. The use of triggered updates and hold-down timers can reduce this, but not eliminate it entirely.

7. Comparison with Link-State Routing

Aspect	Distance-Vector	Link-State
Information exchanged	Distance vectors (distances to all destinations) with neighbours	LSAs (link-state advertisements) flooded to all routers
Topology knowledge	Only knows distances via neighbours	Complete topology map
Convergence speed	Slow; may suffer from count-to-infinity	Fast; all routers compute independently
Complexity	Low (O(degree) per update)	Higher (O(\|V\| log \|V\|) per computation)
Scalability	Limited (RIP max 15 hops)	More scalable with areas
Loop-free guarantee	Not inherent; requires mechanisms	Inherently loop-free due to consistent topology

8. Advanced Topics: Poison Reverse, Triggered Updates, and Damping

Poison reverse is an extension of split horizon that explicitly advertises a metric of infinity to the neighbour from which the route was learned. This quickly informs the neighbour that the route is not usable, preventing loops. Triggered updates propagate changes immediately, reducing convergence time but increasing overhead during flapping. Damping techniques (like hold-down timers and route dampening) are used to suppress oscillations by delaying route acceptance after a metric increase.

In modern routing, distance-vector is rarely used for interior routing except in small networks (RIP). However, the principles are similar to those used in BGP for inter-domain routing, though BGP is path-vector and uses policy.

Figure 1: Simple network illustrating count-to-infinity

    A --- B --- C --- D (destination)
    If A-B fails, B may think it can reach A via C, and C via B, leading to increasing costs.

Quiz

Answer each question; check your understanding by revealing the answer.

Question 1: What information does a router maintain in distance-vector routing?

Show Answer

It maintains a distance vector (cost to each destination) and the next hop for each destination, along with link costs to neighbours.

Question 2: Write the Bellman-Ford equation for a router x.

Show Answer

D_x(y) = min_{v in N(x)} { c(x,v) + D_v(y) }.

Question 3: What is the count-to-infinity problem?

Show Answer

It occurs when routers gradually increase the cost to an unreachable destination due to routing loops, until the cost reaches a predefined infinity value.

Question 4: What is the purpose of split horizon?

Show Answer

To prevent a router from advertising a route back to the neighbour from which it learned that route, reducing the chance of loops.

Question 5: How does poison reverse differ from split horizon?

Show Answer

Poison reverse advertises the route with an infinite metric (poison) to the neighbour, while split horizon simply does not advertise it at all.

Question 6: What is a triggered update?

Show Answer

An immediate update sent when a route's metric changes, instead of waiting for the next periodic update, to speed convergence.

Question 7: What is a hold-down timer and why is it used?

Show Answer

A hold-down timer prevents a router from accepting any new route for a destination for a certain period after a metric increase, to avoid accepting stale information.

Question 8: What is the maximum hop count in RIP?

Show Answer

15; 16 is considered infinity.

Question 9: In distance-vector routing, why do routers exchange their entire vectors periodically?

Show Answer

To ensure all routers eventually learn about changes and to maintain consistency.

Question 10: Can distance-vector routing guarantee loop-free paths without additional mechanisms? Explain.

Show Answer

No, distance-vector can produce loops during convergence; mechanisms like split horizon, poison reverse, and hold-down timers are needed.

Question 11: How does the Bellman-Ford algorithm handle negative edge weights?

Show Answer

It can handle negative weights as long as there are no negative cycles; however, in routing we use positive costs.

Question 12: What is the main advantage of distance-vector over link-state in terms of implementation?

Show Answer

It is simpler and requires less memory and computation per router.

Question 13: What causes routing loops in distance-vector?

Show Answer

Inconsistent distance information among routers due to slow propagation of updates, leading to circular dependencies.

Question 14: How does a router detect a neighbour failure in DV?

Show Answer

By not receiving periodic updates from the neighbour, or via explicit link-down notification.

Question 15: What is the effect of triggered updates on convergence time?

Show Answer

It reduces convergence time by propagating changes faster, but may increase transient overhead.

Question 16: Compare the bandwidth overhead of distance-vector and link-state.

Show Answer

DV exchanges vectors with neighbours, which is O(|V|) per update; link-state floods LSAs to all routers, which can be O(|E|) per update, but DV has periodic updates.

Question 17: In RIP, what happens when a route's metric reaches 16?

Show Answer

It is considered unreachable and is removed from the routing table.

Question 18: Why is distance-vector not suitable for large networks?

Show Answer

Due to slow convergence, count-to-infinity, and the hop count limit (in RIP).

Question 19: How does the hold-down timer interact with triggered updates?

Show Answer

When a metric increases, a hold-down timer starts; during this period, the router ignores better routes from other neighbours (except the one that caused the increase) to prevent flapping.

Question 20: What is the difference between periodic and triggered updates in DV?

Show Answer

Periodic updates are sent at fixed intervals; triggered updates are sent immediately upon significant metric changes.

Question 21: Explain the concept of "routing by rumor" in distance-vector.

Show Answer

It refers to the fact that routers rely on neighbours' information without a global view, so inaccuracies can propagate.

Question 22: In the Bellman-Ford equation, what does D_v(y) represent?

Show Answer

It is the distance from neighbour v to destination y as known by v.

Exercises

Work through these problems; sample solutions are hidden.

Exercise 1: Consider a network with three routers A, B, C. Link costs: A-B=2, B-C=3, A-C=10. Initially, each router knows only its direct links. Show the initial distance vectors. Then perform one exchange of vectors between neighbours (A and B, B and C, A and C) and update each router's vector.

Show Sample Solution

Initial: A: (A=0, B=2, C=10); B: (A=2, B=0, C=3); C: (A=10, B=3, C=0).
After exchange: A receives B's vector (2,0,3) → via B: to C = 2+3=5 (better than 10) → A updates C=5 via B. B receives A's vector (0,2,10) → via A: to C = 2+10=12 (worse than 3), no change. B receives C's vector (10,3,0) → via C: to A = 3+10=13 (worse). C receives A's vector → via A: to B = 10+2=12 (worse than 3); receives B's vector → via B: to A = 3+2=5 (better than 10) → C updates A=5 via B.

Exercise 2: Explain how the count-to-infinity problem occurs in the network A-B-C-D, where A is the destination. Show the sequence of distance vectors when the link A-B fails.

Show Sample Solution

Initially: A=0, B=1 (via A), C=2 (via B), D=3 (via C). When A-B fails, B no longer has a direct path to A. B may have learned from C that C's distance to A is 2 (via B) – so B thinks cost to A = 1 (B-C) + 2 = 3, but C's distance to A is 2 via B. This creates a loop. In the next update, B advertises 3 to C; C updates its cost to A as 1+3=4; then B learns 4, updates to 5, and so on until infinity (16 in RIP).

Exercise 3: Why does split horizon not prevent the count-to-infinity problem in a three-node loop (A-B-C-A) when the link A-B fails?

Show Sample Solution

Split horizon prevents B from advertising the route to A back to A, but in a three-node loop, B and C may still have stale routes through each other. Split horizon only works on a point-to-point basis; in a loop, a router may receive a route from one neighbour and then advertise it to another neighbour, causing a loop.

Exercise 4: Compare the convergence time of distance-vector with and without triggered updates for a network with diameter 5. Assume periodic updates every 30 seconds.

Show Sample Solution

Without triggered updates, changes propagate one hop per 30 seconds → at most 5*30 = 150 seconds. With triggered updates, changes propagate immediately (within milliseconds), so convergence can be sub-second, but may still be limited by hold-down timers.

Exercise 5: How does poison reverse improve upon split horizon? Provide an example where split horizon fails but poison reverse succeeds.

Show Sample Solution

In a three-router network A-B-C, if A learns a route to X via B, split horizon prevents A from advertising X to B. However, B might advertise X to C, and C to B, causing loops. Poison reverse would have B advertise X to C with infinity, preventing C from using B as a path.

Exercise 6: Calculate the number of updates required for all routers to converge in a simple line of n routers when a link at one end fails, using the Bellman-Ford equation with infinity set to 16. How does the presence of triggered updates affect this?

Show Sample Solution

Without triggered updates, it takes n-1 periodic intervals for the increased cost to propagate. With triggered updates, propagation is immediate, but hold-down timers may delay acceptance of new routes. The number of iterative updates to reach infinity is limited by 16.

Exercise 7: A router has the following distance vector: to A: 2 via X, to B: 5 via X, to C: 3 via Y. It receives a vector from neighbour X: (A:1, B:3, C:4). If the link cost to X is 1, what are the new distances and next hops?

Show Sample Solution

New distances: to A = min(2, 1+1=2) no change; to B = min(5, 1+3=4) → update to 4 via X; to C = min(3, 1+4=5) no change. So vector becomes (A:2 via X, B:4 via X, C:3 via Y).

Exercise 8: Explain why distance-vector routing is often called "routing by rumor".

Show Sample Solution

Because routers rely solely on the information they receive from neighbours without verifying its accuracy or knowing the complete topology; a rumour (incorrect vector) can propagate.

Exercise 9: Compare the memory requirements of distance-vector and link-state. Which is more suitable for small networks?

Show Sample Solution

DV stores a vector per destination; link-state stores the entire topology. DV requires less memory, making it suitable for small networks with limited resources.

Exercise 10: In RIP, what is the purpose of the "garbage collection" timer (flush timer)?

Show Sample Solution

After a route is marked invalid (metric 16), the garbage collection timer (flush timer) ensures the route is removed from the routing table after a certain time (e.g., 120 seconds), allowing time for the route to be flushed from other routers.

Homework Assignments

These questions require deeper thought and research. Write comprehensive answers.

Homework 1: Prove that the Bellman-Ford algorithm correctly computes shortest paths in a graph with no negative cycles, and explain why the distributed version eventually converges if updates are periodic.

Show Answer Outline

Use induction on the number of edges in the shortest path. The algorithm relaxes edges repeatedly; after k iterations, all paths with up to k edges are found. In a graph without negative cycles, the shortest paths have at most |V|-1 edges. The distributed version converges because each router's distances are non-increasing and bounded below by the true distances; eventually, all routers have the correct distances.

Homework 2: Derive the maximum time for the count-to-infinity problem to converge in RIP, given a network diameter of d and a hold-down timer of 180 seconds. Consider both periodic updates (30s interval) and triggered updates.

Show Answer Outline

Without triggered updates, worst-case time = d * 30s (to propagate infinity). With triggered updates, propagation is immediate, but hold-down timers may delay the acceptance of new routes; the total time may be bounded by the hold-down timer (180s) plus propagation.

Homework 3: Compare and contrast split horizon, poison reverse, and hold-down timers. When is each most effective? Provide examples where each might fail.

Show Answer Outline

Split horizon effective in two-node loops; poison reverse stronger by actively poisoning; hold-down timers prevent flapping. Failure cases: split horizon fails in three-node loops; poison reverse may not prevent all loops; hold-down timers can delay convergence.

Homework 4: Explain how distance-vector routing can be modified to support policies (as in BGP). What makes BGP a path-vector protocol rather than a pure distance-vector?

Show Answer Outline

BGP advertises paths (AS-PATH) rather than just distances, allowing policies and loop detection. It is a path-vector protocol because it uses the path attribute to enforce policies, not just distance.

Homework 5: Analyse the stability of distance-vector routing under traffic load variations. How can dynamic metrics cause oscillations?

Show Answer Outline

If metrics depend on load, route changes can shift traffic, changing loads again, leading to oscillations. Damping and static metrics are used to avoid this.

Homework 6: Prove that the count-to-infinity problem is bounded in RIP because of the maximum hop count (15). What happens if the network diameter is greater than 15?

Show Answer Outline

RIP cannot route to destinations more than 15 hops away; if diameter > 15, some networks become unreachable. This is a fundamental limitation.

Homework 7: Design a distance-vector protocol that avoids the count-to-infinity problem entirely. Is it possible? Discuss theoretical limitations.

Show Answer Outline

It is possible to avoid count-to-infinity by using a protocol that uses path information (like path-vector) or by using a mechanism like the Diffusing Update Algorithm (DUAL) used in EIGRP, which ensures loop-free paths by querying neighbours before making a change.

Homework 8: Explain the concept of "route poisoning" and how it is used in conjunction with triggered updates to speed up convergence. Give a step-by-step example.

Show Answer Outline

When a route becomes unreachable, the router sets its metric to infinity and immediately sends a triggered update (poisoned route). This informs neighbours quickly, and they propagate the poison.

Homework 9: Compare the convergence of distance-vector routing when using periodic updates versus event-driven updates in a network with frequent link flapping. Which is more stable?

Show Answer Outline

Event-driven updates react faster but can cause instability during flapping; periodic updates provide dampening. A combination with hold-down timers is often used.

Homework 10: Research the Enhanced Interior Gateway Routing Protocol (EIGRP) and explain how it improves upon traditional distance-vector protocols like RIP. Focus on the Diffusing Update Algorithm (DUAL) and its loop-free property.

Show Answer Outline

EIGRP uses DUAL to guarantee loop-free paths by maintaining feasible successors (backup routes) and diffusing queries only when no feasible successor exists, thus avoiding count-to-infinity.

Homework 11: Write pseudocode for a distance-vector routing algorithm that includes split horizon, poison reverse, and triggered updates. Describe the data structures and the event handlers for receiving a vector, timer expiry, and neighbour failure.

Show Answer Outline

Provide pseudocode with functions: initialize, sendVector, receiveVector (which updates distances and sends triggered updates if needed), timer handler for periodic updates, and neighbor timeout handler.

Homework 12: Discuss the trade-offs between using distance-vector and link-state in a mobile ad hoc network (MANET). Why are distance-vector approaches often preferred? What modifications are needed?

Show Answer Outline

In MANETs, topology changes frequently; distance-vector with on-demand route discovery (like AODV) is used to reduce overhead. Link-state would have too much flooding. Modifications include route request/reply mechanisms and sequence numbers to avoid loops.

Summary

This tutorial provided a comprehensive examination of distance-vector routing, including the Bellman-Ford algorithm, distributed computation, convergence issues, and loop prevention mechanisms. We analyzed the count-to-infinity problem and the various techniques used to mitigate it. The comparison with link-state routing highlighted the trade-offs between simplicity and performance. While distance-vector is less common in modern intra-domain routing (except for small networks), its principles are foundational and are also reflected in path-vector protocols like BGP. Understanding these concepts is crucial for network engineers designing and troubleshooting routing protocols.

End of Tutorial 5 .

Tutorial 5: Distance-Vector Routing and Bellman-Ford Algorithm Expanded

Table of Contents

Learning Objectives

Overview

Detailed Technical and Theoretical Content

1. Distance-Vector Principles

2. The Bellman-Ford Equation and Algorithm

3. Distributed Route Computation and Periodic Updates

4. Convergence and the Count-to-Infinity Problem

5. Loop Prevention Mechanisms

6. Mathematical Analysis of Convergence

7. Comparison with Link-State Routing

8. Advanced Topics: Poison Reverse, Triggered Updates, and Damping

Quiz

Exercises

Homework Assignments

Summary