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

Nice read

http://web.mit.edu/6.02/www/currentsemester/handouts/L21_notes.txt

---

Can 0 be considered as an answer, if it were an option?

---

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.

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

I think a MST should work its way

---

@Abhineet Singh Shortcut for this question is, Take each edge and check whether is there any other better path(lest cost path) connecting nodes of this edge, if yes then after algorithm stabilizes, that better path will be updated in the routing tables so our edge will never be used.

We need to do this every edge and it doesn’t take long as graph is small.

Ex: Lets take edge between R1-R2 and its cost is 6, we have better path from R1 to R2 through R3 with a cost of 5, which is less than 6, so R1-R2 edge will never be used.

Even take R4-R8 edge and its cost is 8, but we have better path from R4-R8 through R5 with cost of 5 i.e less than 8 so R4-R8 edge will never be used.

You can check other edges we can’t get better paths if we remove any of them.

 

 

---

jaswanth431 on top of that the edges that r in the MST of the graph will always be used by the two hosts connected by the least weighted edge in that MST hence we can start by finding MST and then apply ur method for the rest of the edges

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

The naive method for solving distance vector problems seem to be time consuming . is there any shortcut ?

---

I think answer obtained using a bellman ford algorithm is sufficient for this.

---

whichever algo you take to solve minimal path/distance we indeed end up in the shortest path, so try to use your intution to solve this kind of problems, because time is most important factor in GATE,

for 54) in the link between R2 - R1, we can have a route between two nodes following R1-R3-R2 , so we neglect that link, similarly R4-R6 link is ignored because of R4-R5-R6, which is minimal.

---

why do we need to add R3-R5 link ?

isn't finding a minimal spanning tree solve this problem ?

step1: add R4-(1)-R5
step2: add R2-(2)-R3
step3: add R1-(3)-R3
step4: add R6-(4)-R5
step5: add R2-(7)-R4
step6 : we wont add R3-R5 as it will form a loop . Similarly we wont add any other edges because it forms loop.

There are 3 links unused in the Minimal spanning tree hence the soution.

What is wrong with this logic ?

---

Either we have to use Dijkstra at every router or we can use  All Pairs Shortest Path algorithm on graph (like Floyd Warshall Algorithm) for solving the problem.

---

@pc we have the minium spanning tree is formed at each respective node and by merging all of them we have to check of if an edge is not used in either of them, thus never used for carrying any data,

---

MST does not always minimizes the shortest path between any two nodes. Thats why its wrong to solve using MST.

---

Pick the links in decreasing order of their weights. If a smaller alternative path is available for that link then that link will never be used.

For example: pick R4- R6 ----> 8 but a smaller path is available from R4 to R6 ---> R4-R5-R6---> 5. so link R4R6 will never be used. Same in case of the link with weight 6.

---

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.