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

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updated interval, three tasks are performed.

  1. A node determines whether its neighbors in the graph are accessible. If so, it sets the tentative cost to each accessible neighbor as $1$. Otherwise, the cost is set to $∞$.
  2. From each accessible neighbor, it gets the costs to relay to other nodes via that neighbor (as the next hop).
  3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.

GATE2005-IT_85b

Continuing from the earlier problem, suppose at some time $t$, when the costs have stabilized, node $A$ goes down. The cost from node $F$ to node $A$ at time $(t + 100)$ is :

  1. $>100$ but finite
  2. $\infty$
  3. $3$
  4. $>3$ and $\leq 100$
asked in Computer Networks by Boss (19.1k points)
edited by | 3.4k views
0
is the correct answer 101 or 102??
0
102should be
0
not getting any of the solution...... :(
+3

@Manu+Thakur

I think cost will be 102 at t+100 but the answer says 101.Please verify 101 or 102.

Time A's distance at B's table A's distance at C's table A's distance at D's table A's distance at E's table A's distance at F's table
t $\infty$ $\infty$ 2 2 3
t+1 3 3 3 3 3
t+2 4 4 4 4 4
... ...... ..... .... ...... ......
.... ..... ...... ....... ...... .......
t+100 102 102 102 102 102
+3

Hi @Shivam Chauhan ji, Good approach.

Small correction in mentioned table so final answer will be 101. Please convert it in answer. 

Time A's distance at B's table A's distance at C's table A's distance at D's table A's distance at E's table A's distance at F's table
t 1 1 2 2 3
t+1 2 2 3
t+2 3 3 3 3 3
           
0
is it 102 ? anybody please confirm
0
nice approach i too did the same and getting 102 as answer
0

A perfect Explaination!

 

0
the answer coming is 102. But i think t should have been mentioned in the question that D sends the update to C, before C or B could send the updated distance of infinity to D. Isn't???

7 Answers

+21 votes
Best answer

We consider A B D F at t they are:

The distance between A and the nodes B,D,F respectively are:
$t:$  $1 2 3$

$t+1:$ $3 2 3$

$t+2 :3 4 3$

$t+3: 5 4 5$

$t+4:  5 6 5$

$t+5: 7 6 7$

$t+6:  7 8 7$

$t+7: 9 8 9$

$t+8: 9 10 9$
and this continues:

So, in every two steps they get incremented by $2$

so at t+99 F is 101

at t+100 F is 101
 
So, count to infinity problem.
So, option A.

answered by Active (4.3k points)
edited by
+4

@Arjun Sir

One doubt here

at t+3 F=5; t+4 nochange

at t+5 F=7;  t+6 nochange

at t+7 f=9;  t+8 nochange

...so on....then at t+99 it should be f=101 and at t+100 also f should be 101

I agree that so in every two steps they get incremented by 2....but that is incemented in each (t+odd) time..not even.

please correct me if i m wrong.

0
how i think it will be infinity as node A goes down b and c will update their values.and after two rounds f will get to know that A is inaccessible thus having values as infinity.

please correct if wrong?
+2
yes it should be 101 at t+100.. so corrected

But I think I have done a little mistake . at t+1 should be 3  4  3 bcz any change between 2 rounds will cause the incident nodes to change their entries in their respective distance vector table.. once the link goes down the entry for the adjacent node's distance vector tables it will be reflected so at t it was 1 2 3, then link goes down and it becomes infinity 2 3 ,now at t+1 it is 3 4 3.. so at t+98 F 's distane 101,t+99 101 and t+100 103..
+3

@Shreya
I think you have not updated the the D-A in t+1,  (You have kept D-A as 2)
At  t+1 ,
Distance of B to A = min [ ∞ direct, 1 + ∞(via C), 1 + 2(via D) ] = 3
Similarly,
Distance of D to A = min [ ∞ direct, 1 + ∞(via B), 1 + ∞(via C), 1 + 2(via E) ] = 3 
Distance of F to A = 3 

Going like this at t=2, F-A will be 4
 

After t, at t+2, we get the distance from F to A as 4.Now, in each t, distance increments. So, at t+100, distance becomes 102.

Plese correct me if wrong.

+1
@shreya roy

it is right that The distance between A and the nodes B,D,F respectively are:
t:  1 2 3

further how u update table ..?

and the first row and col both goes to infinity so how u does update thse  table ...

solve it on paper and upload ..it will help us lot
0
How do u add the time,I m unable to understand the concept and its value gets change with the time?
0
How values are being updated?
+14 votes
A)..the cost would be 102.
answered by Loyal (6.9k points)
0
how?
+2
explanation part is always tedious, anyways..at t1 the cost is 3 as updates are not reached to F, but they have updated the cost at E and D, which is 3(to A) via D and E respectively. At t2 this updated cost will reach to F and it will update its metrix with cost of 4(to A) via D.
0
Since, D and E always have a path through each other, the cost to A never reaches infinity and just increment by one each time rt?
0
Correct!!
0
So How does it be 102?there is no time mentioned for updation of node or for complete 3 step process.
+4
Question ask for distance at time t+100. After t, at t+2, we get the distance from F to A as 4.Now, in each t, distance increments. So, at t+100, distance becomes 102.
+2
isnot this a count to infinity problem  how will it get stablize after t+2 answer shud be option B
0
Sir as far i have read in forouzan . that county to infinity we dont have a number that would represnt infinity . Infact when the time goes to 32 -- it is considered as infnity .

