5.2-2 Bellman Ford Distance Vector Routing (updated)

Introduction to the Distributed Bellman-Ford Algorithm

Overview of the Algorithm

• The distributed Bellman-Ford algorithm is introduced as a simple yet effective method for computing least cost paths, akin to centralized algorithms.

• It emphasizes local and intuitive calculations that can yield results comparable to more complex methods.

Understanding the Bellman-Ford Equation

• The distance vector algorithm relies on the Bellman-Ford equation, which may appear complex but is fundamentally intuitive.

• This equation states that the minimum cost path from source x to destination y must pass through one of x 's neighbors, denoted as v .

Example Illustration

• An example involving nodes u (source) and z (destination) illustrates how neighbors communicate their known costs to reach z . Neighbor costs are:

• Neighbor v : Cost = 5

• Neighbor x : Cost = 3

• Neighbor w : Cost = 3

• The minimum cost path from node u to node z is calculated using these neighbor costs, resulting in a total cost of 4 via neighbor x .

Distance Vector Updates

Computing Distance Vectors

• Each node sends its distance vector estimate periodically to its neighbors; upon receiving an update, it recalculates its own distance vector using the Bellman-Ford equation.

• Node updates involve calculating the minimum cost across all neighbors for each destination in the network.

Steps in the Distributed Algorithm

1. Wait: Nodes wait for either a distance vector from a neighbor or a local link cost change.

2. Calculate: Upon receiving an event, nodes perform calculations based on received vectors.

3. Notify: If changes occur in their own distance vectors, they notify their neighbors with updated information.

Properties and Efficiency of the Distance Vector Algorithm

Key Characteristics

• The algorithm operates iteratively and asynchronously; nodes do not need synchronized updates and can operate at different speeds while still converging effectively.

• It is self-stopping; if no changes occur in a node's distance vector, no further notifications are sent or actions taken by that node.

Conclusion on Simplicity

• The simplicity of this algorithm lies in its three fundamental steps—waiting for updates, performing calculations, and notifying neighbors—making it accessible yet powerful for routing purposes.

Visualizing Bellman-Ford Computation

Network Structure Example

• A nine-node grid network serves as an example structure where nodes have varying distances between them; notably, some links have higher costs than others (e.g., link from A to B has a cost of 8).

Understanding the Distributed Bellman-Ford Algorithm

Initialization of Distance Vectors

• At time t = 0 , node A initializes its distance vector (DV) with costs: destination B has a cost of 8, and destination D has a cost of 1. These are initial estimates for least-cost paths.

• Nodes send their initialized distance vectors to immediate neighbors at t = 1 . Each node computes its local DV based on received information.

• The iterative process allows nodes to operate at different speeds while still converging towards accurate distance vectors.

Local Computation in the Algorithm

• The core computation involves running the Bellman-Ford equation using individual distance vectors from neighboring nodes to compute new local DVs.

• By t = 1 , node B receives initial DVs from neighbors A, C, and E, which it uses to recalculate its own distances.

Recalculating Distances

• Node B recalculates its distances after receiving updates. For example, it assesses the minimum cost to reach A as still being 8 since no cheaper path is available.

• For destination D, B's previous infinite cost is updated by evaluating three potential paths: through A, C, or E. The new minimum cost becomes 2.

Updates and New Distance Vectors

• After recalculating, B's new distance vector shows lower costs for destinations D, F, and H compared to previous entries.

• Node C receives B's updated DV at t = 1 . It recognizes that if B can reach E at a cost of 1 and it can reach B at a cost of 1, then C can reach E via B for a total cost of 2.

Information Propagation in the Network

• As nodes exchange information over time (e.g., from t = 0 to t = 2 ), they gradually learn about each other's states. Initially isolated information spreads through neighbor interactions.

• By t = 2 , other nodes begin receiving updates about node C’s state based on earlier exchanges with node B. This diffusion illustrates how network-wide knowledge builds over iterations.

Understanding Information Propagation in Networks

The Concept of Information Propagation Speed

• The analogy of starlight is used to explain information propagation speed in networks, where the information received reflects a state from the past.

• At time t=3, the state at node C influences computations up to three hops away (nodes D, F, and H).

• By time t=4, this influence extends to four hops away (nodes G and I), illustrating how long it takes for information to propagate across the network.

Convergence of Distance Vector Algorithm

• If there are no changes in a local distance vector, updates will not be sent out; convergence occurs when no local changes are computed.

• The algorithm can accommodate link cost changes by recomputing local distance vectors based on new costs and sending updates if changes occur.

Example of Link Cost Changes

• An example illustrates node Y detecting a link cost change from 4 to 1 with its neighbor X at time t=0.

• Node Z receives an updated distance vector from Y and recalculates its own path cost to X as 2. If Z's distance vector changes, it sends updates back out.

• After two iterations, Y’s least costs remain unchanged; thus, no further updates are sent out.

Impact of Increasing Link Costs

• When link costs increase significantly (e.g., from X to Y going up to 60), nodes must adapt their routing paths accordingly.

• This situation leads to cascading updates among nodes as they adjust their perceived costs through each other—illustrating the "count-to-infinity" problem.

Comparison Between Link State and Distance Vector Algorithms

• Message complexity for link state dissemination is O(n²), while distance vector may take O(diameter of network).

• Speed of convergence varies: link state has potential oscillations while distance vector can experience routing loops during convergence.

Failure Scenarios in Routing Algorithms

• In link state algorithms, incorrect advertisements lead to localized failures since each router computes its own tables independently.

• Conversely, in distance vector algorithms, incorrect path costs can propagate errors throughout the network—known as black holing—leading to widespread issues.

Understanding Routing Algorithms and Their Impact on Internet Traffic

The Consequences of Misconfigured Routing

• A significant issue arises when a major destination network, such as AT&T, experiences a loss of traffic due to routing misconfigurations. This can lead to substantial disruptions in service.

• Smaller ISPs may inadvertently blackhole traffic intended for larger networks, causing confusion for those networks that no longer receive expected data flows.

• The situation highlights the critical importance of proper router configuration within ISPs to ensure seamless internet connectivity across various networks.

Overview of Routing Algorithms

• The discussion wraps up with an overview of key routing algorithms: Dijkstra's centralized link state algorithm and the distributed Bellman-Ford algorithm.

• These algorithms serve as foundational concepts for understanding how data is routed across the internet effectively.

Introduction to Internet Routing Protocols

• Following the discussion on algorithms, the next sections will delve into their practical applications in internet routing protocols, specifically focusing on OSPF (Open Shortest Path First).

• Additionally, BGP (Border Gateway Protocol) will be explored as another crucial protocol in managing how packets are routed between different autonomous systems on the internet.