#1 Download computer science & engineering books free           #2 Display your sponsored posts here. Reach 10,000+ students. Contact: info[at]cpentalk.com for quote           #3 Take the Ultimate Trivia Quiz. See where you rank globally.
0 votes
in Computer Networks by (user.guest)

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

Welcome to CPEN Talk
Solution-oriented students of computer engineering on one platform to get you that

ONE SOLUTION

Chuck Norris doesn't use reflection, reflection asks politely for his help.
...