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]