List of constraints on a successful scalable routing solution which result from the need for widespread voluntary adoption

Robin Whittle  2009-04-22
This is version 04 of this text.
../ To my page on the RRG in 2009.  ../../ To the main Ivip page.

Here is the Text I hope to refine so most people are happy with it.  Please let me know your critiques and suggested improvements, on the RRG list or to rw@firstpr.com.au .  If enough people like it, perhaps it could be included in: http://tools.ietf.org/html/draft-irtf-rrg-recommendation .

* at the right means something I have altered recently.  See the Changelog for details.

The Footnote below does not add meaning to the Text, although there is an example of a cell-phone IPv6 adoption which is a circumstance in which these constraints would not fully apply.  This illustrates how the constraints will apply to any foreseeable attempt to have existing and future non-cellphone end-user networks adopt a scalable routing solution.  

The Footnote mentions the goals of a scalable routing solution and some other related matters, including things which have been mentioned as desirable additions to the Text but which I decided not to add.

The Text

Constraints imposed by the need for widespread voluntary adoption
-----------------------------------------------------------------

A successful solution to the routing and addressing
scaling problem is tightly constrained by the need for
it to be both accessible to and voluntarily adopted by
the great majority of end-user networks of all sizes
who want or need multihoming, inbound traffic
engineering and/or portability of their address space
between ISPs.
 
Broadly speaking, this means that at the time of
introduction:

  1 - The solution must provide immediate and
      compelling benefits to any new or existing 
      end-user networks which
adopt it, irrespective
      of how many other 
networks have so far adopted
      it.


  2 - Therefore, it must provide multihoming, TE and
      portability for the adopting networks in a
      manner which fully supports communications with
      all hosts - including all hosts in non-upgraded
      networks.

  3 - Therefore, the solution must be compatible with
      all hosts (stacks and applications) and routers
      in non-upgraded networks.

  4 - The solution must be compatible with all
      existing applications in the adopting networks.

  5 - Although in principle, some or many host stacks
      could be upgraded in the adopting networks, the
      difficulties this presents means that a scalable
      routing solution will only be widely enough
      adopted on a voluntary basis if no such upgrades
      are required in order for the new system to
      provide compelling benefits.

      Firstly, there are difficulties in motivating
      operating system / stack programmers to add and
      test new facilities.  Secondly there may be
      costs and disruption for the adopting network in
      upgrading the stacks.  Thirdly, in many or most
      end-user networks, some or many hosts will not
      be amenable to stack upgrades due to them using
      operating systems which are no longer being
      maintained or developed.  This is especially
      the case for devices such as printers, routers
      etc. which do not use one of the major
      operating systems.

  6 - If the solution requires extra functionality in
        * 04
      interdomain routers, then it must be feasible from
     *
      technical and business perspectives for the relevant    *
      routers to have this functionality in time for
         *
      deployment.  For instance, a core-edge separation       *
      scheme which relied on new router functions for         *
      ITR to ETR tunneling would require the functionality    *
      to be present in all transit routers and in the         *
      routers of all ISPs with customers which adopt the      *
      solution.                                               *

  7 - The solution must be attractive for the large
      number of smaller networks who currently cannot
      get PI space to do multihoming etc.  Our goal is
      not just to reduce the number of DFZ routes but
      to enable a much larger number of end-user
      networks to gain multihoming, TE and portability
      than is currently possible.

  8 - Ideally the solution will also be attractive for
      most or all end-user networks who currently have
      their own PI prefixes.  This is firstly to
      improve scaling by attracting those larger
      end-user networks away from their current
      conventional PI address space usage and secondly
      to ensure that smaller networks which aspire to
      be bigger in the future will perceive the new
      kind of scalable end-user network address space
      as suitable for their long-term needs.

  9 - Ideally the new system should not compromise
      security or performance compared to that of
      current PI or PA techniques.  Any degradation in
      security, packet path lengths, end-to-end packet
      transit times, packet loss rates and general
      robustness etc. needs to be more than
      compensated for by reduced costs and/or benefits
      such as a more flexible and responsive
      multihoming restoration capability than is
      possible with current BGP techniques.

 10 - The solution will probably not be widely enough    
      adopted if it requires upgrades to the internal
      routers of adopting networks - except perhaps in
      small networks such as SOHO where one or a few     
      inexpensive routers need upgrading anyway to       
      perform ITR and ETR etc. functions.

