Bellman-Ford Algorithm - Distance Vector Routing | OneNoughtOne

0/240

Computer NetworksDistance Vector Routing

Distance Vector Routing

LevelIntermediate

Duration90 mins

TopicDistance Vector Routing

1 / 5

Bellman-Ford Algorithm

The Mathematical Heart of Distance Vector Routing

Every time a packet traverses the Internet, it follows a path computed by routing algorithms executing on thousands of routers worldwide. At the foundation of one major family of these algorithms—distance vector routing protocols—lies a deceptively elegant mathematical concept: the Bellman-Ford algorithm.

Developed independently by Richard Bellman in 1958 and Lester Ford Jr. in 1956, this algorithm solves the single-source shortest paths problem in weighted graphs where edge weights can be negative. Its distributed nature makes it particularly well-suited for network routing, where no single entity has complete visibility of the entire network topology.

Understanding Bellman-Ford isn't merely academic—it's the key to comprehending how protocols like RIP (Routing Information Protocol) function, why they exhibit certain convergence behaviors, and what fundamental limitations they possess.

What You Will Learn

By the end of this page, you will understand the Bellman-Ford algorithm's mechanics, its iterative relaxation process, why it works mathematically, how it translates to distributed network implementations, and the computational complexity implications for real-world routing.

Algorithm Foundation and Problem Statement

Before diving into Bellman-Ford's mechanics, we must precisely define the problem it solves and the context in which it operates.

The Shortest Path Problem:

Given a weighted, directed graph G = (V, E) with:

V: A set of vertices (nodes/routers)
E: A set of edges (links) with associated weights (costs/metrics)
s: A designated source vertex

Find the minimum total weight path from the source vertex s to every other vertex v ∈ V.

Why This Matters for Routing:

In networking terms, vertices represent routers or network nodes, edges represent physical or logical links, and weights represent routing metrics (hop count, delay, bandwidth, etc.). The shortest path from source to destination determines the optimal route for packet forwarding.

Graph Theory to Networking Terminology Mapping
Graph Theory Term	Networking Equivalent	Practical Meaning
Vertex (Node)	Router / Network Device	A point that makes forwarding decisions
Edge	Network Link	Physical or logical connection between devices
Edge Weight	Routing Metric	Cost of traversing a link (hop, delay, bandwidth)
Shortest Path	Optimal Route	Minimum-cost path from source to destination
Path Length	Route Cost	Sum of all edge weights along the path

The Bellman-Ford Equation:

The algorithm is built upon a fundamental recurrence relation known as the Bellman equation (from dynamic programming theory):

dₓ(y) = min { c(x,v) + dᵥ(y) }
          v

Where:

dₓ(y) = minimum cost from node x to destination y
c(x,v) = cost of the direct link from x to neighbor v
dᵥ(y) = minimum cost from neighbor v to destination y

