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

0 votes
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.

## 1 Answer

0 votes
by (user.guest)
selected by (user.guest)

Best answer

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.

If you found this answer helpful, please upvote and share with other students in your network.

## Related questions

0 votes
1 answer 500 views
0 votes
1 answer 1.7k views
0 votes
0 answers 686 views
0 votes
1 answer 897 views
0 votes
1 answer 849 views
+1 vote
1 answer 4.7k views
+1 vote
1 answer 5.3k views
+1 vote
1 answer 11.6k views
0 votes
1 answer 758 views
0 votes
0 answers 325 views
+3 votes
1 answer 733 views
+1 vote
1 answer 402 views
0 votes
0 answers 230 views
0 votes
1 answer 5.1k views
0 votes
1 answer 1.9k views
0 votes
1 answer 1.3k views
0 votes
1 answer 2.0k views
+1 vote
1 answer 759 views
+1 vote
1 answer 2.4k views
0 votes
0 answers 226 views
0 votes
0 answers 191 views
+2 votes
1 answer 676 views
–1 vote
1 answer 770 views
+2 votes
1 answer 1.8k views
0 votes
1 answer 3.5k views
0 votes
0 answers 121 views
+1 vote
1 answer 114 views
+2 votes
1 answer 2.0k views
–1 vote
1 answer 901 views
+1 vote
1 answer 964 views
0 votes
0 answers 183 views
0 votes
1 answer 474 views
0 votes
1 answer 1.8k views
0 votes
1 answer 524 views
+1 vote
1 answer 954 views
+1 vote
1 answer 1.6k views
–1 vote
1 answer 743 views
–1 vote
1 answer 287 views
–1 vote
1 answer 590 views
+1 vote
1 answer 1.6k views
+2 votes
1 answer 310 views
+1 vote
1 answer 6.1k views
0 votes
0 answers 297 views
0 votes
0 answers 198 views
0 votes
0 answers 171 views
0 votes
0 answers 186 views
0 votes
1 answer 334 views
+4 votes
1 answer 4.7k views
0 votes
0 answers 106 views
+4 votes
2 answers 7.8k views