edited by
23,336 views
57 votes
57 votes

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, 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$ ?

  1. $3$
  2. $9$
  3. $10$ 
  4. $\infty$
edited by

6 Answers

Best answer
58 votes
58 votes

First, as soon as $N1-N2$ goes down, $N2$ and $N1$ both update that entry in their tables as infinity. So $N2$ at this moment will be $N2(\text{inf},0,2,\_,\_).$ I have left blank because that details are not important.

Now for $N3$ to get updated in the subsequent round it will get tables from $N2$ and $N4$ only. But first we need to find the $N4$ calculated in previous update. So in previous question $N4$ received updates from $N3$ and $N5$ which are $N3: (7, 6, 0, 2, 6),N5: (4, 3, 6, 4, 0).$

NOW THIS IS VERY IMPORTANT AS WHY N4 DID NOT GET UPDATED TABLES FROM N3. SO ANSWER IS THAT these tables were shared at the same moment and so in a particular round of update old values of all the tables are used and not the updated values.

$N3$ was updates AFTER IT PASSED ITS OLD table to its neighbors AS WHY WOULD $N4$ WAIT FOR $N3$ to GET UPDATED first !!! So N4 will update its table (in prev question) to N4(8,7,2,0,4).

See here path to $N1$ exists via $N5$ and not via $N3$ because when table was shared by $N3$ it contained path to $N1$ as $7$ and $N1$ via $N3$ sums to $7+2 =9.$ Now when $N3$ receives tables from $N2(\text{inf},0,\_,\_,\_)$  and $N4(8,7,2,0,4).$

At first it will see its distance to $N1$ as "Inf" and NOT $3$ because "inf" is the new distance with the same Next hop $N2$ (If next hop is same, new entry is updated even though it is larger than previous entry for the same NEXT HOP).

But at the same time it sees distance to $N1$ from $N4$ as $8$ and so updates with the value $(N3-N4 + N4-N1)= (2+8)=10.$ So $N3-N1$ distance in $N3(10,\_,0,\_,\_)$ is $10.$

So, answer is (C)

Reference: http://www.cs.princeton.edu/courses/archive/spr11/cos461/docs/lec14-distvector.pdf

edited by
22 votes
22 votes
N3 will ask for there distance vectors from N2 and N4. N4 table will inform N3 that it'll take 8 unit time to reach N1 and N2 will show ∞. so, N3 will update 8+2 distance in its table.
10 votes
10 votes
When the link N2-N3 reduces to 2, first round of update will happen. In this round N3 will share [7,2,0,2,6] as its distance vector because immediate nodes will reflect the change in distance vectors immediately. When the link N2-N1 goes down, the following distance vectors will be shared-

Therefore N4 will become [8,4,2,0,4] and N2 will become [inf,0,2,4,3]

The final updated vector at N3 will be [10,2,0,2,5]
4 votes
4 votes

A picture is worth thousand words thats all I can say(also typing this because I’m forced to type 20 characters atleast)

Answer:

Related questions