CIDR – Classless InterDomain Routing

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 24

 

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

RFC 1519 was replaced by RFC 4632, “Classless Inter-Domain Routing (CIDR)”, August 2006, which is the current version.

 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::/64    block of addresses in my main home network

There are continuing concerns regarding the growth of the IPv6 core routing table as well.

 

0xffff0000