This equation expresses a profound insight: to find the shortest path from x to y, consider all neighbors v of x, compute the cost of going through each neighbor (link cost plus the neighbor's distance to y), and choose the minimum.

The Principle of Optimality

Bellman-Ford relies on the principle of optimality: any sub-path of an optimal path is itself optimal. If the shortest path from A to C goes through B, then the sub-path from A to B must be the shortest possible, and the sub-path from B to C must also be shorter. This recursive structure enables dynamic programming solutions.

Algorithm Mechanics: Iterative Relaxation

The Bellman-Ford algorithm operates through a process called relaxation, iteratively improving distance estimates until they converge to the true shortest path values.

Relaxation Defined:

To relax an edge (u, v) with weight w means to test whether the current shortest path estimate to v can be improved by going through u:

if d[v] > d[u] + w(u, v) then
    d[v] = d[u] + w(u, v)
    predecessor[v] = u

The Iterative Process:

Bellman-Ford performs |V| - 1 iterations, where each iteration relaxes all edges in the graph. After i iterations, the algorithm has found all shortest paths that use at most i edges.

bellman_ford.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
def bellman_ford(graph, source):
    """
    Bellman-Ford Algorithm for Single-Source Shortest Paths
    
    Args:
        graph: Dictionary where graph[u] = [(v, weight), ...] for each edge u->v
        source: The source vertex
    
    Returns:
        distances: Dictionary of shortest distances from source
        predecessors: Dictionary for path reconstruction
        has_negative_cycle: Boolean indicating negative cycle presence
    """
    # Step 1: Initialize distances
    # All vertices start at infinity, except source at 0
    vertices = set()
    for u in graph:
        vertices.add(u)
        for v, _ in graph[u]:
            vertices.add(v)
    
    distances = {v: float('inf') for v in vertices}
    predecessors = {v: None for v in vertices}
    distances[source] = 0
    
    # Step 2: Relax all edges |V| - 1 times
    # After iteration i, we have shortest paths using at most i edges
    num_vertices = len(vertices)
    
    for iteration in range(num_vertices - 1):
        updated = False
        for u in graph:
            for v, weight in graph[u]:
                # Relaxation step
                if distances[u] != float('inf') and \
                   distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight
                    predecessors[v] = u
                    updated = True
        
        # Early termination: if no updates, we've converged
        if not updated:
            break
    
    # Step 3: Check for negative-weight cycles
    # If we can still relax, there's a negative cycle
    has_negative_cycle = False
    for u in graph:
        for v, weight in graph[u]:
            if distances[u] != float('inf') and \
               distances[u] + weight < distances[v]:
                has_negative_cycle = True
                break
        if has_negative_cycle:
            break
    
    return distances, predecessors, has_negative_cycle
 
 
def reconstruct_path(predecessors, source, destination):
    """Reconstruct the shortest path from source to destination."""
    path = []
    current = destination
    
    while current is not None:
        path.append(current)
        current = predecessors[current]
    
    path.reverse()
    
    if path[0] != source:
        return None  # No path exists
    return path
 
 
# Example: Network topology
network = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 3), ('D', 2), ('E', 3)],
    'C': [('B', 1), ('D', 4), ('E', 5)],
    'D': [],
    'E': [('D', 1)]
}
 
distances, predecessors, has_cycle = bellman_ford(network, 'A')
print("Shortest distances from A:", distances)
print("Path to D:", reconstruct_path(predecessors, 'A', 'D'))

Why |V| - 1 Iterations?

In a graph with |V| vertices, the longest possible shortest path without cycles contains at most |V| - 1 edges. After i iterations, Bellman-Ford guarantees correct distances for all paths with ≤ i edges. Therefore, |V| - 1 iterations suffice to find all shortest paths in a cycle-free scenario.

Step-by-Step Execution Example

Let's trace through Bellman-Ford on a concrete network topology to solidify understanding. Consider a 5-node network with the following topology:

Converting Mermaid diagram...

Initial State (Source = A):

Vertex	Distance	Predecessor
A	0
B	∞
C	∞
D	∞
E	∞

Iteration 1: Relaxing All Edges

We process each edge and check if we can improve distance estimates:

Edge (A, B, 4): d[B] = ∞ → d[A] + 4 = 0 + 4 = 4 ✓ Update
Edge (A, C, 2): d[C] = ∞ → d[A] + 2 = 0 + 2 = 2 ✓ Update
Edge (B, C, 3): d[C] = 2, d[B] + 3 = 4 + 3 = 7 > 2, no update
Edge (B, D, 2): d[D] = ∞ → d[B] + 2 = 4 + 2 = 6 ✓ Update
Edge (B, E, 3): d[E] = ∞ → d[B] + 3 = 4 + 3 = 7 ✓ Update
Edge (C, B, 1): d[B] = 4, d[C] + 1 = 2 + 1 = 3 < 4 ✓ Update to 3
Edge (C, D, 4): d[D] = 6, d[C] + 4 = 2 + 4 = 6, no update (equal)
Edge (C, E, 5): d[E] = 7, d[C] + 5 = 2 + 5 = 7, no update (equal)
Edge (E, D, 1): d[D] = 6, d[E] + 1 = 7 + 1 = 8 > 6, no update

After Iteration 1:

Vertex	Distance	Predecessor	Change
A	0
B	3	C	Updated
C	2	A	Updated
D	6	B	Updated
E	7	B or C	Updated

Iteration 2: Further Refinement

We repeat the relaxation process with updated distances:

Edge (B, D, 2): d[D] = 6, d[B] + 2 = 3 + 2 = 5 < 6 ✓ Update to 5
Edge (B, E, 3): d[E] = 7, d[B] + 3 = 3 + 3 = 6 < 7 ✓ Update to 6

