In the early 1990's the IETF realized that the classful "3 sizes fit all" (Class A, B and C) allocation scheme was going to deplete all the remaining IPv4 addresses in a very short time indeed (maybe before the year 2000). At the time, the split between the address prefix (network number) and address suffix (interface identifier) could only be in one of three bit positions: 8, 16 or 24. The number of usable addresses is 2 raised to the number of bits in the suffix (32 - prefix length), minus two. Why minus 2? You can't assign the first suffix of a block (0 = "this network") or last suffix of a block (all ones = broadcast), as a node address.
The allocation scheme was "3 sizes fit all":
Prefix Length Blocks per /8 Usable Addresses per Block
8 1 16,777,214
16 256 65,534
24 65,536 254
If an organization needed more than 254 addresses, the next step up was 65,534. If an organization needed more than 65,534 addresses, the next step up was 16.7 million. Ooops. So, RFC 1519, "Classless Inter-Domain Routing (CIDR)", September 1993, allowed the split in the IP address between prefix and suffix to come anywhere from positions 8 to 30. Now we have lots of allocation block sizes, from "/8" (16.7M addresses) down to "/30" (2 usable addresses). We can fit the allocation size much more closely to the customers' needs than before. If they need more than 254 addresses, the next step up now is 510, not 65,534. If they need more than 65,534, the next step up is 131,070, not 16.7 million. Much better!
Here is the list of all possible allocation blocks sizes under CIDR, including how many CIDR allocation blocks could be made from a single /8 block, and how many usable addresses are in each allocation block. It also shows the subnet mask for a block of that size. Now instead of "3 sizes fit all", it is "23 sizes fit all":
Prefix Length Blocks per /8 Usable Addrs per Block Subnet Mask
8 1 16,777,214 255.0.0.0
9 2 8,388,606 255.128.0.0
10 4 4,194,302 255.192.0.0
11 8 2,097,150 255.224.0.0
12 16 1,048,574 255.240.0.0
13 32 524,286 255.248.0.0
14 64 262,142 255.252.0.0
15 128 131,070 255.254.0.0
16 256 65,534 255.255.0.0
17 512 32,766 255.255.128.0
18 1,024 16,382 255.255.192.0
19 2,048 8,190 255.255.224.0
20 4,096 4,094 255.255.240.0
21 8,192 2,046 255.255.248.0
22 16,384 1,022 255.255.252.0
23 32,768 510 255.255.254.0
24 65,536 254 255.255.255.0
25 131,072 126 255.255.255.128
26 262,144 62 255.255.255.192
27 524,288 30 255.255.255.224
28 1,048,576 14 255.255.255.240
29 2,097,152 6 255.255.255.248
30 4,194,304 2 255.255.255.252
Did CIDR save the IPv4 Internet? Here is a chart of IPv4 allocations by IANA - the change in allocation rate is obvious (chart from article by Geoff Huston, APNIC). Imagine when IANA would have run out without CIDR. Maybe 2000?
CIDR and the IPv4 Core Routing Table
The core routing table is like the central telco switch for the Internet. This is where the various blocks of addresses are stitched together to make an Internet. In reality, since the Border Gateway Protocol (BGP) was introduced, no single router has a view of the complete IPv4 Internet, but the concept is still applicable, in that there are total number of core routes, even if distributed over a number of core routers by BGP.
CIDR of course impacted the IPv4 core routing table - if you break a /8 block up into a lots of smaller blocks, instead of one entry in the routing table for the entire /8, you now need one entry for every newly created block. Overnight the growth of the central routing tables started to explode.
Number of Entries in IPv4 BGP Core Routing Table, 1989-2012 (approximate):
Year Routes Increase
1989 1,000
1990 3,000 2,000
1991 6,000 3,000
1992 9,000 3,000
1993 15,000 6,000
1994 20,000 5,000
1995 24,000 4,000
1996 30,000 6,000
1997 40,000 10,000
1998 50,000 10,000
1999 52,000 12,000
2000 70,000 18,000
2001 100,000 30,000
2002 105,000 5,000
2003 120,000 15,000
2004 130,000 10,000
2005 150,000 20,000
2006 170,000 20,000
2007 205,000 35,000
2008 215,000 10,000
2009 225,000 10,000
2010 325,000 100,000
2011 342,000 23,000
2012 385,000 43,000
Route Aggregation
CIDR caused a rapid increase in the number of blocks, and a decrease in the average size of blocks. This caused a large increase in the number of routes in the core routing table. RFC 4632 contains a number of suggestions to try to minimize this. Aggregation in this case means "clumping together". So, if an ISP breaks a /16 up into a bunch of smaller blocks, it should not register every one of those blocks directly in the core routing table - they should put one route for that entire block into the core table pointing to their routers, then the add entries into their own router tables to direct packets to the appropriate customer. This increases the number of hops a packet must traverse, but helps reduce the growth in the size of the core routing table.
Impact of CIDR
You can see the impact that CIDR had on the core routing table (starting in 1993, when RFC 1519 was released), even with its suggestions regarding route aggregation. The giant increase in 2010 was due to the panic allocation of IPv4 addresses as the IANA pool neared exhaustion. With the introduction of
CGN (Carrier Grade NAT), the IPv4 core routing table may experience unprecedented growth. This is one more area where IPv4 is rapidly approaching End of Life.
CIDR also impacts address subnet masks. Under the classful scheme, all class A addresses (identified by first first bit of the address being 0), had a subnet mask of 255.0.0.0. All Class B addresses (identified by first two bits of the address being 10) had a subnet mask of 255.255.0.0. All Class C addresses (identified by the first three bits being 110) had a subnet mask of 255.255.255.0. So the subnet mask could be automatically determined from the address.
Once we started breaking some of the old Class A (and even Class B and C) blocks up into smaller blocks, there was no way to determine the correct subnet mask just by looking at the first few bits of an address. An address that had been in a Class A block (with the first bit of 0) might now be in a /24, so its subnet mask would now be 255.255.255.0.
It is even worse than that. Most of the new smaller blocks were not /16 or /24 in size. The split between address prefix and address suffix no longer need be on a multiple of 8 bits! Now a subnet mask might be something like 255.240.0.0 (for a /12) or 255.255.255.248 (for a /29). You might be able to remember all of these, but I usually have to look them up. Now if subnet masks were in hex, it would be a lot easier:
Prefix Length Blocks per /8 Usable Addrs per Block Subnet Mask in Hex
8 1 16,777,214 0xff000000
9 2 8,388,606 0xff800000
10 4 4,194,302 0xffc00000
11 8 2,097,150 0xffe00000
12 16 1,048,574 0xfff00000
13 32 524,286 0xfff80000
14 64 262,142 0xfffc0000
15 128 131,070 0xfffe0000
16 256 65,534 0xffff0000
Those are so simple I don't have to remember them - I can recreate one anytime. You can see the progression of prefix bits move from left to right (if you can translate hex to binary in your head). You just figure out how many times 4 goes into the prefix length (e.g. for /13, 3 times). Put down that number of f's. If the remainder is 0, you're done. If the remainder is 1, add an 8 (1000). If the remainder is 2, add a C (1100). If the remainder is 3, add an E (1110). The remainder for /13 is 1. So the netmask is 0xfff80000. That's it. There's a pattern with dotted decimal subnet masks also, but not so simple.
CIDR Notation
RFC 4632 also describes a new notation for specifying an address prefix including the prefix length. We used to write the network number, then the subnet mask: 192.168.1.0 mask 255.255.255.0. RFC 4632 recommends writing the network number, followed by a slash, followed by the prefix length in bits: 192.168.1.0/24. This is much more compact. Often you will see just the first "prefixlen" bits worth of the network number instead of the whole network number. For example, instead of 10.0.0.0/8, just 10/8. Instead of 172.20.0.0/16, just 172.20/16. CIDR notation is used frequently in the articles on this website.
CIDR and IPv6
CIDR is really an IPv4 thing. There is no mention of IPv6 in RFC 4632. For the most part, all subnets in IPv6 are /64. However, the CIDR notation is widely used in IPv6. Some examples:
2000::/3 block earmarked for allocation
ff00::/8 all IPv6 multicast addresses
2001:470::/32 typical allocation to an ISP (Hurricane Electric)
2001:470:3d::/48 typical company allocation
2001:470:3d:3000::/52 block of addresses in my home
2001:470:3d:3000::/64 block of addresses in my main home network
There are continuing concerns regarding the growth of the IPv6 core routing table as well.
