draft-ietf-cidrd-ownership-01.txt -- May 1995 -- CIDRD ------------------------------------------------------ CIDRD Working Group Y. Rekhter Internet Draft T.J. Watson Research Center, IBM Corp. T. Li cisco Systems May 1995 On the Implications of Address Ownership 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 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 management policies for the Internet. The major focus of this document is on one possible policy, the concept of "address ownership," and the technical implications of this concept for the Internet. Expiration Date November 1995 [Page 1] INTERNET DRAFT May 1995 2 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. Support for "address ownership" is one possible address allocation and management policy. Supporting "address ownership" means that once a portion of the address space is allocated or assigned to an organization, the organization may always use these addresses. This implies that the organization will never need to change addresses (renumber), even if the organization changes its topological interconnection to the Internet. Some parties have asserted that the Internet assumes the concept of address ownership already. At the same time the fact remains that the concept of address ownership has never been explicit - the words that have been used have been "assignment," "allocation," and "delegation". One should also note that even if the current allocation procedures are consistent with "address ownership," this does not mean that address ownership is, in fact, the current policy. Address allocation and management and the ability of the Internet routing system to scale are not independent - only certain address allocation and management policies yield scalable routing. Since address ownership is a significant factor in such policies, we need to understand its implications on the scalability of the Internet routing system. 3 On the relationship between addressing and routing Syntactically, the set of IPv4 unicast addresses is the (finite) set of integers in the range 0x00000000 - 0xdfffffff. The notable semantics of an IP unicast address is its ability to gain access to the Internet routing service and thereby exchange data with the remainder of the Internet. IP addresses are used for Network Layer (IP) routing, thus an IP address is the sole piece of information about the node that is injected into the routing system. In other words, it is the reachability of an IP address that gives it an intrinsic value - without reachability the address is worthless. The above implies that 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 Internet routing system ceases to be operational, the service disappears, and the addresses cease to have any non-local functional value. At this point, in the context of the Expiration Date November 1995 [Page 2] INTERNET DRAFT May 1995 Internet, all address allocation and management policies, including "address ownership," are rendered meaningless. 4 Address ownership and its implication on hierarchical routing Hierarchical routing [Kleinrock 77] is used in the Internet as the primary mechanism to contain the growth of routing information - without hierarchical routing the Internet routing system would already have collapsed. Further, hierarchical routing is the only known 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 for the entire set. Further, if addresses are assigned correctly, this can be done recursively: multiple advertisements can be combined into a single advertisement. 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 about 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, it is essential that an address in the network reflect its topological location within the network. Consequently, to preserve hierarchical routing as the topology changes, an entity's address may be required Expiration Date November 1995 [Page 3] INTERNET DRAFT May 1995 to change - this process is known as "renumbering." Classless Inter-Domain Routing (CIDR) [RFC 1518, RFC 1519] is an example of the application of hierarchical routing in the Internet, where providers, subscribers, and finally subnets 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. It should be noted that there are today a considerable number of exceptions in the routing system. Information within the routing system is contained in routes, that carry information about possible paths. Also associated with each route is a prefix that describes the portion of the address space that can be found at the end of the path. Each exception is a prefix that has been injected that does not reflect the topology of the network. Further, because the topology of the network is not strictly hierarchical, there are a large 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 which is added to the routing system has a deleterious effect on the scalability of the routing system. The number of exceptions which can be tolerated is dependent on the exact technology which is used to support routing. Unbridled injection of such exceptions will certainly cause the routing system to collapse. Similarly, if the sustained rate of injection of exceptions exceeds the rate at which routing technology scales, the routing system is doomed. By definition, address ownership assumes that addresses, once assigned, do not change, and therefore no renumbering can take place. By definition, hierarchical routing assumes that addresses reflect network topology. 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. In circumstances where the topology can change arbitrarily, we can accommodate one, but not both - we can either have address ownership, in combination with a non-routable (and therefore non-functional) Internet, or we can have a routable Internet, but without address ownership. In the latter case the concept of "address ownership" is being superseded by a policy of "address leasing". An "address leasing" policy means that an organization acquires its addresses on a "lease" basis. After the lease expires, or if the organization moves, the organization may either renew the lease (in which case the addresses stay the same), or terminate the old lease and establish a new lease (in which case the addresses change). The "leasing" policy must be hierarchical as well, so that addresses may be "sub-let" to other organizations. The implication here is that the expiration of a single lease may have effects on organizations Expiration Date November 1995 [Page 4] INTERNET DRAFT May 1995 which have recursively sub-let a portion of the address space from the main lease. 5 Recommendations This document proposes that all requests for address assignment and allocation which are fulfilled by various registries be under the policy of address leasing. Consequently, such assignments and allocations should explicitly include (among other things) the duration of the lease, and conditions under which the lease could be renewed or terminated. Existing address assignments and allocations are outside the scope of this document. Observe that the goal of hierarchical routing in the Internet is not to reduce the total amount of 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. For all other organizations, the reachability information they inject into the Internet routing system would be subject to hierarchical aggregation. Consequently, when such an organization changes its topological attachment to the Internet, but wishes to preserve Internet-wide IP connectivity, the organization eventually needs to renumber to eliminate any exceptional prefixes that they would otherwise inject into the Internet routing system. This applies both to the case where the organization takes its addresses out of its direct provider's block and the organization changes its direct provider, and to the case where the organization takes its addresses out of its indirect provider's block, and the organization changes its indirect provider. If the organization doesn't require Internet-wide IP connectivity, then renumbering can be avoided. In this case the organization may still maintain limited IP connectivity (e.g. with all the subscribers of its direct provider) by limiting the scope of its routing exception to its direct provider. Since renumbering is not cost-free, an organization, when presented with a choice of renumbering vs. limited IP connectivity, needs to carefully analyze its own requirements and compare the tradeoffs associated with each alternative. Organizations should be strongly encouraged to deploy tools that facilitate renumbering (e.g. Dynamic Host Configuration Protocol [RFC 1541]). Use of the DNS (rather than /etc/hosts) should be strongly encouraged. Expiration Date November 1995 [Page 5] INTERNET DRAFT May 1995 6 Conclusions 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 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 collapse of the Internet. Within the context of hierarchical routing, address allocation and management policies that assume unrestricted address ownership have an extremely negative 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. With the current technology or any near-term foreseeable technology, given the Internet's growth rate, the notion that everyone should be able to own address space and receive routing services, regardless of where they connect to the Internet, is technically infeasible. Therefore, this document recommends that any address allocation and management policy should explicitly dispel the notion of "address ownership" and use the policy of "address leasing" instead. 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 Randy Bush, John Curran, Andrew Partan, Scott Bradner, Dave Piscitello and David Conrad for their review and comments. 9 References [Kleinrock 77] Kleinrock, L., Farouk, K., "Hierarchical Routing for Expiration Date November 1995 [Page 6] INTERNET DRAFT May 1995 Large Networks," Computer Networks 1 (1977), North-Holland Publishing Company. [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" 10 Authors' Addresses Yakov Rekhter T.J. Watson Research Center IBM Corporation P.O. Box 218 Yorktown Heights, NY 10598 Phone: (914) 945-3896 email: yakov@watson.ibm.com Tony Li cisco Systems, Inc. 470 Tasman Dr. San Jose, CA 95134 Phone: (408) 526-8186 email: tli@cisco.com Expiration Date November 1995 [Page 7]