DistancevectorapproachThe origin of distance vector protocolsis traced backto theTBellman-Fordalgorithm.Let d,:the cost of the link from node i to nodej, which is oo if the link does notexist. D,(h):the cost of the minimum-cost route from node ito nodejon thenumberof hhops.Initial conditions:D,(h) = O for all i and h, and D,(O) = oo for i± jIterativesteps:D,;(h+1) = min;[dik + Dk(h) for all i j.until D;(h+1) = D,(h) for all i and j
Distance vector approach 6 The origin of distance vector protocols is traced back to the Bellman-Ford algorithm. Let dij: the cost of the link from node i to node j, which is if the link does not exist. Dij(h): the cost of the minimum-cost route from node i to node j on the number of h hops. Initial conditions: Dii(h) = 0 for all i and h, and Dij(0) = for i j. Iterative steps: Dij(h+1) = mink [dik + Dkj(h)] for all i j. until Dij(h+1) = Dij(h) for all i and j
Bellman-Ford algorithm Conditions: The link costs are additive.If all cycles not containing the destination havenonnegative length.The Bellman-Ford algorithm terminates after a finite number of iterations (at mostN, the number of nodes),givesminimum-costpaths from all nodesto other nodesand its computational complexity in the worse case is O(N3)
Bellman-Ford algorithm 7 Conditions: The link costs are additive. If all cycles not containing the destination have nonnegative length. The Bellman-Ford algorithm terminates after a finite number of iterations (at most N, the number of nodes), gives minimum-cost paths from all nodes to other nodes, and its computational complexity in the worse case is O(N3 )
An exampleBBAEDEBBAEED
An example 8 A B E C D A B E C D A B E C D A B E C D
An exampleBED
An example 9 A B E C D
Distributed,asynchronous B-Falgorithm10 Node i executes the B-F algorithm asynchronously:D,(t) = O, for all i and t ≥ 0.D;(t) = mink[dik + Dik;(t) fori±i, where D;(t) is the estimate of the cost to node j available tonode i at time t. Di;(t) is node k's estimate of the cost to node i availableto node iat time t. Node i distributes its distance vector Di(t) for all i toits neighbors
Distributed, asynchronous B-F algorithm 10 Node i executes the B-F algorithm asynchronously: Dii(t) = 0, for all i and t 0. Dij(t) = mink [dik + Di kj(t)] for i j, where Dij(t) is the estimate of the cost to node j available to node i at time t. Di kj(t) is node k’s estimate of the cost to node j available to node i at time t. Node i distributes its distance vector Dij(t) for all j to its neighbors