DEV Community

Cover image for Behind Routing Tables: CIDR and the Longest Prefix Match Rule
Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

Behind Routing Tables: CIDR and the Longest Prefix Match Rule

#computernetworks #networking #systemdesign #softwareengineering

Behind Routing Tables: CIDR and the Longest Prefix Match Rule

The global Internet routing table currently exceeds 1,000,000 routes.

Yet a backbone router must inspect the destination IP address of an incoming packet, find the correct outgoing interface, and forward the packet in under 10 nanoseconds to sustain 100 Gbps line-rate throughput.

The scalability of the entire Internet rests on Classless Inter-Domain Routing (CIDR) and the Longest Prefix Match (LPM) algorithm.

1. CIDR and Route Aggregation (Supernetting)

Before 1993, IP addresses were bound to rigid classes:

  • Class A: /8 (16 million hosts)
  • Class B: /16 (65,536 hosts)
  • Class C: /24 (256 hosts)

Organizations needing 2,000 IPs were forced to request an entire Class B block, wasting 63,000 addresses. Furthermore, every network required its own routing table entry.

CIDR introduced variable-length subnet masks (/n). Upstream Internet Service Providers (ISPs) aggregate contiguous subnets into a single supernet route:

  • Instead of advertising sixteen separate /24 subnets, an ISP announces a single /20 prefix to the global BGP routing table.

2. The Overlapping Route Dilemma

Route aggregation inevitably creates overlapping routing entries:

Network Destination Subnet Mask Next Hop Interface
192.168.0.0 /16 eth0
192.168.1.0 /24 eth1
0.0.0.0 /0 (Default) eth2

Suppose a packet arrives with destination IP 192.168.1.55:

  • Bitwise AND with /16 yields 192.168.0.0 implies Matches eth0.
  • Bitwise AND with /24 yields 192.168.1.0 implies Matches eth1.
  • Bitwise AND with /0 yields 0.0.0.0 implies Matches eth2.

3. The Longest Prefix Match Rule

When a packet destination matches multiple routes, the router forwards the packet out the interface associated with the longest prefix length (the most specific route).

In our example, /24 has 24 matching network bits, compared to 16 bits for /16. The router selects eth1.

Hardware Implementation:

Software linear search across 1,000,000 routes is too slow. Modern core routers use:

  • Patricia Tries / Radix Trees: Hierarchical prefix trees traversed bit by bit.
  • Ternary Content Addressable Memory (TCAM): Specialized associative hardware that searches all 1,000,000 prefixes in parallel in a single clock cycle (<5ns).

Explore full IP networking architectures and subnetting calculators at Binary Dose.

Top comments (0)