The Gateway to Computer Science Excellence

+37 votes

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.

- 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 $∞$.
- From each accessible neighbor, it gets the costs to relay to other nodes via that neighbor (as the next hop).
- 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 :

- $>100$ but finite
- $\infty$
- $3$
- $>3$ and $\leq 100$

+12

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

+8

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

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

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

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

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

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

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

Similarly,

Distance of

Distance of

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

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

+16 votes

+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

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

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 ?

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

Or can we not able to solve count toinfinity by "split horizon and poison reverse"??

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

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

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

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 )

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 )

+3 votes

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

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 _/\_

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

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

@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

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

"have u come across any question where they ..."

I think we will get questions which we never came across :P

+1 vote

https://gateoverflow.in/?qa=blob&qa_blobid=17844584781918638746the answer should be d) or b)

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,296 answers

198,262 comments

104,973 users