# Consider a general topology (that is, not the specific network shown above) and a synchronous version of the distance-vector algorithm.

791 views

Consider a general topology (that is, not the specific network shown above) and a synchronous version of the distance-vector algorithm. Suppose that at each iteration, a node exchanges its distance vectors with its neighbors and receives their distance vectors. Assuming that the algorithm begins with each node knowing only the costs to its immediate neighbors, what is the maximum number of iterations required before the distributed algorithm converges? Justify your answer.

by (user.guest)
selected by (user.guest)

Consider a general topology.

• The synchronous version of the distance – vector algorithm is used to compute the entries in the distance table.

• The nodes in the network are only aware of the costs of their immediate neighbors.

The following procedure gives the maximum number of iterations required for the algorithm converges:

• The node exchanges the distance tables with its neighbors in each iteration.

• For example, let node A represents the source node, and node B is a neighbor of node A, then all the neighbors of node B (which are one or two hops from node A) are aware of the shortest cost path to node A after the first iteration.

• Let d (be the diameter of the network) represents the length of the longest path without loops between any two nodes in the network.

• Using the above example, after  d-1 iterations, all nodes will know the shortest path cost of d or fewer hops to all other nodes.

• Any path with greater than d hops consists of loops which leads the result of the algorithm to converge in at most d-1 iterations.

• When the Distance Vector algorithm runs as a result of a change in the cost of a link, then there is no priori bound on the number of iterations required until convergence and unless a bound on link costs are specified.

Therefore, the distance vector algorithm converges in at most d -1 iterations.

+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
–1 vote
+1 vote
–1 vote
+1 vote
+1 vote
+1 vote
–1 vote
–1 vote
–1 vote
+1 vote
+1 vote