edited by
14,686 views
48 votes
48 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.

  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 by

7 Answers

Best answer
50 votes
50 votes

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 by
32 votes
32 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.
19 votes
19 votes
A)..the cost would be 102.
10 votes
10 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.

Answer:

Related questions

23 votes
23 votes
4 answers
1
15 votes
15 votes
3 answers
2
Ishrat Jahan asked Nov 3, 2014
5,909 views
Count to infinity is a problem associated with:link state routing protocol.distance vector routing protocolDNS while resolving host nameTCP for congestion control
27 votes
27 votes
3 answers
4
Ishrat Jahan asked Nov 3, 2014
19,342 views
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$...