The Gateway to Computer Science Excellence

+36 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$ ?

- $3$
- $9$
- $10$
- $\infty$

0

"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." is given in the question, that means to reflect that change and reach it till N3 it will take 2 rounds and as what asked in the question in 1 round it must be 3 itself?! please help, wont the shared distance vectors from previous round itself with no change @ N3, changes will only be reflected at N2 only for 1 round

0

Why it's answer is not 3? Can someone plz tell whether we compare current table entries with received tables or not? Here after seeing the answer it seems that we are only comparing entries of received tables.

+1

What does the following line means

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.

Does changing N2-N3 should change only N2 cost in N3 table or the entire cost of all nodes in table of N3?

0

The cost of link N2-N3 reduces to 2 (in both directions) --> this line is confusing. The link n2 n3 changes it's fine. But does the distance vectors changes in their routing tables in that state only??

0

After updating of N2 -N1 as inf. N3 will receive value from N4(8,4,2,0,4) and N2(inf,0,2,4,3)

Here N4 has updated from (8,7,2,0,4) to (8,4,2,0,4) in previous round .

" Imp to note that neighbours will propagate their distance vectors only when THERE IS A CHANGE IN THEIR DVs" so N4 got updated that's why it will send it's Dv to N3

" Second imp point .. node will update its value to new value received from the neighbour even if neighbour has larger value , this is the case when there is a change in neighbours value for the same hop"

For eg. Here N3 will receive inf from N2 to reach N1 , prior this N3 already can reach with distance 3 via N2 , thus neighbour node (I.e N2 ) changed its value for the same hop(I.e. N1), therefore N3 has to update it as inf .

After this N4's table is also their to compare ..from their we can change N3's hop to reach N1 via N4 as N4 propagates value 8+2 , which is lesser than inf

Here N4 has updated from (8,7,2,0,4) to (8,4,2,0,4) in previous round .

" Imp to note that neighbours will propagate their distance vectors only when THERE IS A CHANGE IN THEIR DVs" so N4 got updated that's why it will send it's Dv to N3

" Second imp point .. node will update its value to new value received from the neighbour even if neighbour has larger value , this is the case when there is a change in neighbours value for the same hop"

For eg. Here N3 will receive inf from N2 to reach N1 , prior this N3 already can reach with distance 3 via N2 , thus neighbour node (I.e N2 ) changed its value for the same hop(I.e. N1), therefore N3 has to update it as inf .

After this N4's table is also their to compare ..from their we can change N3's hop to reach N1 via N4 as N4 propagates value 8+2 , which is lesser than inf

0

reading comments will get u more confused here, just see the vectors given in the question .

and as said if any link is suddenly changed it will immediately reflect in the nodes connected to that edge only..

now in each round of update each node is getting dist. vector from its neighbors (Keep in mind that link which got changed immediately will be updated and this vector in which only that entry is updated will be forwarded to neighbours )...

just follow these steps and again i'm saying , see the vectors given in the question and find out the answer by writing on the paper.

it is pretty easy.

Note : thing which got me confused was that why didn't N4 updated its value to 5 for entry N1 after receiving packet from N3 , then i suddenly saw the vector given in the question it was 7 for N1 entry in N3 distance vector. so N4 got vector N3 (7, 2, 0, 2, 6) in the previous round of update.which is why it didn't change its value for N1 from its previous value.

then its just simply straight forward .

and as said if any link is suddenly changed it will immediately reflect in the nodes connected to that edge only..

now in each round of update each node is getting dist. vector from its neighbors (Keep in mind that link which got changed immediately will be updated and this vector in which only that entry is updated will be forwarded to neighbours )...

just follow these steps and again i'm saying , see the vectors given in the question and find out the answer by writing on the paper.

it is pretty easy.

Note : thing which got me confused was that why didn't N4 updated its value to 5 for entry N1 after receiving packet from N3 , then i suddenly saw the vector given in the question it was 7 for N1 entry in N3 distance vector. so N4 got vector N3 (7, 2, 0, 2, 6) in the previous round of update.which is why it didn't change its value for N1 from its previous value.

then its just simply straight forward .

0

@akash.dinkar12 latest distance(Min from all neighbours) has to update whether initial own table contain less cost.

i.e Min(infinity,10)=10 am i correct?

+39 votes

Best answer

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(inf,0,2,_,_). I have left blank coz 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 bcoz 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(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**

0

+10

**N4 should be updated to (8,4,2,0,4)** when the cost of link N2-N3 changes to 2 because this change will cause the routers N2 and N3 changes their values immediately as in distance vector, changes in the cost to reach neighbor are known immediately to the node and THIS causes triggered update to be sent to neighboring routers.

Below is the snapshot from forouzan, which states that when there is a change in the routing table of a node, it shares this information with its neighbors.

So, N4 will surely change to (8,4,2,0,4).

So, obviously, first change in routing tables related to neighbors would occur and then updates would be shared.

0

yes, agreed.

but then the soluton says

"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)."**

**hence again N3 would have to choose between 10 and infinity it will choose the min one.**

0

I THINK THE LINE IN BRACKETS CREATS PROBLEM BECZ ORIGINAL LANGUAGE IS DIFFERENT IN QUESTION . WE ARE NOT GIVEN THAT WE NEED TO DO NEXT ROUND OF UPDATE AFTER UPDATION OF LINK THIS CREATE TWO TIMES OF UPDATIONS ...SO I THINK THIS SENTENCE IS EXTRA

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, ∞∞. After the **NEXT ROUND** of update,

0

@Ayush Upadhyaya why we are considering old table ?As question clearly mention tht after reducing to 2 link down so we have to calculate from previous question na?

0

@jk_1-where exactly you have problem in my comment? I too think something went wrong so help me trace it. :)

0