So should i take 32  as >3 and <= 100

or infinity --b ?
0
D and E knows the cost of A from B or C.. When A goes down B or C recognize it and send update to all neighbor nodes about cost of infinity ..

Or can we not able to solve count toinfinity by "split horizon and poison reverse"??
0
Then How the ans is 102?pls explain?
0
Arjun Sir not getting.Pls explain another time
0
F to A at  time: t+100 would be 103 or 102??? I am getting 103.
0
At time: t+1, I am getting F to A as: 4. Therefore at time t+100, F to A will be 103. Is this correct sir? Please point out the error.
+1
sir, its coming 101 :(
+9 votes
I think there is some mistake in the question. Assuming that the link cost for B and C changes immediately even before updation as node A goes down, see the following calculations: (based on bellman-ford algo)

========  At  t+1 instance =====================

distance of B to A = min(  $\infty$  .......direct,  1 + $\infty$   ....from C, 1+ 2 ......from D ) = 3

distance of C to A = 3 (on the same lines)

distance of D to A = 3 (on the same lines)

distance of E to A = 3 (on the same lines)

distance of F to A = 3 (on the same lines)

 

========  At  t+2 instance =====================

distance of B to A = 4

distance of C to A = 4

distance of D to A = 4

distance of E to A = 4

distance of F to A = 4

========  At  t+100 instance =====================

distance of B to A = 102

distance of C to A = 102

distance of D to A = 102

distance of E to A = 102

distance of F to A = 102

So, option A.
answered by Boss (18.3k points)
+1
I am also getting similar answer!!!
+1
I am also getting the same answer :(
+3 votes

Please Note: Please consider Node E in the image as Node F(There was labelling mistake in diagram).

Below is the image showing vector exchanges over a short period of time from which we will calculate what is the distance from F to A.

As, you can see, after every two instance of time, the distance to A from F is getting increased by 2.

By observation I have tried to deduce a formula to compute value to get to A from F at t+100.

I divided the 10 time slots into 5 stages with each stage showing 2 vector exchanges.

At time t which belongs to Stage S,

The value will be given by 3+2*(S-1).

For example at t=t+5, Stage S will be given by ceil(5/2)=3

Value=3+2*(3-1) = 3+4=7 this is the distance from F to reach A.

Similarly to calculate at t+100,

Stage number = ceil(100/2)=50

Value = 3+2*(50-1) = 3+98=101

This will be the distance from F to reach A at time instant t+100.

So, answer is option A.

answered by Boss (16k points)
0
Good job Ayush :)
0
is it correct?
0
ayush where is your f and at 99 101 then at 100 102 , at 101 also 102 ...

its going like t=3 t+1=3, t+2=5 ,t+3= 5 .... so at even place it increment by 2 remain till odd place(means just after even number )
0
labelling mistake sonam :P
felt too lazy to draw it out on another paper :P
Didn't get your last line.
0
t+0 even place , t+1 odd place ...

now read again
0

@Ayush, When Node A goes down, C immediately updates its value to $\infty$ right ?

So at t+1, value at D would be min {1 + $\infty$, 1+$\infty$, 1+2, 1+3} = 3 and not 2 as it receives the values to reach A from B,C,E and F.

Please check your answer.

+2 votes

yep, answer will be 101.

answered by Boss (41k points)
edited by
0
@manu

why not updating D and E at instance t+1 itself?

 

why updating only B and C values

at t+1 itself shouldnt it be 3 3 4 4 5 ?
0
why are we considering it as count to infinity problem? It occurs when a link is down, but here a node is down. So, we can still reach A in 3, but A will not respond. And there now should be no path which passes through A.

So, I think the answer should be 3. Please help me  _/\_
0
@rishabh makes sense

but i guess they mean that A is not accessible by those words

which means thelink is down :)

could u also just look into my doubt and help please
0
@aish but how would I understand this during exam?
0
@rishabh

what i meant is ..........node down or link down means the same

have u come across any question where they said that the node is down but the link was taken as working

probably u cannot find any

by node or liink being down...they mean the same
+1
Thanks @aish. I got it.
"have u come across any question where they ..."
I think we will get questions which we never came across :P
0
@rishabh

in this solution

why not updating D and E at instance t+1 itself?

 

why updating only B and C values

at t+1 itself shouldnt it be 3 3 4 4 5 ?
0
@Aish I am not sure, but this is because at t = 1 node A will not receive that information.
0 votes

Answer is A:102

answered by Junior (553 points)
0 votes
answered by (25 points)
Answer:

Related questions



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

42,575 questions
48,566 answers
155,470 comments
63,592 users