In the longer term - in the years and decades to come
- upgrades to DFZ routers, to ISP and end-user network
internal routers, to host stacks and to some
applications may be made
without significant cost or
inconvenience and may
allow enhanced performance for
the new system.

The benefits resulting from the best imaginable
solution for IPv4 may be limited by shortage of IPv4
space and resulting difficulties for new networks in
gaining this space.  While no such restrictions exist
with IPv6, constraints similar to 2, 3, 4 and 5 are
likely to continue to be a barrier to widespread
migration to IPv6.

The above constraints generally apply for IPv4 when
end-user networks already have IPv4 space and need to
retain full connectivity to all, or almost all,
existing hosts.  They may not apply in other
circumstances, such as if IPv4 space is unobtainable
and/or if the functionality of devices in a newly
established end-user network does not depend so
strongly on connectivity to IPv4 hosts and/or if the
hosts in the new network are all purpose built for
it.  Development of a large IPv6-based cellphone
network may exemplify these circumstances.



The Footnote


This is NOT text I expect everyone to agree with, but it supplies some background for the above and mentions various loose ends.  

Any piece of text such as the above leads thoughtful folks to questions and suggestions for extensions.  I want to keep the scope of the above text focused on the constraints on sufficiently wide adoption of a scalable routing solution, based on our reliance on voluntary adoption by end-user networks and their ISPs.

Tom Vest suggested msg04819msg04830 and msg04856 extending the text to include a goal of the solution enabling access to new entrants after the IPV4 fresh space run out - such as by adding a goal, requirement or whatever that IPv6 would be widely adopted and therefore be a usable alternative to IPv4.  However, this Text is not a set of goals - it is intended to be a statement of facts about constraints which most RRG people agree with.  There are many other constraints and goals - I just want to list those constraints which arise from our dependence on widespread voluntary adoption.

Please read Tom's messages and my responses.  He raises many points of interest which I do not fully respond to in the Footnote.

Please suggest improvements to this footnote or debate it on the RRG list.  Maybe if enough people like parts of it, those parts might wind up in the http://tools.ietf.org/html/draft-irtf-rrg-recommendation too.


Footnote
--------

It is tempting to add to the above Text in ways which
would broaden its scope.  I want to 
scratch that itch
in this Footnote rather than burden
the Text with more
words and greater responsibilities.
 

The following is an expansive consideration of the
agreed goals of a routing scaling solution, and some
other goals which a solution arguably would also
attain. 

I argue that constraints such as the above are
unfortunately also a barrier to resolving the other
major challenge confronting the Internet: the IPv4
address shortage and its only apparent resolution -
mass migration to a new addressing system such as IPv6
with more space.

I contemplate these other challenges and goals,
including the strong desire / need to support
mobility.

No matter what extra goals we have for a scalable
routing solution, we are absolutely bound by the
above constraints, because we must rely on voluntary
adoption.

