GATE CS 2011 Q.53 (CS Q.53): Routing Algorithms (Distance Vector, Link State) and BGP/OSPF

Linked answer questions

Statement for Linked Answer Questions 52 and 53:

Consider a network with five nodes, N1 to N5, as shown below.

Five-node network graph with nodes N1 through N5 and link costs (N1, N2)=1, (N2, N5)=3, (N2, N3)=6, (N5, N4)=4, (N4, N3)=2

The network uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as following:

N1: $(0, 1, 7, 8, 4)$

N2: $(1, 0, 6, 7, 3)$

N3: $(7, 6, 0, 2, 6)$

N4: $(8, 7, 2, 0, 4)$

N5: $(4, 3, 6, 4, 0)$

Each distance vector is the distance of the best known path at that instance to nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors.

Shared with question 52.

After the update in the previous question, the link N1-N2 goes down. N2 will reflect this change immediately in its distance vector as cost, $\infty$ . After the NEXT ROUND of update, what will be the cost to N1 in the distance vector of N3?

$\infty$

Official answer and solution

Official answer: C
From: Official GATE 2011 answer key

Solution

Trace the next round of distance vector updates at node N3 after link N1-N2 fails.

When the link N1-N2 goes down, node N2 immediately updates its distance vector entry to N1 as $\infty$ .

In the subsequent update round, node N3 receives distance vectors from its neighbors N2 and N4:

From N2: Distance to N1 is reported as $\infty$ .
From N4: Distance to N1 is still reported as 8 (since N4 has not yet updated its distance to N1).

Node N3 recalculates its best distance to node N1:

D_{N3}(N1) = \min(c(N3, N2) + D_{N2}(N1), c(N3, N4) + D_{N4}(N1))

D_{N3}(N1) = \min(2 + \infty, 2 + 8) = \min(\infty, 10) = 10

Therefore, the cost to N1 in the distance vector of N3 after this round of update is 10.

Final answer

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

Source

Paper: GATE 2011 Computer Science and Information Technology (CS)
Question: 53 of 65, printed as CS Q.53
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.