GATE CSE 2011 | Question: 52

Question

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)$

Comments

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

​​​​​​what does 2 round means here in stament?

---

https://gateoverflow.in/43317/gate2011-53

second part

---

question from offline paper I think.

Answer 1

Answer is (A).

1. As soon as $N2-N3$ reduces to $2$,both $N2$ and $N3$ instantly updates their distance to $N3$ and $N2$ to $2$ respectively. So, $N2$: $(1, 0, 2, 7, 3)$, $N3$: $(7, 2, 0, 2, 6)$ becomes this.

After this starts first round of update in which each node shares its table with their respective neighbors ONLY. BUT KEEP IN MIND THAT ONLY OLD TABLES WILL BE SHARED.What I mean is tables that will be used for updation at this moment contain the values as $N1$$:$ $(0, 1, 7, 8, 4)$,$N2:$ $(1, 0, 2, 7, 3)$,$N3$: $(7, 2, 0, 2, 6)$,$N4:$ $(8, 7, 2, 0, 4)$,$N5:$ $(4, 3, 6, 4, 0)$.

SEE at this time all the entries are old EXCEPT in $N2$ and $N3$ where value changes to $2$ instead of $6$.

Question asks for $N3$. So focus on that.

N3 receives tables from $N2:$ $(1, 0, 2, 7, 3)$ and $N4:$ $(8, 7, 2, 0, 4)$. Using THIS ONLY original $N3:$ $(7, 2, 0, 2, 6)$ updates to $N3(3,2,0,2,5)$. (For updation and forming the tables for this refer FOROUZAN.)

So, answer is (A).

Comments

@Ayush Upadhyaya 

thats helpful than any YT vid , thanx 

---

@Ayush Upadhyaya sir thanks.very helpful solution

---

@Ayush Upadhyaya Thanks.Its nicely explained

Answer 2

Last line of the question is very important to solve this correctly

Comments

i think something is wrong in part 1 solution.

As clearly mention any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors . so due to update of 6-------> 2 , Both N2 and N3  will update that particular entries....

i.e  N2 (1,0,2,7,3) and N4 (8,7,2,0,4) will share thier distance vector to N3 (7,2,0,2,6) 

then in next update N3 (3,2,0,2,5).......

Ans (3,2,0,2,5)

(If I am wrong , Let me know.....)

Answer 3

4.11  Answer should be A.

Each node sends their distance vectors to their neighbours. So, N3 receives the following updates in next round of updates.

From N2 - B{1,0,6,7,3}

From N4 - C{8,7,2,0,4}

Now, the new distance from N3 to N2 is 2 and to N4 is 2.

So, the table for N3 will be updated as follows;

Suppose array A represents distance vectors at N3, B represents distance vectors received from N2 and C represents distance vectors received from N4.

for i=1 to 5 :

     A[i] = minimum(A[i],B[i]+2,C[i]+2)

 

Hence, the updated value will be A{3,2,0,2,5}

 

4.12 Answer is a) 3.

N2 reports the distance to N1 as infinity but since N3 already has an entry 3 for distance to N1, it will not update the entry.

Comments

answer of of 4.12  is c) 10 as in DVR the routers rely completely on their neighbour Routers .So N2 , N4 will send their distance vector to N3 and N3 will find out that in order to reach N1 the option I have are:

1) infinity (from N1)+ 2(N1 N2 distance ) =infinity

2)8 (from N4 )+ 2 (N4 N3 distance)= 10

N3 will choose the minimum of two which is 10.

---

How is it 8 from N4 ? It should be 5, right?

Answer 4

At first, Option (D) seems to be the correct answer if we consider immediate round after the cost changes. But, the question asks for the new distance vector after next

round of updates (note the plural).

Answer 5

There are 2 parts of this question and it gave me a lot of clarity in DVR . I will try including the points where one can possibly have confusion in this question .

 

Part 1:

As soon as the cost of the link between N3 and N2 is reduced to 2, both N3 and N2 will immediately update their distance vectors. Specifically:

N3 updates its distance to N2 to 2, and

N2 updates its distance to N3 to 2.

However, other nodes (such as N4, N5, etc.) do not get affected immediately. This is because:

Between two update rounds, a change in link cost causes only the two directly connected nodes to update their distance vectors with respect to each other. The change does not propagate further until the next round of distance vector exchange.

Now, in the next update round, every node shares its updated distance vector with its immediate neighbors. So, N3 receives updated distance vectors from N2 and N4 (indicated by red arrows in the diagram).
N3 then recalculates its distance vector by checking all possible paths via its neighbors.

For each destination in the network, N3 does the following

Computes the sum of:

1. the cost to reach a neighbor, and

2. the neighbor's reported distance to the destination.

   Chooses the minimum of these computed values across all neighbors.

NOTE: While updating its distance vector, N3 does not compare the new values with its own previous distance vector entries. Instead, it only considers the new cost estimates coming from its neighbors. This is because, in Distance Vector Routing, a node relies on its neighbors to provide the best known paths.
Its own old values are considered outdated during the update process, as the whole point is to revise them based on neighbor-reported costs.

Part 2:

Now, before the N2–N1 link goes down, all the nodes undergo one round of update after the N2–N3 link cost is changed from 6 to 2. So first, let's process that update round, and only then consider the failure of the N2–N1 link. Since the cost to N1 is asked, I will maintain only the entry corresponding to N1 in each node's distance vector after the update round.

N2:
Cost to N1 = 1

N3: Receives (old) vectors from N2 and N4.
Cost to N1 = min(1 + 2, 8 + 2) = 3

N4: Receives (old) vectors from N3 and N5.
Cost to N1 = min(4 + 4, 7 + 2) = 8

N5: Receives (old) vectors from N4 and N3.
Cost to N1 = min(1 + 3, 8 + 4) = 4

Note: I have explicitly mentioned "old" vectors because it is important to understand that in any update round, the distance vectors from the previous round are used for calculations. For example, while calculating the distance from N4 to N1, the value received from N3 is 7, not 3, because 3 is the value N3 is computing in the current round and hasn’t yet shared with neighbors.

Now, when the N2–N1 link goes down, N2 immediately updates its cost to N1 as infinity.

In the next update round, N3 receives vectors from N2 and N4.
Cost to N1 = min(infinity (from N2), 8 + 2 (from N4)) = 10

Hence, the answer is 10.

In the image values updated after N3-N2 node changes from 6 to 2 are indicated by blue and that are updated after the N2-N1 link goes down updated by red.

Answer 6

l