I am saying why we are taking previous node distance vectors ? As question clearly. Saying that we have to first decrease by 2 and then it goes down .so we should calculate new distance vector from updated vectors

0

@jk_1-Check this

https://cs.stackexchange.com/questions/102533/distance-vector-routing-example/102559#102559

Still any trouble then feel free to ask again.

0

After the last exchange & the link down between N2 & N1 the distance vectors for,

N2 is (infinity, 0, 2, 4, 3)

N3 is (3, 2, 0, 2, 5)

N4 is (8, 4, 2, 0, 4)

now N3 will get vectors from N2 & N4 we should have min(3, infinity+2, 8+2). so N3-N1 record should be 3?? Please explain to me what am i doing wrong??

N2 is (infinity, 0, 2, 4, 3)

N3 is (3, 2, 0, 2, 5)

N4 is (8, 4, 2, 0, 4)

now N3 will get vectors from N2 & N4 we should have min(3, infinity+2, 8+2). so N3-N1 record should be 3?? Please explain to me what am i doing wrong??

0

ok...n hope stabilize at max (n-1) round....after down you have to check at least 4 round then you will get ans....did you check it.

0

When N2-N3 link cost reduces to 2, does N3 not change its distance vector from (7,6,0,2,6) to (3,2,0,2,6) ?,

"Each router receives and saves the most recently received distance vector from each of its neighbors. "(taken from here :https://www.geeksforgeeks.org/computer-network-routing-protocols-set-1-distance-vector-routing/)

I think each router keeps with it the information of it's links and the tables shared by its neighbours, so when ever the a link goes down or cost changes , it recalculates its distance vectors from its saved neighbour tables.

**So,I think N3 has the below information before N2-N3 link cost reduces to 2.**

Link costs (-,6,0,2,-)

Distance vector of neighbours

N2:(1,0,6,7,3)

N4:(8,7,2,0,4)

So based on above N2 and N4 ,N3 DV = (7,6,0,2,6)

**After N2-N3 link cost reduces to 2.**

Link costs (-,2,0,2-)

it uses its saved N2 and N4 tables and recalculate the DV again ,so N3 = (3,2,0,2,5) .

Please someone correct me if I am wrong here?

0

**T1**: Stabilization has just completed. (All DVs as per the data given in question)

**T2** : The change in distance from 6 to 2 has occurred. i.e **between 2 rounds**. (The next round of updates will occur at T3)

As soon as this change takes place the only nodes affected are N2 and N3. Their updated DVs become

N2: (1,0,2,7,3)

N3: (7,2,0,2,6)

Rest all DVs for N1,N4 and N5 remain unaltered.

**T3:** A round of update occurs.

N1 [currently (0,1,7,8,4)] gets DV of N2(1,0,2,7,3). Hence updates to (0,1,4,8,4)

N2 : gets DVs from N1 [old (0,1,7,8,4)], N3[ altered (7,2,0,2,6)] and N5(old (4,3,6,4,0)). Changes may occur only

corresponding to N3. final N2 (1,0,2,4,3)

N3: gets DVs from N2 [ altered (1,0,2,7,3)] and N4 [old (8,7,2,0,4) ]. Hence changes only corresponding to N2.

Final N3** (3,2,0,2,5) : Answer to first part.**

N4 : gets DVs from N3[ altered (7,2,0,2,6)] and N5 [old (4,3,6,4,0)] : Final DV (8,4,2,0,4)

N5 : gets DVs from N4[old(8,7,2,0,4)] and N2[ altered(1,0,2,7,3)] : final (4,3,5,4,0)

**<< 2nd Part >>**

The cost of link

N2−N3N2−N3 reduces to 22 (in both directions). After the next round of updates, the linkN1−N2N1−N2 goes down.

so and end of T3 one round of updates has completed and now the link between N1 and N2 breaks

**T4 :** N1 to N2 weight becomes INF. N2 updates Immediately

N2 : (INF,0,2,4,3)

N1 should change as well but nothing mentioned about it in question, also not relevant

**T5 :** Next round of updates start. (Will focus on N3 only)

N3[ current state (3,2,0,2,5) ] gets DVs from N4[old (8,4,2,0,4) ] and N2 [altered (INF,0,2,4,3)].

So it seems there is no change for N3. **Shouldn't the answer be 3**

0

@Mayank0343 No, because the current state of N3 doesn't matter when update happens.

It will choose the minimum from the fetched distance vectors from it's neighbors, so it will be $\text{min}( 8+2, \infty +2) = 10$

+15 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.

+2

I don't get this.... It is written in previous question "After next round of updates"... Why didn't N3 send its distance vector (3,2,0,2,5) to N4

0

It ia said that only neighbours will send info to each other. So in first round n3 n n4 will exchange old values of their tables and won't be changed. And this part of ques says "after the update in previous ques" means thAt round is over and we got n3 n2 changed but all three remaining tables unchaged. Now n1-n2 goes down and n2 reflect this change into its table..then again all neighbours will send table to each other. N3 will get old table of n4 and New table of n2. So n3 to n1 updates with 8+2=10

+6 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]

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]

0 votes

one needs to carefully read the first line of the second question.

" After the **update** in the previous question.

and also below line of common data for both ques:

"any change in cost of a link will cause the two incident nodes to change in **only that entry** their distance vectors."

It is this update one must refer to

i.e after the update in prev question means only the update of changing N2 ->N3 cost to 2 in N2 and N3->N2 to 2 in N3.

and not consider the tables after the **'next round of updates'**

Next round of updates is used only to compute the answer of first question and thats it.

Hence N4 will exchange its old table (8,7,2,0,4) with N3 and hence N3 will update N3->N1 to min(8+2=10,2+infinity)

52,215 questions

60,010 answers

201,236 comments

94,696 users