When might the constraints not apply?

   It may be possible to imagine a future scenario
   where IPv4 space is completely unobtainable,
   leaving new networks with no option but to populate
   the initially generally uninhabited IPv6 Internet.

   However, this is a simplistic notion.  IPv4 access
   will always be available - just with greater and
   greater degradation due to using NAT to get 
   multiple hosts, or networks, onto one global
   unicast IP address. 

   The question would then be: When does a new network
   decide IPv6-only is better than NATted IPv4? 

   Perhaps this threshold will first be crossed by
   IP-based mobile networks, where only a part of the
   device's functionality depends on access to all
   existing hosts, which would mainly be using IPv4.

   In that situation, the above constraints would not
   apply.  The above constraints assume that users in
   the end-user networks which may adopt the new
   system are primarily using desktop machines,
   running servers, etc. for which full connectivity
   to all other hosts is a primary functional
   requirement.

   In this IPv6 mobile network scenario, there was no
   adequate means of providing full connectivity to
   all other hosts, since suitable IPv4 space was not
   available.  Also, the devices' major functionality
   is to be a cell-phone, mobile media player etc. and
   to interact with other such devices and servers in
   the same network.  Any "content" or service
   provider or whatever who wants to give or sell
   things to these users can do so simply be having
   their servers on IPv6.

   This exception illustrates the principle that the
   above constraints are relevant when the end-users
   networks in question have the option of doing
   nothing - remaining on PI space or PA space
   (without multihoming, TE or portability.  IPv4
   address shortage is not a concern, and the
   functionality of their network is assumed to
   depend entirely on their hosts' ability to
   communicate with essentially all existing hosts:
   IPv4 hosts.


   So the constraints reflect the situation of the
   great majority of end-user networks at the time
   of introduction, such as in the middle or towards
   the end of this decade.


What are the goals of scalable routing?

   The routing and addressing scaling problem can be
   defined by stating some goals, which if achieved in
   a number of years and in the decades to come, would
   solve the problem.  A terse statement of these
   goals is:
:

     A - To limit the growth in the BGP, RIB and
         ideally the FIB demands which are placed on
         all DFZ routers to a level which does not
         involve excessive costs or barriers to entry
         for ISPs. 

     B - Allowing the maintenance or improvement of
         the security and robustness of the
         interdomain routing system.  Also, its
         ability to work with increasing numbers of
         routers and networks and to continue to
         respond rapidly to outages and changes in
         configuration.

     C - Scalably (that is, meeting 1 and 2 above)
         providing for the multihoming, inbound TE and
         portability needs of a growing number of
         end-user networks of all sizes and types,
         from the largest established PI-using
         networks such as corporations and
         universities to the smallest, single person,
         potentially single device, networks of the
         future which have these needs.

         This includes newly established end-user
         networks which have no prior allocation of
         address space.

   As noted below in "
Migration to IPv6" the only
   routing scaling problem which exists is in the
   IPv4 Internet
.  We need to solve this, and be
   ready to deploy a solution in time to ensure
   IPv6 does not develops such a problem.  That
   said, opinions differ considerably as to what
   number of DFZ routes constitutes a problem,
   how many end-user networks need multihoming etc.
   - and so to what degree the problem exists for
   any given set of circumstances.
   
 

Voluntary adoption

   Since we (RRG, IETF etc.) have no coercive powers,
   we can only develop and encourage the use of
   protocols and other arrangements which will help
   solve the scalability problem.  Therefore, we are
   entirely dependent on voluntary adoption - by the
   end-user networks which need multihoming, TE and
   portability and by their ISPs.

   Since there are and will be a much larger number
   of these end-user networks than are currently
   driving the most of the burden on DFZ routers by
   getting  multihoming etc. via their own PI
   addresses, the
solution will only be effective if
   the great majority 
of the total number of these
   current and future
multihoming-needing end-user
   networks adopt the scalable solution.  If even a
   small fraction, however 
defined, of this much
   larger number of end-user
networks kept using
   conventional BGP-based PI space t
hen the scaling
   problem would not be sufficiently
reduced.

   Therefore, we rely not just on voluntary adoption,
   but over a period of years (3 to 6 maybe?) we are
   relying on a widespread, ideally ubiquitous
   adoption 
of the new form of scalable address space
   for
end-user networks which need (in their own
   estimation) 
multihoming, inbound TE and/or
   portability.


   For most current users, the most important
   characteristic of the Internet is its support for
   communication with the hosts of all other users.
   Workarounds for NAT mean that for most applications
   the IPv4 Internet meets this requirement.

   Due to the lack of interoperability between the
   IPv4 
and IPv6 Internets, the IPv6 Internet will
   only meet 
this requirement if and when all users
   adopt it.



Further challenges and goals

   Assuming that the goals A, B and C above can be
   solved 
for IPv4 in the next decade (I think they
   can be) 
there remain several problems and therefore
   goals
which will be increasingly important towards
   the end
of the decade and in the decades to come.  
   Maybe 
other problems will appear, but these three
   are
clearly foreseeable now:

   a - Support for mobility.  (More on this below.)

   b - Shortage of IPv4 address space supporting
       all users, even if it was "fairly distributed"
       (however that is defined).

   c - The fact that IPv4 space is finite and will be
       largely "owned" by established participants
       in the Internet's routing system raises
       important competition policy concerns about the
       ability of new entrants to gain access to
       sufficient usable Internet address space to
       conduct their operations and compete on a
       fair basis.

   I think a few people don't see any point in trying
   to make the most of IPv4 space.  Some may even think
   it is a bad idea.  Their position is that the IPv4
   Internet is moribund and that the only future is in
   IPv6 - so the sooner we migrate to IPv6 the easier
   and better it will be for everyone.

   I think there are arguments for this line of
   thinking, but I think it is unrealistic to expect
   a billion or whatever users to start using some
   new Internet which is no practical use to them
   in order that in the end, we will all be better
   off.  
 
   

Migration to IPv6

   Arguably, if everyone adopted IPv6, all three above
   problems could be solved, since Mobile IP
   techniques (
MIP) work for IPv6 only and since IPv6
   has vastly
more address space than IPv4.

   However, as the years go by, we seem no closer to
   finding a way of transitioning to IPv6 due to
   barriers
such as the need to rewrite many
   applications, user
difficulties with dual-stack
   application behavior and
primarily the lack of
   incentive to adopt IPv6 before
it has the required
   utility: enabling communication
with the hosts of
   essentially all other users.


   Constraints similar to the above list seem to
   preclude
widespread voluntary adoption of IPv6
   (with or without scalable r
outing):

   2 & 3 - Hosts with the IPv6 address only work with
           other IPv6 hosts. 

   4 & 5 - Most end-user networks at present, do not
           have all their hosts and applications fully
           ready for IPv6.

   There is no routing scaling problem in IPv6, in
   that 
there are nowhere near enough BGP advertised
   routes
to constitute a serious burden on the DFZ
   routers. 
The number is about 1/256th of that of
   the number in
the IPv4 DFZ, with a doubling time of
   about 2 years.


   Unless there is dramatically increased adoption of
   IPv6, it would take about 16 years to reach the
   number 
of BGP routes as IPv4 has today.

   So in practical terms, for the foreseeable future,
   there is only the IPv4 scaling problem to solve. 
   A
solution which is capable of solving it and which
   
meets the 10 constraints listed above may well
   solve 
it for IPv4 - which would still leave the
   challenges 
a, b and c above as important
   limitations.


   If there was a way that a scalable routing
   solution
could support widespread adoption of and
   migration to
IPv6 (or, in principle, any other
   protocol which
had a much larger address space than
   IPv4) then I
think it would make sense to make this
   a further goal.


   However no such system has yet been devised.


Mobility

   I think there is a way that a scalable routing
   solution, in the form of a core-edge separation
   scheme such as LISP, APT, Ivip or TRRP could
   support
a new form of mobility: a portable IP
   address or 
range of IP addresses for mobile devices
   or networks 
irrespective of how or where they are
   attached and 
what their Care of Address (CoA) is:

     http://www.firstpr.com.au/ip/ivip/TTR-Mobility.pdf
 
   Non-mobile correspondent hosts need no new stack
   or application software.  This should work for IPv4
   for any point of attachment 
including behind NAT,
   with generally optimal path
lengths - and without
   adding any architectural
complexity to the core
   edge separation scheme.


   Since Mobility is so important and since I think
   a scalable routing solution could directly
   facilitate 
it - I think that this should be a
   further goal.
 However, many people can't imagine
   this, or think 
that mobility in the MIP form is in
   some way
orthogonal to what a core-edge separation
   scheme does.


   So some people will regard this as a non-goal, and
   some will regard it an an optional goal.  I think
   anyone who agrees that the TTR Mobility approach
   is practical and desirable would think that this
   should be an actual goal of a scalable routing
   solution, since it would be a great mistake to
   implement one scalable routing solution which could
   not support this new form of mobility, when another
   practical solution could.
       

     D - Facilitate or at least allow for a new
         approach to global mobility, with generally

         optimal path lengths, and full session
         continuity by way of mobile IP addresses.
         This is for both IPv4 and IPv6, with or
         without the
mobile device or network using
         conventional
MIP at the point of attachment
         - and with correspondent hosts being any
         conventional host.


Efficient use of IPv4 space

   There is also the goal of enabling IPv4 space to be

   used very efficiently, such as by tens or hundreds
   of 
millions or even a billion or more of end-user
   
networks, most of which want just one or a few IPv4
   addresses. 

   I am sure that the best of the candidate 
solutions
   will naturally do this - since one important metric
   
of their suitability will be the number of end-user
   networks 
they can scale to.  Any system which can
   scale to
a billion or more IPv4 end-user networks
   must have 
a way of working efficiently with one or
   a few IPv4 
addresses for each.  This naturally
   enables the most 
efficient use of IPv4 space.  So I
   think this does 
not need to be stated as a goal.


Ameliorating the anticompetitive aspects of IPv4 runout
   
   If I thought it was possible for anything to be
   done about this, I would suggest that any scalable
   routing solution should at least allow for it and
   would ideally directly facilitate it
.  

   Other than the above benefit of enabling better
   IPv4 utilization via finer, more flexible and more
   accessible slicing and dicing of available space,
   I doubt that much can be done in the technical
   sphere
.  
 

Migration from IPv4 to IPv6 or something better
   
   If someone can devise a mechanism by which we can
   all migrate from IPv4 to some other system which
   is superior, at least in terms of having more than
   3.7B global unicast addresses, then I would say
   that it would be an absolute requirement that
   a scalable routing solution support that system.

   Until such a thing is invented, I propose another
   goal, which is really just emphasizing good design:

     E - The solution should be as open-ended and
         flexible as possible, to facilitate its use
         for additional purposes which are yet to be
         clearly identified, including the possibility
         that the system be used to help facilitate
         migration from IPv4 to a new addressing
         system, such as IPv6.





Changelog

#00 2009-04-15
As part of a message msg04786 I wrote the paragraphs about the scalable routing problem:

This is not some mathematical problem awaiting solution via profound
insights, perhaps based on semantics developed with penetrating rigour.

It is a problem whose solutions are tightly bound by the need for
compatibility with all existing hosts and most existing routers - and
by the need to ensure immediate benefits for early adopters, since
the solution will only work if it is voluntarily adopted by most
end-user networks which want multihoming, portability etc.

Three people wrote to the list stating their support for the second paragraph:  XZDF and JZ.  

Joel Halpern msg04797 wrote that we had not agreed to this (indeed - we have not reached consensus on this) and that he does "not buy that we can not adopt solutions where the primary value requires changes in hosts, or in many routers over the long term".

So I wrote an extended version, with 10 points.



#01 2009-04-16  msg04815 Constraints on a solution - "incrementally deployable" again

This is the extended version with 10 points.

Joel Halpern msg04816 gave what I regard as qualified support for some items on the list.

Tom Vest msg04819 wrote "FWIW I like what's here." and began a detailed discussion of the impact of IPv4 address shortage on the ability of new entrants to participate in the global routing system.  So far, only he and I have continued this discussion.
   

#02 2009-04-17 msg04835    

Minor changes to the Text, one prompted by a critique of Joel's.  I tried to cover cover Tom's concerns by adding a Footnote.

Tom responded in detail here: msg04856 .


#03 2009-04-19 Archived as index-03.html in this directory.

Put the Text and a completely revised Footnote here on the website.  

The first paragraph is slightly revised with "both accessible to and voluntarily adopted by" as suggested by Tom.  

In point 1, added "new or existing", as suggested by Tom.

Added "some applications" to (what was) the last paragraph's list of things which may be upgraded with little cost or inconvenience in the future.

Added two paragraphs at the end, mentioning:
I discussed Tom's concerns in the Footnote and in a message: Scalable solution hitting IPv4's limits : http://www.ietf.org/mail-archive/web/rrg/current/msg04865.html   

Tom wrote: "The above two modifications do, indeed, adequately reflect the concerns I expressed."

#04 (Current) 2009-04-22 Archived as index-04.html in this directory.

Changed point 6 regarding upgrading DFZ routers, to refer to a potentially smaller subset of all DFZ routers which would need to be upgraded, and in what timeframe.

This was prompted by Bill's message: msg04866 though he suggested point 6 be much simpler, without allowing for upgrades to routers, which he considered to be unrealistic.  He also suggested a change to point 1, which I didn't make.  Overall, he liked it:  "I like where you're going with this list.".  My response, including more discussion on which routers might need to be upgraded, is: msg04873 .