[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
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]