Network Working Group Yakov Rekhter Internet Draft Cisco Systems Paul Resnick AT&T Steve Bellovin AT&T Expiration Date: December 1996 June 1996 Financial Incentives for Route Aggregation and Efficient Address Utilization in the Internet: A Framework draft-bellovin-piara-framework-00.txt 1. Status of this Memo This document is an Internet-Draft. Internet-Drafts are working doc- uments of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute work- ing documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference mate- rial or to cite them other than as ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). 2. Abstract The ability to sustain continuous growth of the Internet is affected both by the ability of the Internet routing system to scale, and by the availability of IP addresses that are unique within the Internet. We argue that scalable routing and efficient address space utiliza- tion should not be treated as two separate problems, but as two inter-related facets of a single problem - how to scale the Internet. Unfortunately, scalable routing and efficient address space utiliza- tion do not come for free: they sometimes require renumbering of existing hosts to new addresses or otherwise undersirable address allocations. We propose to use financial incentives rather than just Rekhter, Resnick, Bellovin [Page 1] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 the existing methods of persuasion and coercion to motivate IP address assignment that is efficient both with respect to its suit- ability for aggregation (via hierarchical routing), and with respect to the address space utilization. We argue that where tradeoffs must be made between conflicting goals, use of financial incentives will permit local decisions that take into account local differences, thus leading to better choices than could be made by any centralized administrative body. 3. Motivations What is the goal ? This document assumes a goal of enabling Internet growth through the smallest resource expenditures possible. For the purpose of this doc- ument, the size of the Internet is measured as the number of hosts that have either full access or client access [RFC1775]. In pursuing the goal of least cost growth, we need to respect the distributed nature of decision-making on the Internet. We cannot expect partici- pants to endure private losses that generate public gains, at least not for an indefinite period of time. We do not claim that the forms of charging discussed here are neces- sary, at least at this time. Rather, we assert that, at the least, monetary mechanisms are a possible alternative solution to the Inter- net's growing pains. As such, they should be explored, much as we explore new technical ideas. Accordingly, our motive in writing this memo is to stimulate discussion of the ideas and issues involved, and -- where necessary -- to begin consideration of any new protocols that might be needed. 4. Growth While Minimizing Resource Utilization Suppose a new host joins the Internet. The host needs an unambiguous address and full connectivity. That is, from every existing host there must be at least one path by which packets can travel to the new host. At each step along each of those paths, a router must be able forward packets to the correct next hop. There are two limits, then, on growth. First, there must be an unam- biguous address available for each new host. Second, many routers must keep track of an extra "route", an extra entry in the table of where to forward packets. One could argue that new technology can expand these limits. For example, by moving to IPv6, we can get longer addresses, and hence Rekhter, Resnick, Bellovin [Page 2] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 make available more unambiguous addresses. At least in principle, one could argue that to keep track of extra routes we just need to build routers with more memory. Additional technology, however, is costly and is not always available just when you need it. The technology growth curve may also be unable to keep up with the growth of the Internet. Sometimes it will be either cost effective or just neces- sary to make more efficient use of existing resources instead. Hierarchical route aggregation is one way to make more efficient use of existing resources. While the notion of a route and route aggrega- tion may be applied to various types of route information, this docu- ment focuses on one particular type: addressing information. In par- ticular, if all packets destined for addresses with the same prefix get forwarded to the same next hop, a router can include just one entry in its router table for that prefix, rather than a separate entry for each individual address. This method can be applied recur- sively to create larger and larger address blocks that share shorter and shorter prefixes. Hierarchical route aggregation is widely used on the Internet today and was the main technology behind CIDR [ref.]. Hierarchical aggregation only works, however, if all traffic destined to all the addresses covered by a particular address prefix should be routed to the same next hop. Thus, the assignment of addresses to hosts must follow the connection topology of the network in order for hierarchical aggregation to be successful. Even when address assignments match connection topology sufficiently at one point in time, it's hard to keep them aligned over time. Dif- ficulties arise both from networks that grow and shrink, and from changes in network topology that occur when customers switch providers or peering arrangements change. Consider the growth problem. An organization initially has n hosts to connect, but at a later time may need to connect an as-yet unknown number of additional hosts. There are only three ways to handle this, none of which is completely satisfactory: 1) Assign the block of n but leave spare addresses with the same prefix unused in anticipation of future needs. When the addresses are eventually used, they can be routed as a single aggregate. For example, the current RIPE NCC policy is to give out a /19 to a new ISP, but to reserve the companion /19 that shares the same prefix, so that it can also be given to that ISP in the future, thus cre- ating an 18-bit prefix that can all be routed to the same destina- tion. This wastes addresses, however, since the ISP may never need the reserved addreses, and doesn't completely solve the problem, since the ISP may need more addresses than those that have been Rekhter, Resnick, Bellovin [Page 3] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 reserved. 2) When additional addreses are needed, renumber the existing n hosts into a larger block that accommodates the additional hosts. The cost of renumbering the existing hosts, however, may be quite high. 3) Allocate the additional addresses separately, and advertise an extra route. Because renumbering costs can be high, and addresses may not be reserved, this is a common practice. This imposes a cost on the organizations that must carry the additional route. The best choice will depend on time-varying and local circumstances. If addresses are plentiful, the inefficient address space utilization of the first method may be acceptable. If renumbering costs are low, the second may be appropriate. If routers are not overloaded, the last method may be fine. 5. Distributed Decision Making The Internet consists of many independent decision-makers. The self- interest of these decision-makers does not always align with the interests of the Internet as a whole. Even when interests are not aligned, we need to motivate behavior that benefits the Internet as a whole. For subscribers, we need to motivate use of as few addresses as pos- sible, and use of addresses that are suitable for hierarchical aggre- gation. Currently, such address assignment has no immediate and/or direct benefits, but has immediate and obvious drawbacks to a sub- scriber -- the need to renumber whenever they add more hosts. Con- versely, continuing to use non-aggregatable addresses imposes a direct cost on the rest of the Internet: the need for increased router memory. For providers, we need to motivate advertisement of aggregate routes for their subscribers whenever that is possible. In particular, providers should always aggregate their stub subscribers. Currently, providers gain no direct benefits from advertising aggregate routes. In fact, by doing this the provider benefits other providers, who may be the provider's competitors. Rekhter, Resnick, Bellovin [Page 4] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 5.1. The Spirt of Cooperation The "spirit of cooperation" is often invoked when self-interest does not align with the larger interest. It calls on everyone to cooperate with each other and do whatever is necessary for the "goodness of the Internet". We shouldn't underestimate the power of this incentive. The fact that the Internet is still operational is largely due to the "spirit of cooperation". But it is dangerous to rely solely on this spirit, especially as the Internet grows larger and anonymous commer- cial ties replace the personal ties that bound network operators together in the old days. 5.2. Administrative Policies Sometimes rules, or policies, can align individual behavior with the common good despite a misalignment of interests. Policies are diffi- cult to enforce, however, because there is no central authority on the Internet. Moreover, as the Internet continues to grow, it becomes ever more difficult even to agree on policies. For example, today there are three major address registries; in general, they co- ordinate their address policies. If several more registries were to come into being, such co-ordination would become more difficult. Such a development is likely, since more than half the population of the planet lives in areas with very little Internet connectivity, and some of these areas have very different economic and social philoso- phies. A final problem with policies is that it is difficult make them reflect the heterogeneity of the Internet. A policy about advertising aggregate routes that is appropriate for organizations with low renumbering costs may not be appropriate for those with higher costs. Similarly, a blanket policy determining the number of addresses to allocate to a new ISP does not take into account the likely growth of the ISP, while an allocation policy that takes into account business plans requires sophisticated, and sometimes subjective, decision- making rules. 5.3. Financial Incentives Alternatively, we can use financial incentives to bring individual self-interest into closer alignment with the global interest, thus motivating behavior that serves the common good. For example, if an organization is forced to pay the cost that advertising an additional route imposes on others, it will choose to do so only when its own benefits outweigh the global costs. Similarly, if organizations paid Rekhter, Resnick, Bellovin [Page 5] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 for addresses, they would reserve unused addreses for future use only when the benefits outweighed the cost. As an added feature, the money collected can compensate those entities that actually bear the costs. Decisions based on financial incentives will naturally take into account local factors. If there are charges both for addresses and for advertisement of routes, organizations will trade off these costs against their own costs of renumbering. Since the cost of renumbering will vary between organizations, different organizations will make different tradeoffs. The rest of the document outlines a framework for using financial incentives in conjuction with route advertisements, and address allo- cations. 6. Charging for route advertisements The primary goal of introducing charging for route advertisment is to limit the number of routes within the Internet routing system, while still maintaining full IP connectivity. To put it differently, the goal is to propagate each route to as few domains as possible, while maintaining connectivity among as many domains as possible. 6.1. Route "push" vs route "pull" To understand how charging could be imposed, we need to examine routing information dissemination. Specifically, we need to differen- tiate between the distribution of routing information that is neces- sary to provide connectivity, and routing information that results in improved connectivity (better paths). 6.1.1. Route "push" Route "push" occurs when a provider has a route to reach some desti- nation and offers to others to handle transit traffic, so that they can use the route. This is the natural way to expand the region of hosts with connectivity to a destination. Note, however, that connec- tivity provided by pushing may not yield the most desirable path between the destination and every other host. In the context of hierarchical routing a route has to be "pushed" until it gets aggregated with other routes. In the worst case the route has to be "pushed" first to "default-free" zone of the Inter- net, and then through the whole "default-free" zone. Rekhter, Resnick, Bellovin [Page 6] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 The scope of how far a route has to be "pushed" is influenced by the assignment of the addresses covered by the route. 6.1.2. Route "pull" Route "pull" occurs when a provider chooses to use a better route to a destination than the route that was pushed to it, asking providers along the new route to provide transit service. Thus, route "pull" is not necessary to provide connectivity - from the connectivity per- spective route "pull" is optional. The decision on when to "pull" a route is influenced by the tradeoffs between path optimality and the volume of routing information. It is a purely local matter. 6.2. Use of bilateral agreements To scale the system we propose that both route "push" and route "pull" be realized solely as a composition of bilateral agreements. Individual agreements will be constrained to the organizations (e.g., providers, subscribers) that are directly connected (thus physical connectivity constrains the number of possible agreements). Composi- tion (including subcontracting) of bilateral agreements enables extension of the scope of "push" or "pull" beyond directly connected providers/subscribers. Suppose X has a route to Z. For X to push the route to another orga- nization Y (directly connected to X), X and Y would sign a "contract" of the form, "I, Y, promise that the following organizations (e.g., providers), ____, will be able to reach destination Z by sending traffic to me (Y), which I will forward to X." Typically, Y would then subcontract with downstream organizations to further push the route. Suppose Y has a route to Z. For an organization X to pull a route from an organization Y (directly connected to X), X and Y would sign a "contract" of the form, "I, Y, promise to forward traffic from X to Z via the following sequence of organizations __________." This requires a bilateral agreement with the first organization in the sequence, which then has a subcontracting agreement with the next organization in the sequence, etc. Both the sign and magnitude of payments accompanying a contract are open to negotiation. For example, in a contract for X to push a route to Y, X might pay Y, which might in turn redistribute some of that payment to the subcontractors it relies on to fulfill the original contract. Rekhter, Resnick, Bellovin [Page 7] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 6.3. Interaction with hierarchical routing The use of provider-based address allocation reduces the scope of route "push" for subscribers. A subscriber needs to "push" just to its provider. A provider that aggregates routes from N of its sub- scribers into a single route will presumably be able to negotiate a more favorable push contract with downstream organizations than a provider that pushes N separate routes for its customers, thus creat- ing an incentive for aggregation. 6.4. Interaction with route optimality Aggregation could cause suboptimal routing because the optimal next hop may differ for two destinations whose routes have been aggre- gated. Thus one could argue that any mechanism that encourages aggre- gation could also (indirectly) encourage suboptimal routing. Aggre- gation, however, does not always result in suboptimal routing. For example, aggregation of stub subscribers has no impact on route opti- mality. 6.5. Interaction with address allocation policies Charging for route advertisement may make portable addresses (address "ownership" in the language of addr-own...[ref.]) less attractive to small and medium size sites. Since portable addresses will not be easily aggregated, the routing costs of portable addresses will be higher. Those who prefer not to pay these higher costs will accept address allocations from their providers ("address lending.") 6.6. Interaction with transit traffic When an organization X contracts to accept traffic from another orga- nization Y, the routing information passed from X to Y would control what destinations Y would be able to reach through X. This would impact the amount of traffic X would receive from Y. X's decision about what routing information to pass to Y could also be affected by Y's charges for routes. Thus, the amount of routing information that X would pass to Y would represent a balance between the amount of traffic X is willing to accept from Y, and the charges for routes that Y would impose when accepting routes from X. (Clearly, this concept is also related to settlements payments for traffic. If X can profit by carrying traf- fic from Y, it will be more willing to pay the cost of advertising Rekhter, Resnick, Bellovin [Page 8] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 more routes.) 7. Charging for Address Allocation While charging for route advertisement may motivate address assign- ment that is efficient with respect to its suitability for aggrega- tion, it does little (or nothing) to produce efficient address space utilization. To improve address space utilization we propose to charge for addresses, thus motivating transfer of addresses to those who value them most. 7.1. "Transferable address ownership" address allocation policy In the current model, when an organization acquires addresses based on the "address ownership" policy, the organization can take the addresses with them when switching providers, but the organization can't transfer the ownership to another organization. The organiza- tion could only either loan these addresses to another organization, or return these addresses back to the Internet Registry that provided the initial allocation. Address lending policy allows transfer of addresses from one organi- zation to another, but the transfer is expected to be on a temporary basis, and is also expected to be coupled with the connectivity between two organizations. Neither of these policies is ideal for introduction of charges for address allocation. Charges, or taxes, could be introduced in the non-transferable address ownership situation, but there would be no market forces operating to discover the appropriate level of charges. It is also unclear to whom the charges would be paid. Charges are a natural part of address lending, but when customers switch providers they have no way to trade off the costs of renumbering against addi- tional routing costs that come with address portability. Instead, a third policy, transferrable address ownership, is needed. The transferable address ownership policy could be viewed as a gener- alization of the address lending policy, where the loan is not bounded by a specific time period or connectivity, and is recursive. The transferable address ownership policy could also be viewed as a relaxation of the current address ownership policy, where an organi- zation may transfer ownership of its addresses to another organiza- tion. For an organization that wants to acquire addresses, the purchase price would create an incentive to use as few addresses as possible. Rekhter, Resnick, Bellovin [Page 9] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 For organizations that already own addresses, the opportunity cost of not selling unneeded addresses would create the same incentive. 7.2. Scope of ownership Transferable address ownership is defined with respect to a particu- lar set of organizations that are willing to honor the ownership right. We'll refer to this set as a "club" The address ownership rights mean that address assignment consistent with the right would result in unambiguous routing to this address from any host within the organizations that are willing to honor the rights. One could also observe that the property right results in unique address assignment within the club. We can operationally define the address property right in terms of an ownership database consisting of ownership deeds for or blocks of IP addresses. The club is defined as the set of organizations who agree to respect the database entries, refusing to route data (within the club) destined for a particular address except as authorized to do so by the owner of the address. The model doesn't preclude an organization being in more than one club. However, membership in more than one club can't violate owner- ship right of any member of any of these clubs. Clubs can be inter- connected by any mechanism that doesn't pass unmodified IP addresses. These include NAT boxes and some forms of firewall. 7.3. Address ownership without connectivity The transferrable address ownership policy doesn't couple acquisition of the address ownership rights with the actual connectivity. Owning a (transferrable) address without having global routability may have what economists call "option value." That is, there is value in hav- ing the option of global routability sometime in the future. For example, this would permit an organization to change its style of firewall without incurring the cost of renumbering. 7.4. Interaction with hierarchical routing The market price of address blocks is likely to be influenced by route charges. In particular, a large block of addresses that share a common prefix is likely to sell for more than an equivalent number of addresses that do not share a common prefix: it will be cheaper to contract for routing of the large block than the collection of smaller blocks. Rekhter, Resnick, Bellovin [Page 10] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 7.5. Address Ownership Registry If addresses are to be owned by individual parties, it is necessary to have some way to ascertain who owns -- and has the right to have routed -- each address. This can be accomplished in a number of ways. The most obvious is to continue the present registry system. The various registries already maintain such lists; making addresses transferrable will presumably increase the rate of change of owner- ship, but to a first approximation imposes no serious problems. Any- one wishing to confirm the validity of a routing change request can simply consult the registry, and notify the owner-of-record of the change. Companies that desire confidentiality in address ownership could use the service of a third party. This third party would be the listed owner of record, and would have to initiate any change requests; how- ever, rather than acting on its own, it would act based on instruc- tions from the real owner. Negotiations, including any provisions for audit trails, contract provisions, escrow or bonding money, etc., would be determined by bilateral negotiations between the owner and the third party, and would be outside the scope of this document. We could accomplish the same thing technically, if we wished. The registry could list a public cryptographic key with each address; all change requests would be signed by the corresponding private key. Transaction types would include rekeying, to allow for ownership changes; additionally, address blocks could be subdivided, in which case a new public key would be specified for each new block. If desired, change requests could even be accompanied by an anonymous digital cash payment, to reimburse the registry for its administra- tive overhead. 8. Summary The current routing and addressing situation in the Internet is unstable. Avoiding facing the problem of scaling the Internet woudn't make the problem to go away. The combination of charging for address allocation and for route advertisement could lead to an address assignment that is efficient both with respect to the address space utilization, and the ability to perform hierarchical aggregation of addressing information. Rekhter, Resnick, Bellovin [Page 11] Internet Draft draft-bellovin-piara-framework-00.txt June 1996 9. Security Considerations Security issues are not discussed in this document. 10. References [1] R. Myerson and M. Satterthwaite, "Efficient Mechanisms for Bilateral Trade," Journal of Economic Theory, vol. 28, pp. 265-281, 1983. 11. Acknowledgements To be supplied. 12. Author Information Yakov Rekhter cisco Systems, Inc. 170 Tasman Dr. San Jose, CA 95134 Phone: (914) 528-0090 email: yakov@cisco.com Paul Resnick AT&T Research 600 Mountain Avenue Murray Hill, NJ 07974 Phone: (908) 582-5370 email: presnick@research.att.com Steven M. Bellovin AT&T Research 600 Mountain Avenue Murray Hill, NJ 07974 Phone: (908) 582-5886 email: smb@research.att.com Rekhter, Resnick, Bellovin [Page 12]