Question
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.
Answer
The general topology is considered.
- The distance table entries are computed using the distance-vector algorithm synchronous version.
- The nodes in the network has limited knowledge about their neighbors.
- They know only their neighbors costs.
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.
- Assume that d (the networks diameter) is the length of the longest path and without loops between any two nodes in the network.
- From the above analogy, after performing d-1 iterations, all nodes will have the knowledge about the shortest path cost of d to all other nodes.
- If the path length is greater than d hops, then the path contains loops. The removal of loops converges the algorithm result to at most d-1 iterations.
- 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.
Therefore, the result of the distance vector algorithm converges in at most d-1 iterations.