Bellman Ford Distance Vector Algorithm

Tags: #◇CSNETWK #◇Computer Science #◇Computer Networks #◇Networking Protocols #◇Graph Theory Basics

---

◇Overview

Distance Vector routing is decentralized. Routers do not know the full topology. They only know:

◇Key Concepts

Target Router Nodes

◇Details / Theory

◇1. Concept Overview: Distance Vector (DV)

Definition

Distance Vector routing is decentralized. Routers do not know the full topology. They only know:

1. Cost to direct neighbors.
2. Distance vectors received from those neighbors.

The "Tell Your Neighbors" Rule

Each router periodically sends its own best-path estimates (vector) to its neighbors. If a neighbor finds a cheaper path using that information, it updates its own vector.

Bellman-Ford Equation:

$D_x(y) = \min_v \{ c(x,v) + D_v(y) \}$
$D_x(y)$: Cost from $x$ to $y$. $c(x,v)$: Cost to neighbor $v$. $D_v(y)$: Neighbor $v$'s current known cost to $y$.

◇2. The Network Topology

Scenario Data
!◇Pasted image 20251121093513.png
Target Router: V (Question 1) and X (Question 2) Nodes: u, v, w, x, y

◇3. Problem Analysis

Question 1

When the algorithm converges, what are the distance vectors from router 'V' to all routers? (u,v,w,x,y)

Analytical Breakdown:

We need to find the shortest path from V to everyone else by looking at the diagram globally (since "convergence" implies everyone knows the best paths).

1. V to V: 0 (Self).
2. V to U: Direct link is 6. No other path is faster. $\rightarrow$ 6
3. V to W: Direct link is 5. Path V-X-W is $5+2=7$ (worse). $\rightarrow$ 5
4. V to X: Direct link is 5. Path V-W-X is $5+2=7$ (worse). $\rightarrow$ 5
5. V to Y:
   Path V-X-Y: Cost is $5 (\text{to } X) + 1 (\text{X to Y}) = 6$.
   Path V-W-X-Y: $5 + 2 + 1 = 8$ (worse).
   Result: $\rightarrow$ 6

Correct Answer: (6, 0, 5, 5, 6)

Question 2

What are the initial distance vectors for router 'X'? (u,v,w,x,y)

Analytical Breakdown:

"Initial" means the router only knows about its direct physical neighbors. It does not yet know about nodes that are two or more hops away.

1. X to U: Not a neighbor. Unknown. $\rightarrow$ $\infty$ (x)
2. X to V: Direct neighbor. Cost 5.
3. X to W: Direct neighbor. Cost 2.
4. X to X: Self. Cost 0.
5. X to Y: Direct neighbor. Cost 1.

Correct Answer: (x, 5, 2, 0, 1)

Question 3

...what is the name of the problem that can occur when link costs increase?

Analytical Breakdown:

In DV routing, "bad news travels slow."
If a link breaks or cost increases significantly, routers may form a routing loop where they bounce traffic back and forth, incrementing their cost counter endlessly because they rely on each other's outdated information. Example: A thinks best path is B; B thinks best path is A. They keep adding +1 to the cost until it hits a predefined "Infinity".

Correct Answer: Count to Infinity problem

◇Summary of Logic (Cheat Sheet)

Key Phrase:

"Good news travels fast" (Cost decrease propagates quickly).

"Bad news travels slow" (Cost increase causes Count-to-Infinity).

◇Common Pitfalls

Confusing initial distance vectors (only direct neighbors known; rest $\infty$) with converged vectors (global shortest paths). Forgetting the Count-to-Infinity problem when link costs increase — "bad news travels slow." Applying the Bellman-Ford equation incorrectly: $D_x(y) = \min_v\{c(x,v) + D_v(y)\}$ minimizes over neighbors $v$, not all nodes.

◇Summary

TL;DR — Bellman-Ford is a decentralized distance-vector algorithm where each node shares its distance vector with neighbors and updates using $D_x(y) = \min_v\{c(x,v) + D_v(y)\}$. It converges to shortest paths but suffers from the Count-to-Infinity problem on cost increases.

◇Links

Related: - ◇Pasted image 20251121093513.png Source / Reference:

◇References & Navigation

• Previous Topic: ◇Dijkstra's Algorithm (Advanced)
• Next Topic: ◇Link Layer
• Related Notes: ◇Internetworking