Avoiding the Routing Explosion

Fifteen years ago, a change to the way IP addresses were assigned was the first major step taken to combat the problem "the Internet is rapidly running out usable IP addresses". You hear that problem still talked about today as one of the reasons to adopt IPv6, which has been very slowly increasing in usage over the past nine years. The change I'm talking about though is the adoption of classless routing between domains. The reason that classless routing was adopted relatively quickly is that it solved not only the problem of running out of usable addresses but also a more urgent problem at the time of routers running out of memory.

The original allocation of IP addresses used three fixed-size classes to split up the 32-bit address space. There was a range of addresses that were class A addresses (having 24 bits of address space), a range of addresses that were class B addresses (having 16 bits of address space), and a range of addresses that were class C addresses (having 8 bits of address space).

The problem with this class approach was both that address assignments were typically wasteful as well as having no way of performing routing besides knowing about every single active class. To avoid assigning an entire class B address to an organization with only 800 machines, you had to make active routing entries for several class C addresses. It was a tradeoff between being so wasteful with addresses that you would run out or advertising so many routing entries that routers would fail.

The solution to this problem used a technique called variable-length masking to both subdivide and aggregate the existing classes. Variable-length masking allows a route to be advertised for any number of contiguous significant bits rather than just 8, 16, or 24. An organization might be assigned a 10-bit address space instead of a 16-bit address space to use with 800 machines. However, while avoiding waste with less hassle than using multiple class C addresses, you would still have an explosion of routes if every organization's allocation had to be advertised.

Combined with variable-length masking was the assignment of large contiguous blocks to service providers. Service providers could subdivide their blocks into smaller contiguous regions for subscribers without having to advertise the individual small blocks. These smaller blocks could then be divided and redivided as necessary as long as the allocations were always kept contiguous. This allowed routing across the Internet to work without having to know about a whole bunch of routes. You only needed to know about one level of detail within your block as well as the biggest blocks in the world, both of which could have reasonable limits in quantity.