CIDRD Working Group Y. Rekhter INTERNET DRAFT cisco Systems T. Li cisco Systems October 1995 Implications of Various Address Allocation Policies for Internet Routing Status of this Memo This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress.'' Please check the 1id-abstracts.txt listing contained in the internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any Internet Draft. 1 Abstract IP unicast address allocation and management are essential operational functions for the Public Internet. The exact policies for IP unicast address allocation and management continue to be the subject of many discussions. Such discussions cannot be pursued in a vacuum - the participants must understand the technical issues and implications associated with various address allocation and management policies. The purpose of this document is to articulate certain relevant fundamental technical issues which must be considered in formulating unicast address allocation and Expiration Date April 1996 [Page 1] INTERNET DRAFT October 1995 management policies for the Public Internet. The major focus of this document is on two possible policies, "address ownership" and "address lending", and the technical implications of these policies for the Public Internet. 2 On the intrinsic value of IP addresses Syntactically, the set of IPv4 unicast addresses is the (finite) set of integers in the range 0x00000000 - 0xdfffffff. IP addresses are used for Network Layer (IP) routing - an IP address is the sole piece of information about the node that is injected into the routing system. The notable semantics of an IP unicast address is its ability to gain access to the Public Internet routing service and thereby exchange data with the remainder of the Internet. In other words, in the context of the Public Internet, it is the reachability of an IP address that gives it an intrinsic value - without reachability the address is worthless. The above implies that in the context of the Public Internet it is the service environment (the Internet) and its continued operation, including its routing system, which provides an IP address with its intrinsic value, rather than the inverse. Consequently, if the Public Internet routing system ceases to be operational, the service disappears, and the addresses cease to have any functional value in the context of the Internet. At this point, in the context of the Public Internet, all address allocation and management policies, including existing policies, are rendered meaningless. 3 Hierarchical routing and its implication on address allocation Hierarchical routing [Kleinrock 77] is a mechanism that allows to improve the scaling property of a routing system. Hierarchical routing is the only proven mechanism for scaling routing to the current size of the Internet. Hierarchical routing works by taking a set of addresses and generating a single routing advertisement (route) for the entire set. Further, if addresses are assigned correctly, this can be done recursively: multiple advertisements (routes) can be combined into a single Expiration Date April 1996 [Page 2] INTERNET DRAFT October 1995 advertisement (route). By exercising this recursion, the amount of information necessary to provide routing can be decreased substantially. A common example of hierarchical routing is the phone network (and more precisely, the North American Numbering Plan), where country codes, area codes, exchanges, and finally subscriber lines are different levels in the hierarchy. In the phone network, a switch need not keep detailed routing information about every possible subscriber in a distant area code. Instead, the switch knows one routing entry for the entire area code. Notice that the effect on scaling is dramatic. If we look at the space complexity of the different schemes, the switch which knows about every subscriber in the world needs O(n) space for n worldwide subscribers. Now consider the case of hierarchical routing. If we break n down into the number of subscribers in the local area (l), the number of other exchanges in the area code (e), the number of other area codes in the local country code (a) and the number other country codes (c), then hierarchical routing has space complexity O(l + e + a + c). Notice that each of these factors is much, much less than n, and grows very slowly, if at all. This implies that a phone switch can be built today which has some hope of not running out of space as soon as it is deployed. The fundamental property of hierarchical routing that makes this scalability possible is the ability to form abstractions: in this case the ability to group subscribers into exchanges, area codes and country codes. Further, such abstractions must provide useful information for the ability to perform routing. Some abstractions, such as the group of users with green phones, are not useful when it comes time to route a call. Since the information that routing really needs is the location of the address within the topology, for hierarchical routing, the useful abstraction must capture the topological location of an address within the network. In principle this could be accomplished by either (a) constraining the topology (and allowed topology changes) to match address assignment, or (b) avoiding constraints on the topology (and topology changes), but requiring that as the topology changes, an entity's address may need to change as well - this process is known as "renumbering." Expiration Date April 1996 [Page 3] INTERNET DRAFT October 1995 4 Scaling the Internet routing system The enormous growth of the Public Internet places a heavy load on the Internet routing system. The growth rate has doubled the size of the routing table roughly every 9 months. At the same time, computer technology doubles roughly every 24 months, resulting in untenable mismatch. Even if we would double capacities of routers in the Internet every 24 months or so, while the Internet is doubling every 9 months, sooner or later the size of the routing tables is going to exceed the limit of the routers, even if we would keep upgrading the routers as fast as the computer industry can do so. Therefore, to preserve uninterrupted continuous growth of the Public Internet it is essential to deploy mechanisms(s) that contain the growth rate of the routing information. In absence of mechanism(s) to contain the growth rate of the routing information, the Internet growth would have to be either limited or even frozen, or the Internet routing system would become overloaded. The result of routing overload is that the routing subsystem will fail: either equipment (routers) will not be able to maintain an adequate number of routes to insure global connectivity, or providers will simply exclude certain routes to insure that other routes do provide global connectivity to particular sites. This document assumes that neither of the outcomes mentioned in this paragraph is acceptable. Classless Inter-Domain Routing (CIDR) [RFC1518, RFC1519] has been deployed since late 1992 in the Public Internet as the primary mechanism to contain the growth rate of the routing information - without CIDR the Internet routing system would already have collapsed. The following demonstrates some of the savings provided by CIDR. In August 1995 within AlterNet (which is one of the major Internet Service Providers) there were 3246 routes. As a result of aggregation (due to CIDR), Alternet aggregated 3246 routes into 1113 routes, and advertised only these 1113 routes to the rest of the Internet - a saving of 2133 routes (66%) [Partan 95]. In October 1995 the IRR contained 61,430 unique prefixes listed, not counting prefixes marked as withdrawn (or 65,191 prefixes with prefixes marked as withdrawn). That is roughly a lower bound since a lot of prefixes are not registered in the IRR. CIDR aggregation allowed to reduce this number of prefixes to less than 30,000 routes in the default-free part of the Internet routing system [Villamizar 95]. CIDR is an example of the application of hierarchical routing in the Public Internet, where subnets, Expiration Date April 1996 [Page 4] INTERNET DRAFT October 1995 subscribers, and finally providers are some of the many different possible levels in the hierarchy. For example, a router within a site need not keep detailed routing information about every possible host in that site. Instead the router maintains routing information on a per subnet basis. Likewise, a router within a provider need not keep detailed routing information about individual subnets within its subscribers. Instead the router could maintain routing information on a per subscriber basis. Moreover, a router within a provider need not keep detailed routing information about stub (single home) subscribers of other providers. Instead the router could maintain routing information on a per provider basis. As a result of pre-CIDR address allocation, today there is a considerable number of routes in the Internet that are not suitable for hierarchical aggregation. Moreover, there are sites with pre-CIDR address allocation that are not yet connected to the Internet. If these sites would connect to the Internet at some point in the future, the routes to these sites are unlikely to be suitable for hierarchical aggregation. The topology of the Public Internet, taken as a whole, is not strictly hierarchical, even though most parts are. The hierarchical routing requires that aggregation boundaries for the addressing information be formed along some hierarchy. As a result, there are a number of exceptions which will have to be injected into the routing system in the future, in addition to those exceptions which currently exist. Each such exception that is added to the routing system has a deleterious effect on the scalability of the routing system. The exact number of exceptions which can be tolerated is dependent on the technology which is used to support routing. Unbridled growth in the number of such exceptions will certainly cause the routing system to collapse. 4 Address allocation and management policies IP address allocation and management policy is a fairly complex, multifaceted issue. It covers a broad range of issues, such as who formulates the policies, who executes the policies, what are the roles of various registries, what are the roles of various organizations (e.g., ISOC, IAB, IESG, IETF, IEPG, various government bodies, etc.), the participation of end users in requesting addresses, and so on. Address allocation and management and the ability of the Expiration Date April 1996 [Page 5] INTERNET DRAFT October 1995 Internet routing system to scale are not independent - only certain address allocation and management policies yield scalable routing. The Internet routing system is subject to both technological and fundamental constraints. These constraints restrict the choices of address allocation policies that are practical. 4.1 "Address ownership" allocation policy and its implications on the Public Internet "Address ownership" is one possible address allocation and management policy. The "address ownership" policy means that a portion of the address space, once allocated to an organization, remains allocated to the organization as long as that organization desires to retain it, and that the portion would not be allocated to any other organization. Quite often such addresses are referred to as "portable". While it have never been expressly stated that various Internet Registries use the "address ownership" allocation policy, it has however always been assumed (and practiced). To understand the implications of the "address ownership" policy ("portable" addresses) on the scalability of the Internet routing system observe that: (a) by definition, address ownership assumes that addresses, once assigned, do not change owners, i.e. the same addresses remain at the same organization no matter how radically the organization might change its connectivity to the Public Internet, and therefore no renumbering can take place; (b) by definition, hierarchical routing assumes that addresses reflect network topology as much as possible. Therefore, the only way to accommodate both address ownership and hierarchical routing for everyone is to assume that the topology (or at least certain pieces of it) will be permanently fixed. Given the distributed, decentralized, largely unregulated, and global (international) nature of the Internet, constraining the Internet topology (or even certain parts of it) may have far reaching technical, social, economical, and political implications. So far little is known of what these implications are; even less is known whether these implications would be acceptable (feasible) in practice. Expiration Date April 1996 [Page 6] INTERNET DRAFT October 1995 Therefore, at least for now we have to support the Internet whose topology (and allowed topology changes) is not constrained. Since the Internet does not constrain the topology (or allowed topology changes), in the Internet we can accommodate one, but not both - we can either have address ownership ("portable" addresses) for everyone, in which case the routing overhead will lead to a breakdown of the routing system resulting in a fragmented (partitioned) Internet, or we can have a routable Internet, but without address ownership ("portable" addresses) for everyone. 4.2 "Address lending" allocation policy and its implications on the Public Internet Recently, especially since the advent of CIDR, subscribers and providers have followed a model in which address space is not owned (not portable), but is bound to the topology. This model suggests an address allocation and management policy that differs from the "address ownership" policy. The following describes a policy, called "address lending", that provides a better match (as compared to the "address ownership" policy) to the model. An "address lending" policy means that an organization acquires its addresses on a "loan" basis. For the length of the loan, the lender cannot lend the addresses under the loan to any other borrower. Assignments and allocations based on the "address lending" policy should explicitly include the conditions of the loan. Such conditions must include that the allocation be returned if the borrower is no longer contractually bound to the lender, and the lender can no longer provide aggregation for the allocation. If a loan is terminated, the organization can no longer use addresses acquired via the loan, and therefore has to acquire new addresses and renumber to new addresses. The "address lending" policy does not constrain how the new addresses could be acquired. This document expects that the "address lending" policy would be used primarily by Internet Registries associated with providers; however, this document does not preclude the use of the "address lending" policy by an Internet Registry that is not associated with a provider. This document expects that when the "address lending" policy is used by an Internet Registry associated with a provider, the provider is responsible for arranging Expiration Date April 1996 [Page 7] INTERNET DRAFT October 1995 aggregation of these addresses to a degree that is sufficient to achieve Internet-wide IP connectivity. This document expects that when the "address lending" policy is used by an Internet Registry associated with a provider, the terms and conditions of the loan would be coupled to the service agreement between a provider's subscriber that borrows the addresses and the provider that lent the addresses. That is, if the subscriber moves to another provider, the loan would be terminated. To minimize disruptions when a subscriber changes its providers, this document strongly recommends that the terms and conditions of the loan should include a grace period provision. This provision would allow a subscriber that disconnects from its provider a certain grace period after the disconnect. During this grace period, the borrower (the subscriber) may continue to use the addresses obtained under the loan. This document recommends a grace period of at least 30 days. At the same time, to contain the routing information overhead, this document suggests that a grace period be no longer than 6 months. To understand the implications of the "address lending" policy on the scalability of the Internet routing system, observe that if an organization (subscriber) borrows its addresses from a block of addresses of its provider, then the provider would be able to aggregate addressing information for all such subscribers into a single address prefix. This reduces the amount of routing information that needs to be carried by the Internet routing system (for more on this see Section 5.3.1 of RFC1518). As the organization (subscriber) changes its provider, the loan from the old provider would be returned, and the loan from the new provider would be established. As a result, the organization would renumber to the new addresses. Once the organization renumbers, the new provider would be able to aggregate addressing information for the organization with addressing information for the rest of its subscribers that lease their addresses out of the block of the provider. Therefore, the "address lending" policy, if applied appropriately, is consistent with the constraints on address allocation policies imposed by hierarchical routing, and thus promotes a scalable routing system. Thus, the "address lending" policy, if applied appropriately, could play an important role in enabling the continuous uninterrupted growth of the Internet. To be able to scale routing in other parts of the hierarchy, the "lending" policy may also be applied hierarchically, so that addresses may in turn be loaned Expiration Date April 1996 [Page 8] INTERNET DRAFT October 1995 to other organizations. The implication here is that the termination of a single loan may have effects on organizations which have recursively borrowed a portion of the address space from the main allocation. The exact effects are difficult to determine a priori as a loan may represents a sufficient degree of aggregation within a lower level of the hierarchy and which be aggregated at a higher level, thus not affecting higher levels of the routing hierarchy. 4.3 In the absence of explicit "address lending" policy Organizations connecting to the Internet should be aware that even if their current provider, and the provider they switch in the future would not require renumbering, renumbering may still be needed in order to achieve Internet-wide IP connectivity. For example, an organization may now receive Internet service from some provider and allocate its addresses out of the CIDR block associated with the provider. Later the organization may switch to another provider. The previous provider may still be willing to allow that organization to retain a portion of the provider's CIDR block (allow the organization to "own" addresses), and accept a more specific prefix (that covers destinations within the organization) from the new provider. Likewise, the new provider may be willing to accept that organization without renumbering and advertise the more specific prefix (that covers destinations within the organization) to the rest of the Internet. However, if there exist one or more other providers, that is unwilling or unable to accept the long prefix (that covers destinations within the organization) advertised by the new provider, then the organization would not have IP connectivity to a portion of the Internet. In the future, this may become a large portion, perhaps even the majority. The above shows that the absence of explicit "address lending" policy from a current provider in no way assures that renumbering will not be required in the future when changing providers. Organizations should be aware of this fact should they encounter a provider making claims to the contrary. 5 Recommendations Observe that the goal of hierarchical routing in the Public Internet is not to reduce the total amount of Expiration Date April 1996 [Page 9] INTERNET DRAFT October 1995 routing information in the Internet to the theoretically possible minimum, but just to contain the volume of routing information within the limits of technology, price/performance, and human factors. Therefore, organizations which could provide reachability to a sufficiently large fraction of the total destinations in the Internet and could express such reachability through a single IP address prefix could expect that a route with this prefix will be maintained throughout the default- free part of the Internet routing system. Therefore, using the "address ownership" policy when allocating addresses to such organizations is a reasonable choice. Within such organizations this document suggests to use the "address lending" policy. For all other organizations that expect Internet-wide IP connectivity, the reachability information they inject into the Internet routing system should be subject to hierarchical aggregation. For such organizations, allocating addresses based on the "address ownership" policy makes hierarchical aggregation difficult, if not impossible. This, in turn, has a highly detrimental effect on the Internet routing system. To prevent collapse of the Internet routing system, for such organizations this document recommends to use the "address lending" policy. Consequently, when such an organization first time connects to the Public Internet and wants to acquire Internet-wide IP connectivity, or changes its topological attachment to the Public Internet, but wishes to preserve Internet-wide IP connectivity, the organization eventually (within the grace period) needs to renumber to eliminate any exceptional prefixes that the organization would otherwise inject into the Internet routing system. This applies to the case where the organization takes its addresses out of its direct provider's block and the organization changes its direct provider. This may also apply to the case where the organization takes its addresses out of its indirect provider's block, and the organization changes its indirect provider. Carrying routing information has a cost associated with it. This cost, at some point, may be passed back in full to the organizations that inject the routing information. Aggregation of addressing information (via CIDR) could reduce the cost, as it allows to increase the number of destinations covered by a single route. Organizations whose addresses are allocated based on the "address ownership" policy (and thus may not be suitable for aggregation) should be prepared to absorb the cost completely on their own. Observe that neither the "address ownership", nor the Expiration Date April 1996 [Page 10] INTERNET DRAFT October 1995 "address lending" policy, by itself, is sufficient to guarantee Internet-wide IP connectivity. Therefore, we recommend that sites whose addresses are allocated based on either the "address ownership", or the "address lending" policy should consult with their providers about the reachability scope that could be achieved with these addresses, and associated costs that result from using these addresses. If the organization doesn't require Internet-wide IP connectivity, then address allocation for the organization could be done based on the "address ownership" policy. In this case the organization may still maintain limited IP connectivity (e.g., with all the subscribers of its direct provider) by limiting the distribution scope of its routing information to its direct provider. Connectivity to the rest of the Internet could be accomplished by the use of application layer gateways, Network Address Translators (NATs), etc. Use of these technologies eliminates the need for renumbering. Both renumbering (due to the "address lending" policy) and non-aggregated routing (due to the "address ownership" policy) result in some costs. Therefore, an organization needs to carefully analyze its own connectivity requirements and compare the tradeoffs associated with using addresses acquired via the "address lending" policy vs. addresses acquired via "address ownership". To reduce the cost of renumbering organizations should be strongly encouraged to deploy tools that facilitate renumbering (e.g., Dynamic Host Configuration Protocol [RFC 1541]). Use of the DNS should be strongly encouraged. 6 Summary Any address allocation and management policy for IP addresses used for the Internet connectivity must take into account its impact on the scalability of the Public Internet routing system. Among all of the possible address allocation and management policies only the ones that yield a scalable routing system are feasible - all other policies are self-destructive in nature, as they lead to a collapse of the Internet routing system, and thereby to the fragmentation (partition) of the Public Internet. Within the context of the current Public Internet, address allocation and management policies that assume unrestricted address ownership have an extremely negative Expiration Date April 1996 [Page 11] INTERNET DRAFT October 1995 impact on the scalability of the Internet routing system. Such policies are almost certain to exhaust the scalability of the Internet routing system well before we even approach the exhaustion of the IPv4 address space and certainly well before we will be able to make moderate use of the IPv6 address space. As a result, with the current technology or any near-term foreseeable technology, given the Internet's growth rate, the notion that everyone should able to own address space and receive Internet-wide routing services, regardless of where they connect to the Internet, is technically infeasible. Therefore, this document recommends that (a) the "address lending" policy should be formally added to the set of address allocation policies in the Public Internet, and (b) such policy should be used to deliver routing services to organizations that by themselves do not provide a sufficient degree of routing information aggregation. Since the current IPv6 address allocation architecture is based on CIDR, recommendations presented in this document apply to IPv6 address allocation and management policies as well. 7 Security Considerations Security issues are not discussed in this document. 8 Acknowledgments This document borrows heavily from various postings on various mailing lists. Special thanks to Noel Chiappa, Dennis Ferguson, Eric Fleischman, Geoff Huston, and Jon Postel whose postings were used in this document. Many thanks to Scott Bradner, Randy Bush, Brian Carpenter, Noel Chiappa, David Conrad, John Curran, Sean Doran, Robert Elz, Dorian Kim, Thomas Narten, Andrew Partan, Dave Piscitello, Simon Poole, Curtis Villamizar, and Nicolas Williams for their review, comments, and contributions to this document. Finally, we like to thank all the members of the CIDR Working Group for their review and comments. Expiration Date April 1996 [Page 12] INTERNET DRAFT October 1995 9 References [Kleinrock 77] Kleinrock, L., Farouk, K., "Hierarchical Routing for Large Networks," Computer Networks 1 (1977), North-Holland Publishing Company. [Partan 95] Partan, A., e-mail to big- internet@munnari.OZ.AU, August 24, 1995 [RFC 1541] Droms, R., "Dynamic Host Configuration Protocol". [RFC 1519] V. Fuller, T. Li, J. Yu, K. Varadhan, "Classless Inter- Domain Routing (CIDR): an Address Assignment and Aggregation Strategy" [RFC 1518] Y. Rekhter, T. Li, "An Architecture for IP Address Allocation with CIDR" [Villamizar 95] Villamizar, C., private communications, October 13, 1995 10 Authors' Addresses Yakov Rekhter cisco Systems, Inc. 470 Tasman Dr. San Jose, CA 95134 Phone: (914) 528-0090 email: yakov@cisco.com Tony Li cisco Systems, Inc. 470 Tasman Dr. San Jose, CA 95134 Phone: (408) 526-8186 email: tli@cisco.com Expiration Date April 1996 [Page 13]