GATE CS 2011 Q.52 (CS Q.52): 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 53.

The cost of link N2-N3 reduces to 2 (in both directions). After the next round of updates, what will be the new distance vector at node, N3?

$(3, 2, 0, 2, 5)$

$(3, 2, 0, 2, 6)$

$(7, 2, 0, 2, 5)$

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

Official answer and solution

Official answer: A
From: Official GATE 2011 answer key

Solution

Use the Bellman-Ford update rule at node N3 after the direct link cost c(N3, N2) reduces to 2.

Identify the network neighbors of node N3 from the given network topology: the neighbors of N3 are N2 and N4.

Before the update round, the cost of the link between N2 and N3 decreases from 6 to 2. Node N3 immediately updates its local link cost entry to $c(N3, N2) = 2$ . The link cost to N4 remains $c(N3, N4) = 2$ .

In the update round, N3 receives distance vectors from its neighbors:

From N2: $(1, 0, 6, 7, 3)$
From N4: $(8, 7, 2, 0, 4)$

Compute the updated distances at N3 using $D_{N3}(x) = \min_{v \in \{N2, N4\}} [c(N3, v) + D_v(x)]$ :

To N1: $\min(c(N3, N2) + D_{N2}(N1), c(N3, N4) + D_{N4}(N1)) = \min(2 + 1, 2 + 8) = \min(3, 10) = 3$ .
To N2: $\min(c(N3, N2) + D_{N2}(N2), c(N3, N4) + D_{N4}(N2)) = \min(2 + 0, 2 + 7) = \min(2, 9) = 2$ .
To N3: Distance to itself is 0.
To N4: $\min(c(N3, N2) + D_{N2}(N4), c(N3, N4) + D_{N4}(N4)) = \min(2 + 7, 2 + 0) = \min(9, 2) = 2$ .
To N5: $\min(c(N3, N2) + D_{N2}(N5), c(N3, N4) + D_{N4}(N5)) = \min(2 + 3, 2 + 4) = \min(5, 6) = 5$ .

The new distance vector at node N3 is $(3, 2, 0, 2, 5)$ , which corresponds to Option A.

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: 52 of 65, printed as CS Q.52
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.