Subject: Re: [RRG] incrementally deployable - roundup of proposals

From: Robin Whittle <[email-masked]>
Date: Sat, 10 Nov 2007 13:54:27 +1100

Hi Darrel,

In responding to Christian Vogt, you wrote, in part:

> So are you claiming incremental deployment is not possible with
> LISP?
>
> What if a 3rd party provides a proxy between the two systems,
> then incremental deployment is possible. Then networks who
> are not LISP capable can reach EIDs that are not in the global
> Routing table.
>
> Alternatively, what if an xTR performs NAT between PA space
> and EID space?
>
> There are some other possibilities here, but I think you are
> being too harsh in your analysis.

I don't understand your NAT or the "3rd party proxy" proposals in
sufficient detail to evaluate them.

In on-list discussions regarding LISP incremental deployability, two
solutions have emerged - both of which I think are in principle the
same as the "anycast ITRs in the core" idea I proposed in mid June
and which became part of Ivip.

There are no doubt other aspects to incremental deployability, but
one problem which certainly needs to be solved is reachability from
non-upgraded networks.  A sending host in a network with no ITR
needs to be able to successfully send a packet to a destination host
with an address which is managed by the LISP/eFIT-APT/Ivip/TRRP system.

The only way this is going to happen, as far as I can see, is for
the destination host's address to be part of a BGP advertised
prefix.  Otherwise, the border router of the sending host's network
will drop the packet.

The addresses which Ivip manages are all part of BGP advertised
prefixes.  The idea is that there are one or more ITRs outside the
non-upgraded networks which advertise this prefix, and the packet is
forwarded to one of these, where it is tunnelled to the ETR of the
destination host.

Bill Herrin uses the term "micronet" to refer to the range of
addresses which belongs to each end-user network.  For Ivip or any
other ITR-ETR scheme to provide a beneficial reduction in the number
of advertised prefixes, there generally needs to be two (or ideally
many more) "micronets" per advertised prefix which is managed by the
scheme.

In these messages:

  http://psg.com/lists/rrg/2007/msg00260.html
  http://psg.com/lists/rrg/2007/msg00264.html
  http://psg.com/lists/rrg/2007/msg00288.html

I think it can be seen that Eliot arrived at an arrangement for
LISP-NERD in August which is much the same as Ivip's "anycast ITRs
in the core".

In this message a few weeks ago:

  http://psg.com/lists/rrg/2007/msg00487.html

I think Dino accepted that a similar approach would be needed for
LISP-CONS to achieve reachability from sending hosts in networks
without ITRs:

DF >>> . . . so the only way to get packets to a LISP site from a
DF >>> non-LISP site is to have the packets hit an ITR some where
DF >>> on the path to the LISP site. That could be a proxy ITR that
DF >>> does this.

RW >> As far as I can see, the only way a "proxy ITR" could
RW >> receive packets from non-upgraded networks is for the prefix
RW >> these addresses are part of to be advertised in BGP.  Without
RW >> a BGP advertisement for the prefix in which LISP maps address
RW >> space, the packets will never leave the border routers of the
RW >> non-upgraded networks.

DF > Right. Either we make them a very small number of prefixes (I
DF > say < 100) or we don't do it. And the only alternative is then
DF > to do a NAT in the ITR.

I think that every end-user network with a LISP-mapped address would
require continued reachability from non-upgraded networks, so the
idea of limiting the number of prefixes to 100 or so makes no sense
to me.  I imagine that any successful ITR-ETR scheme would have
hundreds to tens of thousands of address blocks, each block, on
average, containing many "micronets".

Dino seems to have a very firm goal with advertised prefixes - to
radically reduce their number.  My aims are more modest - to be
happy with a similar or higher number of BGP advertised prefixes
than there are at present, as long as the ITR-ETR scheme is used in
a way that many more end-user networks get multihomable and portable
address space than would be possible with the same number of BGP
advertised prefixes without the scheme.

Can you explain your "3rd party proxy" or "NAT" approaches in
greater detail?

The current eFIT-APT proposal does not seem to provide reachability
from non-upgraded networks.  Michael Meisel acknowledged this as a
difficulty on 12 October:

  http://psg.com/lists/rrg/2007/msg00446.html

RW > With eFIT-APT, there would be no benefit for early
RW > adopters (no portability without grave loss of reachability
RW > and TE only for packets from upgraded networks) and no
RW > benefit for the whole network (removal of prefixes from the
RW > BGP routing table) until virtually all networks had
RW > upgraded.

MM > This is one issue we will certainly be putting a lot of thought
MM > into over the next couple months. Stay tuned.

Bill Herrin discussed TRRP reachability from non-upgraded networks:

  http://psg.com/lists/rrg/2007/msg00488.html

This too involves "anycast ITRs in the core" and I think address
space for each end-user network (a "micronet") being part of larger
blocks of address space, each of which remains advertised in BGP,
for as long as there needs to be reachability from non-upgraded
networks.  For Ivip, this is forever.  For TRRP and perhaps other
systems, this may not be forever.

BH > For these micronets to be reachable by networks without an
BH > ITR, someone has to deploy an ITR and announce a covering
BH > "route of last resort" which leads to an ITR. So, we put it
BH > out for bid and one company wins.
BH >
BH > Why would any company bid? Because its almost free money.
BH > Until ITRs are ubiquitously deployed, that company will
BH > essentially have a monopoly on PI micronets.  If you want
BH > any real inbound bandwidth for your micronet then until TRRP
BH > is ubiquitous, you'll have to pay them.
BH >
BH > So, they deploy the first ITR. Global scope limited to the
BH > covering prefix for the micronets.
BH >
BH > Who's next? Who deploys the second ITR where the process
BH > becomes anycast?

