Consider a network with five nodes, N1 to N5, as shown as below. The network…
2011
Consider a network with five nodes, N1 to N5, 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.
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.
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?
- A.
(3,2,0,2,5)
- B.
(3,2,0,2,6)
- C.
(7,2,0,2,5)
- D.
(7,2,0,2,6)
Attempted by 89 students.
Show answer & explanation
Correct answer: A
After the link cost N2 − N3 drops to 2, N2 and N3 immediately update only their entry for each other; in the next exchange every node uses neighbors’ distance vectors to recompute shortest distances. Compute N3’s new distances by checking paths via its two neighbors N2 and N4.
Step-by-step (testseries-ready):
Initially (before the change) the distance vectors were:
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)
The cost of link N2 − N3 reduces to 2. Between rounds only the two incident nodes update the entry for each other:
N2 becomes (1,0,2,7,3) [changed N2→N3 from 6 → 2]
N3 becomes (7,2,0,2,6) [changed N3→N2 from 6 → 2]
In the next round N3 receives distance vectors from its neighbours N2 and N4. Use the Bellman–Ford update:
cost(N3→N2) = 2, cost(N3→N4) = 2 (links from diagram).
For each destination d,
distN3(d)=min{2+DVN2(d), 2+DVN4(d)}
Compute entries:
To N1: min(2+N2[N1], 2+N4[N1]) = min(2+1, 2+8) = min(3,10) = 3.
To N2: min(2+N2[N2], 2+N4[N2]) = min(2+0, 2+7) = min(2,9) = 2.
To N3: 0.
To N4: min(2+N2[N4], 2+N4[N4]) = min(2+7, 2+0) = min(9,2) = 2.
To N5: min(2+N2[N5], 2+N4[N5]) = min(2+3, 2+4) = min(5,6) = 5.
So the new distance vector at N3N3N3 is (3, 2, 0, 2, 5) → option (A).