A Spoonful Of CIDR Helps the Routing Tables Go Down

In 1990, things looked grim for the Internet as routers sagged under the weight of an exploding address space. Learn how CIDR saved the day, and how it can help you deal with your own growing network.

In 1990, the situation for the Internet looked bleak. "The World" (www.world.std.com) became the first Internet Service Provider (ISP) open to the public. ARPANET, the project giving birth to the Internet was spinning down; and NSFNET, the new backbone provider, was about to start allowing commercial use on-line. Universities, government agencies, and businesses were adding their isolated campus networks into the larger interconnected Internet. E-mail was the champion of the day, with FTP closely behind in popularity. Microsoft Windows 3.0 was allowing businesses of all sizes access to new services, connecting even more people to the budding new network. The biggest event of the year, though, was Tim Berners-Lee demonstrating "WorldWideWeb," the first GUI "Web" browser.

While all of these events pointed toward the Internet exploding in popularity, the underlying flawed structure of IP address allocation and routing was moving the Internet toward exploding in an altogether nasty way. Network engineers were predicting the total collapse of the Internet by 1995, when routing tables would be too large to be handled by the technology of the day. And besides, even if the routers could handle the load, there would be no more IP addresses to give out. The Internet of the early 1990s was simply not designed to be the Next Big Thing.

As we'll see, getting into this mess then getting out of it saved the 'net, and what we learned can help you manage your network today.

It became clear in the old ARPANET days that a hierarchical routing approach would be needed for a global network. Hierarchical routing allows for separate routing layers to be used, and gives engineers more flexibility in allocating resources. Think about a phone number. By having the first three numbers define a particular area code or prefix, the seven digits after could repeat themselves in each individual area. 503-555-1234 is just as valid as 812-555-1234.

The Internet Engineering Task Force (IETF) knew that networks were going to be various sizes with a few very large networks and many small ones. With that in mind, the "Area Code" sizes of the Internet were broken down in to three separate categories; Class A , Class B, and Class C. Like population distribution in most countries, IETF expected a few very large metropolitan areas (Class A), a handful of cities (Class B), and many small towns (Class C).

In networking, the human readable decimal IP address (10.0.0.1) is transformed into a series of four 8-bit binary strings or octets; such as 00001010.00000000.00000000.00000001. (Eight 1s in binary equals 255, the highest number you will ever see in an octet.) The four octets described in binary form is what your IP address looks like on the network. The first three bits of the first octet, or most significant bits were used to encode the class. Class A started with binary 000 (0.0.0.0 is reserved for special purposes.),Class B started with 010, and Class C started with 110.

This mathematically elegant approach created the following network breakdown:

[000]00000

16,777,214   

50%

[010]00000

65,534

25%

[110]00000

254

12.5%

(Note this only accounts for 87.5% of the total IP space. "Class D" or 11100000, was reserved and is now used for multicast space which is why all multicast addresses start above 224.0.0.0)

While this was good for an initial estimate of how addresses would be used, the reality of the Internet was moving toward many more small networks "towns" than large "metropolises." And with half of the total address space wrapped up in only 126 mega networks, there was a lot of wasted space. The arbitrary network sizes made it difficult for universities and companies to get the right amount of space. If a company only needed 8,000 addresses, there was a difficult choice between a very limited and expensive class B network, wasting another 8,000 addresses, or purchasing and attempting to administer 32 separate class C addresses.

If the company in the example above went with the cheaper class C option, that company would be part of the second major issue extremely large and unwieldy routing tables. Our company would need to "inject" 32 separate router entries into the Internet core for just one location. Border Gateway Protocol (BGP), the protocol behind the Internet, would need to update every router that touched the Internet when any of those 32 separate class C entries went down. In the early 1990s, volatile RAM to handle the large tables was extremely expensive and computing capabilities of CPUs running routers was simply not up to handling the constant changes (or "router flaps") from these small networks constantly going up and down.

The Internet was doomed to collapse under its own weight before the first eBay auction could even be conceived.

Continued on page 2: CIDR to the Rescue

Continued From Page 1

