in Computer Networks retagged by
1,154 views
1 vote
1 vote

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$
in Computer Networks retagged by
1.2k views

3 Comments

@Ruturaj Mohanty What is M?

 

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

1 Answer

0 votes
0 votes
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?
edited by

4 Comments

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

@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?

0
0
Answer:

Related questions