7a:Ta7c,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'))7b:T934,#include #include #include #include #include struct Edge { std::string from; std::string to; int weight; }; struct BellmanFordResult { std::unordered_map distances; std::unordered_map predecessors; bool has_negative_cycle; }; BellmanFordResult bellman_ford( const std::vector& edges, const std::vector& vertices, const std::string& source ) { const int INF = std::numeric_limits::max(); // Step 1: Initialize distances std::unordered_map distances; std::unordered_map predecessors; for (const auto& v : vertices) { distances[v] = INF; predecessors[v] = ""; } distances[source] = 0; int num_vertices = vertices.size(); // Step 2: Relax all edges |V| - 1 times for (int i = 0; i < num_vertices - 1; ++i) { bool updated = false; for (const auto& edge : edges) { if (distances[edge.from] != INF && distances[edge.from] + edge.weight < distances[edge.to]) { distances[edge.to] = distances[edge.from] + edge.weight; predecessors[edge.to] = edge.from; updated = true; } } // Early termination optimization if (!updated) break; } // Step 3: Check for negative cycles bool has_negative_cycle = false; for (const auto& edge : edges) { if (distances[edge.from] != INF && distances[edge.from] + edge.weight < distances[edge.to]) { has_negative_cycle = true; break; } } return {distances, predecessors, has_negative_cycle}; } std::vector reconstruct_path( const std::unordered_map& predecessors, const std::string& source, const std::string& destination ) { std::vector path; std::string current = destination; while (!current.empty()) { path.push_back(current); current = predecessors.at(current); } std::reverse(path.begin(), path.end()); if (path.front() != source) { return {}; // No path exists } return path; }7c:T140f,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)7d:T4d7,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.72:{"json":{"id":"seed_4a7a3fda82ef97cb220446c1067cf0d1","slug":"distance-vector-routing","category":"Computer Networks","topic":"Distance Vector Routing","title":"Distance Vector Routing","description":"Master distance vector routing protocols, from the foundational Bellman-Ford algorithm to practical implementations like RIP. Understand routing table exchange mechanisms, tackle the count-to-infinity problem, and learn critical solutions including split horizon and poison reverse.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_269423f35a3888f58d105650324be322","title":"Bellman-Ford Algorithm","order":0,"content":[{"id":"opening-hook","title":"The Mathematical Heart of Distance Vector Routing","content":[{"data":{"content":"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**.\n\nDeveloped 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.\n\nUnderstanding 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."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"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.","variant":"info"},"type":"callout"}]},{"id":"algorithm-foundation","title":"Algorithm Foundation and Problem Statement","content":[{"data":{"content":"Before diving into Bellman-Ford's mechanics, we must precisely define the problem it solves and the context in which it operates.\n\n**The Shortest Path Problem:**\n\nGiven a weighted, directed graph G = (V, E) with:\n- **V**: A set of vertices (nodes/routers)\n- **E**: A set of edges (links) with associated weights (costs/metrics)\n- **s**: A designated source vertex\n\nFind the minimum total weight path from the source vertex s to every other vertex v ∈ V.\n\n**Why This Matters for Routing:**\n\nIn 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."},"type":"text"},{"data":{"rows":[["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"]],"caption":"Graph Theory to Networking Terminology Mapping","headers":["Graph Theory Term","Networking Equivalent","Practical Meaning"]},"type":"table"},{"data":{"content":"**The Bellman-Ford Equation:**\n\nThe algorithm is built upon a fundamental recurrence relation known as the **Bellman equation** (from dynamic programming theory):\n\n```\ndₓ(y) = min { c(x,v) + dᵥ(y) }\n v\n```\n\nWhere:\n- **dₓ(y)** = minimum cost from node x to destination y\n- **c(x,v)** = cost of the direct link from x to neighbor v\n- **dᵥ(y)** = minimum cost from neighbor v to destination y\n\nThis 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."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Principle of Optimality","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"algorithm-mechanics","title":"Algorithm Mechanics: Iterative Relaxation","content":[{"data":{"content":"The Bellman-Ford algorithm operates through a process called **relaxation**, iteratively improving distance estimates until they converge to the true shortest path values.\n\n**Relaxation Defined:**\n\nTo *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:\n\n```\nif d[v] > d[u] + w(u, v) then\n d[v] = d[u] + w(u, v)\n predecessor[v] = u\n```\n\n**The Iterative Process:**\n\nBellman-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."},"type":"text"},{"data":{"fileName":"bellman_ford.py","languages":[{"code":"$7a","label":"Python","value":"python"},{"code":"$7b","label":"C++","value":"cpp"}]},"type":"code"},{"data":{"icon":"Info","title":"Why |V| - 1 Iterations?","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"step-by-step-execution","title":"Step-by-Step Execution Example","content":[{"data":{"content":"Let's trace through Bellman-Ford on a concrete network topology to solidify understanding. Consider a 5-node network with the following topology:"},"type":"text"},{"data":{"height":"320px","mermaidSyntax":"graph LR\n A((A)) -->|4| B((B))\n A -->|2| C((C))\n B -->|3| C\n B -->|2| D((D))\n B -->|3| E((E))\n C -->|1| B\n C -->|4| D\n C -->|5| E\n E -->|1| D"},"type":"mermaid-excalidraw"},{"data":{"content":"**Initial State (Source = A):**"},"type":"text"},{"data":{"rows":[["A","0","-"],["B","∞","-"],["C","∞","-"],["D","∞","-"],["E","∞","-"]],"headers":["Vertex","Distance","Predecessor"]},"type":"table"},{"data":{"content":"**Iteration 1: Relaxing All Edges**\n\nWe process each edge and check if we can improve distance estimates:\n\n1. **Edge (A, B, 4)**: d[B] = ∞ → d[A] + 4 = 0 + 4 = 4 ✓ Update\n2. **Edge (A, C, 2)**: d[C] = ∞ → d[A] + 2 = 0 + 2 = 2 ✓ Update\n3. **Edge (B, C, 3)**: d[C] = 2, d[B] + 3 = 4 + 3 = 7 > 2, no update\n4. **Edge (B, D, 2)**: d[D] = ∞ → d[B] + 2 = 4 + 2 = 6 ✓ Update\n5. **Edge (B, E, 3)**: d[E] = ∞ → d[B] + 3 = 4 + 3 = 7 ✓ Update\n6. **Edge (C, B, 1)**: d[B] = 4, d[C] + 1 = 2 + 1 = 3 < 4 ✓ Update to 3\n7. **Edge (C, D, 4)**: d[D] = 6, d[C] + 4 = 2 + 4 = 6, no update (equal)\n8. **Edge (C, E, 5)**: d[E] = 7, d[C] + 5 = 2 + 5 = 7, no update (equal)\n9. **Edge (E, D, 1)**: d[D] = 6, d[E] + 1 = 7 + 1 = 8 > 6, no update\n\n**After Iteration 1:**"},"type":"text"},{"data":{"rows":[["A","0","-","-"],["B","3","C","Updated"],["C","2","A","Updated"],["D","6","B","Updated"],["E","7","B or C","Updated"]],"headers":["Vertex","Distance","Predecessor","Change"]},"type":"table"},{"data":{"content":"**Iteration 2: Further Refinement**\n\nWe repeat the relaxation process with updated distances:\n\n1. **Edge (B, D, 2)**: d[D] = 6, d[B] + 2 = 3 + 2 = 5 < 6 ✓ Update to 5\n2. **Edge (B, E, 3)**: d[E] = 7, d[B] + 3 = 3 + 3 = 6 < 7 ✓ Update to 6\n\n**After Iteration 2:**"},"type":"text"},{"data":{"rows":[["A","0","-","-"],["B","3","C","-"],["C","2","A","-"],["D","5","B","Updated"],["E","6","B","Updated"]],"headers":["Vertex","Distance","Predecessor","Change"]},"type":"table"},{"data":{"content":"**Iteration 3:**\n\nNo further improvements possible. Algorithm terminates.\n\n**Shortest Paths from A:**\n- A → C: cost 2 (direct)\n- A → C → B: cost 3\n- A → C → B → D: cost 5\n- A → C → B → E: cost 6"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Convergence Insight","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"complexity-analysis","title":"Complexity Analysis","content":[{"data":{"content":"Understanding Bellman-Ford's computational complexity is crucial for evaluating its suitability in network environments with varying scale constraints."},"type":"text"},{"data":{"rows":[["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"]],"caption":"Bellman-Ford Complexity Breakdown","headers":["Aspect","Complexity","Explanation"]},"type":"table"},{"data":{"left":[{"data":{"items":["**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"],"title":{"icon":"CheckCircle","text":"Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**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"],"title":{"icon":"XCircle","text":"Disadvantages","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"AlertCircle","title":"Scalability Consideration","content":"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.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"distributed-implementation","title":"Distributed Implementation for Networks","content":[{"data":{"content":"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.\n\n**The Distributed Bellman-Ford Approach:**\n\nEach router:\n1. Maintains a distance vector: estimated distances to all known destinations\n2. Periodically exchanges distance vectors with directly connected neighbors\n3. Updates its own distance vector based on received information\n4. Converges to the correct shortest paths through iterative refinement"},"type":"text"},{"data":{"fileName":"distributed_bellman_ford.py","languages":[{"code":"$7c","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"Info","title":"Asynchronous Execution","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"network-protocol-mapping","title":"From Algorithm to Protocol: RIP","content":[{"data":{"content":"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."},"type":"text"},{"data":{"rows":[["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"]],"caption":"Bellman-Ford to RIP Mapping","headers":["Bellman-Ford Concept","RIP Implementation","Practical Details"]},"type":"table"},{"data":{"content":"**RIP Message Format:**\n\nRIP uses a simple message structure for distance vector exchange:\n\n```\n+------------------------+\n| Command (1 byte) | 1 = Request, 2 = Response\n+------------------------+\n| Version (1 byte) | 1 = RIPv1, 2 = RIPv2\n+------------------------+\n| Reserved (2 bytes) |\n+------------------------+\n| Address Family (2) |\n+------------------------+\n| Route Tag (2) | (RIPv2 only)\n+------------------------+\n| IP Address (4 bytes) |\n+------------------------+\n| Subnet Mask (4) | (RIPv2 only)\n+------------------------+\n| Next Hop (4) | (RIPv2 only)\n+------------------------+\n| Metric (4 bytes) | Hop count (1-16)\n+------------------------+\n ... up to 25 entries ...\n```\n\n**Triggered Updates:**\n\nBeyond periodic 30-second broadcasts, RIP sends immediate updates when routing table changes occur. This mechanism accelerates convergence when topology changes happen."},"type":"text"},{"data":{"icon":"AlertCircle","title":"RIP Limitations from Bellman-Ford","content":"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.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"mathematical-proof","title":"Mathematical Foundation: Why It Works","content":[{"data":{"content":"$7d"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Negative Cycle Detection Proof","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary-transition","title":"Summary and What's Next","content":[{"data":{"content":"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:"},"type":"text"},{"data":{"type":"ordered","items":["**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"],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next: Routing Table Exchange**\n\nWith 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."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"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.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_e9b4f570ab44f1105de8e685dfadd017","title":"Routing Table Exchange","order":1,"content":null,"isLocked":true},{"id":"seed_eeca3311d90fae7edb1b40ba79a25e6a","title":"Count-to-Infinity Problem","order":2,"content":null,"isLocked":true},{"id":"seed_91a58d562119d59d679ecb49dfd27029","title":"Split Horizon","order":3,"content":null,"isLocked":true},{"id":"seed_32ada49c8dd2283fbaa161e7ab248bb8","title":"Poison Reverse","order":4,"content":null,"isLocked":true}]}} 73:{"json":[]}