Forwarding tables & Longest Prefix Match (LPM)

1. Can four /24 blocks starting at 192.168.4.0/24 be aggregated into a single /22?
   Stuck? Peek at 3.1.4 CIDR notation (/n), block size, alignment & route aggregation

   • CIDR a.b.c.d/n: n prefix bits, h = 32 − n host bits, block size N = 2ʰ.
   • Alignment rule: first address must be divisible by 2ʰ (for /(24−k), 3rd octet must be divisible by 2ᵏ).
   • Supernetting: 2ᵏ contiguous, aligned /n blocks merge into one /(n − k) block.

   Read lesson 3.1.4

2. How do you test whether IP address D matches a subnet with network address N and mask M?
   Stuck? Peek at 3.1.3 Subnet masks, subnetting, network/broadcast & usable hosts

   • Borrow s bits from host field, leaving h bits → 2ˢ subnets, each with 2ʰ − 2 usable hosts.
   • Subnet address = IP AND Mask; Broadcast = host bits all 1s.
   • Stride Δ = 256 − Mask octet: blocks start at 0, Δ, 2Δ, … and end at Δ−1, 2Δ−1, ….
   • Valid mask octets: 128, 192, 224, 240, 248, 252, 254, 255.

   Read lesson 3.1.3

3. In datagram packet switching, how does a router decide which outgoing link to use for an arriving packet?
   Stuck? Peek at 1.2.2 Packet switching: store-and-forward, datagrams, statistical multiplexing

   • Packet switching: packets with headers; no reservation; full link rate while sending.
   • Store-and-forward: receive whole packet → buffer/queue → forward; full buffer → loss.
   • Datagram: each packet routed independently; may reorder; robust to failures.
   • Statistical multiplexing: share capacity on demand; P(exactly k of n) = C(n,k)pᵏ(1−p)ⁿ⁻ᵏ.

   Read lesson 1.2.2

Suppose ISP-A owns the aggregated block 200.150.0.0/16, so every router in the world points 200.150.0.0/16 to ISP-A. Then a small customer owning 200.150.68.0/22 switches to ISP-B while keeping their IP addresses! Now a packet for 200.150.70.15 matches both 200.150.0.0/16 (ISP-A) and 200.150.68.0/22 (ISP-B).

To send the packet to the right place, every IP router obeys one golden rule: Longest Prefix Match (LPM) — one of the highest-yield numerical topics in all of GATE CSE.

You are sorting mail. One bin says "All of Tamil Nadu (600xxx)" and another bin says "IIT Madras Post Office (600036)". A letter arrives for PIN 600036. It matches both bins — which bin do you drop it into, and why?

The IIT Madras (600036) bin, because it is more specific (matches 6 digits instead of 3). In IP forwarding, the entry with the largest prefix length /n is the most specific match.

Anatomy of a Forwarding Table

Every router maintains a forwarding table. Each row contains:

• Destination Prefix / Mask (e.g. 200.150.68.0/22)
• Next-Hop IP (the IP address of the next router's interface along the path, or "direct" if attached)
• Outgoing Interface (e.g. E0, E1, m0 — the physical link out of which the frame is sent)

The Longest Prefix Match (LPM) Rule

Trap alert: A longer prefix is chosen only if it actually matches D! Always filter for matching rows first, then pick the longest /n.

The Default Route: 0.0.0.0/0

What if a packet's destination IP does not match any specific prefix in the router's table? Rather than storing millions of prefixes, stub and enterprise routers add a default route written as 0.0.0.0/0 (mask 0.0.0.0, prefix length n = 0).

Because (D AND 0.0.0.0) is always 0.0.0.0, the default route matches every IPv4 address — but since its prefix length is 0 (the shortest possible), LPM picks it only when no other row matches!

Putting it together

• A router forwarding table maps destination prefixes to next-hop IPs and outgoing interfaces.
• When multiple prefixes match a destination IP, Longest Prefix Match (LPM) picks the most specific match (largest /n).
• The default route 0.0.0.0/0 matches every IP with prefix length 0, acting as the fallback when no specific prefix matches.

• Never pick the longest prefix without checking if it matches! In Example 3(ii), /26 is the longest prefix in the table, but 200 lies outside 128..191, so /25 wins.
• Default route mask is 0.0.0.0, NOT 255.255.255.255! ANDing with 0.0.0.0 produces 0.0.0.0 for every IP.
• If no entry matches and there is NO default route 0.0.0.0/0, the router drops the packet.

Filter by MATCH first; crown the LONGEST /n among the survivors!

Now we know how routers use variable prefix lengths to aggregate and forward packets. Next question (3.1.6): When a network engineer is handed one CIDR block like 192.168.1.0/24 and needs subnets of different sizes (say 100 hosts, 50 hosts, and 10 hosts), how do we carve it up without overlaps or wasted space?

1. MCQ

   What is the CIDR notation and subnet mask of the default route in an IPv4 forwarding table?

   1. 0.0.0.0/0, mask 0.0.0.0
   2. 255.255.255.255/32, mask 255.255.255.255
   3. 0.0.0.0/32, mask 255.255.255.255
   4. 127.0.0.1/8, mask 255.0.0.0
2. MCQ

   A forwarding table has entries: R1: 10.1.0.0/16 → E0, R2: 10.1.16.0/20 → E1, R3: 10.1.20.0/22 → E2, R4: 0.0.0.0/0 → E3. Which interface is selected for destination 10.1.25.10?

   1. E0
   2. E1
   3. E2
   4. E3
3. MSQ

   For the same table (R1: 10.1.0.0/16 → E0, R2: 10.1.16.0/20 → E1, R3: 10.1.20.0/22 → E2, R4: 0.0.0.0/0 → E3), which of the following destination-to-interface mappings are CORRECT?

   1. 10.1.22.5 → E2
   2. 10.1.32.5 → E0
   3. 10.1.19.255 → E1
   4. 10.2.1.1 → E0
4. NAT

   A packet with destination 192.168.10.130 arrives at a router with three matching entries of prefix lengths /16, /24, and /25. What is the prefix length (number after the slash) of the route chosen by the router?

   Write your answer before opening the key.

• Match condition: Row N/n (mask M) matches destination D iff (D AND M) == N (i.e. D falls in [N .. N + 2³²⁻ⁿ − 1]).
• Longest Prefix Match (LPM): Among all matching rows, pick the one with the largest prefix length n.
• Default route 0.0.0.0/0: matches every address with n = 0 (used only if nothing else matches).

• forwarding table
• next hop
• outgoing interface
• longest prefix match (LPM)
• default route 0.0.0.0/0

1. What is the Longest Prefix Match (LPM) rule?
   Reveal answer

   Among all forwarding table entries whose prefix matches the destination IP, select the entry with the greatest number of leading 1s (largest /n).
2. Why does the default route 0.0.0.0/0 never override a matching /16 or /24 route?
   Reveal answer

   Because its prefix length is n = 0, which is strictly smaller than any specific prefix length n ≥ 1.
3. Fastest way to solve a GATE LPM question?
   Reveal answer

   Write the address range [start .. end] of each row, test from longest /n down to shortest /n, and stop at the first range that contains the destination IP.

• Test Longest-First Strategy: Sort candidate rows in your head from largest /n to smallest /n; the first one whose range contains the destination IP is the answer! — solving GATE LPM table questions in half the time.
• Range method over Bitwise AND: Convert each row into its octet interval [start .. start + Δ − 1]; interval membership is faster and less error-prone than binary ANDing. — any LPM question with 3–5 rows.