After Iteration 2:

Vertex	Distance	Predecessor	Change
A	0
B	3	C
C	2	A
D	5	B	Updated
E	6	B	Updated

Iteration 3:

No further improvements possible. Algorithm terminates.

Shortest Paths from A:

A → C: cost 2 (direct)
A → C → B: cost 3
A → C → B → D: cost 5
A → C → B → E: cost 6

Convergence Insight

Notice how the algorithm discovered that the path A → C → B (cost 3) is shorter than the direct path A → B (cost 4). This illustrates how iterative relaxation can find non-obvious optimal paths by progressively refining distance estimates through intermediate nodes.

Complexity Analysis

Understanding Bellman-Ford's computational complexity is crucial for evaluating its suitability in network environments with varying scale constraints.

Bellman-Ford Complexity Breakdown
Aspect	Complexity	Explanation
Time Complexity	O(\|V\| × \|E\|)	Each of \|V\|-1 iterations processes all \|E\| edges
Space Complexity	O(\|V\|)	Store distances and predecessors for each vertex
Best Case (Early Termination)	O(\|E\|)	If graph is already ordered optimally, one iteration suffices
Negative Cycle Detection	O(\|E\|)	One additional pass to detect negative cycles
Dense Graph (\|E\| ≈ \|V\|²)	O(\|V\|³)	Becomes cubic for fully connected networks
Sparse Graph (\|E\| ≈ \|V\|)	O(\|V\|²)	More practical for typical network topologies

Advantages

•Handles negative weights — Unlike Dijkstra's algorithm, which requires non-negative edge weights
•Detects negative cycles — Can identify if a negative-weight cycle exists, making shortest paths undefined
•Simple implementation — Straightforward iterative logic, easy to understand and implement
•Distributed execution — Naturally parallelizable across network nodes, which is the key property for distance vector routing

Disadvantages

•Slower than Dijkstra — O(|V||E|) vs O(|E| + |V|log|V|) for graphs with non-negative weights
•Convergence time — May require many iterations before all distances stabilize
•Full edge processing — Each iteration must process all edges, even if most won't change
•Memory for large networks — Each node must maintain distance estimates to all destinations

Scalability Consideration

For large networks, Bellman-Ford's O(|V||E|) complexity can become prohibitive. This is why distance vector protocols like RIP are typically used in smaller networks or autonomous systems, while larger networks prefer link-state protocols (OSPF) that use Dijkstra's more efficient algorithm after constructing a complete topology map.

Distributed Implementation for Networks

The true power of Bellman-Ford for networking lies in its natural adaptation to distributed execution. Rather than a single node running the algorithm with complete graph knowledge, each router executes a local version using only information from its immediate neighbors.

The Distributed Bellman-Ford Approach:

Each router:

Maintains a distance vector: estimated distances to all known destinations
Periodically exchanges distance vectors with directly connected neighbors
Updates its own distance vector based on received information
Converges to the correct shortest paths through iterative refinement

