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.

The Longest Match Routing Rule

Routing to all destinations is always done on a longest match basis: a router that has to decide between two different length prefixes of the same network will always follow the longer mask. Suppose, for example, that a router has the following two entries in its routing table:

-198.32.1.0/24 via path 1

-198.32.0.0/16 via path 2

When trying to deliver traffic to host 198.32.1.1, the router tries to match the destination with the longest prefix and would deliver the traffic via path 1. This is illustrated in figure 3-12 where Domain C is receiving the two updates 198.32.1.0/24 and 198.32.0.0/16; traffic toward 198.32.1.1 is following path 1. In case path 1 goes down for some reason, traffic will take path 2. In cases where Domain C is receiving identical routing updates with masks of equal length coming from Domain A and Domain B, Domain C would pick one path or the other or both depending on the load balancing techniques offered by the specific routing implemetation defined for that domain.

Figure 3-12  Following the longest match.

The longest match rule implies that destinations connected to multiple domains must always be explicitly announced—that is, announced in their most specific, not aggregate, forms—by these domains. In figure 3-12, because Domain B does not explicitly advertise route 198.32.1.0/24, traffic from the customer to the host must always go via the longest prefix match, through Domain A. Such a routing configuration might put an unacceptable burden on Domain A.

Less Specific Routes of a Network's Own Aggregate

