Skip to content
GATEiit

GATE CSE 2021 Set 2 Q55: Distance vector update at R from neighbours X, Y, Z

Question

Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is as shown below.

The objective is to find the shortest-cost path from the router RR to routers PP and QQ. Assume that RR does not initially know the shortest routes to PP and QQ. Assume that RR has three neighbouring routers denoted as XX, YY, and ZZ. During one iteration, RR measures its distance to its neighbours XX, YY, and ZZ as 3, 2, and 5, respectively. Router RR gets routing vectors from its neighbours that indicate that the distance to router PP from routers XX, YY, and ZZ are 7, 6, and 5, respectively. The routing vector also indicates that the distance to router QQ from routers XX, YY, and ZZ are 4, 6, and 8, respectively. Which of the following statement(s) is/are correct with respect to the new routing table of RR, after updation during this iteration?

Router R connected to three neighbours X, Y and Z; dotted continuations below them lead to router Q (below X) and router P (below Z)
Tap the figure to enlarge

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: B, C (official GATE 2021 final answer key)

Concept used: Bellman–Ford update: DR(v)=min⁡n{c(R,n)+Dn(v)}D_R(v) = \min_n \{c(R, n) + D_n(v)\}, and the next hop is the minimising neighbour.

First step: For P compute 3+73+7, 2+62+6, 5+55+5; for Q compute 3+43+4, 2+62+6, 5+85+8.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key