The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+32 votes
4.3k views

Consider a network with $6$ routers $R1$ to $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?

  1. $4$
  2. $3$
  3. $2$
  4. $1$
asked in Computer Networks by Veteran (106k points)
edited by | 4.3k views

4 Answers

+32 votes
Best answer

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$

answered by Boss (22.4k points)
edited by
+23 votes
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.
answered by Junior (551 points)
edited by
0
The naive method for solving distance vector problems seem to be time consuming . is there any shortcut ?
0
I think answer obtained using a bellman ford algorithm is sufficient for this.
+2
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.
+1
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 ?
+15

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.

+1
@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,
+6
MST does not always minimizes the shortest path between any two nodes. Thats why its wrong to solve using MST.
+2
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.
+13 votes
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.
answered by Loyal (9.1k points)
+5 votes
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.
answered by (109 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,613 questions
48,609 answers
155,802 comments
63,796 users