A specific rule of routing states that, for the sake of preventing routing loops, a network must not follow a less specific route for a destination that matches one of its own aggregated routes. A routing loop occurs when traffic circles back and forth between domains, never reaching its final destination. Default routes 0.0.0.0/0.0.0.0 are a special case of this rule. A network should not follow the default to destinations that are part of one of its aggregated advertisements. This is why routing protocols that handle aggregation of routes should always keep a Pit Bucket (Null0 route in Cisco's terminology) to the aggregate route itself. Traffic sent to the pit bucket will be dropped, which would stop the loop situation.

---

Troubleshooting:  
Avoiding loops in default routing by use of pit buckets.

---

Figure 3-13 illustrates ISP1 aggregating its domain into a single route 198.32.0.0/13. Assume that the link between ISP1 and its customer Samnet (where network 198.32.1.0/24 exists) broke. Suppose also that ISP1 has a default route 0.0.0.0/0.0.0.0 that points to ISP2 for addresses not known within ISP1. Traffic toward 198.32.1.1 will follow the aggregate route to ISP1, will not find the destination, and will follow the default route back to ISP2. The traffic will bounce back and forth between ISP2 and ISP1. To prevent such a loop, a null0 entry to the aggregate route, installed in ISP1's border router will drop all packets destined to an unreachable destination less specific than the aggregate route.

Figure 3-13  Following less specific routes of a network's own aggregate causes loops.

Aggregation, if not properly applied, could result in routing loops and black holes. A black hole occurs when traffic reaches and stops at a destination that is not its intended destination, but from which it cannot be forwarded. These and other routing challenges will become more apparent as you learn about multiple IP address allocation schemes and how they interact with aggregation.

Single-Homing Scenario: Addresses Taken from Outside the Provider's Address Space

In this scenario, the customer is connected to a single provider and has an IP address space totally different from the provider's. This could have happened because the customer changed providers and kept the addresses of the previous provider. Usually in this situation, customers are encouraged or forced to renumber. But if renumbering does not take place, the new provider cannot aggregate the customer addresses. Moreover, the old provider cannot aggregate as efficiently as it once did, because a hole has been punched in its address space. The overall effect of using addresses from outside the provider's address space is that more routes must be installed in the global routing tables.

Multihoming Scenario: Addresses Taken from One Provider

In this scenario, customers are connected to multiple providers. Customers are small enough that they need to take IP addresses from only one of their multiple providers. We will consider two ISPs, ISP1 and ISP2, and their customers: Jamesnet, Stubnet, and Lindanet. The IP address ranges for each domain, corresponding aggregate, and provider are listed in table 3-3.

Note that Jamesnet and Lindanet are multihomed to ISP1 and ISP2 with their address ranges taken from ISP1. Stubnet is single-homed to ISP1 with an address range taken from ISP1. This is illustrated in figure 3-14.

Figure 3-14  ISP2 advertising the wrong aggregate causes black holes.

Advertising aggregates is a tricky business. Customers and ISPs have to be careful about the IP address ranges that the aggregate covers. No one is allowed to aggregate someone else's routes (proxy aggregation) unless the aggregating party is a superset of the other party or both parties are in total agreement. In the following, you will see how ISP2 can cause a routing black hole by aggregating the ranges coming from Jamesnet and Lindanet.

---

Troubleshooting:  
Black holes that result from inappropriate aggregation of others' routes.

---

If ISP2 were to send an aggregate that summarizes Jamesnet and Lindanet into one update (198.24.0.0/18), then a routing black hole will occur. Stubnet, for example, which is a customer of ISP1, has an IP address space that falls inside the aggregate 198.24.0.0/18. If ISP2 were to advertise that aggregate, then traffic to Stubnet will follow the longest match and end up in ISP2. This is why ISP2 will have to specifically list each of the IP address ranges that it has in common with ISP1 on top of its own address space 198.32.0.0/13.

Figure 3-15 shows the correctly advertised aggregates. ISP2 has to advertise the aggregates from Jamesnet and Lindanet explicitly. This way, traffic advertised to Stubnet would never go to ISP2.

Figure 3-15  Correctly advertised aggregates.

Note in figure 3-15 that ISP1 is also advertising the explicit aggregates of Jamesnet and Lindanet. If ISP1 were to advertise the less-specific aggregate 198.24.0.0/13 only, all traffic toward Jamesnet and Lindanet would always follow the longest match via ISP2.

Multihoming Scenario: Addresses Taken from Different Providers

One possibility for large domains is to take addresses from different providers based on the geographic location. Consider figure 3-16. Largenet has taken its IP addresses from two different providers, ISP1 and ISP2. With this design, each provider will be able to aggregate its own address space without having to list specific ranges from the other provider. ISP1 would advertise the aggregate 198.24.0.0/13, and ISP2 would advertise the aggregate 1928.32.0.0/13. Both aggregates are supersets of an IP address block in Largenet.

Figure 3-16  Multihomed environment with addresses from different providers.

The major drawback with the design illustrated in figure 3-16 is that backup routes to multihomed organizations are not maintained. ISP2 is advertising only its block of addresses and not the block taken from ISP1. In case ISP1 has problems and the 198.24.0.0/13 is lost, traffic to Largenet destined for 198.24.0.0/20 will be affected because it is not advertised anywhere else. The same reasoning applies for Largenet's addresses taken from ISP2. If the link to ISP2 fails, accessibility of the 198.32.0.0/20 range will be impaired. To remedy this situation, ISP1 has to advertise 198.32.0.0/20 and ISP2 has to advertise 198.24.0.0/20.

Multihoming Scenario: Addresses Taken from None of the Providers

Figure 3-17 illustrates a situation in which addresses are taken from a range totally different from ISP1 or ISP2's address space. In this case, both ISP1 and ISP2 will advertise a specific aggregate (204.24.0.0/20) on top of their own ranges (198.24.0.0/13 and 198.32.0.0/13). The drawback of this method is that all routers in the Internet must have a specific route to the new range that is introduced. Too many of such instances would result in an increase in the overall routing tables.

Figure 3-17  Addresses obtained outside ISP address space.

Aggregation Recommendations

In conclusion, a domain that has been allocated a range of addresses has the sole authority for aggregation of its address space. When a domain performs aggregation, it should aggregate as much as possible without causing ambiguity such as is possible in the case of multihomed networks.

Different situations require different designs. No one specific solution can handle all cases. It is recommended that single-homed customers obtain a single contiguous prefix from the direct provider. If they change providers, a plan should be put in place to transition the addressing to the new provider's address space. For multihomed customers, address assignments should be done in a way to maximize aggregation as much as possible. In the case where aggregation impacts redundancy, redundancy should prevail even if extra networks have to be listed.

The introduction of CIDR has helped damper the explosion of global routing tables tremendously over the last few years. The Border Gateway Protocol 4 (BGP4) is the routing protocol of choice on the Internet in part because it so efficiently handles route aggregation and propagation between different autonomous systems. As this book progresses, you will see more and more examples of the importance of CIDR in controlling traffic behavior and stability.

To find ways to slow down the pace at which the IP addresses were being allocated, it was important to identify different connectivity requirements and try to assign IP addresses accordingly.

Most organizations' connectivity needs fall in the following categories:

•  Global connectivity

•  Private connectivity (total or partial)

Global Connectivity

Global connectivity means that hosts inside an organization have access to both internal hosts and Internet hosts. In this case, hosts have to be configured with globally unique IP addresses that are recognized inside and outside the organization. Organizations requiring global connectivity must request IP addresses from their service providers.

Private Connectivity

Private connectivity means that hosts inside an organization have access to internal hosts only, not Internet hosts. Examples of hosts that require only private connectivity include bank ATM machines, cash registers in a retail company, or any host that does not really need to reach or be reached by hosts outside the company. Private hosts need to have IP addresses that are unique inside the organization, but do not have to be unique outside the organization. For this type of connectivity, the IANA has reserved the following three blocks of the IP address space for what is referred to as "private Internets:"

•  10.0.0.0 through 10.255.255.255 (a single class A network number)

•  172.16.0.0 through 172.31.255.255 (16 contiguous class B network numbers)

•  192.168.0.0 through 192.168.255.255 (256 contiguous class C network numbers)

An enterprise that picks its addresses from the preceding range does not need to get permission from the IANA or an Internet Registry. Hosts that get a private IP address can connect with any other host inside the organization, but cannot connect to hosts outside the organization without going through a proxy gateway. The reason is that IP packets leaving the company will have a source IP address that is ambiguous outside the company and cannot be replied to by outside hosts. Because multiple companies building private networks can use the same IP addresses, fewer unique global IP addresses need to be assigned.

Hosts having private addresses can co-exist with hosts having global addresses. Figure 3-18 illustrates such an environment. Companies might choose to have most of their hosts private and still keep particular segments with hosts having global addresses. The latter hosts can reach the Internet as usual. Companies that use private addresses and still have connectivity to the Internet have the responsibility of applying routing filters to prevent the private networks from being leaked to the Internet.

Figure 3-18  General private Connectivity environment.

The drawback of this approach is that if an organization later on decides to open up its hosts to the Internet, the private IP addresses will have to be renumbered.With the introduction of new protocols such as the Dynamic Host Configuration Protocol (DHCP) [5], this task might become easy. DHCP provides a mechanism for transmitting configuration parameters (including IP addresses) to hosts using the TCP/IP protocol suite. Provided that the hosts are DHCP-compatible, hosts can get their new addresses dynamically from a central server.

Hosts that have private addresses can still reach the outside by going through a gateway or some kind of host that has a global address.

Host A in Figure 3-19 has a private IP address. If A wants to telnet to a destination outside the company, it can do so by first logging into host B and then telnetting from host B to the outside. Packets leaving the company now would have B's source IP address, which is global and can be replied to.

Figure 3-19  Privately addressed hosts accessing Internet resources.

Network Address Translator

Companies migrating from a private address to a global address space can do so with the help of Network Address Translators (NAT). Cisco Systems offers this solution as part of its Cisco Internetwork Operating System (IOS)™ software running on its routers.

NAT technology enables private networks to connect to the Internet without resorting to renumbering IP addresses. A NAT router is placed at the border of a domain, and it translates the private addresses into global addresses before sending packets to the Internet.

As illustrated in figure 3-20, hosts A and B have private IP addresses 10.1.1.1 and 10.1.1.2. If A and B want to reach destinations outside the company, the NAT will convert the source IP addresses of the packets according to the predefined mapping in the NAT table. Packets from host A will reach the outside with a source IP address of 128.213.x.y, and packets from host B will reach the outside as coming from source IP address 128.213.z.w. Hosts in the global domains will not know the difference and will reply to hosts A and B as they would to any other host. On the way back, the destination address of the packets will be mapped back to the private IP address.

Figure 3-20  Network Address Translator example.

Discussions about NAT devices are beyond the scope of this book because they have to handle many "corner cases" and more involved situations. Such cases include enterprises that have used addresses that are not part of the IANA private addresses. In this case, addresses used could be already assigned by the IANA to some other company. Other situations involve enterprises that get assigned fewer global addresses than their number of hosts. In this case, the NAT has to dynamically map private IP addresses to a smaller pool of global addresses.

IP Version 6 (IPv6)

IP version 6 (IPv6), also known as IP next generation (IPng), is a move to improve the existing IPv4 implementation.

The IPng proposal was released in July 1992 at the Boston Internet Engineering Task Force (IETF) meeting, and a number of working groups were formed in response. IPv6 tackles issues such as the IP address depletion problem, quality of service capabilities, address autoconfiguration, authentication, and security capabilities.

IPv6 is still in its experimentation stage. It is not easy for companies and administrators deeply invested in the IPv4 architecture to migrate to a totally new architecture. As long as the IPv4 implementation keeps providing hooks and techniques (as cumbersome as they might be) to tackle all the major issues that IPv6 will solve, adopting IPv6 might not seem very compelling to many companies. How soon or how late people will migrate to IPv6 is yet to be seen.

As far as this book is concerned, we will only touch on part of the IPv6 addressing scheme and how it compares to what you already have seen in IPv4.

The IPv6 addresses are 128 bits long (compared to 32 bits in IPv4). This should provide ample address space to handle scalability issues in the Internet (128 bits of addressing will translate into 2¹²⁸—which is a lot of addresses).

The types of IPv6 addresses are indicated by the leftmost bits of the address in a variable length field called the Format Prefix (FP). This is illustrated in figure 3-21.

Figure 3-21  IPv6 prefix and address format.

Table 3-4 outlines the initial allocation of these prefixes. IPv6 has defined multiple types of addresses; we are interested in the provider-based unicast addresses and the local use addresses for comparison with IPv4 techniques.

Provider-Based Unicast Addresses

Provider-based unicast addresses are similar to the IPv4 global addresses. The format of these addresses is illustrated in figure 3-22. Descriptions of the address fields are as follows:

•  Format Prefix—First three bits are 010, indicating a provider-based unicast address.

•  REGISTRY ID—Identifies the Internet address registry that assigns the PROVIDER ID.

•  PROVIDER ID—Identifies the service provider responsible for this address.

•  SUBSCRIBER ID—Identifies which subscriber is connected to the service provider.

•  SUBNET ID—Identifies the physical link to which the address belongs.

•  INTERFACE ID—Identifies a single interface among interfaces that belong to the SUBNET ID. For example, this could be the traditional 48-bit IEEE-802 Media Access Control (MAC) address.

Figure 3-22  IPv6 address assignment hierarchy.

The IPv6 global address incorporates the CIDR functions of the IPv4 scheme. Addresses are defined in such a way as to allow hierarchy, where each entity takes its portion of the address from an entity above it, as illustrated in figure 3-23.

Figure 3-23  IPv6 address assignment hierarchy.

Local-Use Addresses

Local-use addresses are similar to the IPv4 private addresses defined in RFC 1918. Local-use addresses are divided into two types: Link-Local Use (prefix 1111111010), which are private to a particular physical segment, and Site-Local Use (prefix 1111111011), which are private to a particular site. Figure 3-24 illustrates the format of these local use addresses.

Figure 3-24  Local-use address formats.

The local-use addresses have local meaning. The link addresses have local meaning to a particular segment, and the site addresses have local meaning to a particular site.

Companies that are not connected to the Internet can easily assign their own addresses without a need for requesting prefixes from the global address space. If the company later decides to interconnect globally over the Internet, a REGISTRY ID, PROVIDER ID, and SUBSCRIBER ID will be assigned to be used with the already assigned local addresses. This is a major improvement over having to replace all private addresses with global addresses or using Network Address Translation tables to get things working in the IPv4 addressing scheme.

Looking Ahead

IP addresses and addressing schemes are basic elements of interdomain routing. Addressing by itself defines where certain information can be found, but does not give any indication on how the information is to be accessed. A mechanism is needed to exhange information about destinations and to calculate the optimal way to reach a certain destination. This mechanism, of course, is routing.

This chapter concludes all the foundation material required before proceeding to study routing architecture itself. In the next chapter, the basics of interdomain routing are covered, building on concepts of addressing, global networks, and domains as discussed in this and previous chapters. Routing protocols in general, and BGP in particular, are discussed, with implementation details on BGP to follow in Chapter 5 and beyond.

References

[1] RFC 791 Internet Protocol (IP)

[2] RFC 917 Internet Subnets

[3] RFC 1878 Variable Length Subnet Table for IPv4

[4] RFC 1519 Classless Interdomain Routing (CIDR)

[5] RFC 1541 Dynamic Host Configuration Protocol

[6] RFC 1918 Address Allocation for Private Internets

[7] RFC 1631 The IP Network Address Translator (NAT)

[8] RFC 1884 IP Version 6 Addressing Architecture

Previous | Content | Next