Internet DRAFT - draft-ietf-cidrd-ownership
draft-ietf-cidrd-ownership
HTTP/1.1 200 OK
Date: Tue, 09 Apr 2002 01:39:09 GMT
Server: Apache/1.3.20 (Unix)
Last-Modified: Fri, 06 Oct 1995 23:00:00 GMT
ETag: "2ed689-78fb-3075b4f0"
Accept-Ranges: bytes
Content-Length: 30971
Connection: close
Content-Type: text/plain
CIDRD Working Group Y. Rekhter
INTERNET DRAFT cisco Systems
T. Li
cisco Systems
October 1995
Implications of Various Address Allocation Policies for Internet Routing
<draft-ietf-cidrd-addr-ownership-02.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. Internet Drafts may be updated, replaced,
or obsoleted by other documents at any time. It is not
appropriate to use Internet Drafts as reference material
or to cite them other than as a ``working draft'' or
``work in progress.''
Please check the 1id-abstracts.txt listing contained in
the internet-drafts Shadow Directories on nic.ddn.mil,
nnsc.nsf.net, nic.nordu.net, ftp.nisc.sri.com, or
munnari.oz.au to learn the current status of any Internet
Draft.
1 Abstract
IP unicast address allocation and management are
essential operational functions for the Public Internet.
The exact policies for IP unicast address allocation and
management continue to be the subject of many
discussions. Such discussions cannot be pursued in a
vacuum - the participants must understand the technical
issues and implications associated with various address
allocation and management policies.
The purpose of this document is to articulate certain
relevant fundamental technical issues which must be
considered in formulating unicast address allocation and
Expiration Date April 1996 [Page 1]
INTERNET DRAFT October 1995
management policies for the Public Internet. The major
focus of this document is on two possible policies,
"address ownership" and "address lending", and the
technical implications of these policies for the Public
Internet.
2 On the intrinsic value of IP addresses
Syntactically, the set of IPv4 unicast addresses is the
(finite) set of integers in the range 0x00000000 -
0xdfffffff. IP addresses are used for Network Layer (IP)
routing - an IP address is the sole piece of information
about the node that is injected into the routing system.
The notable semantics of an IP unicast address is its
ability to gain access to the Public Internet routing
service and thereby exchange data with the remainder of
the Internet. In other words, in the context of the
Public Internet, it is the reachability of an IP address
that gives it an intrinsic value - without reachability
the address is worthless.
The above implies that in the context of the Public
Internet it is the service environment (the Internet) and
its continued operation, including its routing system,
which provides an IP address with its intrinsic value,
rather than the inverse. Consequently, if the Public
Internet routing system ceases to be operational, the
service disappears, and the addresses cease to have any
functional value in the context of the Internet. At this
point, in the context of the Public Internet, all address
allocation and management policies, including existing
policies, are rendered meaningless.
3 Hierarchical routing and its implication on address
allocation
Hierarchical routing [Kleinrock 77] is a mechanism that
allows to improve the scaling property of a routing
system. Hierarchical routing is the only proven
mechanism for scaling routing to the current size of the
Internet.
Hierarchical routing works by taking a set of addresses
and generating a single routing advertisement (route) for
the entire set. Further, if addresses are assigned
correctly, this can be done recursively: multiple
advertisements (routes) can be combined into a single
Expiration Date April 1996 [Page 2]
INTERNET DRAFT October 1995
advertisement (route). By exercising this recursion, the
amount of information necessary to provide routing can be
decreased substantially.
A common example of hierarchical routing is the phone
network (and more precisely, the North American Numbering
Plan), where country codes, area codes, exchanges, and
finally subscriber lines are different levels in the
hierarchy. In the phone network, a switch need not keep
detailed routing information about every possible
subscriber in a distant area code. Instead, the switch
knows one routing entry for the entire area code.
Notice that the effect on scaling is dramatic. If we
look at the space complexity of the different schemes,
the switch which knows about every subscriber in the
world needs O(n) space for n worldwide subscribers. Now
consider the case of hierarchical routing. If we break n
down into the number of subscribers in the local area
(l), the number of other exchanges in the area code (e),
the number of other area codes in the local country code
(a) and the number other country codes (c), then
hierarchical routing has space complexity O(l + e + a +
c). Notice that each of these factors is much, much less
than n, and grows very slowly, if at all. This implies
that a phone switch can be built today which has some
hope of not running out of space as soon as it is
deployed.
The fundamental property of hierarchical routing that
makes this scalability possible is the ability to form
abstractions: in this case the ability to group
subscribers into exchanges, area codes and country codes.
Further, such abstractions must provide useful
information for the ability to perform routing. Some
abstractions, such as the group of users with green
phones, are not useful when it comes time to route a
call.
Since the information that routing really needs is the
location of the address within the topology, for
hierarchical routing, the useful abstraction must capture
the topological location of an address within the
network. In principle this could be accomplished by
either (a) constraining the topology (and allowed
topology changes) to match address assignment, or (b)
avoiding constraints on the topology (and topology
changes), but requiring that as the topology changes, an
entity's address may need to change as well - this
process is known as "renumbering."
Expiration Date April 1996 [Page 3]
INTERNET DRAFT October 1995
4 Scaling the Internet routing system
The enormous growth of the Public Internet places a heavy
load on the Internet routing system. The growth rate has
doubled the size of the routing table roughly every 9
months. At the same time, computer technology doubles
roughly every 24 months, resulting in untenable mismatch.
Even if we would double capacities of routers in the
Internet every 24 months or so, while the Internet is
doubling every 9 months, sooner or later the size of the
routing tables is going to exceed the limit of the
routers, even if we would keep upgrading the routers as
fast as the computer industry can do so. Therefore, to
preserve uninterrupted continuous growth of the Public
Internet it is essential to deploy mechanisms(s) that
contain the growth rate of the routing information.
In absence of mechanism(s) to contain the growth rate of
the routing information, the Internet growth would have
to be either limited or even frozen, or the Internet
routing system would become overloaded. The result of
routing overload is that the routing subsystem will fail:
either equipment (routers) will not be able to maintain
an adequate number of routes to insure global
connectivity, or providers will simply exclude certain
routes to insure that other routes do provide global
connectivity to particular sites. This document assumes
that neither of the outcomes mentioned in this paragraph
is acceptable.
Classless Inter-Domain Routing (CIDR) [RFC1518, RFC1519]
have been deployed since late 1992 in the Public Internet
as the primary mechanism to contain the growth rate of
the routing information - without CIDR the Internet
routing system would already have collapsed (without
CIDR, the routing table today would be approximately
105,000 routes; thanks to CIDR, the table is instead
30,000 routes).
CIDR is an example of the application of hierarchical
routing in the Public Internet, where subnets,
subscribers, and finally providers are some of the many
different possible levels in the hierarchy. For example,
a router within a site need not keep detailed routing
information about every possible host in that site.
Instead the router maintains routing information on a per
subnet basis. Likewise, a router within a provider need
not keep detailed routing information about individual
subnets within its subscribers. Instead the router could
maintain routing information on a per subscriber basis.
Moreover, a router within a provider need not keep
detailed routing information about stub (single home)
subscribers of other providers. Instead the router could
Expiration Date April 1996 [Page 4]
INTERNET DRAFT October 1995
maintain routing information on a per provider basis.
As a result of pre-CIDR address allocation, today there
is a considerable number of routes in the Internet that
are not suitable for hierarchical aggregation. Moreover,
there are sites with pre-CIDR address allocation that are
not yet connected to the Internet. If these sites would
connect to the Internet at some point in the future, the
routes to these sites are unlikely to be suitable for
hierarchical aggregation.
The topology of the Public Internet, taken as a whole, is
not strictly hierarchical, even though most parts are.
The hierarchical routing requires that aggregation
boundaries for the addressing information be formed along
some hierarchy. As a result, there are a number of
exceptions which will have to be injected into the
routing system in the future, in addition to those
exceptions which currently exist. Each such exception
that is added to the routing system has a deleterious
effect on the scalability of the routing system. The
exact number of exceptions which can be tolerated is
dependent on the technology which is used to support
routing. Unbridled growth in the number of such
exceptions will certainly cause the routing system to
collapse.
4 Address allocation and management policies
IP address allocation and management policy is a fairly
complex, multifaceted issue. It covers a broad range of
issues, such as who formulates the policies, who executes
the policies, what are the roles of various registries,
what are the roles of various organizations (e.g., ISOC,
IAB, IESG, IETF, IEPG, various government bodies, etc.),
the participation of end users in requesting addresses,
and so on.
Address allocation and management and the ability of the
Internet routing system to scale are not independent -
only certain address allocation and management policies
yield scalable routing. The Internet routing system is
subject to both technological and fundamental
constraints. These constraints restrict the choices of
address allocation policies that are practical.
4.1 "Address ownership" allocation policy and its
implications on the Public Internet
Expiration Date April 1996 [Page 5]
INTERNET DRAFT October 1995
"Address ownership" is one possible address allocation
and management policy. The "address ownership" policy
means that a portion of the address space, once allocated
to an organization, remains allocated to the organization
as long as that organization desires to retain it, and
that the portion would not be allocated to any other
organization. Quite often such addresses are referred to
as "portable".
While it have never been expressly stated that various
Internet Registries use the "address ownership"
allocation policy, it has however always been assumed
(and practiced).
To understand the implications of the "address ownership"
policy ("portable" addresses) on the scalability of the
Internet routing system observe that:
(a) by definition, address ownership assumes that
addresses, once assigned, do not change owners, i.e.
the same addresses remain at the same organization no
matter how radically the organization might change its
connectivity to the Public Internet, and therefore no
renumbering can take place;
(b) by definition, hierarchical routing assumes that
addresses reflect network topology as much as
possible.
Therefore, the only way to accommodate both address
ownership and hierarchical routing for everyone is to
assume that the topology (or at least certain pieces of
it) will be permanently fixed. Given the distributed,
decentralized, largely unregulated, and global
(international) nature of the Internet, constraining the
Internet topology (or even certain parts of it) may have
far reaching technical, social, economical, and political
implications. So far little is known of what these
implications are; even less is known whether these
implications would be acceptable (feasible) in practice.
Therefore, at least for now we have to support the
Internet whose topology (and allowed topology changes)
is not constrained.
Since the Internet does not constrain the topology (or
allowed topology changes), in the Internet we can
accommodate one, but not both - we can either have
address ownership ("portable" addresses) for everyone, in
which case the routing overhead will lead to a breakdown
of the routing system resulting in a fragmented
(partitioned) Internet, or we can have a routable
Internet, but without address ownership ("portable"
addresses) for everyone.
Expiration Date April 1996 [Page 6]
INTERNET DRAFT October 1995
4.2 "Address lending" allocation policy and its implications
on the Public Internet
Recently, especially since the advent of CIDR,
subscribers and providers have followed a model in which
address space is not owned (not portable), but is bound
to the topology. This model suggests an address
allocation and management policy that differs from the
"address ownership" policy. The following describes a
policy, called "address lending", that provides a better
match (as compared to the "address ownership" policy) to
the model.
An "address lending" policy means that an organization
acquires its addresses on a "loan" basis. For the length
of the loan, the lender cannot lend the addresses under
the loan to any other borrower. Assignments and
allocations based on the "address lending" policy should
explicitly include the conditions of the loan. Such
conditions must include that the allocation be returned
if the borrower is no longer contractually bound to the
lender, and the lender can no longer provide aggregation
for the allocation. If a loan is terminated, the
organization can no longer use addresses acquired via the
loan, and therefore has to acquire new addresses and
renumber to new addresses. The "address lending" policy
does not constrain how the new addresses could be
acquired.
This document expects that the "address lending" policy
would be used primarily by Internet Registries associated
with providers; however, this document does not preclude
the use of the "address lending" policy by an Internet
Registry that is not associated with a provider.
This document expects that when the "address lending"
policy is used by an Internet Registry associated with a
provider, the provider is responsible for arranging
aggregation of these addresses to a degree that is
sufficient to achieve Internet-wide IP connectivity.
This document expects that when the "address lending"
policy is used by an Internet Registry associated with a
provider, the terms and conditions of the loan would be
coupled to the service agreement between a provider's
subscriber that borrows the addresses and the provider
that lent the addresses. That is, if the subscriber moves
to another provider, the loan would be terminated.
To minimize disruptions when a subscriber changes its
providers, this document strongly recommends that the
terms and conditions of the loan should include a grace
period provision. This provision would allow a subscriber
Expiration Date April 1996 [Page 7]
INTERNET DRAFT October 1995
that disconnects from its provider a certain grace period
after the disconnect. During this grace period, the
borrower (the subscriber) may continue to use the
addresses obtained under the loan. This document
recommends a grace period of at least 30 days. At the
same time, to contain the routing information overhead,
this document suggests that a grace period be no longer
than 6 months.
To understand the implications of the "address lending"
policy on the scalability of the Internet routing system,
observe that if an organization (subscriber) borrows its
addresses from a block of addresses of its provider, then
the provider would be able to aggregate addressing
information for all such subscribers into a single
address prefix. This reduces the amount of routing
information that needs to be carried by the Internet
routing system (for more on this see Section 5.3.1 of
RFC1518). As the organization (subscriber) changes its
provider, the loan from the old provider would be
returned, and the loan from the new provider would be
established. As a result, the organization would renumber
to the new addresses. Once the organization renumbers,
the new provider would be able to aggregate addressing
information for the organization with addressing
information for the rest of its subscribers that lease
their addresses out of the block of the provider.
Therefore, the "address lending" policy, if applied
appropriately, is consistent with the constraints on
address allocation policies imposed by hierarchical
routing, and thus promotes a scalable routing system.
Thus, the "address lending" policy, if applied
appropriately, could play an important role in enabling
the continuous uninterrupted growth of the Internet.
To be able to scale routing in other parts of the
hierarchy, the "lending" policy may also be applied
hierarchically, so that addresses may in turn be loaned
to other organizations. The implication here is that the
termination of a single loan may have effects on
organizations which have recursively borrowed a portion
of the address space from the main allocation. The exact
effects are difficult to determine a priori as a loan may
represents a sufficient degree of aggregation within a
lower level of the hierarchy and which be aggregated at a
higher level, thus not affecting higher levels of the
routing hierarchy.
4.3 In the absence of explicit "address lending" policy
Organizations connecting to the Internet should be aware
Expiration Date April 1996 [Page 8]
INTERNET DRAFT October 1995
that even if their current provider, and the provider
they switch in the future would not require renumbering,
renumbering may still be needed in order to achieve
Internet-wide IP connectivity. For example, an
organization may now receive Internet service from some
provider and allocate its addresses out of the CIDR block
associated with the provider. Later the organization may
switch to another provider. The previous provider may
still be willing to allow that organization to retain a
portion of the provider's CIDR block (allow the
organization to "own" addresses), and accept a more
specific prefix (that covers destinations within the
organization) from the new provider. Likewise, the new
provider may be willing to accept that organization
without renumbering and advertise the more specific
prefix (that covers destinations within the organization)
to the rest of the Internet. However, if there exist one
or more other providers, that is unwilling or unable to
accept the long prefix (that covers destinations within
the organization) advertised by the new provider, then
the organization would not have IP connectivity to a
portion of the Internet. In the future, this may become
a large portion, perhaps even the majority.
The above shows that the absence of explicit "address
lending" policy from a current provider in no way assures
that renumbering will not be required in the future when
changing providers. Organizations should be aware of
this fact should they encounter a provider making claims
to the contrary.
5 Recommendations
Observe that the goal of hierarchical routing in the
Public Internet is not to reduce the total amount of
routing information in the Internet to the theoretically
possible minimum, but just to contain the volume of
routing information within the limits of technology,
price/performance, and human factors. Therefore,
organizations which could provide reachability to a
sufficiently large fraction of the total destinations in
the Internet and could express such reachability through
a single IP address prefix could expect that a route with
this prefix will be maintained throughout the default-
free part of the Internet routing system. Therefore,
using the "address ownership" policy when allocating
addresses to such organizations is a reasonable choice.
Within such organizations this document suggests to use
the "address lending" policy.
Expiration Date April 1996 [Page 9]
INTERNET DRAFT October 1995
For all other organizations that expect Internet-wide IP
connectivity, the reachability information they inject
into the Internet routing system should be subject to
hierarchical aggregation. For such organizations,
allocating addresses based on the "address ownership"
policy makes hierarchical aggregation difficult, if not
impossible. This, in turn, has a highly detrimental
effect on the Internet routing system. To prevent
collapse of the Internet routing system, for such
organizations this document recommends to use the
"address lending" policy. Consequently, when such an
organization first time connects to the Public Internet
and wants to acquire Internet-wide IP connectivity, or
changes its topological attachment to the Public
Internet, but wishes to preserve Internet-wide IP
connectivity, the organization eventually (within the
grace period) needs to renumber to eliminate any
exceptional prefixes that the organization would
otherwise inject into the Internet routing system. This
applies to the case where the organization takes its
addresses out of its direct provider's block and the
organization changes its direct provider. This may also
apply to the case where the organization takes its
addresses out of its indirect provider's block, and the
organization changes its indirect provider.
Carrying routing information has a cost associated with
it. This cost, at some point, may be passed back in full
to the organizations that inject the routing information.
Aggregation of addressing information (via CIDR) could
reduce the cost, as it allows to increase the number of
destinations covered by a single route. Organizations
whose addresses are allocated based on the "address
ownership" policy (and thus may not be suitable for
aggregation) should be prepared to absorb the cost
completely on their own.
Observe that neither the "address ownership", nor the
"address lending" policy, by itself, is sufficient to
guarantee Internet-wide IP connectivity. Therefore, we
recommend that sites whose addresses are allocated based
on either the "address ownership", or the "address
lending" policy should consult with their providers about
the reachability scope that could be achieved with these
addresses, and associated costs that result from using
these addresses.
If the organization doesn't require Internet-wide IP
connectivity, then address allocation for the
organization could be done based on the "address
ownership" policy. In this case the organization may
still maintain limited IP connectivity (e.g., with all
the subscribers of its direct provider) by limiting the
Expiration Date April 1996 [Page 10]
INTERNET DRAFT October 1995
distribution scope of its routing information to its
direct provider. Connectivity to the rest of the
Internet could be accomplished by the use of application
layer gateways, Network Address Translators (NATs), etc.
Use of these technologies eliminates the need for
renumbering.
Both renumbering (due to the "address lending" policy)
and non-aggregated routing (due to the "address
ownership" policy) result in some costs. Therefore, an
organization needs to carefully analyze its own
connectivity requirements and compare the tradeoffs
associated with using addresses acquired via the "address
lending" policy vs. addresses acquired via "address
ownership". To reduce the cost of renumbering
organizations should be strongly encouraged to deploy
tools that facilitate renumbering (e.g., Dynamic Host
Configuration Protocol [RFC 1541]). Use of the DNS should
be strongly encouraged.
6 Summary
Any address allocation and management policy for IP
addresses used for the Internet connectivity must take
into account its impact on the scalability of the Public
Internet routing system. Among all of the possible
address allocation and management policies only the ones
that yield a scalable routing system are feasible - all
other policies are self-destructive in nature, as they
lead to a collapse of the Internet routing system, and
thereby to the fragmentation (partition) of the Public
Internet.
Within the context of the current Public Internet,
address allocation and management policies that assume
unrestricted address ownership have an extremely negative
impact on the scalability of the Internet routing system.
Such policies are almost certain to exhaust the
scalability of the Internet routing system well before we
even approach the exhaustion of the IPv4 address space
and certainly well before we will be able to make
moderate use of the IPv6 address space. As a result,
with the current technology or any near-term foreseeable
technology, given the Internet's growth rate, the notion
that everyone should able to own address space and
receive Internet-wide routing services, regardless of
where they connect to the Internet, is technically
infeasible. Therefore, this document recommends that (a)
the "address lending" policy should be formally added to
the set of address allocation policies in the Public
Internet, and (b) such policy should be used to deliver
Expiration Date April 1996 [Page 11]
INTERNET DRAFT October 1995
routing services to organizations that by themselves do
not provide a sufficient degree of routing information
aggregation.
Since the current IPv6 address allocation architecture is
based on CIDR, recommendations presented in this document
apply to IPv6 address allocation and management policies
as well.
7 Security Considerations
Security issues are not discussed in this document.
8 Acknowledgments
This document borrows heavily from various postings on
various mailing lists. Special thanks to Noel Chiappa,
Dennis Ferguson, Eric Fleischman, Geoff Huston, and Jon
Postel whose postings were used in this document.
Many thanks to Scott Bradner, Randy Bush, Brian
Carpenter, Noel Chiappa, David Conrad, John Curran, Sean
Doran, Robert Elz, Dorian Kim, Thomas Narten, Andrew
Partan, Dave Piscitello, Simon Poole, Curtis Villamizar,
and Nicolas Williams for their review, comments, and
contributions to this document.
Finally, we like to thank all the members of the CIDR
Working Group for their review and comments.
9 References
[Kleinrock 77] Kleinrock, L., Farouk, K., "Hierarchical
Routing for Large Networks," Computer Networks 1 (1977),
North-Holland Publishing Company.
[RFC 1541] Droms, R., "Dynamic Host Configuration
Protocol".
[RFC 1519] V. Fuller, T. Li, J. Yu, K. Varadhan,
"Classless Inter- Domain Routing (CIDR): an Address
Expiration Date April 1996 [Page 12]
INTERNET DRAFT October 1995
Assignment and Aggregation Strategy"
[RFC 1518] Y. Rekhter, T. Li, "An Architecture for IP
Address Allocation with CIDR"
10 Authors' Addresses
Yakov Rekhter
cisco Systems, Inc.
470 Tasman Dr.
San Jose, CA 95134
Phone: (914) 528-0090
email: yakov@cisco.com
Tony Li
cisco Systems, Inc.
470 Tasman Dr.
San Jose, CA 95134
Phone: (408) 526-8186
email: tli@cisco.com
Expiration Date April 1996 [Page 13]
