• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Computer Networks

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram. (Network topology: R1 connects to R2 (weight 2), R1 connects to R3 (weight 7), R2 connects to R4 (weight 3), R3 connects to R4 (weight 5), R3 connects to R5 (weight 1), R4 connects to R5 (weight 4), R4 connects to R6 (weight 3), R5 connects to R6 (weight 1)) 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 are stabilized, how many links will never be used for carrying any data? A. 4 B. 3 C. 2 D. 1

GATE 2010 · Computer Networks · Distance Vector Routing · medium

Answer: D. 1

  1. Compute Shortest Paths from Each Router (Dijkstra): Shortest distances: From R1: R1=0, R2=2, R3=7, R4=5, R5=8, R6=8 Paths: R1->R2(2), R1->R2->R4(5), R1->R3(7), R1->R2->R4->R5(9)? or R1->R3->R5(8), R1->R2->R4->R6(8) or R1->R3->R5->R6(9)? Let me recompute carefully: R1: d=0 R2: d=2 via R1-R2 R3: d=7 via R1-R3 (direct), or R1-R2-R4-R3=2+3+5=10 (longer), or R1-R2-R4-R5-R3=2+3+4+1=10 (longer). So d(R1,R3)=7. R4: d=5 via R1-R2-R4 R5: d=8 via R1-R3-R5 (7+1=8), or R1-R2-R4-R5(2+3+4=9), or R1-R2-R4-R3-R5(2+3+5+1=11). Best: 8 via R1-R3-R5. R6: d=9 via R1-R3-R5-R6(7+1+1=9), or R1-R2-R4-R6(2+3+3=8). Best: 8 via R1-R2-R4-R6.
  2. Check Each Link for Usage in ANY Shortest Path: Links and usage: - R1-R2 (2): Used for R1->R2, R1->R4, R1->R6. USED. - R1-R3 (7): Used for R1->R3 (d=7), R1->R5 (via R1-R3-R5, d=8). USED. - R2-R4 (3): Used for R1->R4, R1->R6, R2->R4, R2->R6. USED. - R3-R4 (5): Check: d(R3,R4)=5 direct vs via R3-R5-R4=1+4=5 (tie!). So R3-R4 may or may not be on a shortest path. Is it on any pair? R1->R4 via R1-R3-R4 = 7+5=12 (not shortest, d=5). R2->R3 via R2-R4-R3=3+5=8 vs R2-R1-R3=2+7=9. So R2->R3 shortest is 8 via R2-R4-R3. USED. - R3-R5 (1): Used for R1->R5, R3->R5, etc. USED. - R4-R5 (4): d(R4,R5) direct=4. Via R4-R3-R5=5+1=6 (longer). Via R4-R6-R5: d(R4,R6)=3, d(R6,R5)=1, so R4-R6-R5=3+1=4 (TIE with direct!). So for R4-R5 pair, direct and via R6 are equal. Is R4-R5 used for any other pair? R2->R5: d=2+3+4=9 via R2-R4-R5, vs R2-R1-R3-R5=2+7+1=10, vs R2-R4-R6-R5=2+3+3+1=9 (tie). R1->R5 via R1-R3-R5=8, vs R1-R2-R4-R5=2+3+4=9 (longer). So R4-R5 direct is NOT on R1->R5 shortest. For R4<->R5: both direct and via R6 cost 4. If via-R6 is preferred, R4-R5 direct is NEVER USED. - R4-R6 (3): Used for R1->R6 (R1-R2-R4-R6=8), R4->R6. USED. - R5-R6 (1): Used for R5->R6, R3->R6 (R3-R5-R6=2), R1->R6 via R1-R3-R5-R6=9 (not shortest since R1-R2-R4-R6=8 is better). R4->R6 via R4-R5-R6=4+1=5 vs direct R4-R6=3 (direct is shorter). So R5-R6 is used for R5->R6, R3->R5-R6, etc. USED. Conclusion: R4-R5 (weight 4) is potentially never used, since d(R4,R5)=4 can be achieved via R4-R6-R5=3+1=4 as well, and for all other pairs there is an equally short or shorter path not using R4-R5.