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.
The general topology is considered.
The maximum number of iterations required for the algorithm convergence can be calculated as follows:
In each iteration, the nodes in the network will exchange information of distance tables with their neighbors.
After the first iteration, all the neighboring nodes to the current node will be aware of shortest path cost to current node. For example, let X and Y represent two nodes and they are neighbors. Then after first iteration, all the neighbors of Y will be aware of shortest path cost to node X.
Therefore, the result of the distance vector algorithm converges in at most d-1 iterations.