The IPv6-only proposals Six-One and SHIM6 have no problem with
"reachability from non-upgraded networks".

  http://psg.com/lists/rrg/2007/msg00524.html

These schemes are quite different from the schemes discussed above -
there are no ITRs or ETRs.  They are IPv6-only, they require changes
to operating systems in participating hosts, and I think that for
Six-One to provide its benefits over SHIM6 (router centric
multihoming management, not just host-centric), routers of
participating networks need to be upgraded too.

I think the major incremental deployment challenge challenge for
Six-One and SHIM6 is that when an end-user deploys Six-One or SHIM6
in one host, or in multiple hosts and in their network's routers
(Six-One) that they only gain benefits when the other host in the
communication has also upgraded.  So initially there are very modest
benefits, since very few other hosts will be upgraded.  This is a
classic problem of incremental deployment in that there is little
benefit in being an early adopter, which must be weighed against the
probably significant cost and effort of upgrading.

This means that while a Six-One or SHIM6 upgraded host gains
multihoming benefits (not portability or support for mobility, as I
think are possible and desirable with an ITR-ETR scheme such as
Ivip) when communicating with upgraded hosts, those benefits do not
apply to communications from other hosts.  So the whole system still
has to cope with lack of multihoming for some proportion (initially
close to 100%) of its communications.

But that is not as severe a barrier to incremental deployment as
upgrading and being unable to communicate with any host in a
non-upgraded network.

I think a properly implemented ITR-ETR scheme such as Ivip will be
able to provide these benefits absolutely 100% of the time, for
communications with all hosts:

  Multihoming.

  Portable address space (apologies to those who wince at this
  phrase) - retain the address range and use any ISP who has an ETR.

  Finer divisions and so more efficient use of IPv4 space without
  each end-user network requiring its own BGP advertised prefix.

  Support for mobility (so far, only Ivip aspires to this).

  No changes to host operating systems, applications or most
  internal and BGP routers.  This means multihoming and portability
  etc. is managed centrally - not on a host-by-host basis, as with
  SHIM6 and Six-One.

    - Robin              http://www.firstpr.com.au/ip/ivip/

--
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: "Stephen Sprunk" <[email-masked]>
Date: Sat, 10 Nov 2007 10:29:30 -0600

Thus spake "Robin Whittle" <[email-masked]>
> one problem which certainly needs to be solved is reachability
> from non-upgraded networks.  A sending host in a network with
> no ITR needs to be able to successfully send a packet to a
> destination host with an address which is managed by the LISP/
> eFIT-APT/Ivip/TRRP system.

I understood that to be a fundamental requirement of this work; you can't 
call a solution "incrementally deployable" unless upgraded sites are 
reachable from non-upgraded ones.  Fortunately, that seems easy to tack on 
to any of the proposals I've read.  (see below)

> prefix.  Otherwise, the border router of the sending host's network

It might be the sending host's upstream, but the idea is correct.  If there 
isn't a route in the DFZ to the destination EID, and there's no ITR in the 
path, then the packet won't make it there.

> average, containing many "micronets".

In theory, one doesn't necessarily need lots of prefixes to reach millions 
of micronets -- you just need all EIDs to be within a small number of 
aggregate prefixes.

> than there are at present, as long as the ITR-ETR scheme is used
> in a way that many more end-user networks get multihomable and
> portable address space than would be possible with the same
> number of BGP advertised prefixes without the scheme.

I think asking folks to give up existing PI blocks they're using is probably 
a waste of effort, though we can certainly try.  We could definitely ensure 
no new ones were assigned, though, which means the total would gradually 
dwindle over time.  Trying to shrink the routing table is an admirable goal, 
but none of these proposals will make any noticeable progress since the vast 
majority of routes in the DFZ today are PA deaggregates.  There are other 
folks working on solving _that_ problem.

> forwarded to one of these, where it is tunnelled to the ETR of the
...
> LISP-NERD in August which is much the same as Ivip's "anycast ITRs
...
> LISP-CONS to achieve reachability from sending hosts in networks
...
> systems, this may not be forever.

Reading all the various proposals and archives of the discussions here, the 
mental model I've come up with is that there would be two types of ITRs: 
ITR-Cs, or ITRs with caches, and ITR-Ds, or ITRs with a full copy of the 
mapping database.

Eventually large end sites and ISP POPs would have ITR-Cs.  If the ITR-C 
encountered an EID it didn't have cached, it'd (a) send a mapping request to 
an ITR-D, either buffering the packet to be forwarded when a response is 
received or dropping it, or (b) forward the packet to an ITR-D (which would 
make it a RETR, I suppose) and hopefully receiving a mapping response back 
which would enable shortcut forwarding.  One could also envision multiple 
layers of ITR-Cs/RETRs, if that ever turns out to be necessary.

However, the initial case (and probably final case, for some parts of the 
'net) is that there won't be ITR-Cs deployed and all packets would end up 
flowing to the (anycast) ITR-Ds.  Overloading or rate-limiting (both of 
which seem likely, for obvious reasons) of those ITR-Ds is the only real 
motivation for deploying ITR-Cs, and in some cases it may not be bad enough 
to bother.  It shouldn't be much of a problem for the first few dozen sites 
that deploy...

The above model seems quite compatible with most of the existing proposals, 
except that it may be merging LISP-NERD and LISP-CONS* into a single LISP. 
Ivip is the main exception, but it already has a similar anycast ITR 
mechanism to what I describe.

(* I'll admit to not understanding LISP-CONS very well; my eyes started 
glazing over when CARs and CDRs were added to ITRs and ETRs -- too many 
moving parts for me.)

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