GATE CS 2021 Set 2 Q.55 (CS Q.45): Routing Algorithms (Distance Vector, Link State) and BGP/OSPF

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

Partial network topology: router R at the top is connected to its three neighbours X, Y and Z. Each of X, Y and Z has further links that continue off into dots (unknown parts of the network). Routers Q and P at the bottom each have a link that continues upward into dots. — Network topology for distance vector routing

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

The distance from $R$ to $P$ will be stored as 10.

The distance from $R$ to $Q$ will be stored as 7.

The next hop router for a packet from $R$ to $P$ is $Y$ .

The next hop router for a packet from $R$ to $Q$ is $Z$ .

Official answer and solution

Official answer: B and C
From: Official GATE 2021 answer key

Solution

Apply the Bellman-Ford distance vector update equation $D_R(d) = \min_{v} \{ c(R, v) + D_v(d) \}$ for destinations $P$ and $Q$ .

Router $R$ has direct links to neighbors $X, Y, Z$ with link costs:

c(R, X) = 3, \quad c(R, Y) = 2, \quad c(R, Z) = 5

Calculate the updated distance to destination $P$ :

Via neighbor $X$ : $c(R, X) + D_X(P) = 3 + 7 = 10$
Via neighbor $Y$ : $c(R, Y) + D_Y(P) = 2 + 6 = 8$
Via neighbor $Z$ : $c(R, Z) + D_Z(P) = 5 + 5 = 10$
Taking the minimum:

D_R(P) = \min(10, 8, 10) = 8 \quad \text{with next hop } Y

Thus, the distance to $P$ is stored as 8 (not 10), and the next hop router is $Y$ . Statement C is correct, and statement A is incorrect.

Calculate the updated distance to destination $Q$ :

Via neighbor $X$ : $c(R, X) + D_X(Q) = 3 + 4 = 7$
Via neighbor $Y$ : $c(R, Y) + D_Y(Q) = 2 + 6 = 8$
Via neighbor $Z$ : $c(R, Z) + D_Z(Q) = 5 + 8 = 13$
Taking the minimum:

D_R(Q) = \min(7, 8, 13) = 7 \quad \text{with next hop } X

Thus, the distance to $Q$ is stored as 7, and the next hop router is $X$ (not $Z$ ). Statement B is correct, and statement D is incorrect.

Hence, statements B and C are correct.

Final answer

B, C

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 55 of 65, printed as CS Q.45
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source