5.2k 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, what will be the new distance vector at node, $N3$?

1. $(3, 2, 0, 2, 5)$
2. $(3, 2, 0, 2, 6)$
3. $(7, 2, 0, 2, 5)$
4. $(7, 2, 0, 2, 6)$
edited | 5.2k views
0
Please explain how to solve these kind of Routing problems
+5
These problems are very straight forward and hardly goes wrong. So, shouldn't be missed for GATE.
0

Arjun sir plz resolve my doubt here https://gateoverflow.in/2160/gate2011-52

0

"In each round, all nodes exchange their distance vectors with their respective neighbors"

In the update round, Node N2 and N4 will share their distance vectors with N3. By taking the help from both N2 and N4, N3 will update its table to what given in the option (A).

0

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

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?

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

edited
0
How is it 8 from N4 ? It should be 5, right?
+1

Sir,

Regarding updation of N4 in the previous update,

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

N4 receives routing info from  N3: (7, 2, 0, 2, 6),N5: (4, 3, 6, 4, 0).

So N4 will be updated as follows (5,4,2,0,4) ryt?

Then y u r saying '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...'

I am not able to understand...pls explain sir

+6

In each round, the update algorithm runs simultaneously in all the nodes. So, all the nodes use the resulting table from previous round. It is similar to following code.

loop{
Iteration i:
}

+1

at t=0  the vector for N4 is given as (8,7,2,0,4)

Then, the distance in N2-N3 node was updated from 6 to 2. Then after next round of updates

at t=30 N4 stablised at (5,4,2,0,4)

Now the links breaks off and next round of updates takes place :

So, N4 will send previous record which has 5 . Why will it send 8 ??

+2
At T2, distance to N1 in N4 won't be updated as N4 won't know that N1 distance is reduced. This information will take some rounds to reach N4 as in each round only the neighbour information is being passed.
+1
Finally Understood !! Thanks :)
0

As per the question, when N2-N3 is updated only N2 and N3 will update their entries for that link. In the next round of updates, N2 will send its routing table to N5, N1 and N3.

Similarly, N3 will send its routing table to N4 and N2 (its neighbors). So, at T2, N4 will get the information about the link N2-N3 thus changing its routing table to reach N1 with 5 (next hop being N3).

0

1:

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.

2:

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

I am not understanding why would N3 send different updates in round 1?

I think in 2nd block the vector of N3 should be same as 1st. Please correct me if I am wrong.

+1

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 ?

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

N4 thus would get updated to (8,4,0,2,4) in round1 and not (8,7,0,2,4)

So N4 will update its table (in prev question) to N4(8,7,2,0,4).

0

arjun sir, why have you used new tables from N2 and N3 here for first round of update but in the subsequent question where distance is changed to infinity, you have used old tables to compute the distance vector of N4?

you wrote-

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

i am not able to understand.

0
same doubt i have.
0
With the above logic I am not able to solve the next part of the q. Because N2 entry got updated with infinity but in the next round of update it will not share that value , it will share the previous value that is n2-n1 :1
+1

@sushmita

node1  | node2  | node 3 ...

All updates their distance vectors in one round in parallel. Then they send to the neighbours and this repeats in each round.

+1
i.e, in round i, say node1 will be sending distance vectors updated in round i-1. That's all. Here, in question it is asked "after next round of updates". So, distance update happens, each node sends the new values (it is next round).
0
sir, the mistake i was doing is that i was first solving all the distance vectors for part A and then further did one more round of update when the node N1-N2 goes down. We will do it simultaneously. ?

.
0
@ arjun sir got the explanation. Thanx a lot :)
+2

I have discussed it here along with my doubt. Very Useful Explanation provided. :)

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

0

thats helpful than any YT vid , thanx

0

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

0

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

+1 vote

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}

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.
0

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.

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

1