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]