GATE CSE 2010 | Question: 54

Question

Consider a network with $6$ routers $\textbf{R1}$ to $\textbf{R6}$ connected with links having weights as shown in the following diagram.

All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its routing table initialized to contain an entry for each neighbor with the weight of the respective connecting link. After all the routing tables stabilize, how many links in the network will never be used for carrying any data?

• A. $4$
• B. $3$
• C. $2$
• D. $1$

Comments

Next Linked QS

https://gateoverflow.in/43326/gate-cse-2010-question-55 

---

Easily we can do by finding max no of hops between any two nodes and ya surely this hop count help us to find the min distance can be found out in how many hops max to max.After that we can find which links are used and which are unused.

---

R3---R5  link is needed bcz from R1 to R5 shortest dist = 3 + 9 = 12    not via R1--R3--R2--R4--R5 = 3+2+7+1 = 13

Answer 1

Answer (C)

Following will be distance vectors of all nodes.

Shortest Distances from $R_1$ to $R_2, R_3, R_4, R_5\ and\ R_6$
$R_1 (5, 3, 12, 12, 16)$
Links used$:R_1-R_3, R_3-R_2, R_2-R_4, R_3-R_5, R_5-R_6$

Shortest Distances from $R_2$ to $R_3, R_4, R_5\ and\ R_6$
$R_2 (2, 7, 8, 12)$
Links used$: R_2-R_3, R_2-R_4, R_4-R_5, R_5-R_6$

Shortest Distances from $R_3$ to $R_4, R_5$ and $R_6$
$R_3(9, 9, 13)$
Links used$:R_3-R_2, R_2-R_4, R_3-R_5, R_5-R_6$

Shortest Distances from $R_4$ to $R_5$ and $R_6$
$R_4 (1, 5)$
Links used$:R_4-R_5, R_5-R_6$

Shortest Distance from $R_5 to R_6$
$R_5$ (4)
Links Used: $R_5-R_6$

If we mark, all the used links one by one, we can see that following links are never used.
$R_1-R_2$
$R_4-R_6$

Comments

The general way here would be to keep making distance vector routing until it converges, which is a very long and time-consuming process.

---

@Sachin Mittal 1sir in this question why does cycle property not applicable, if so then there are 3 cycles and therefor the links R1-R2, R3-R5 and R4-R6 must never be visited?

---

MST will not work. use all pair shortest path.

Answer 2

C is the right answer.. The links $R_1-R_2$  and $R_4-R_6$ will never be used for
data transfer because there are shorter paths available in any case.

Comments

because to reach R1  to R5 we have two options

1.R1-R3-R2-R4-R5 which will cost 13

2.R1-R3-R5 with 12 ....so R3-R5 will definitely be in use

---

@Sachin Mittal 1 Sir can floyd warshall be used even though it is not distributed?

---

It is wrong because the shortest distance between R1 and R5 is 12 using (R1-3-R3) and (R3-9-R5)

When you construct a MST the min distance you will get from R1 to R5 is 13 via (R1-3-R3), (R3-2-R2), (R2-7-R4) and  (R4-1-R5)

Answer 3

Ans __2

Use your intuition and you will gain answer 2 link

These r respectively R1---R2 and R4------R6.

Find shortest path from each node to other node and mark each edge visited.Then u will automatically find out unused edge.

Answer 4

INORDER TO REACH R1 TO R2 COST(6)WE HAVE A BETTER PATH R1--> R3-->R2 COST(5), SO WE CAN REMOVE THIS LINK.

Similarly, WE HAVE A BETTER PATH FOR R4 TO R6 COST(8) VIA R5 COST(4).

SO ANSWER IS 2.

OPTION C

YOU NEED NOT DRAW ENTIRE ROUTING TABLE AT ALL.

Answer 5

This kind of question should always be dealt with SMARTNESS

We will observe that the following image is the best option for going to every other router in shortest possible cost.

Comments

you solved my biggest doubt why r3-r5 could not be removed ?

thanks!!!!

Answer 6

ans is C