GATE IT 2005 | Question: 85b

Question

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 :

• A. $>100$ but finite
• B. $\infty$
• C. $3$
• D. $>3$ and $\leq 100$

Comments

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

---

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

---

One of the most beautuful problem in count to infinity

Answer 1

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.

Comments

I am getting 102. Regardless ans is A.

---

For those, who are getting confused why their answer is 102 and not 101:

Time	B	C	D	E	F
t	1	1	2	2	3
t+1	3	3	2	2	3
t+2	3	3	4	4	3
t+3	5	5	4	4	5
t+4	5	5	6	6	5
t+5	7	7	6	6	7
t+6	7	7	8	8	7
t+7	9	9	8	8	9

We can clearly see that, in general: At t+i , Updated value at F will be: (i-1) + Initial value at F.

But wait! This will work only when value of i is odd. For even number i, the value will be as it is as it was for its previous odd i.Means, we can see that for i=5, we have 7. For i=6, same value (value 7) is retained. Hence, for t+100; i=100 i.e. Even so value will be same as it was for odd i=99. 

Using same generalized formula, 

At t+i=t+99,

Value at F will be: (i-1) + Initial value of F= (99-1)+ 3 = 101.

Same value will be for i=100.

Hence answer will be 101 at t+100 as well and not 102.

---

At $t+99:  101\;100\;101$
$t+100: 101\;102\;101$
So, from $F$ to $A$ at time $(t+100)$ is: $101>100$

Answer 2

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.

Comments

I am also getting similar answer!!!

---

I am also getting the same answer :(

Answer 3

A)..the cost would be 102.

Comments

F to A at  time: t+100 would be 103 or 102??? I am getting 103.

---

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.

---

sir, its coming 101 :(

Answer 4

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.

Comments

t+0 even place , t+1 odd place ...

now read again

---

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

---

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