in Computer Networks edited by
2,934 views
10 votes
10 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 edited by
by
2.9k views

2 Comments

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 

MORE IMPORTANT POINTS:

  1. There are two ways to recover from this  

                   a.      Split Horizon 

                   b.   Poison reverse 

NOTE:
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” --- 

B.Forouzan 

F.Mosharraf  

3
3
2
2

2 Answers

13 votes
13 votes
Best answer

Answer : $0.5$

Once Q-R fails then Q will immidiately update its distance to R to $\infty$. But P will still be having some finitie 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 continious variable.

We are intrested in probability represented by shaded are. 

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

 

Also refer forouzan snapshot of count to infinity

selected by

4 Comments

@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

0
0
edited by

@Prakhar_shrimal

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.

2
2
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$ ?]

1
1

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

1
1
2 votes
2 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.