GATE CS 2024 Set 1 — Question 58

NAT+2 / -0MediumLongest Prefix MatchNetwork Layer: RoutingComputer NetworksSubnetting & CIDRNetwork Layer: Addressing

Computer Networks → Network Layer: Addressing → Longest Prefix Match

Last updated 20 August 2026

Question

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.

Prefix	Next hop router
10.1.1.0/24	R1
10.1.1.128/25	R2
10.1.1.64/26	R3
10.1.1.192/26	R4

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 _______

Correct answer

40 to 40

Solution

To determine the next hop router for each destination IP address, we apply the Longest Prefix Match (LPM) rule.

First, let's define the address ranges for each prefix in the forwarding table:

10.1.1.0/24: Addresses from 10.1.1.0 to 10.1.1.255 (Next hop: R1)
10.1.1.128/25: Addresses from 10.1.1.128 to 10.1.1.255 (Next hop: R2)
10.1.1.64/26: Addresses from 10.1.1.64 to 10.1.1.127 (Next hop: R3)
10.1.1.192/26: Addresses from 10.1.1.192 to 10.1.1.255 (Next hop: R4)

Now, we match each host IP address to the longest matching prefix:

1.10.1.1.16: Matches only 10.1.1.0/24. Best Match: R1.

2.10.1.1.72: Matches 10.1.1.0/24 and 10.1.1.64/26. The longest prefix is /26. Best Match: R3.

3.10.1.1.132: Matches 10.1.1.0/24 and 10.1.1.128/25. The longest prefix is /25. Best Match: R2.

4.10.1.1.191: Matches 10.1.1.0/24 and 10.1.1.128/25. (Note: 191 in binary is

10111111_2

, while the /26 prefix 192 is

11000000_2

, so it does not match R4). The longest prefix is /25. Best Match: R2.

5.10.1.1.205: Matches 10.1.1.0/24, 10.1.1.128/25, and 10.1.1.192/26. The longest prefix is /26. Best Match: R4.

The hosts whose packets are routed to R2 are 10.1.1.132 and 10.1.1.191.
Since there are 20 packets for each host, the total number of packets forwarded to R2 is:

20 \text{ (for 10.1.1.132)} + 20 \text{ (for 10.1.1.191)} = 40

GATE CS 2024 Set 1 — Question 58

Question

Correct answer

Solution

More questions on Network Layer: Addressing