Skip to content
GATEiit

GATE CSE 2022 Q57: Probability of a routing loop after link failure in distance vector

Question

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

Three routers in a line: P connected to Q, and Q connected to R
Tap the figure to enlarge

The routers exchange distance vector routing information and have converged on the routing tables, after which the link Q−R fails. Assume that P and 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 P and Q, leading to count-to-infinity problem, is___________.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 0.5 (official GATE 2022 final answer key)

Concept used: Count-to-infinity starts if P's stale route to R (via Q) reaches Q before Q's "R unreachable" update reaches P.

First step: After the failure, either P or Q sends its next update first, each with probability 12\frac{1}{2}; decide which order creates the loop.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key

More Computer Networks PYQs

PracticePractise Computer Networks questions →Full paperAll GATE CSE 2022 questions →