The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+34 votes

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?

- $4$
- $3$
- $2$
- $1$

+35 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$

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

data transfer because there are shorter paths available in any case.

0

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

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

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 ?

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 ?

+18

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,

+7

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.

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.

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

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.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,931 questions

52,334 answers

182,382 comments

67,816 users