In September of 1993, RFC 1519 laid out a new direction in network architecture, called Classless Inter-Domain Routing. The idea, proposed by network engineers from the Bay Area Regional network (BARRNet), Cisco, and the Michigan Educational Research Information Triad (MERIT) was to simply do away with the "classful" breakdown of deploying networks and rely on the already well understood subnet mask to handle the heavy lifting.

Traditionally, subnetting is the component of IP networking that allows further hierarchical breakdowns of an IP space. If the three most significant bits of an IP address are compared to the area code, then the subnet mask is analogous to the phone prefix, or the 555 portion of 503-555-1234. For example 129.0.1.0/255.255.255.0 lets us know we are dealing with a Class B network (based on most significant bits in first octet) and the space is subnetted at the third octet. The administrator can have separate subnets using the "two to the sixteen" subnets available (every possible combination in the second and third octets) for about 65,535 possibilities.

If a computer has a class B source IP address (129.0.0.1) and a network mask (255.255.255.0), it knows to look at the first three octets only for differences in a destination network and identify if it were on the same subnet (129.0.0.2) or on a different subnet (129.0.1.2). If the destination is on the same network, the computer sends the IP packet along. If the destination address is on a different subnet, the computer simply sends the IP packet along to the default gateway for the subnet. The router handles the rest.

What the creators of RFC1519 were proposing was permitting administrators to go beyond simple subnetting, and gain the ability to do "supernetting": Using any subnet or supernet mask possible, not just classic 255.0.0.0, 255.255.0.0, and 255.255.255.0. This supernetting along with variable length subnet masking (or VLSM) fixed both the IP space allocation and the routing table issue.

The IP space allocation problem was diminished because the Internet Assigned Numbers Authority (IANA) was no longer constrained to classful deployment of address spaces. Instead of having half of the entire IP space reserved for massive Class A networks, those spaces could be chopped up into smaller more usable sizes. CIDR, along with Network Address Translation (NAT, proposed in RFC 1631 in 1994), made it possible for IPv4 addressing to survive almost ten years past the point where all addresses would have been unavailable. While engineers are still concerned about address allocation and migrating to the new and expansive IPv6 (which uses a 128-bit address scheme rather than 32 bits of IPv4), they are no longer warning of an address catastrophe.

The routing table size issue was also resolved by CIDR and VLSM. Supernetting gives administrators a mask to represent multiple networks with a single routing entry.

For example, if you ran an ISP and were allocated 194.50.0.0, you could dole out subnets to your customers (194.50.1.0 to company A, 194.50.2.0 to company B, etc.) and inject 194.50.0.0/255.255.0.0 into the BGP tables to represent all of your networks. VLSM enables you to purchase only half of that space, for example 194.50.0.0/255.128.0.0, which means you would own 194.50.0.0 to 194.50.127.0. The 194.50.128.0 to 194.50.254.0 range could be sold to another company. The ability to summarize multiple subnets with one supernetted address and mask drastically reduced the sizes of routing tables globally. While the sizes of the tables are increasing again, memory and CPU technology is now sufficiently advanced to handle the slower growth.

VLSM is not just useful for major ISPs and Fortune 500 companies. An administrator with more than one subnet can use VLSM to utilize his or her allocated space more efficiently. Consider the example map below:

The ISP assigns you 100.1.50.0 with a subnet mask of 255.255.255.128. You now own the lower half of the 100.1.50.0 network, up to 100.1.50.127.0. You can then further break down your networks as follows:

You'll notice that the maximum number of hosts is two shy of the total possible addresses. This is because the first available number designates the network, and the last possible number is the special "all hosts" broadcast address for that subnet. When you are setting up your VLSM spaces, it is best to double the number of hosts on each subnet and use that as your target maximum hosts number. That way you can allow for proper expansion. Finally, the "point-to-point" link for the ISP net really only requires a single address for each "point." You are effectively wasting 27 IP addresses. To fix this, you could further sub-divide the 100.1.50.0/255.255.255.224 subnet.

There are many great free "IP address calculators" available which can help you work through the details of setting up your network. Routers across the board support VLSM as a standard feature. When figuring out how IP addresses you need for your clients, don't forget that one of the addresses in the range needs to be reserved for the router gateway.

CIDR and VLSM together not only saved the Internet from completely failing, they can also be a useful tool for you to more effectively manage your own company's address space!