GATE 2024 CS1 Q.58: solution and answer

GATE 2024 · CS1Q.58 · 2 marks · NAT

Consider the entries shown below in the forwarding table of an IP router. Each entry consists of an IP prefix and the corresponding next hop router for packets whose destination IP address matches the prefix. The notation "/N" in a prefix indicates a subnet mask with the most significant N bits set to 1.

This router forwards 20 packets each to 5 hosts. The IP addresses of the hosts are 10.1.1.16, 10.1.1.72, 10.1.1.132, 10.1.1.191, and 10.1.1.205. The number of packets forwarded via the next hop router R2 is ______

GATE 2024 CS1 question 58: A two-column table with header Prefix | Next hop router. — Figure from the GATE 2024 CS1 paper. It is part of the question.

Answer and solution

ANSWER

The number of packets forwarded via R2 is 40.

Official answer: 40Source: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

Only the last octet differs, so work out the range each prefix covers in the last octet: $10.1.1.0/24$ covers $0$ to $255$ (R1); $10.1.1.128/25$ covers $128$ to $255$ (R2); $10.1.1.64/26$ covers $64$ to $127$ (R3); $10.1.1.192/26$ covers $192$ to $255$ (R4).
The router uses longest prefix match: among all entries that match a destination, the entry with the largest $N$ is used.
10.1.1.16 (last octet $16$ ) lies only in the /24 range, so it goes to R1.
10.1.1.72 (last octet $72$ ) lies in $64$ to $127$ , so it matches /24 and /26. The longest prefix is /26, so it goes to R3.
10.1.1.132 (last octet $132$ ) lies in $128$ to $255$ but below $192$ , so it matches /24 and /25. The longest prefix is /25, so it goes to R2.
10.1.1.191 (last octet $191$ ) is below $192$ , so it also matches only /24 and /25, and goes to R2.
10.1.1.205 (last octet $205$ ) lies in $192$ to $255$ , so it matches /24, /25 and /26. The longest prefix is /26, so it goes to R4.
Two hosts (10.1.1.132 and 10.1.1.191) are forwarded via R2, so the packets via R2 are $2 \times 20 = 40$ .

KEY IDEA

Routers pick the matching forwarding entry with the longest prefix. Convert each prefix to a range of the last octet and find the most specific range containing each host.

WATCH OUT FOR

Stopping at the first or shortest matching prefix. 10.1.1.205 also matches the /25 entry (R2), but the /26 entry is longer, so it goes to R4. Counting it under R2 would give 60.

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 20 IPv4 questions, with notes

GATE 2024 CS1 Q.58: solution and answer

Answer and solution

More IPv4 questions