COMPUTER NETWORKS - II

Bellman-Ford Algorithm or Ford-Fulkerson algorithm

Posted by AJ × 09:05

Principle: - If each neighbor of node A knows the shortest path to node Z, then node A can determine its shortest path to node Z by calculating the cost/distance to node Z through each of its neighbors and picking the minimum.

Bellman-Ford algorithm

* Consider computations for one destination d

* Initialization

* Each node table has 1 row for destination d

* Distance of node d to itself is zero: Dd=0

* Distance of other node j to d is infinite: Dj=μ, for j¹ d

* Next hop node nj = -1 to indicate not yet defined for j ¹ d

* Send Step

* Send new distance vector to immediate neighbors across local link

* Receive Step

* At node j, find the next hop that gives the minimum distance to d,

* Minj { Cij + Dj }

* Replace old (nj, Dj(d)) by new (nj*, Dj*(d)) if new next node or distance

* Go to send step

For the above figure Apply Bellman-ford algorithm to find both minimum cost from each node to the destination node 6 and the next node along the shortest path.

Each node I maintains an entry (n,Di), where n is the next node along the current shortest path and Di is the current minimum cost from node i to destination.

Initially all nodes, other than the destination node 6, are at infinite cost (distance) to node 6. Node 6 informs its neighbors it is distance 0 from itself.

Iteration 1:- Node 3 finds that it is connected to node 6 with cost of 1. Node 5 finds it is connected to node 6 at a cost of 2. nodes 3 and 5 update their entries and inform their neighbors.

Iteration 2:- Node1 finds it can reach node 6, via node 3 with cost 3. Node 2 finds it can reach node 6, via node 5 with cost 6. Node 4 finds it has paths via nodes 3and 5,with costs 3 and 7 respectively. Node 4 selects the path via node 3. Nodes 1, 2, and 4 update their entries and inform their neighbors.

Iteration 3:- Node 2 finds that it can reach node 6 via node 4 with distance 4. Node 2 changes its entry to (4,4) and informs its neighbors.

Iteration 4:- nodes 1,4, and 5 process the new entry from node 2 but do not find any new shortest paths. The algorithm has converged.