4k 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$
edited | 4k views

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$

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

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

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 ?
+14

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.
+1
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.
Ans __2

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

OPTION C

YOU NEED NOT DRAW ENTIRE ROUTING TABLE AT ALL.