Subject: [RRG] Hosts, DFZ, purity & incremental deployment

From: Robin Whittle <[email-masked]>
Date: Mon, 17 Mar 2008 13:19:09 +1100

Short version:    In case anyone actually doubts this . . .

                  I try to show why architectural purity of having
                  a completely independent namespace is bound to be
                  incompatible with incremental deployability in the
                  current Internet.

                  This is long and pernickety, but it still may not
                  cover every possible option.

                  In short, since we can't upgrade the entire DFZ
                  to forward packets which use the new namespace
                  in a destination address, we can't use a new
                  addressing space for location information.

                  If we used a new space for identification, that
                  would require major changes to operating systems
                  and applications on the hosts at both ends of a
                  communication - which is not incrementally
                  deployable.

In "Re: On 'jack-down' models", Victor Grishchenko wrote:

> Hypothetically, if some new **layer** of routing is able to
> a) substitute the need for "serious tools" (AS, PI addresses)
> b) eat other layers upwards and downwards
> Then you'll get both purity and incremental deployment.
> Just a counter-example.

OK - I didn't write that it couldn't be done - just that I couldn't
imagine it.

This rough diagram of the Net divides it into hosts, edge networks
(end-user networks and those parts of ISP networks which directly
support customers such as home/office DSL users) and the DFZ.

  (For an explanation of DFZ etc. search for "Newbies"
   in http://psg.com/lists/rrg/2008/maillist.html.)

  ******** = DFZ links

      ------------------                       -----------
  H--|                  |                     |           |--H
  H--|      ISP1        |*********************|   EU3     |--H
  H--|                  |*                    |           |--H
      ------------------  *********     ******|           |--H
                     *             *   *      |           |--H
                    ---------    ---------     -----------
      ----------   |         |  |         |         *
  H--|          |  |  ISP2   |**|   TP1   |    -----------
  H--|   EU1    |--|         |  |         |***|           |--H
  H--|          |  |         |   ---------    |   EU4     |--H
      ----------   |         |       *        |           |--H
                   |         |   ---------    |           |--H
                H--|         |  |         |***|           |--H
                H--|         |**|  TP2    |    -----------
                   |         |  |         |*
      ----------  *|         |   ---------  *  -----------
  H--|          |*  ---------        *       *|           |--H
  H--|          |       *            *        |   EU5     |--H
  H--|   EU2    |   ----------------------    |           |--H
  H--|          |  |                      |***|           |--H
  H--|          |**|        ISP3          |    -----------
  H--|          |  |                      |
      ----------    ----------------------
                     |  |  |  |  |  |  |
                     H  H  H  H  H  H  H

  TP1, TP3:  Transit Providers - no hosts connected.

  EU1:       Singlehomed end-user network, may be on PI address or
             PA address, may or may not use BGP - but is not part
             of DFZ because if it uses BGP, there is only one
             upstream link.   For instance a small company.

  EU2:       End-user network, such as a corporation, multihomed
             with BGP to two upstream ISPs.

  EU4, EU5, EU6:  Multihomed end-user networks, such as universities
             banks, corporations, larger companies, government
             departments etc.

In the "On jack-down models" thread, Tony Li wrote of architectural
purity, involving the introduction of an independent namespace.

I responded that the only proposals which looked incrementally
deployable to me were not "architecturally pure" by his definition.

Here is why I can't imagine any genuinely independent namespace
being incrementally deployable.

 1 - A solution which requires host changes in both communicating
     hosts is not incrementally deployable, since benefits only
     accrue to a tiny proportion of end-users (people who use hosts)
     due to the fact that initially, very few hosts have the
     upgrades.

     Eg. SHIM6 and Six/One.

 2 - A solution which provides benefits for the host which is
     upgraded, but does not require upgrades in the other host
     is incrementally deployable.

     Eg. Mobile IP, relying on all traffic from and probably
     to non-upgraded correspondent hosts going via the home-agent
     router.  (This also involves an upgrade to a router in the
     home network.)

 3 - Likewise for networks: if the networks of both hosts need
     to be upgraded before either host or network experiences a
     benefit, the scheme is not incrementally deployable.

     As with point 1, inconsistent behavior with benefits for
     communications with some correspondent hosts but not others
     could be more trouble than the benefits themselves.

 4 - If the network of one host needs to be upgraded, but not of
     the other, for the one host to experience benefits, then the
     scheme is incrementally deployable.

     I don't know of any routing and addressing scaling solutions
     of this kind.

 5 - We can't suddenly upgrade the entire DFZ, because that
     involves upgrades to all the major networks.  Any scheme
     which relies on an end-to-end upgrade of DFZ routers is
     not incrementally deployable.

     For example, Six/One Router which requires DFZ routers
     to handle IPv4 header options at full speed - but most
     do not.

 6 - The above rules out these types of solution:

     a - Upgrade both hosts.
     b - Upgrade both networks.
     c - Upgrade both hosts and networks.
     d - Upgrade the DFZ (all major networks).

 7 - This leaves the following types of solution:

     e - Upgrade only one host - if benefits accrue to
         that host when communicating with non-upgraded
         hosts.

     f - Likewise, upgrade only one network, if benefits
         accrue to that network and/or its hosts when
         communicating with non-upgraded hosts in non-upgraded
         networks.

     g - Likewise, upgrade both hosts and networks to
         achieve immediate benefits for one or probably
         both, when communicating with non-upgraded
         hosts in non-upgraded networks.

     h - Upgrade some routers in the DFZ, which support
         communications from all non-upgraded networks to
         all upgraded networks, and then upgrade some
         networks so that those networks and the hosts in
         those networks (also the end-user networks which
         connect to those upgraded networks) experience
         immediate benefits.

         Ivip, LISP with Proxy Tunnel Routers, APT and
         (I guess) TRRP fit this description.

I will now examine e, f, g and h above regarding the question of a
completely new namespace.

The new namespace must be for locating the end-point of a
communication.  If it was for identifying it, then both hosts would
need to be upgraded (operating system and applications) - so it
would not be incrementally deployable.

So how could a new namespace work with e, f, g or h?

LISP, Ivip, APT and TRRP do not use a new namespace.  They simply
use a subset of the existing IPv4 or IPv6 space for the purpose of
addressing ETRs, and leave most of the rest usable by applications
for endpoint identifiers.

This diagram depicts the upgraded host HA, its edge network, the
DFZ, the edge network of the other host and the other host, HB.

         /----------\
         |   DFZ    |

   HA---NA==========NB---HB

The DFZ routers can't all be upgraded, but it would be allowable for
a few of them to be, such as with Ivip's "anycast ITRs in the
core/DFZ" or LISP's "Proxy Tunnel Routers".  APT does the same thing
with border routers of upgraded networks advertising prefixes
containing APT-mapped address space.

  e - HA is upgraded.  It has a concept of a new namespace for
      locating itself and perhaps the other host.  But this can't
      work since NA, the DFZ and NB have no way of understanding
      packets sent by HA which involve bits which specify anything
      according to the new namespace.

  f - NA is upgraded.  Likewise, its use of a new namespace for
      locating endpoints (HA or HB) is no use because no routers
      in the DFZ or in NB understand packets with bits which use
      this namespace.

  g - HA, NA and perhaps some DFZ routers are upgraded.  The same
      problem.

  h - NA and some DFZ routers are upgraded.  The same problem as
      for f - NB and HB doesn't understand the new types of
      packets which include bits which use the new namespace.

Point 5 is the key to all this.

  An upgrade to every DFZ router is not incrementally deployable.

  We need the DFZ routers to get packets from any one host to any
  other host.

  The non-upgraded DFZ routers can't handle any packets which
  use the new namespace.

  So no amount of work in the hosts or networks which use a new
  namespace will result in the ability to send packets from any
  such host and network to any other such host or network.

Introducing multihoming and portability on an incremental basis,
without directly involving BGP, involves allowing existing host
applications and potentially upgraded host operating systems on one
end (not both) to communicate in new ways.

Since this involves the DFZ, since we can't upgrade the entire DFZ
to handle packets which use a new namespace and since incremental
deployability means benefits must accrue to early adoptors, a fresh
namespace for location is not incrementally deployable, since the
DFZ can't handle the packets.

  - Robin

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: "Tony Li" <[email-masked]>
Date: Mon, 17 Mar 2008 00:51:07 -0700

Hi Robin,

| 1 - A solution which requires host changes in both communicating
|     hosts is not incrementally deployable, since benefits only
|     accrue to a tiny proportion of end-users (people who use hosts)
|     due to the fact that initially, very few hosts have the
|     upgrades.

Hmmm... Well, you and I have very different semantics assigned to
"incremental deployability".  I would consider anything that could be rolled
out one host at a time without breaking anything as being the maximal amount
of incremental deployability.

| 7 - This leaves the following types of solution:
|
|     e - Upgrade only one host - if benefits accrue to
|         that host when communicating with non-upgraded
|         hosts.
|
|     f - Likewise, upgrade only one network, if benefits
|         accrue to that network and/or its hosts when
|         communicating with non-upgraded hosts in non-upgraded
|         networks.
|
|     g - Likewise, upgrade both hosts and networks to
|         achieve immediate benefits for one or probably
|         both, when communicating with non-upgraded
|         hosts in non-upgraded networks.
|
|     h - Upgrade some routers in the DFZ, which support
|         communications from all non-upgraded networks to
|         all upgraded networks, and then upgrade some
|         networks so that those networks and the hosts in
|         those networks (also the end-user networks which
|         connect to those upgraded networks) experience
|         immediate benefits.
|
|         Ivip, LISP with Proxy Tunnel Routers, APT and
|         (I guess) TRRP fit this description.

So from this perspective, I guess you'd define incremental deployability as
some manner of monotonically increasing benefit function, yes?  

Under your definition (which I don't agree with), your point certainly seems
valid.

However, under the looser definition of a non-decreasing benefit function, I
don't see that it follows.  Any two host can deploy a new namespace and
benefit from it for their private connections.  It's true that a single host
won't benefit, but that's not a corner case that I consider to be essential.

Tony

---

From: Randall Atkinson <[email-masked]>
Date: Mon, 17 Mar 2008 06:17:11 -0700

Earlier, Robin Whittle said:

It is not obvious to me that changing operating systems
(and/or applications) necessarily prohibits incremental
deployment.  draft-rja-ilnp-intro-00.txt provides a specific
example of a host stack change architecture that I believe
to be incrementally deployable.  At least some major host OS
vendor folks agree with that assessment.

Ran

---

From: Robin Whittle <[email-masked]>
Date: Tue, 18 Mar 2008 00:23:18 +1100

Short version:   Comparing my notion of "incrementally deployable"
                 with Tony's.  I thought we all agreed on what
                 this meant.

Hi Tony,

I think it would be good to have a clear definition of "incremental
deployability" - if you and I disagree about it so much, others
probably do too.  It is a requirement of the RRG design goals, so we
all need to agree on what it means.

Here is my definition, by way of an example:

Technologies A and B can be installed on hosts, and provide benefits
to the host under different conditions.  A provides benefits for all
the host's communications and B only provides benefits when
communicating with other hosts with technology B.

So in the early days of deployment, when 1 in 10,000 hosts has the
technology:

  Hosts with A gain benefits for 100% of their communications.

  Hosts with B gain benefits, on average, for 0.01% of their
  communications.

Another example, closer to home:

This is for LISP before December last year - without PTRs (Proxy
Tunnel Routers).

The hosts which adopt LISP-mapped addresses (EIDs) and are connected
to a LISP network only get LISP's benefits of multihoming, TE and
portability of addresses for communications from hosts in networks
which also adopted LISP.

So when 1% of networks have LISP, hosts on LISP-mapped addresses
have these benefits for about 1% of their communications.  I think
this would be close to useless, or worse, because it is so
confusing.  My main point is that there is little benefit from
deploying LISP like this, when so few other networks use it.  So
there is little incentive for anyone to deploy it.  So in fact it is
never widely deployed.

(Another example is IPv6, which through no fault of its own, can't
be backwards compatible with IPv4 and therefore suffers the same
problem: initial deployers can only gain benefits from a tiny subset
of their communications, so in fact, the years go by and virtually
no-one really uses it.)

Ivip, or LISP with PTRs, is completely different.

Every host with an Ivip micronet address or LISP EID address
experiences the benefits for 100% of its communications.  This means
there is a genuine incentive to adopt the technology, even when very
few other networks have adopted it.

By my definition, technology B and LISP without PTRs are not
incrementally deployable - and technology A, Ivip and LISP with PTRs
are incrementally deployable.

Yet by your definition, all these technologies are incrementally
deployable because they can be installed on a single host or network
without disrupting anything else.

> I would consider anything that could be rolled out one host at
> a time without breaking anything as being the maximal amount

Can you suggest any technologies which are not incrementally
deployable by your definition?

Ivip was the first "incrementally deployable" map-encap scheme.  I
am sure I was not the only one to use the phrase in this way at the
time.  LISP became the second, with draft-lewis-lisp-interworking.
Yet I see "increment***" doesn't appear in this draft . . .

  - Robin

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 20 Mar 2008 15:33:39 +1300

> vendor folks agree with that assessment.

A solution is incrementally deployable if it has a backwards
compatible mode where an updated host can still talk to a
non-updated host. I'm pretty sure that Robin's constraint
(no new namespace) satisfies that rule, and I'm pretty sure
that ILNP doesn't actually create a new namespace either.
It just redefines some of the rules for the RFC 4291 namespace.

Oh, and see RFC 4843 for where this line of argument can lead.

    Brian

---

From: "Stephen Sprunk" <[email-masked]>
Date: Sat, 22 Mar 2008 23:33:37 -0500

Thus spake "Tony Li" <[email-masked]>
> "incremental deployability".  I would consider anything that could be
> rolled out one host at a time without breaking anything as being the
> maximal amount of incremental deployability.

I think this definition is too weak.  What is the incentive to deploy 
something when the only benefit it offers today is "doesn't break the status 
quo"?  Not deploying also offers that benefit at a lower cost.

The minimum bar, to me, is that the first site receives benefits when it 
pays the cost of deployment.  Those benefits may grow when more sites 
deploy, but they cannot be zero in the initial state or you'll never achieve 
critical mass, i.e. nobody wants to pay the costs because they don't get 
benefits until _everyone else_ also pays the costs, so you get a classic 
chicken-and-egg result just like IPv6 still suffers from.

> won't benefit, but that's not a corner case that I consider to be 

It's not essential, but if you can solve that problem, many other problems 
solve themselves.

For instance, Ivip or LISP with anycast PTRs offers benefits to a site for 
using Ivip/LISP even if it's the _only site on the planet_ that deploys. 
Every additional site that joins in increases the benefits to all.  Compare 
to other models that require both sides of each flow to upgrade before 
either sees a benefit.

S

Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

---

From: "William Herrin" <[email-masked]>
Date: Sun, 23 Mar 2008 11:16:56 -0400

>  chicken-and-egg result just like IPv6 still suffers from.

Stephen,

I don't think you understand. After the major vendors have implemented
our new protocol to a standard of quality superior to BGP (before
they've been paid the first dollar I might add), we're going to
convince all of the tier-1 networks to deploy it. After all, they're
sensible people who know our new protocol is good and right. Then
they'll let all their customers know that they have to upgrade because
BGP is going away. The new protocol will have to be dual-stack for a
few weeks of course; we can't just have a flag day. That's why it has
to be able to run alongside BGP on the same equipment.

Really Stephen, how did you think we were going to deploy a new
routing protocol? Start with small edge systems and arrange things so
that they receive immediate benefits from the upgrade even though none
of their neighbors has upgraded yet? That's crazy talk!

Regards,
Bill Herrin

-- 
William D. Herrin [email-masked] [email-masked]
3005 Crane Dr. Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: [email-masked]
Date: Sun, 23 Mar 2008 19:59:02 EDT

In einer eMail vom 23.03.2008 16:18:35 Westeuropäische Normalzeit schreibt  
[email-masked]:

The new  protocol will have to be dual-stack for a
few weeks of course; we can't  just have a flag day. That's why it has
to be able to run alongside BGP on  the same equipment.

Regards,
Bill Herrin

You are so right, Bill, by pointing out, that the solution must  be 
dual-stack.(and if there were even several solutions, then multi-stack). I  like to go 
further and say, every solution must be incrementally deployable  as it has to 
deal with a growing/changing internet even after being well  deployed (like 
BGP which today still must be and is incrementally  deployable).
I can't imagine a concept which needs a flag day, and if any one came up  wit
h such a concept he easily could be helped.
 
I am very much in favor of replacing BGP by some better solution, but for  
the start BGP is a big help:
The incremental deployment of a new protocol does not have to start from  one 
single point in the network nor is it necessary that it expands along strict  
links from there.
BGP-based VPN (RFC2547 I think) provide some fundamental  discovery mechanism 
for combining remote parts as to form some new  structure (there the VPN 
tunnel mesh). It can be re-used as a starter  motor.
 
Hence, I do not like the current discussion by which the incremental  
deployability argument is used for better qualifying the own resp. disqualifying  any 
other solution.
 
Heiner