in Computer Networks retagged by
18 votes
18 votes

Consider a network with three routers $\text{P, Q, R}$ shown in the figure below. All the links have cost of unity.

The routers exchange distance vector routing information and have converged on the routing tables, after which the link $\text{Q-R}$ fails. Assume that $\text{P}$ and $\text{Q}$ send out routing updates at random times, each at the same average rate. The probability of a routing loop formation (rounded off to one decimal place) between $\text{P}$ and $\text{Q},$ leading to count-to-infinity problem, is _______________.

in Computer Networks retagged by


Few points about Count to Infifnity problem:

  1. This problem appears in DVR only not in LSR (Link state Routing)

                  This is a Possibility not a definite case . (why??)                                                                                       P-----Q-------X

let this is a connection that is already stabilised

P: [(0,X),(1,Q),2]

now some how Q-----X is disconnected .

DVR of Q : [1,0,infinity], [generally DVR is applicable for 15 or lesser nodes therefore 16 refers infinity this is by convention as per “Foruzan”]

Here Comes two possible ways: 

case a: 

P sends its distance vector to Q  as : [0,1,2] 

After receiving this DV to Q

Q will start to count to infinity 

and hence the DV of Q will be like: [1,0,3] as Q thinks P may have some path to X

because in DV we send the values only.

Case b:

Q sends it DV to P and P recognizes that there is no link between Q----R 

so, DV of P is updates and understood that there is no way to go X

So, among this two cases 


  1. There are two ways to recover from this  

                   a.      Split Horizon 

                   b.   Poison reverse 

Two nodes instability can be Solved by using the two approaches that are enlisted above but three node instability may or may not solvable by using this approaches too.

Refer this book

“Computer Networks: A Top Down Approach” --- 




2 Answers

20 votes
20 votes
Best answer

Answer : $0.5$

Once Q-R fails then Q will immediately update its distance to R to $\infty$. But P will still be having some finite value (which is 2).

Now it depends on P and Q, who is sending distance vector first.

if Q sends then system becomes stable immediately but if P sends first then it will be count to infinity. Please understand that count to infinity is not some wrong thing, it is just it takes some time to stable.

Since it is given in question that both have same average rate hence probability is also $\frac{1}{2}$ that P sends first than Q. Hence the answer.

But we can calculate answer more mathematically considering that time is continuous variable.

We are interested in probability represented by the shaded area,  

which will be  = $\frac{\text{Area of Tringle}}{\text{Area of Square}} = \frac{\frac{1}{2}t^2}{t^2} = \frac{1}{2}$

$\text{Method 2 OPTIONAL}$

Let $X$ and $Y$ be uniform random variables in $[0,t]$ representing time for $P$ and $Q$ respectively.
We need to find $P(X<Y) = ?.$

$P(X<Y) = P(X \leq Y) = P(X \leq k)$ (Let $Y =k$).

$ P(X \leq k) =$ Can you continue from here ?.

Also refer Forouzan snapshot of count to infinity


Similar question – [page 22, 23] 

edited by


@Sachin Mittal 1 

why we have not taken a case when both sends routing packet simultaneously.... 

case1 when P sends first

case 2 when Q sends first

case 3 when both sends simultaneously

edited by


Time is continuous, $\color{red}{\text{in case of continuous probability, there is a zero prob for any EXACT point}}$.

If both are choosing to send exactly at 10:00am then you need to make sure that it is 10:00000000000 for both and not 10:00000000000am for one and 10:00000000001 am for other.

Choosing both 10:00000000000000000am is zero probability. because it is 1/inf. inf is because of infinite possible values of time.

edited by

Respected @Sachin Mittal 1 sir, I was having one doubt. The above is a screen shot from Forouzan. But Forouzan just discusses the thing in words, without rigorous mathematics.  Especially the line:

If A can send its table to B immediately, everything is fine. However, the system becomes unstable if B sends its routing table to A before receiving A’s routing table.

Sir, here the important point is, to avoid the loop B should send its DV only after it has received the DV from A. So to work out this gate problem more formally, I tried this way. Let $T_p$ be the propagation time and $T_t$ be transmission time of the DV.

Now suppose sir, $Q$ sends it packets out at time $x$ then it shall reach $P$ only at time $y=x+T_p+T_t$. So $P$ should transmit only after $x+T_p+T_t$ so that there is no loop.

Let us consider the time span of $[0,t]$. Then the required probability is lies in the area shaded in yellow.

$$\text{Probability}=\frac{\text{Area of yellow triangle}}{\text{Area of the rectangle}}$$

$$=\frac{\frac{1}{2}[t-(T_p+T_t)]^2}{t^2} =\frac{1}{2}\left[1-\frac{T_p+T_t}{t}\right]^2$$

If we assume $T_p+T_t=0$ then only we get $probability=0.5$

Otherwise in the most general case, $probability<0.5$

Please can you check my analysis once sir...

[PS: Or is it so that since the $t$ is arbitrarily chosen by us, so to allow for this arbitrary thing to be reflected in our answer, we should account for infinitely large $t$, i.e. $\lim_{t\to \infty} probability = 0.5$ ?]


Since it is given in question that both have same average rate hence probability is also 1/2 that P sends first than Q. Hence the answer.

can you explain precisely the meaning of “same average rate”.


P and Q send out routing updates at random times

I think this statement is what makes the difference.

If the question was that they send out routing updates at the “same time” (i.e. both send out their old tables same time) it will always lead to a count-to-infinity problem, making the probability 1.


@Sachin Mittal 1 @Deepak Poonia sir, we here take two cases that either P sends first or Q sends first but why didn’t you consider the case of P and Q both sends at the same time?



Your doubt is answered HERE.

3 votes
3 votes
0.5 because it depends on Node Q or node P sharing information first.

If node Q shares it first there is no looping.

If node P does it there will definitely be a count to infinity problem.