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

i did not understand this question should i come after studying probability subject?

---

@S_Sandeep main concept used here  is related to count to infinity problem
most basic formula of probability is used here

---

$\underline{\text{video solution}}$

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

@viniit AND  @Deepak PooniaA single channel between two host or two router two packet can be sent at the same time because it will be collided in a particular channel AND BOTH WILL ROUTER OR HOST ANY THINK - WILL GET MESSAGE THAT THE PACKET IS BEEN COLLIDED SO SEND IT AGIAN AND WE THAT LEARN THAT THEN IT WILL BE RUN BACKOFF ALGO 

 

---

@amar100 check Sachin's comment above

---

what if connection between them is full duplex.

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.

Answer 3

.

Comments

answer solution bro which tablet ur using for notes :}? @Shaikh_hasib

---

Ipad

---

I also thought like same, since it is not given that which scheme they are using to send D.V,

 

we can assume either periodic update or triggered updates are being used

there is no problem in case of trigerred update as Q will trigger a routing table update about R and P knows about distance of R from Q

but, if periodic update comes first, then there will be count to inf problem

 

so prob is 1/2 = 0.5

---

Best Answer

Answer 4

COMMENT BELOW IF YOU HAVE ANY DOUBT

Answer 5

🔁 What causes the loop?

After Q–R fails:

• Q no longer has a valid route to R.

• But if P hasn’t yet learned about the failure, it might still advertise a route to R via Q.

• Q, seeing P’s route to R, might believe R is reachable via P.

• This mutual misbelief causes a routing loop between P and Q, leading to the count-to-infinity problem.

🎲 Probability of Loop Formation

The key is timing:

• For a loop to form, Q must send its update before P does, so P still thinks R is reachable via Q.

• Since both send updates randomly at the same average rate, the probability that Q sends first is: 0.5

Comments

2nd part of your answer is wrong as count to infinity will occur if node p ( not Q) send first which will lead to formation of a loop. P(P sends first) = 0.5