1,154 views

Let $N$ be the number of nodes and $M$ be the number of edges. For Link state routing how many message exchanges (roughly, explained as a function of the above parameters) need to be exchanged to build the topology at each and every node in the network?

1. $\text{Min } (N+M, N*M)$
2. $\text{Max } (N+M, N*M)$
3. $N*M$
4. $N+M$

What is M?

M is the no of edges. Just typo. Thanks for pointing it out. updated.
Welcome...I got -ve because of that :-)

Is it like that each node builds a link state packet for each link and floods this to all nodes in the network.?

Since, for M edges, M link state packets generated and flooded among N nodes, so total $M \times N$ message exchanges.

Is it like that?

You have to explain it as parameters of N and M. Not just N. If M = N-1 then yes it might be N*N-1...
Is this because ,the number of edges matters ,there can be more than one path where a packet reaches the node(since it is flooding) ,so we have it count it all, as N*M

@Ruturaj Mohanty

If M = N-1 then yes it might be N*N-1...

and if M>(N-1) say M=N then msg exchanges = N*N. What for these extra N message exchanges [N*N-N(N-1)=N] take place?