Number of messages in DVRP

Question

1. In distance vector, suppose we define a round as an interval during which each node exchanges with its neighbor its routing table information. Assume N number of nodes and E number of edges in the graph. How many messages are exchanged in a round as a function of N and E? Express it as a function of N and  E.
2. Consider a network topology with N nodes, E edges and a diameter of d. Diameter is the hop count of the longest path between any two nodes in the network without loops. Assume a synchronous version of distance vector that works in rounds. In each round, each node exchanges its distance vector with its neighbors and receives their distance vectors. Initially, each node knows only the cost to its immediate neighbors. What is the maximum number of rounds needed for the distance vector algorithm to converge? Express it as a function of N, E and d. Also assume that the network topology does not change during the rounds.

Answer 1

Each edge  of graph has a message going in each direction for every round. So the number of messages per round = number of edges X number of messages per edge = 2E

Since the longest hops between two nodes  is d, the number of rounds needed = d-2.

Since 2 routers the destination router and the router connected with it already know their shortest paths.Hence the first exchange of information coveys the distance of destination router(d) to (d-2)th router. So for the information to reach 1st router, it takes d-2 exchanges.

Comments

i think it will be d-1 rounds