Early registration models

In the 1980s, the American National Science Foundation's (NSF's) high-speed network, NSFNET, was connected to the ARPANET, a US Department of Defense Advanced Research Projects Agency (ARPA, now DARPA) wide-area network, which essentially formed the infrastructure that we now know as the Internet.

From these early days of the Internet, the task of assigning addresses was a necessary administrative duty, to ensure simply that no two networks would attempt to use the same network address in the Internet. At first, the elementary task of maintaining a list of assigned network addresses was carried out voluntarily by Jon Postel, using (according to legend) a paper notebook.

As the Internet grew, and particularly as classful addressing was established, the administrative task grew accordingly. The Internet Assigned Numbers Authority (IANA) was established, and within it the Internet Registry (IR). But as the task of the IR outgrew Dr Postel’s notebook, it was passed to SRI International in Menlo Park, California, under a NSF contract, and was called the Defense Data Network (DDN) Network Information Center (NIC).

During this time, under the classful address architecture, networks were allocated liberally and to any organization that fulfilled the simple request requirements. However, with the accelerating growth of the Internet during the late 1980s, two problems loomed: the rapid depletion of address space, due to the crude classful divisions; and the uncontrolled growth of the Internet routing table, due to unaggregated routing information.

Conservation vs. Aggregation

The problems of three sizes fit all highlight the basic dilemma of address space assignment: conservation versus aggregation. On the one hand, one wants to conserve the address space by assigning as little as possible; on the other hand, one wants to ease routing table pressures by aggregating as many addresses as possible in one routing table entry.

This can be illustrated by looking at a typical networking set-up of the time. Within organizations having a single Internet connection, buildings, departments, or campuses would have their own local networks. Often the use of multiple networks was dictated by distance limitations inherent in the emerging local area networking technologies, such as Ethernet.

These networks typically had to accommodate more than the 254 hosts addressable by a class C address, but would rarely exceed 1,000 hosts. Using pure classful addressing one could either subdivide networks artificially to remain below the 254 host limit, or use a class B address for each local network, possibly wasting more than 60,000 addresses in each. While the latter solution is obviously wasteful in terms of address space, the former is obviously cumbersome. Less obviously, the former also puts an additional burden on the Internet routing system, as each of these networks would require a separate route propagated throughout the whole Internet.

This basic dilemma persists to this day. Assigning address space generously tends to reduce the routing table size but wastes address space. Assigning conservatively will waste less, but it causes more stress for the routing system.

Subnetting

In order to address some of the problems of classful addressing, the technique of subnetting was invented. Described in RFC 791 in 1984, subnetting provided another level of addressing hierarchy by inserting a subnet part into the IP address between the network and local parts. Global routing remained the same using the network part of the address (class A, B, or C) until traffic reached a router on the network identified by the network part of the address. This router, configured for subnetting, would interpret a statically configured number of bits from the local part of the address (the subnet part) to route the packet further along a set of similarly configured routers. Once the packet reached a router connected to the destination subnet, the remaining bits of the local part would be used to determine the destinations local address as usual. So, in the previous example, the organization could have used a class B address with 6-bit subnetting, which would allow for 62 networks of 1,022 hosts each.

Subnetting nicely solved the routing table problem, since now only one global routing table entry was needed for the organization. It also helped address space conservation somewhat because it provided an obvious alternative to using many sparsely populated class B networks.

Since the boundary between the subnet part and the local part of an address could not be determined from the address itself, this local knowledge needed to be configured into the routers. At first, this was done by static configuration. Later, interior routing protocols carried that information. RFC 791 may be referred to for a number of historically interesting case studies.

Supernetting

Within seven years, however, it was becoming clear that subnetting was no longer sufficient to keep up with Internet growth. RFC 1338 stated the problem:
As the Internet has evolved and grown … in recent years, it has become painfully evident that it is soon to face several serious scaling problems. These include:

1. Exhaustion of the class-B network address space. One fundamental cause of this problem is the lack of a network class of a size which is appropriate for mid-sized organization; class-C, with a maximum of 254 host addresses, is too small while class-B, which allows up to 65534 addresses, is to large to be widely allocated.
   
   
2. Growth of routing tables in Internet routers beyond the ability of current software (and people) to effectively manage.
   
   
3. Eventual exhaustion of the 32-bit IP address space.

It has become clear that the first two of these problems are likely to become critical within the next one to three years.

The solution proposed was to extend the subnetting technique beyond the local organization into the Internet itself. In other words, RFC 1338 proposed abolishing classful addressing, replacing it with supernetting. The proposal was summarized as follows:

The proposed solution is to hierarchically allocate future IP address assignment, by delegating control of segments of the IP address space to the various network service providers.

CIDR

In 1993, the supernetting technique was published as a standards track RFC under the name Classless Inter-Domain Routing (CIDR), by which it is known and used today. Two main ingredients were necessary to make CIDR work: routing system changes and new address allocation and assignment procedures.

Under CIDR, routers could no longer determine the network part of an address from the address itself. This information now needed to be conveyed by Internet routing protocols. Fortunately, there was only one such protocol in widespread use at the time, and it was quickly extended by the major router vendor of the time. According to legend, the necessary extensions of BGP-3 to BGP-4 were designed on a napkin, with all implementors of significant routing software present. The changes were implemented in a matter of days, but only much later described by the Internet standards track RFC 1654.

CIDR also required that forwarding decisions of routers be changed slightly. The network part of an address, now more generally called the prefix, can be of any length. This means that a router can have multiple valid routes covering a specific 32-bit destination address. Routers need to use the most specific of these routes the longest prefix when forwarding packets.

In additional to technical changes, the success of CIDR also relied on the development of administrative procedures to allocate and assign address space in such a way that routes could be aggregated as much as possible. Since the Internet was evolving towards the current state of arbitrarily interconnected networks of Internet Service Providers (ISPs), it was obvious that ISPs should play a role in address space distribution. In the new technique, ISPs would now, as much as possible, assign address space to their customers in contiguous blocks, which could be aggregated into single routes to the rest of the Internet.