Lecture on Distributed Bellman-Ford Algorithm

Introduction

• Covered Dijkstra's link-state routing algorithm.
• Now exploring the Distributed Bellman-Ford Algorithm.
• Demonstrates simple, local, distributed calculations for computing least-cost paths.

Bellman-Ford Equation

• Basis for the Distance Vector Algorithm.
• Concept: Minimum cost path from source x to destination y involves a neighbor v as the first hop.
• Calculation: Cost from x to v plus the cost from v to y. Take minimum over all neighbors v.

Example

• Network: Source node U with neighbors V, X, and W; destination node Z.
• Neighbor Costs:
  • V to Z: Cost 5
  • X to Z: Cost 3
  • W to Z: Cost 3
• Bellman-Ford calculates minimum cost from U to Z by evaluating paths through its neighbors.

Distance Vector Algorithm

• Nodes send distance vector estimates to neighbors.
• Node x updates its distance vector upon receiving a new vector from neighbors using the Bellman-Ford equation.
• Algorithm Steps:
  1. Wait for a distance vector from a neighbor or a local link cost change.
  2. Run Bellman-Ford calculations for all destinations.
  3. If distance vector changes, send new vector to neighbors.

Properties of the Algorithm

• Iterative and Asynchronous: Nodes exchange vectors independently.
• Distributed and Self-Stopping: Nodes notify neighbors only when changes occur.

Practical Example

• Nine-node Grid Network: Initial distance vectors sent to neighbors.
• Iterations:
  • Nodes exchange vectors, recalculating local distance vectors within time steps.
  • Convergence occurs without strict synchronization between nodes.

Local Computations

• Nodes recompute local distance vectors using the Bellman-Ford equation upon receiving updates.
• Example provided with node B recalculating paths based on received data.

Information Propagation

• Diffusion Concept: Information about a node's state propagates through the network over time.
• Speed of propagation akin to starlight seen across light-years.

Handling Link Cost Changes

• Distance vector algorithm adapts to changes by recomputing vectors.
• Example of link cost drop from 4 to 1 demonstrating quick convergence.
• Count to Infinity Problem: Pathological increase in cost propagations when link costs rise.

Comparison with Link State Algorithm

• Message Complexity: Link state has higher complexity than distance vector.
• Speed of Convergence: Distance vector can lead to routing loops and varying convergence times compared to link state.
• Failure Handling:
  • Link state: Errors localized, each router calculates its routing.
  • Distance vector: Errors propagate, leading to black-holing issues.

Conclusion

• Reviewed the distributed Bellman-Ford algorithm, its properties, and applications.
• Upcoming sections will cover OSPF and BGP protocols based on these routing principles.