The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
3.8k views

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$
asked in Computer Networks by Veteran (111k points)
edited by | 3.8k views
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
Simple question. Giving  try is quicker then reading all the comments and answer :)
+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
+1

0
What will be the values of N2 here?
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 .
0
yes the answer should not be 7?

4 Answers

+30 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

answered by Loyal (7.8k points)
edited by
+3

@ arjun sir- its written that So N4 will update its table (in prev question) to N4(8,7,2,0,4). 

 How?? N4 will receive distance vector ( 7,2,0,2,6) from N3 and the distance vector of N4 will become     (8,4,2,0,4)? what wrong am i doing??

Well after the distance changed to infinity then before the routing tables were stabilized, the link between N1 and N2 got down? So are we taking both scenarios in the same round of update?? Its confusing. Plzz clear it.

+8

The value for N2-N3 is changed from 6 to 2 in their vectors immediately and these changed values ( others remaining same, replace 6 by 2) are used for 1st round of updates which are N3 ( 7,2,0,2,6) and N2 (1,0,2,7,3). So in 1st round N4 gets updated from N3 (7,2,0,2,6). Why is then N3(7,6,0,2,6) being used, as mentioned in the solution ?

PLEASE SOMEONE RESOLVE THIS DOUBT OF MINE.

+2
I think u missed the last line in the question. Last line indicates that the vector shared will be different
0

@Arjun Sir and Sandeep_Uniyal

The cost of link N2-N3 changes to 2 in between rounds, so N2 and N3 will update the respective entry immediately. When the new round of update starts, N4 will get N3(7,2,0,2,6) and after this round of update N4 will be (8, 4, 2, 0, 4) and not (8, 7, 2, 0, 4). Although this doesn't affect the final answer.

My confusion:

The N1-N2 link goes down. Now doesn't the final DV of N3 depend on the sequence of arrival of respective DVs of N2 and N4?

Let's say after the first round of updates (as in the previous question) DVs of N2 and N4 are denoted by N2_1 and N4_1 .  After the link N1-N2 breaks, let the changed DV of N2 be N2_2. If N4_1 is advertised to N3 before N2_2, then won't the final entry in DV of N3 for N1 be $\infty$ ? 

Options also don't clarify this as both 10 and $\infty$ are present.

0
I think here the order of  the arrival of advertisements are not important. We are calculating the minimum distance via all the neighbours and will take which one is minimum.
+7

@sushmita I think u r right.

N2-N3 cost reduce to 2 from 6.

Then We complete one round.

After that  N4 should  be (8,4,2,0,4) .

0
@neeraj what reason can be give then for selecting 10 over infinity because distance between n4 and n2 from n3 is same which is equal to 2 ?
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" -- does this mean that changes in routing table (for only that distance b/w two nodes) will take place instantly after the link change occurs or will the updations take place at the starting of the next round?
+1
the incident nodes will change their routing tables immediately.
0
yes it should be updated one only. sort of ambiguity in the question :(
0

The above comments added to this question seems right as N4 should get updated to (8,4,2,0,4) prior to the disruption of N1 and N2 links. However, this update will not affect the answer to the current question.
Further, it is explained in https://gateoverflow.in/2160/gate2011-52 (the current question is an extension to this).

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

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 thats true. Thanx
0
N4 should be updated to (8,4,2,0,4),how? I donot think so. 4 is already down right?
0
@Sreshta, How is 4 down?
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
how N3 is knowing the updated value of n2 -> n1, while n5 still has got the old value ?
0
What will be the values of N2 here?
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, 

+10 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.
answered by Junior (933 points)
+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
+1
@khushtak

Still not clear :( Can you elaborate a bit??
0
Why N4 table will inform N3 that it'll take 8 unit time to reach N1 ? hen N2 's table is updated, it will share its info with N5 no ?
+1 vote
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]
answered by Boss (15.2k points)
0 votes
Why the ans is not 3 ?

As N3: (3, 2, 0, 2, 5)
answered by Active (1.2k points)
Answer:

Related questions

0 votes
0 answers
6


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,942 questions
49,497 answers
162,337 comments
65,748 users