GATE CS 2015 Set 2 Q.51 (CS Q.41): Routing Algorithms (Distance Vector, Link State) and BGP/OSPF

Consider the following routing table at an IP router:

For each IP address in Group I identify the correct choice of the next hop from Group II using the entries from the routing table above.

Group I
i) 128.96.171.92
ii) 128.96.167.151
iii) 128.96.163.151
iv) 128.96.165.121

Group II
a) Interface 0
b) Interface 1
c) R2
d) R3
e) R4

i-a, ii-c, iii-e, iv-d

i-a, ii-d, iii-b, iv-e

i-b, ii-c, iii-d, iv-e

i-b, ii-c, iii-e, iv-d

Official answer and solution

Solution

Perform longest prefix matching by bitwise-ANDing destination IP addresses with routing table masks.

We evaluate each IP address against the routing table prefixes:

Mask 255.255.254.0 (/23): The third octet has mask $254 = 11111110_2$ . $171 = 10101011_2 \implies 171 \text{ AND } 254 = 10101010_2 = 170.$ Result: 128.96.170.0. Matches row 1 $\implies$ Interface 0 (a).

Mask 255.255.254.0: $167 = 10100111_2 \implies 167 \text{ AND } 254 = 10100110_2 = 166.$ Result: 128.96.166.0. Matches row 3 $\implies$ R2 (c).

Mask 255.255.254.0: $163 \text{ AND } 254 = 162$ (no match).
Mask 255.255.252.0 (/22): $252 = 11111100_2$ . $163 = 10100011_2 \implies 163 \text{ AND } 252 = 10100000_2 = 160 \neq 164.$
No specific network match $\implies$ Default route R4 (e).

Mask 255.255.254.0: $165 \text{ AND } 254 = 164$ (no match with 170, 168, or 166).
Mask 255.255.252.0: $165 = 10100101_2 \implies 165 \text{ AND } 252 = 10100100_2 = 164.$ Result: 128.96.164.0. Matches row 4 $\implies$ R3 (d).

Matching: i-a, ii-c, iii-e, iv-d (option A).

Final answer

Common trap

Miscalculating the bitwise AND with mask 254 or 252, confusing 163 AND 252 (= 160) with 164.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.