CIDR Aggregation and the Reasons It Cannot Fully Summarize

The original IPv4 address plan divided the space into three classes by the top bits of the address: class A with eight bits of network, class B with sixteen, class C with twenty-four. An organisation needing more than 254 hosts and fewer than 65,534 had to take a class B, and a class B is one part in sixty-five thousand of the address space while being the smallest unit that could serve a network of that size. The plan exhausted the supply faster than the address count alone would suggest, because it forced allocation in units far larger than most requests. The fix, adopted in the early 1990s, was to stop treating the boundary as a class and start carrying it explicitly as a prefix length.

The class boundary was never a network boundary

Nothing in IP forwarding depends on classes. The header carries a full thirty-two-bit destination, and the lookup described in longest-prefix match and forwarding structures works on prefixes of any length. The class system was a convention for interpreting an address without an accompanying mask, and it survived because early routing protocols transmitted only addresses and relied on the class to derive the mask.

CIDR replaces the convention with an explicit length, written after a slash: 192.0.2.0/24 means the first twenty-four bits are the network part and the remaining eight identify hosts. The length is carried in routing protocol updates, so a router learns the mask along with the address and no longer guesses. Two consequences follow immediately. Any length from zero to thirty-two is legal, and the set of addresses covered by a prefix is a contiguous power-of-two block aligned to a multiple of its own size.

Alignment is the constraint that makes aggregation hard. A /24 can only start at a multiple of 256 in the address space. Two adjacent /24s, say 192.0.2.0/24 and 192.0.3.0/24, merge cleanly into 192.0.2.0/23, because 192.0.2.0 is even in the third octet and the pair is aligned. Two /24s that differ by more than one in the third octet cannot merge at all; the smallest prefix covering both includes addresses in between, which belong to someone else.

The merge test, stated precisely

Two prefixes of equal length L can be combined into one of length L-1 if and only if they differ only in the bit at position L-1, counting from the most significant end. In address terms, they must be adjacent and the lower one must be aligned to the larger block. Applied repeatedly, the test is what produces an aggregate.

import ipaddress

def can_merge(a: ipaddress.IPv4Network, b: ipaddress.IPv4Network):
    """True when a and b are siblings under one prefix of length len(a)-1."""
    if a.prefixlen != b.prefixlen or a.prefixlen == 0:
        return False
    shorter = a.prefixlen - 1
    return (a.supernet(new_prefix=shorter) ==
            b.supernet(new_prefix=shorter))

for lo, hi in [("192.0.2.0/24", "192.0.3.0/24"),
               ("192.0.2.0/24", "192.0.4.0/24")]:
    a, b = ipaddress.ip_network(lo), ipaddress.ip_network(hi)
    print(lo, hi, can_merge(a, b))

The first pair merges to a /23. The second does not, and no amount of recursion fixes it: the smallest prefix that covers both is a /21, running from 192.0.0.0 through 192.0.7.255, which includes 192.0.0.0/24, 192.0.1.0/24, 192.0.3.0/24 and others the pair does not own. Announcing that /21 would black-hole or misroute those addresses, so the only honest announcements remain the two separate /24s.

This is the arithmetic that makes an address plan either aggregatable or not. Allocating contiguous, aligned blocks to a customer and to that customer’s downstream networks means the customer can announce one prefix upstream. Allocating from whatever happens to be free means the customer announces a scattered set, and every one of those entries occupies a slot in every router’s table on the path. The size of the global table is therefore a function of allocation discipline, not of the number of networks.

Holes, and the decision to punch them

A provider holding a /20 may have delegated one /24 inside it to a customer who then moved to a different provider but kept the addresses. The provider can no longer announce the /20 alone, because traffic for that /24 must go elsewhere. It has two choices, both bad in different ways.

The first is to announce the /20 and accept that the delegated /24 is unreachable through it, relying on the customer’s new provider to announce the more specific route. Longest-prefix match then delivers those addresses correctly to the new path, and the /20 carries everything else. This works exactly as long as the more specific announcement exists. If the customer’s new provider stops announcing, traffic for the hole falls back to the /20 and disappears into a network that no longer has a route for it. The hole becomes a black hole.

The second is to deaggregate: announce the /20 minus the hole as a set of smaller prefixes. Removing one /24 from a /20 requires four prefixes, one for each level between the two lengths, because at every step from the /24 upward the surviving sibling can be announced as a block. The general rule is that punching a hole of length L out of a prefix of length M costs at most L minus M announcements. The table grows by a small multiple for that one delegation, and by a small multiple again for every other hole in the same aggregate. Providers generally accept the first choice and rely on the more specific route, which is why the global table contains many pairs of overlapping prefixes.

The practical lesson is that a prefix in the table is not a summary of reachability. Reachability is the union of the most specific matches, and any aggregate is a claim about the addresses it covers that a more specific route can contradict.

Multi-homing and the impossibility of one route

An organisation connected to two providers would like to announce one prefix and have both links used. It cannot, because a single prefix announced identically on both links gives every remote router two equal paths to the same destination, and the routing system picks one. The other link carries nothing inbound. This is not a defect of any particular protocol; it follows from the destination-based forwarding model, where a router’s decision depends only on the destination address and not on which of several equally good paths is less loaded.

The usual workaround is to announce a more specific prefix from one link, so that some fraction of the address space prefers one path and the rest prefers the other. Splitting a /22 into two /23s announced from different providers gives a coarse form of load sharing at the cost of doubling the table entries for that organisation. Splitting further gives finer control and a larger table. The global table’s growth has tracked this incentive as much as it has tracked the number of connected networks.

A second workaround is to accept asymmetric paths: announce the same prefix on both links and let inbound traffic arrive on whichever the remote routers prefer, while outbound traffic follows local policy. The result is that return traffic may traverse a different path than forward traffic, which breaks any middlebox that expects to see both directions and complicates troubleshooting, since the two directions must be traced separately. Local policy is what selects the outbound direction in that arrangement, and the mechanism for expressing it is covered in policy routing with multiple tables.

Renumbering and the lifetime of an allocation

CIDR made addresses scarce enough to be worth keeping, and that changed the operational model. Before classless allocation, an organisation that changed providers could be given a new block and renumber, because blocks were plentiful relative to demand. After it, addresses are a finite resource allocated through a registry hierarchy, and an organisation that moves keeps its block and expects the new provider to route it. That expectation is what produces the provider-independent prefix, which cannot be aggregated into any provider’s block and therefore occupies its own entry everywhere.

The registry structure itself is classless: allocations are made in power-of-two blocks from the space each registry holds, and the records state the prefix length. The alignment rule applies at every level, so a registry with a /12 free can only delegate aligned /16s or smaller blocks within it. Fragmentation of a registry’s free space is a permanent cost, because merging two adjacent free blocks back into a larger one is possible only under the sibling test above, and the pieces left after years of allocation rarely satisfy it.

What aggregation cannot do

Aggregation reduces the number of entries a router must store, and it does nothing for the correctness of the decision. A router that receives only aggregates forwards correctly for the addresses they cover and incorrectly for any address that a more specific route would have handled. The mechanism’s value is entirely in the assumption that the aggregates are true summaries, and every operational practice around route filtering exists to check that assumption.

The other limit is arithmetic. A prefix of length L covers 2^(32-L) addresses. The set of all prefixes is not a partition; it is a lattice in which every prefix is contained in exactly one prefix of each shorter length. There is no assignment of addresses to networks that makes the table small if the networks are not themselves contiguous, and no protocol can recover contiguity that the allocation did not provide.