GATE CSE 2022 | Question: 47

Question

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

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  

---

link of book:

https://www.amazon.in/Computer-Networks-Top-Down-Approach/dp/1259001563

306 page :

---

0.5

Answer 1

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] https://www.classes.cs.uchicago.edu/archive/2003/winter/54001-1/data/hw2sol.pdf 

Comments

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?

---

@viniit

Your doubt is answered HERE.

Answer 2

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.