distributed_bellman_ford.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
class Router:
    """
    Simulates a router running distributed Bellman-Ford algorithm.
    Each router maintains its own distance vector and exchanges with neighbors.
    """
    
    def __init__(self, router_id, neighbors):
        """
        Args:
            router_id: Unique identifier for this router
            neighbors: Dict of {neighbor_id: link_cost}
        """
        self.router_id = router_id
        self.neighbors = neighbors  # {neighbor_id: link_cost}
        
        # Distance vector: {destination: (cost, next_hop)}
        # Initialize with direct neighbor costs
        self.distance_vector = {router_id: (0, router_id)}
        for neighbor_id, cost in neighbors.items():
            self.distance_vector[neighbor_id] = (cost, neighbor_id)
        
        # Store received distance vectors from neighbors
        self.neighbor_vectors = {}
    
    def get_distance_vector_to_share(self):
        """Returns distance vector to share with neighbors."""
        return {dest: cost for dest, (cost, _) in self.distance_vector.items()}
    
    def receive_distance_vector(self, neighbor_id, neighbor_dv):
        """
        Receive and store distance vector from a neighbor.
        
        Args:
            neighbor_id: ID of the neighbor sending the update
            neighbor_dv: Dict of {destination: cost} from neighbor's perspective
        """
        self.neighbor_vectors[neighbor_id] = neighbor_dv
    
    def update_distance_vector(self):
        """
        Apply Bellman-Ford update using received neighbor distance vectors.
        Returns True if any distance changed.
        """
        changed = False
        
        # Collect all known destinations
        all_destinations = set(self.distance_vector.keys())
        for neighbor_dv in self.neighbor_vectors.values():
            all_destinations.update(neighbor_dv.keys())
        
        for destination in all_destinations:
            if destination == self.router_id:
                continue  # Distance to self is always 0
            
            # Find best path through any neighbor
            best_cost = float('inf')
            best_next_hop = None
            
            for neighbor_id, link_cost in self.neighbors.items():
                if neighbor_id in self.neighbor_vectors:
                    neighbor_dv = self.neighbor_vectors[neighbor_id]
                    if destination in neighbor_dv:
                        total_cost = link_cost + neighbor_dv[destination]
                        if total_cost < best_cost:
                            best_cost = total_cost
                            best_next_hop = neighbor_id
            
            # Update if we found a better path
            current_cost = self.distance_vector.get(destination, (float('inf'), None))[0]
            if best_cost < current_cost:
                self.distance_vector[destination] = (best_cost, best_next_hop)
                changed = True
        
        return changed
    
    def print_routing_table(self):
        """Display the current routing table."""
        print(f"
=== Router {self.router_id} Routing Table ===")
        print(f"{'Destination':<12} {'Cost':<8} {'Next Hop':<10}")
        print("-" * 30)
        for dest, (cost, next_hop) in sorted(self.distance_vector.items()):
            cost_str = str(cost) if cost != float('inf') else "∞"
            print(f"{dest:<12} {cost_str:<8} {next_hop:<10}")
 
 
def simulate_distributed_bellman_ford(routers, max_iterations=10):
    """
    Simulate distributed Bellman-Ford across a network of routers.
    """
    print("Starting Distributed Bellman-Ford Simulation")
    print("=" * 50)
    
    for iteration in range(max_iterations):
        print(f"
--- Iteration {iteration + 1} ---")
        
        # Phase 1: All routers share their distance vectors
        shared_vectors = {}
        for router_id, router in routers.items():
            shared_vectors[router_id] = router.get_distance_vector_to_share()
        
        # Phase 2: Routers receive vectors from neighbors
        for router_id, router in routers.items():
            for neighbor_id in router.neighbors:
                router.receive_distance_vector(neighbor_id, shared_vectors[neighbor_id])
        
        # Phase 3: Routers update their distance vectors
        any_changed = False
        for router in routers.values():
            if router.update_distance_vector():
                any_changed = True
        
        # Check for convergence
        if not any_changed:
            print(f"
Converged after {iteration + 1} iterations!")
            break
    
    # Print final routing tables
    print("
" + "=" * 50)
    print("FINAL ROUTING TABLES")
    print("=" * 50)
    for router in routers.values():
        router.print_routing_table()
 
 
# Example network topology
#     2
#  A --- B
#  |     |
# 4|     |3
#  |     |
#  C --- D
#     1
 
routers = {
    'A': Router('A', {'B': 2, 'C': 4}),
    'B': Router('B', {'A': 2, 'D': 3}),
    'C': Router('C', {'A': 4, 'D': 1}),
    'D': Router('D', {'B': 3, 'C': 1}),
}
 
simulate_distributed_bellman_ford(routers)

Asynchronous Execution

In real networks, routers don't execute in synchronized rounds. Updates happen asynchronously as routers receive neighbor advertisements. This asynchrony affects convergence time and can introduce temporary routing loops during topology changes—issues we'll explore in subsequent pages.

From Algorithm to Protocol: RIP

The Routing Information Protocol (RIP) is a direct implementation of distributed Bellman-Ford. Understanding how the abstract algorithm maps to protocol specifics illuminates the practical considerations of distance vector routing.

Bellman-Ford to RIP Mapping
Bellman-Ford Concept	RIP Implementation	Practical Details
Edge weight	Hop count (fixed cost = 1)	Each link costs 1 hop; maximum 15 hops
Distance vector	RIP response message	Contains (destination, metric) pairs
Iteration	Update interval	Broadcast every 30 seconds
Relaxation	Route update	If new route has lower metric, update table
Convergence detection	Holddown timer	Wait period before accepting new routes
Infinity	Metric = 16	Destinations with 16+ hops are unreachable

RIP Message Format:

RIP uses a simple message structure for distance vector exchange:

+------------------------+
|  Command (1 byte)      |  1 = Request, 2 = Response
+------------------------+
|  Version (1 byte)      |  1 = RIPv1, 2 = RIPv2
+------------------------+
|  Reserved (2 bytes)    |
+------------------------+
|  Address Family (2)    |
+------------------------+
|  Route Tag (2)         |  (RIPv2 only)
+------------------------+
|  IP Address (4 bytes)  |
+------------------------+
|  Subnet Mask (4)       |  (RIPv2 only)
+------------------------+
|  Next Hop (4)          |  (RIPv2 only)
+------------------------+
|  Metric (4 bytes)      |  Hop count (1-16)
+------------------------+
  ... up to 25 entries ...

Triggered Updates:

Beyond periodic 30-second broadcasts, RIP sends immediate updates when routing table changes occur. This mechanism accelerates convergence when topology changes happen.

RIP Limitations from Bellman-Ford

RIP inherits Bellman-Ford's slow convergence characteristics. The 15-hop limit exists precisely because larger networks would take prohibitively long to converge. The count-to-infinity problem, which we'll explore in detail, further constrains RIP's applicability to small networks.

Mathematical Foundation: Why It Works

For a rigorous understanding, let's examine why Bellman-Ford correctly computes shortest paths. The proof relies on induction over the number of edges in shortest paths.

Theorem: After k iterations of Bellman-Ford, for every vertex v, d[v] equals the length of the shortest path from source s to v using at most k edges.

Proof by Induction:

Base Case (k = 0):

d[s] = 0 (correct: path to source using 0 edges has length 0)
d[v] = ∞ for v ≠ s (correct: cannot reach other vertices with 0 edges)

Inductive Step: Assume the theorem holds after k-1 iterations. Consider any vertex v and the shortest path P from s to v using exactly k edges.

Let u be the vertex immediately before v on path P. Then:

The sub-path from s to u uses k-1 edges
By inductive hypothesis, d[u] equals shortest path length to u after k-1 iterations

In iteration k, when we relax edge (u, v):

We set d[v] = min(d[v], d[u] + w(u,v))
This equals the length of path P

Since we consider all predecessors u of v, we find the minimum over all k-edge paths.

Corollary: Since any shortest path in a graph with |V| vertices has at most |V| - 1 edges (assuming no negative cycles), |V| - 1 iterations suffice to find all shortest paths.

Negative Cycle Detection Proof

If a negative-weight cycle exists, the shortest 'path' length is -∞ (we can traverse the cycle infinitely). After |V| - 1 iterations, any further relaxation indicates a negative cycle: we found a path with |V| edges that's shorter than any |V| - 1 edge path, which is only possible if the path contains a cycle—and if it's shorter, the cycle must have negative total weight.

Summary and What's Next

We've established a solid foundation in the Bellman-Ford algorithm—the mathematical engine powering distance vector routing protocols. Let's consolidate the key insights:

Key Takeaways

•The Bellman equation expresses the optimal substructure: best cost to destination = min(link cost to neighbor + neighbor's best cost to destination)
•Iterative relaxation progressively improves distance estimates; |V| - 1 iterations guarantee convergence for graphs without negative cycles
•O(|V||E|) complexity makes Bellman-Ford slower than Dijkstra but enables distributed execution and handles negative weights
•Distributed implementation allows each router to run locally with neighbor information only—the fundamental property enabling distance vector protocols
•RIP directly implements distributed Bellman-Ford with hop count metric, 30-second update intervals, and a 15-hop infinity threshold

What's Next: Routing Table Exchange

With the algorithm mechanics understood, we now explore how routers actually exchange routing information. The next page examines the routing table exchange process in detail: message formats, update triggers, timing considerations, and how the distributed algorithm executes across real network devices.

Page Complete

You now understand the Bellman-Ford algorithm—the mathematical heart of distance vector routing. This foundation is essential for comprehending both the power and limitations of protocols like RIP, and for appreciating the solutions to problems like count-to-infinity that we'll explore later in this module.