CIDR and Hierarchical Address Aggregation

A CIDR address is written as `a.b.c.d/n`, where `a.b.c.d` is a 32-bit IPv4 address and `n` is the prefix length — the number of leading bits that identify the network, with the remaining `32 - n` bits identifying hosts within it. This single notation subsumes the old class system: a "Class C" network is just a `/24`, a "Class B" is a `/16`, but crucially `n` can be any value from 0 to 32, not just 8, 16, or 24. A block `192.168.16.0/20` covers all addresses whose top 20 bits match `192.168.16.0`, i.e., the contiguous range `192.168.16.0`–`192.168.31.255`, containing `2^12 = 4096` addresses. The forwarding consequence of variable-length prefixes is longest-prefix match. A router's forwarding table is a set of (prefix, next-hop) pairs. Given a destination address, more than one prefix may match — a `/8`, a `/16`, and a `/24` route can all legitimately cover the same address, representing routing information at different granularities (a broad default region, a specific customer network, a specific sub-office). The router is required to select the entry with the longest matching prefix, because it is the most specific, most authoritative statement about how to reach that address. This is the rule that lets a general aggregate route (e.g., an ISP's `/16` announcement) coexist with a more specific `/24` for a multihomed customer without either one making the other unreachable.

Route aggregation (summarization, supernetting) is the deliberate act of replacing several contiguous, equally-routed prefixes with one shorter prefix that covers them all. If a service provider owns `200.24.0.0/24` through `200.24.7.0/24` (eight contiguous `/24` blocks, all reached via the same next hop), it can advertise the single aggregate `200.24.0.0/21` instead of eight separate routes. This is the mechanism, hierarchical summarization, that keeps the global routing table from growing linearly with the number of individually addressed subnets in the world — the same structural idea used in postal codes, telephone numbering plans, and file-system directory trees.

Step 1 — Prefix matching test. A prefix `P/n` matches address `A` if the top `n` bits of `A` equal the top `n` bits of `P`. Equivalently, using a network mask `M` with `n` leading 1-bits, `A` matches `P/n` iff `(A AND M) == (P AND M)`.

Step 2 — Longest-prefix-match lookup. Given a table of prefixes and a destination address, find all matching prefixes and select the one with the largest `n`. Ties cannot occur among distinct prefixes of the same length pointing at the same address space (they would be duplicate/conflicting routes, which is a configuration error, not a normal case).

Step 3 — Aggregation (supernetting). Given a set of contiguous prefixes that share a next hop, replace them with the shortest common prefix that exactly covers their union — but only if that union is exactly representable as a single CIDR block (contiguous range whose size is a power of two and whose start address is aligned to that size). ``` function longest_prefix_match(table, dest_addr): best_len = -1 best_route = null for (prefix, mask_len, next_hop) in table: network_mask = make_mask(mask_len) # top mask_len bits = 1 if (dest_addr AND network_mask) == (prefix AND network_mask): if mask_len > best_len: best_len = mask_len best_route = next_hop if best_route == null: return DEFAULT_ROUTE # e.g., 0.0.0.0/0 if present return best_route

function can_aggregate(prefix_list, n):

# prefix_list: n contiguous /k blocks with the same next hop,

# sorted by address. Check whether they merge into one /(k-1) block. if n != 2: return false (p1, k1, h1) = prefix_list[0] (p2, k2, h2) = prefix_list[1] if k1 != k2 or h1 != h2: return false block_size = 2^(32 - k1) if p2 != p1 + block_size: return false # must be immediately adjacent if (p1 mod (2 * block_size)) != 0: return false # must be aligned for a /(k1-1) return true # aggregate is p1/(k1 - 1)

function aggregate_table(routes):

# Iteratively merge pairs of sibling blocks bottom-up (like building

# a binary trie and collapsing subtrees with identical next hops). changed = true while changed: changed = false sort routes by (prefix_address, mask_len) for i in 0 .. len(routes) - 2: if can_aggregate([routes[i], routes[i+1]], 2): new_prefix = routes[i].prefix new_len = routes[i].mask_len - 1 replace routes[i], routes[i+1] with (new_prefix, new_len, routes[i].next_hop) changed = true break return routes ``` The lookup routine above is the specification of longest-prefix match; real routers do not scan the table linearly (that would be O(number of routes) per packet). Instead they build a data structure — most commonly a multibit trie or a hardware Ternary Content-Addressable Memory (TCAM) — that answers the same query in time independent of table size for practical purposes. A binary trie encodes each prefix as a root-to-node path following its bits; a lookup walks the trie bit by bit from the root, remembering the last node marked "route present" (the deepest such marker is the longest match, by construction of the trie). Multibit tries examine several bits per step to cut the number of memory accesses, trading some extra memory for fewer probes.

