Network Working Group T. Li
INTERNET-DRAFT Juniper Networks
Expire in six months Y. Rekhter
cisco Systems
June 1996
Towards a Cost Model for Routing and Addressing
<draft-li-piara-cost-model-00.txt>
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
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material 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).
Introduction
The IP address space is a fixed size, fully recyclable resource which
must be shared amongst the entire Internet community in order to
achieve global connectivity. Similarly, the routing table entries in
the routers that comprise the backbone are a scarce resource.
Squandering either of these resources can lead to an Internet in
which some systems have significantly reduced reachability.
There are a variety of mechanisms which could be employed to ensure
that neither address space nor routing table space is needlessly
wasted. Some have proposed [Rekhter, Resnick] that a market based
approach is a practical and reasonable allocation of these scarce
resources.
This memo is a preliminary investigation into a cost model for
routing and addressing services, in an attempt to understand the
interaction between the address market and the routing table entry
market. As this is a preliminary model, it makes some significant
simplifications. It's hoped that this memo will also interest those
Li, Rekhter [Page 1]
INTERNET-DRAFT Towards a Cost Model June 1996
more skilled in the art of cost modeling to correct and refine this
model.
The Intuitive Model
We begin by constructing the model based on the costs that the user
sees when provisioning Internet service. We make the simplifying
assumption that the user needs to provision a singly homed, non-
transit domain (a.k.a., a stub network) that can be addresse entirely
by a single prefix (i.e., a contiguous power of two range of
addresses). Note that the following analysis can be extended for
multiple prefixes by extending the cost functions to take vectors of
prefixes as arguments.
In purchasing such an Internet service, we posit that there are three
significant costs: the cost of bandwidth, the cost of addressing, and
the cost of routing. We'll proceed by describing these components
intuitively and then turn to a more formal description. The cost of
bandwidth includes the cost of the link, both in installation and
periodic charges, and the hardware necessary to support both ends of
the link (e.g., routers, CSU/DSU's, cables, etc.). There will also
be an administrative component to support the link and other non-
addressing and non-routing services, which we will consider to be
part of the cost of bandwidth in order to simplify this analysis.
Note that this implies that the cost of bandwidth is a function of
the bandwidth requested and the service provider that it's requested
from. Also note that we make the simplifying assumption that
bandwidth from all providers is identical, implying a consistent
level of service from all competitors in a local market.
The cost of addressing is the amount that the user must pay to borrow
a particular prefix from an address broker. The bandwidth provider
may or may not be an address broker. This cost would include any
charges for the administrative costs of lending out the prefix, such
as DNS PTR record maintenance. Thus, the cost of addressing is a
function of the prefix and the address broker. It's likely that the
addressing cost is charged periodically.
The cost of routing is the amount that the user must pay to the
provider for routing information to the remainder of the Internet.
This may involve making configuration changes in a series of routers,
in a routing registry, or in the administrative databases of several
domains. In the common case where the bandwidth provider is also the
address broker, it is likely that the cost of routing is amortized
across all customers sharing the particular address block that
contains the user's prefix and that the cost of routing is a periodic
charge.
Li, Rekhter [Page 2]
INTERNET-DRAFT Towards a Cost Model June 1996
Note that not all of these costs may be apparent today. This is not
to say that these costs do not exist, just that they're not charged
for separately.
The Formal Model
In this section, we describe all of the above in a more formal
manner. First, we let the cost of bandwidth be a function Cbw : BW X
Prov -> $, where BW is the space of possible bandwidths, Prov is the
space of possible providers, and $ is the space of monetary cost. We
will also write this as Cbw(bw, P), where bw is the bandwidth and P
is the provider.
Second, we let the cost of addressing be a function Ca : Pref X Brok
-> $, where Pref is the space of possible address prefixes, and Brok
is the space of address brokers. We will also write this as Ca(p,
B). Note that the space of address brokers may intersect with the
space of service providers.
Third, we let the cost of routing be a function Cr : Pref X Prov ->
$. We will write this as Cr(p, P). We assume that Cr is not
sensitive the size of prefix p, but it is sensitive to the allocation
of prefix p. Thus, it costs the same to route a /16 or a /8 prefix.
However, a /16 from another provider may cost more to route that a
/16 where P = B.
Finally, we let the total cost be the function C : BW X Prov X Brok X
Pref -> $. We will write this as C(bw, P, B, p). Further, as this
is simply the sum of the previous three functions, we have:
C(bw,P,B,p) = Cbw(bw,P) + Ca(p,B) + Cr(p,P) (1)
Some Observations
We make the simplifying assumptions that the market always has
perfect information and that the consumer will always minimize the
overall cost C.
Observation 1: If Ca(p,B) is insensitive to the size of prefix p,
then address space will be squandered.
In this situation, there is no negative feedback to the user for
wasting address space. As there is potential benefit in having
future address space available, it is in the user's best interest to
overstate their addressing needs. Subsequently, demand for addresses
will increase, and Ca(p,B) will rise. If it rises sufficiently, then
those who have borrowed an address will subdivide their unused
addresses, becoming brokers themselves, thus resulting in a Ca(p,B)
Li, Rekhter [Page 3]
INTERNET-DRAFT Towards a Cost Model June 1996
which is sensitive to the size of the prefix. This is to say that an
insensitive Ca(p,B) is self-correcting.
Corollary 1: If Ca(p,B) is 0, then address space will be squandered.
Observation 2: If Ca(p,B) << C(bw,P,B,p), then address space will be
squandered.
By reasoning similar to that of Observation 1, the marginal cost of
unnecessary address space must exceed the user's marginal benefit of
such space, given the user's cost sensitivity or address space will
be wasted. For example, consider the case where Ca is only 0.01% of
C, and doubling the size of the prefix results in doubling Ca. The
resulting Ca is only 0.02% of C, which is not a significant deterrent
to wasting addresses.
Corollary 2: If Ca(p,B) << Cr(p,P), then address space will be
squandered.
Observation 3: We call a prefix which is borrowed from the service
provider a 'local prefix'. We call a prefix which borrowed from a
broker who is not the service provider a 'foreign prefix'. If
Cr(p,P) is insensitive to whether a prefix is local or foreign, then
routing table entries will be squandered.
Note that we also make the simplifying assumption that proxy
aggregation is not effective. In the above scenario, if the local
and foreign prefixes are identical in cost, then it the user will
optimize wholly based on the independent costs of bandwidth and
address space, obtaining address space from any address broker,
regardless of the possibilities of aggregation. Normal entropy at
this point will eventually flood the backbone routing tables. Note
that a Cr(p,P) which is insensitive to foreign prefixes is also self
correcting as it will increase demand on routing table entries,
thereby encouraging aggregation.
Corollary 3: If Cr(p,P) = 0 for a foreign prefix, routing table
entries will be squandered.
Observation 4: If Cr(p,P) << C(bw,P,B,p) then routing table entries
will be squandered.
By reasoning similar to observation 2.
Corollary 4: If Ca(p,B) >> Cr(p,P), then routing table entries will
be squandered.
Corollary 5: To encourage conservation, Ca(p,B) and Cr(p,P) must be
Li, Rekhter [Page 4]
INTERNET-DRAFT Towards a Cost Model June 1996
proportional to Cbw(bw,P), and Ca(p,B) ~= Cr(p,P).
From observations 2 and 4 and equation (1), it follows that
increasing Cbw(bw,P) must also increase Ca(p,B) and Cr(p,P). From
corollaries 2 and 4, it follows that Ca(p,B) and Cr(p,P) must be
roughly equal.
Observation 5: Within the U.S., Cbw(bw,P) is predominantly a function
of the length of the circuit and bandwidth selected.
Hardware costs are generally a small fraction of the line costs
involved in providing bandwidth, usually due to periodic or usage
charges. These charges are a function of the length of the circuit
(or distance called) and the bandwidth of the circuit. The
granularity of the length of the circuit varies depending on the
exact media (e.g., Frame Relay may be sold for a flat rate anywhere
within a LATA. Local loops may be charged by the mile.) Outside the
U.S., the local tariff structure may have significant political
distortions.
Corollary 6: To encourage conservation within the U.S., Ca(p,B) and
Cr(p,P) must be a significant function of the length and bandwidth of
the circuit.
Note that this is a non-intuitive result which will be difficult to
justify to most customers. We suspect that many providers will not
even attempt to do so, instead charging a flat rate for routing
services, or basing the charge on prefix length. If this occurs,
corollary 5 implies that those who are paying the most for Internet
services will see little economic incentive for conservation.
It's also interesting to observe that an address broker who is not
also the service provider has a particularly difficult situation.
For the broker to be an agent of conservation, she must charge
varying amounts based on the cost of bandwidth as charged by the
service provider. This coupling of costs between different entities
has possibly severe legal and logistic implications, not the least of
which is the liability of anti-trust action for price fixing. As a
result, it seems as if an address broker can never actually price
address space in a manner that is consistent with address space
conservation.
Conclusions
This memo has attempted to posit a simple cost model for Internet
addressing and routing in order to help understand the possible
markets for address space and routing services. The model focused on
the costs as seen by an end user. The implications of the model are
Li, Rekhter [Page 5]
INTERNET-DRAFT Towards a Cost Model June 1996
rather disturbing. If the end user does see costs that would
encourage conservation, then the costs are non-trivial and are
proportional to the cost of the bandwidth that he purchases.
Further, in such a situation, there appears to be no feasible role
for an independent address broker, resulting in users who have to get
address space from their service provider.
Alternatively, if a 'natural' market for address space and routing
services develops, then the costs for these services are independent
of the other costs of provisioning Internet services. The
implication is that those who are not cost sensitive will not be well
motivated to conserve scarce resources.
We further observe that perfect allocation of scarce resources cannot
occur unless there is a perfectly accurate measurement of each users
need for address space and routing services. The willingness to pay
for a resource is only slightly correlated with true need. Thus, any
scheme which depends on cost for resource allocation is inherently
flawed and can at best provide a first order approximation. The only
alternative to such a cost based scheme is political allocation,
which has a variety of its own problems.
Acknowledgements
Tony Li's contribution to this work was supported in part by cisco
Systems, Inc.
References
[Rekhter] Rekhter, Yakov, "Charging for Routes", Presentation at the 35th
IETF, March 1996
[Resnick] Resnick, Paul, "Suggestions for Market-Based Allocation of IP
Address Blocks", Internet Draft,
draft-ietf-cidrd-mktbased-alloc-00.txt, Feb. 1996
Authors' Addresses
Tony Li
Juniper Networks, Inc.
101 University Ave Ste 240
Palo Alto, CA 94301
Phone: +1 (415) 614 4145
Email: tli@jnx.com
Yakov Rekhter
cisco Systems, Inc.
170 Tasman Dr.
Li, Rekhter [Page 6]
INTERNET-DRAFT Towards a Cost Model June 1996
San Jose, CA 95134
Phone: (914) 528-0090
Email: yakov@cisco.com
Li, Rekhter [Page 7]