GATE 2025 CS1 Q.40: solution and answer

Official answer: ASource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

1. A router forwards by longest-prefix match: find every entry whose prefix matches the destination, then take the match with the longest mask. If nothing else matches, the default route applies.

2. All four non-default entries begin with 145.36, which is also the first two octets of the destination 145.36.109.70. Only the third octet separates them. The destination's third octet is $109=01101101_2$.

3. $$\begin{array}{cccc}\text{Entry}& \text{Third-octet range}& \text{Contains }109?& \text{Interface}\\ 145.36.0.0/16& 0\text{ to }255& \text{yes}& \text{E1}\\ 145.36.128.0/17& 128\text{ to }255& \text{no}& \text{E2}\\ 145.36.64.0/18& 64\text{ to }127& \text{yes}& \text{E3}\\ 145.36.255.0/24& 255\text{ only}& \text{no}& \text{E4}\\ \text{Default}& \text{all}& \text{yes}& \text{E5}\end{array}$$

4. Why the /18 range is 64 to 127: the first 18 bits are the 16 bits of 145.36 plus the top 2 bits of the third octet. The entry's third octet is $64=01000000_2$, so its top two bits are $01$. The remaining 6 bits are free, giving $01000000_2$ to $01111111_2$, which is 64 to 127. Since $109=01101101_2$ also starts with $01$, it matches.

5. Likewise /17 needs the top bit of the third octet to be 1 (128 to 255), but $109$ starts with 0, so it does not match. /24 needs the third octet to equal 255, so it does not match either.

6. The matching entries are /16 (E1), /18 (E3) and the default (/0, E5). The longest prefix is /18, so the packet is forwarded to E3, which is option (A).