GATE Overflow | Mock GATE | Test 1 | Question: 31

Question

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?

• A. $\text{Min } (N+M, N*M)$
• B. $\text{Max } (N+M, N*M)$
• C. $N*M$
• D. $N+M$

Comments

@Ruturaj Mohanty What is M?

 

---

M is the no of edges. Just typo. Thanks for pointing it out. updated.

---

Welcome...I got -ve because of that :-)

Answer 1

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?

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

---

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?

Answer 2

Link State Routing uses Flooding.

What Flooding means is forwarding a packet that you receive from one interface to all other interface except the one from which the packet was received.

So assuming a node has N edges and it will receive one packet from each edge once, and will forward it to remaining N-1 edges, making a total of N*(N-1) exchanges.

This is the count for only one node, but this happens at all other nodes also which adds a factor of M to the above exchanges, making the total count = M*N*(N-1).

So the total count always has the factor of M*N or in other words it can be expressed in terms of M*N.