GATE Overflow Test Series | Mock GATE | Test 4 | Question: 39

Question

Consider a network with five nodes, $N_1$ to $N_5$, as shown as below.

The network uses a Distance Vector Routing protocol. Once the routes have been stabilized, the distance vectors at different nodes are as follows.
$N_{1}: (0, 3, 11, 14, 8)$
$N_{2}: (3, 0, 8, 11, 5)$
$N_{3}: (11, 8, 0, 4, 10)$
$N_{4}: (14, 11, 4, 0, 6)$
$N_{5}: (8, 5, 10, 6, 0)$
Each distance vector is the distance of the best known path at that instance to nodes, $N_{1}$ to $N_{5}$, 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.
The cost of link $N_{5}-N_{2}$ reduces to $4$ (in both directions). After the next round of updates, the link $N_{1}-N_{2}$ goes down. $N_{2}$ will reflect this change immediately in its distance vector as cost, $\infty$. After the next round of update, the cost to $N_{1}$ in the distance vector of $N_{5}$ is _______

Answer 1

After the update since $N_2-N_5$ reduces to $4,$

$N_{1}: (0, 3, 11, 14, 8)$

$N_{2}: (3, 0, 8, 11, 4)$

$N_{3}: (11, 8, 0, 4, 10)$

$N_{4}: (14, 11, 4, 0, 6)$

$N_{5}: (7, 4, 10, 6, 0)$

Now, when $N_1-N_2$ goes down,

$N_{1}: (0, \infty, 11, 13, 8)$

$N_{2}: (\infty, 0, 8, 10, 4)$

$N_{3}: (17, 8, 0, 4, 10)$

$N_{4}: (13, 10, 4, 0, 6)$

$N_{5}: (20, 4, 10, 6, 0)$

So, the correct answer is $20.$

Comments

It should be 19 na ?

---

After the first link cost (N5-N2) changed, entries are :

N1 = (0,3,11,13,8)

N2 = (3,0,8,11,4)

N3 = (11,8,0,4,10)

N4 = (13,11,4,0,6)

N5 = (8,4,10,6,0).

shouldn’t it be like this ? N1 [to N4] shall be 13 instead of 14. Hence finally answer turns out to be 19 in my case.

---

Initially

N5 (8,5,10,6,0)

N2 (3,0,8,11,5)

 

N5-N2 cost reduce to 4 (update cost to N2-N5 not to ther nodes through that node)

N5(8,4,10,6,0)

N2(3,0,8,11,4)

 

Now N5 share this

at N4

min{6+(8,4,10,6,0),4+(11,8,0,4,10)}

N4 new (14,10,4,0,6)

here even though the distance from N4 to N2 re updated to newer value it did not change the value to N1.

it is because when a value changes(N2-N5) it is reflected to its immediate neighbors (N2,N5) but not all nodes distance through that path(N4-N5-N2-N1) will get updated at same time it take few more round to complete.

(Now N4 thinks that there is a new path at 10 distance to N2 through N5, and from N5 8 to N1, N4 don’t know that the path to N1 is N5-N2-N1 so it consider new value for N5-N2 and old value for N5-N1.When it was sharing the information N5 new only that there an update  in distance to N2. It will update the distance to N2 but not update all path through N2

Distance vector routing use information from its immediate neighbors only not the entire network )

 

N1-N2 goes down

N2 ($\infty$,0,8,10,4) and share this with N5

at N5 min{6+(14,10,4,0,6),4+($\infty$,0,8,10,4)}

N5 (20,4,10,6,0)