# GATE2005-IT-85b

7.9k 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.

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$

edited
0
is the correct answer 101 or 102??
1
102should be
0
not getting any of the solution...... :(
17

@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
12

Hi @Shivam Chauhan ji, Good approach.

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

@Chhotu why t+1 in B & C value infinite and D,E,F can't update can you explain?

1

@Gangani_Son since D,E,F are not directly connected to A. So their routing table will be updated from table of their neighbours(updated B,C).

@sushmita answer should be 101 at time t+100.

0
One of the most beautuful problem in count to infinity

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.

edited
5

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

3
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..
4

@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?
2
How values are being updated?
0
At t+100, cost F to A will be 102.
0
I am getting 102. Regardless ans is A.
A)..the cost would be 102.
0
how?
3
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.
5
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 :(
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.
1
I am also getting similar answer!!!
1
I am also getting the same answer :(

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.

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
0
t+0 even place , t+1 odd place ...

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.

0

Question says:-

A node determines whether its neighbors in the graph are accessible. If so, it sets the tentative cost to each accessible neighbor as 11. Otherwise, the cost is set to ∞

At t+0, B will immediately come to know that A is down and will update its distance to A as infinity. Now, next round of update will be based on B having the value infinity. So, ans will be 102 at t+100

edited
3
@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.

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.
1 vote

## Related questions

1
3k 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. ...
Suppose that two parties $A$ and $B$ wish to setup a common secret key (D-H key) between themselves using the Diffie-Hellman key exchange technique. They agree on $7$ as the modulus and $3$ as the primitive root. Party $A$ chooses $2$ and party $B$ chooses $5$ as their respective secrets. Their D-H key is $3$ $4$ $5$ $6$
Consider the following message $M = 1010001101$. The cyclic redundancy check (CRC) for this message using the divisor polynomial $x^5+x^4+x^2+1$ is : $01110$ $01011$ $10101$ $10110$