The trie diagram shows the essential correctness argument visually: a walk from the root following the destination address's bits passes through every node whose prefix matches that address (by definition of "prefix" as a bit-string that is a prefix of the address). The deepest such marked node encountered on that walk is exactly the longest matching prefix, so a single root-to-leaf traversal — of length at most 32 for IPv4 — finds the LPM answer without ever comparing against unrelated prefixes.

Correctness of longest-prefix match via a trie. Represent each prefix `P/n` as a path of `n` edges from the root, labeled by the bits of `P`, with a marker at the terminal node recording the associated route. Claim: for a destination address `A`, the set of prefixes matching `A` is exactly the set of markers found along the unique root-to-depth-32 path determined by `A`'s bits. Proof. A prefix `P/n` matches `A` iff the first `n` bits of `A` equal the first `n` bits of `P`. In the trie, the node at depth `n` reached by following `A`'s first `n` bits is, by construction, the same node that `P/n`'s marker sits on exactly when those bit-strings agree — i.e., exactly when `P/n` matches `A`. So walking the trie along `A`'s bits visits precisely the nodes corresponding to matching prefixes, and the deepest marked node on that walk is the longest match. ∎ Since ties in prefix length between distinct markers cannot coexist at the same trie node (a node's marker is unique), the longest match is well-defined whenever at least one prefix matches; a default route `0.0.0.0/0` guarantees at least one match always exists.

Time complexity.

• Naive linear scan (as in the pseudocode's spec version): `O(R)` per lookup, where `R` is the number of routing-table entries. This is the "obviously correct, obviously too slow" baseline — with `R` in the hundreds of thousands on a backbone router and lookups needed at line rate (tens to hundreds of millions of packets/second), linear scan is infeasible.
• Binary trie: `O(W)` per lookup, where `W = 32` (or 128 for IPv6) is the address width, independent of `R`. Insertion/deletion of a prefix is also `O(W)`.
• Multibit trie (stride k): `O(W/k)` memory probes per lookup, at the cost of `O(2^k)` children per node — a classic time–space trade governed by the stride `k`.
• TCAM hardware: effectively `O(1)` per lookup (one parallel associative-memory cycle), at the cost of specialized, power-hungry, expensive memory whose capacity limits table size.

Space complexity. A trie over `R` prefixes has `O(R · W)` nodes in the worst case (each prefix contributes a path of up to `W` edges, though shared prefixes share ancestor nodes), so space is `O(R·W)` in the worst case, typically much less in practice due to prefix-sharing.

Correctness and benefit of aggregation. Aggregating `2^k` contiguous, aligned `/n` blocks that share a next hop into one `/(n-k)` block is correct precisely because CIDR matching is bitwise-prefix-based: the union of all addresses matching any of the `2^k` sibling blocks is exactly the set of addresses matching the shorter, shared prefix of length `n-k` — no more, no less. This is a set-theoretic identity, not an approximation: if the `2^k` blocks are the full set of children sharing a common `(n-k)`-bit ancestor prefix in the trie, their union is definitionally the address space of that ancestor. The efficiency payoff is table-size reduction: `2^k` entries collapse to 1, and — just as importantly for Inter-Domain Routing with BGP — a single change below the aggregation boundary (e.g., one constituent subnet flaps) does not need to be re-advertised past the aggregation point, cutting update/convergence traffic across the wider internet.

Honest tradeoff. Aggregation only helps when reachability and policy are uniform across the merged range. If even one constituent `/24` inside an aggregated `/21` needs a different next hop (e.g., it is multihomed to a different upstream, or traffic-engineered differently), the aggregate is either wrong (traffic to that sub-block is silently misrouted to the aggregate's next hop) or must be supplemented by re-advertising the specific `/24` — at which point you have both the aggregate and the more-specific route, and LPM correctly resolves it, but you no longer save that table entry. This tension — the fundamental reason the global routing table (over 900,000 IPv4 prefixes as of the early 2020s) is far larger than the "ideal" hierarchical count — is central to real-world BGP operations.

Suppose an ISP has allocated eight `/24` blocks to a downstream customer, all reached through the same next-hop router `R1`:

All eight share the top 21 bits (`200.24.0` through `200.24.7` differ only in the low 3 bits of the third octet: `000` to `111` — all 8 combinations present, contiguous, and aligned since `0 mod 8 == 0`). Applying `aggregate_table` repeatedly: `0` merges with `1` → `200.24.0.0/23`; `2` merges with `3` → `200.24.2.0/23`; then those two `/23`s merge → `200.24.0.0/22`. Symmetrically `4`–`7` collapse to `200.24.4.0/22`, and finally the two `/22`s merge into `200.24.0.0/21`. Eight table entries become one. Now trace a forwarding decision. Suppose the router's table (after partial aggregation, plus an unrelated default route and a more-specific customer override) looks like this:

Destination `200.24.5.37`:

• Matches `0.0.0.0/0` (length 0) — trivially, everything matches the default.
• Matches `200.24.0.0/21` (length 21): top 21 bits of `200.24.5.37` are `11001000.00011000.00000` (`200 = 11001000`, `24 = 00011000`, third octet `5 = 00000101`, top 5 bits `00000`) — compare against `200.24.0.0`'s top 21 bits, which are identical. Match.
• Matches `200.24.5.0/24` (length 24): top 24 bits of the destination are `200.24.5`, exactly equal to the prefix. Match.

Three candidates match; longest-prefix match selects the `/24` (length 24 > 21 > 0), so the packet correctly goes to R2, not R1 — demonstrating that a more-specific route always overrides an aggregate that would otherwise misroute it. Destination `200.24.2.130`, by contrast, matches only `0.0.0.0/0` and `200.24.0.0/21`; LPM selects the `/21`, sending it to R1, which is correct since that sub-block was never re-homed.

CIDR emerged from an engineering crisis: by 1992–1993 the classful IPv4 addressing scheme was projected to exhaust the routable address space and explode routing tables simultaneously, since a growing internet of small and mid-sized networks had to take Class C (`/24`) or Class B (`/16`) blocks with nothing in between, wasting addresses and multiplying table entries. The Internet Engineering Task Force formalized CIDR in RFC 1517–1520 (1993), driven substantially by the work of Vince Fuller, Tony Li, Kannan Varadhan, and Yakov Rekhter, building on earlier variable-length subnet mask (VLSM) ideas already used within individual organizations' networks.

Every internet backbone router performs longest-prefix match on every packet, making the trie/TCAM lookup structures described here some of the most performance-critical data structures in networked computing. Internet Service Providers rely on hierarchical address allocation — regional internet registries assign large blocks to ISPs, who sub-allocate to customers — precisely so that aggregation stays possible up the hierarchy; this is the addressing discipline that keeps the global BGP table from growing at the same rate as the number of end networks, a concern central to Inter-Domain Routing with BGP. CIDR notation itself (`/n` prefixes) is now the universal way subnets are described in cloud provider consoles (VPC CIDR blocks), firewall rules, and router configuration files. The scarcity that CIDR only partially alleviated is also the direct motivation for Network Address Translation (NAT), which lets many hosts share a single public address, and for the eventual, ongoing transition to IPv6, whose 128-bit address space applies the same hierarchical-aggregation philosophy at a scale meant to never again face exhaustion pressure.

Ask the tutor: How does BGP decide which aggregated prefixes to actually announce to neighboring autonomous systems, and what happens when two ASes disagree about aggregation boundaries?