Classless Interdomain Routing (CIDR)

In recent years, the IP routing tables held in the Internet routers have grown in a way that caused routers to start being saturated as far as processing power and memory allocation. Statistics and growth rate projections suggest that routing tables have doubled in size every 10 months between 1988 and 1991. Figure 3-9 illustrates this growth. Without any plan of action, the routing table would have grown to about 80,000 routes in 1995. Actual data in 1996, however, showed that the routing table size is around 42,000 routes. This reduction in growth is attributed to the IP address allocation scheme discussed in the previous section and to the adoption of CIDR.

Figure 3-9  Routing table growth chart.

CIDR is a move away from the traditional IP classes A/B/C. In CIDR, an IP network is represented by a prefix, which is an IP address and some indication of the leftmost contiguous significant bits within this address. For example, 198.32.0.0, which used to be an illegal class C network, is now a valid prefix with a notation 198.32.0.0/16. The /16 is an indication that you are using 16 bits of mask counting from the far left. This is similar to 198.32.0.0 255.255.0.0.

A network is called a supernet when the prefix boundary contains fewer bits than the network's natural mask. A class C network 198.32.1.0, for example, has a natural mask of 255.255.255.0. The representation 198.32.0.0 255.255.0.0 also represented as 198.32.0.0/16 has a shorter mask than the natural mask (16 < 24); hence, it is a supernet.

These address schemes are illustrated in figure 3-10.

Figure 3-10  CIDR-based addressing illustration.

This notation enables you to lump all the more specific routes of 198.32.0.0 (such as 198.32.1.0 and 198.32.2.0, and so on) into one advertisement called an aggregate.

It is easy to be confused by all this new terminology, especially because the terms aggregate, CIDR block, and supernet are often used interchangeably in casual discussion. Generally, the terms all indicate that a list of contiguous IP networks has been summarized into one announcement. More precisely, CIDR is the <prefix,length> notation; supernets have a prefix length shorter than the natural mask; and aggregates indicate any summary route.

All the networks that are a subset of an aggregate or a CIDR block are called "more specific" because they give more information about the location of a network. More specific prefixes have a longer prefix length than the aggregate:

•  198.213.0.0/16—aggregate of length 16

•  198.213.1.0/20—more specific prefix of length 20

Routing domains that are CIDR-capable are called classless, in contrast to the traditional classfull routing domains. CIDR has depicted a new, more hierarchical Internet architecture, where each domain takes its IP addresses from a higher hierarchical level. This gives tremendous savings in route propagation especially when summarization is done close to the so-called leaf networks. Leaf networks are endpoints on the global network; they do not, in turn, provide Internet connection to other networks. An ISP that supports numerous leaf networks subdivides its subnets into many smaller blocks of addresses to serve those customers. Aggregation permits the ISP to advertise the addresses in a single notation rather than many, thus resulting in more efficient routing strategies and propagation.

The efficiency of aggregation is illustrated in figure 3-11. In this example, ISP3 has been given the block 198.0.0.0 through 198.255.255.0. ISP3 has given two blocks of its addresses to ISP1 and ISP2. ISP1 has the range 198.32.0.0 through 198.32.255.0, and ISP2 has the range 198.33.0.0 through 198.33.255.0. In the same manner, ISP1 and ISP2 have allocated their own customers a block of addresses from their own ranges. The left side instance of figure 3-11 shows what happens if you do not use CIDR: ISP1 and ISP2 would have to advertise all the subnets coming from their customers, and ISP3 would have passed all these advertisements to the outside world. This would result in a major increment in the global IP routing tables.

Figure 3-11  Comparison of classful addressing and CIDR-based addressing.

The right side instance of figure 3-11 shows the same scenario when CIDR is applied. ISP1 and ISP2 are performing aggregation on their customer subnets, ISP1 is advertising the aggregate 198.32.0.0/16, and ISP2 is advertising the aggregate 198.33.0.0/16. In the same manner, ISP3 is performing aggregating on its customer subnets, ISP1 and ISP2, and is sending only one aggregate 198.0.0.0/8. This results in tremendous savings in the global IP routing tables.

As you can see, aggregation results in more significant efficiency gains when done close to the leaf node because the majority of the subnets to be aggregated are deployed at the customer premises. Aggregation at higher levels, such as ISP3, results in less reduction because it is dealing with fewer networks to start with.

Aggregation works optimally if every customer connects to his provider via one connection only (a scenario called single-homing), and also if the customer has taken its IP addresses from its provider's prefixes. Unfortunately, this is not always the case in the real world. Situations arise, for example, where customers already have IP addresses that do not belong to their provider's range. As another example, some customers (who could be providers themselves) have found the need to connect to multiple providers at the same time (a scenario known as multihoming). These situations result in further complications and less flexibility in aggregation.

These complications to aggregation are discussed in more detail. But first, it is important to understand a couple of routing rules, as described in the next two subsections.