[RAM] LISP NERD/CONS, eFIT-APT & Ivip compared

I started off wanting to discuss what was in common and different
between LISP 3.x and eFIT - however it grew into an attempt to
compare major aspects of the current proposals.

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

LISP 1.0 and to a limited extent 1.5 is documented in the LISP-01
I-D:

  http://tools.ietf.org/html/draft-farinacci-lisp

There is nothing specific there or anywhere else about LISP 3.x -
however it has been stated on the RAM list that 3.x is the most
likely variant to be deployed.  1 and 1.5 are theoretical models
for trying out concepts - but the look very different to me from
3.x, so I don't know what lessons learnt with them would be
applicable to 3.x.  According to Dino's RAM list message 1703
(July 13), the three mapping distribution systems applicable to
LISP 3.x would be:

NERD   (No data driven Map Reply messages.)

  http://tools.ietf.org/html/draft-lear-lisp-nerd-01 (June 12)

CONS   (No data driven Map Reply messages.)

  http://tools.ietf.org/html/draft-meyer-lisp-cons-00 (July 3)

APT    (Perhaps some data driven Map Reply messages.)

  http://tools.ietf.org/html/draft-jen-apt-00 (July 2)

APT is designed not for LISP, but for eFIT:

  http://www.cs.ucla.edu/~lixia/papers/07SIG_IP6WS.pdf

    A Scalable Routing System Design for Future Internet
    Daniel Massey, Lan Wang, Beichuan Zhang and Lixia Zhang.
    July 2007

  http://tools.ietf.org/html/draft-wang-ietf-efit-00

    Of the efit-00 I-D, Lixia wrote on this list on 10 July:

    > That one is really outdated.  We are working on a new
    >  version.  Will send a pointer before Chicago.

So there are now five potential new architectures - all but one
with a push database arrangement:

LISP-NERD
LISP-CONS  (Pull.)
LISP-APT   (APT is only intended for eFIT.)
eFIT-APT
Ivip

All these are in an early stage of development. Ivip is
extensively documented, http://www.firstpr.com.au/ip/ivip/.

NERD is a push system in that all ITRs have a copy of each mapping
database for each prefix of LISP-mapped addresses.  It has only
modest speed goals.  "... updates to the mapping are intended to
be relatively rare".  The mapping database is not intended to
change when a link fails or is restored - so the ITRs must somehow
be smart enough to detect loss of reachability to an ETR, and
already have the alternative ETR's address in their database, to
switch to another ETR which is reachable.  Since there is no
ITR-to-ITR communication about this as far as I know, I guess each
ITR has to figure out reachability on its own when it tries to
send packets.  This is much more complex for the database contents
and for ITR functionality than Ivip - in which an external
monitoring system changes the mapping and the ITRs simply follow
the changes to the mapping, which need to be delivered very quickly.

While NERD is "push", in comparison to CONS - which is purely a
query and cache system - the mapping updates are not actually sent
to the ITRs.  Each ITR has to poll a server and retrieve the
update files.  However NERD-01 anticipates ITRs advertising the
update files they have, and downloading these files from
neighbouring ITRs, as an alternative to getting them from
centralised servers.  If each update file needs to be fully
downloaded and authenticated before it can be made available for
other ITRs to download, then this will lead to a slow propagation
of these files across the Net.

Alternative approaches using NNTP, and with ITRs only storing part
of the database with "push" and are also contemplated.  (I don't
understand how an ITR would have only part of the database, unless
it has another ITR with the full database to which it would tunnel
the packets it doesn't have mapping for, or a nearby full database
query server like in Ivip or eFIT-APT's Default Mappers.)

LISP-CONS is a "pull" system.  ITRs query and cache the mapping
data, via local CARs which also cache.  Requests and replies
traverse a mesh of CARs and (non-caching) CDR servers, all linked
via authenticated TCP sessions.

Depending on the caching time, LISP-CONS could work with more
frequent database updates than LISP-NERD, but there is no attempt
to speed things up as with Ivip's Notify (cache invalidation) or
the same concept in eFIT-APT: "updated mapping entry" - which are
real-time, local, push messages directed to the caching ITRs (and
for Ivip, the caching Query Servers) which they query.

eFIT-APT differs from LISP and Ivip in a number of respects,
including:

1 - ETR and ITR functions are always contained in the same device
    (TR) whereas these can be in separate devices for both LISP
    and Ivip.  These TRs will replace all current Provider Edge
    routers - or all PE routers will be upgraded to have these
    capabilities.

2 - The ITR function is a query and cache system, as with
    LISP-CONS and Ivip's ITRC (ITR Cache) and ITFH (Ingress Tunnel
    Function in Host), but unlike the full database ITR in
    LISP-NERD in in Ivip's ITRD.

3 - Each transit network is expected to run at least one "Default
    Mapper", which may be router (at least it can encapsulate
    packets, even if it only has one interface), and which has a
    real-time updated copy of the entire eFIT-APT mapping
    database.  (Except in the future for IPv6 - section 7.4.)
    There is nothing about implementation of Default Mappers in
    the I-D, but I think they would best be implemented in a
    server, rather than a conventional router with hardware FIB
    etc.)

    ITRs send queries to the Default Mapper in their network.
    Each query is packet they do not currently have mapping data
    for.  The Default Mapper encapsulates the packet and forwards
    it towards the ETR in the destination network, and then sends
    back an ICMP response to the ITR with the mapping information
    the ITR needs to handle such a packet in the future.  (If a
    future packet's DA was part of a prefix with the same mapping
    data, then the ITR would then know how to encapsulate it.)

    This aspect of the Default Mapper is analogous to Ivip's QSD
    (Query Server with Database) combined with Ivip's ITRD
    handling packets which can't immediately be tunneled by an
    ITRC or ITFH.

    This will lead to much faster and more reliable query
    responses than LISP-CONS - but as with Ivip, raises the
    challenging problem of distributing the database updates in
    real-time to all these Default Mappers.  However, eFIT-APT
    has very slow goals regarding the speed of distributing
    these updates.

    As with Ivip, there is no delay for packets which cannot be
    mapped by an ITR, although APT's Default Mapper or Ivip's
    "backup" (maybe I should call it a wicket-keeper . . .) ITR
    could be a bottleneck.  With Ivip, there could be a chain of
    ITRCs leading to a final ITRD.

4 - The Default Mappers can be reached by anycast within a
    particular provider network.  (I don't propose QSDs be
    accessed this way, but it is an interesting idea as an
    option, provided all queries, responses and Notifications can
    be done with UDP.  Since Notification involves the QSD
    ensuring that the message was received by whichever QSD or
    ITRC the QSD sent it to, TCP might be a better approach than
    UDP - so anycast QSDs may not be such a good idea.)

    There is no two-way communication when the Default Mapper
    sends the ICMP packet with the mapping information to the
    ITR.  Two-way communication would be tricky with anycast
    unless all the Default Mappers had very intimate links
    between them, which is to be avoided.  However, I guess
    non-guaranteed ICMP reply is fine, since if the ITR
    doesn't get it, the worst thing that can happen is that
    the ITR will send the next data packet to the Default Mapper
    as well.

    Default Mappers also have the equivalent of an Ivip "Notify":
    "M1 can respond with an updated mapping entry".  There's
    no mention of the ITR having to acknowledge this - and even
    if it did, if anycast is used, it would be difficult to ensure
    that the ack would go to the correct Default Mapper.  Both
    Ivip and APT should have a way of ensuring the updated mapping
    information really has been received by the ITR (APT) or QSC,
    ITRC or ITFH (Ivip) it was sent to.

5 - The ITR function of APT TRs does not make any decisions
    regarding which of multiple ETRs to tunnel to in a multihoming
    scenario.  Each ITR is told to tunnel packets which match a
    particular EID prefix to a single RLOC location: a single ETR.

    (However, see the next point about the ETR function performing
    various functions and sending messages back to an ITR.)

    This *greatly* simplifies the FIB work of the ITRs - and
    reduces the size and complexity of the mapping information
    they cache.  In this respect, the ITR function of an APT TR
    somewhat resembles an Ivip ITRC.  However, unlike an Ivip
    ITRC, and APT ITR is required to detect unreachability of
    the tunnel endpoint - the ETR's address.  It can do this via
    the ETR's address being unreachable, or via an ICMP
    Destination Unreachable message, or some other ICMP message
    for the third kind of failure (5.1.3).  (I am not convinced
    there would always be an ICMP Destination Unreachable message
    if there was no host at the address where the ITR (ITR
    function of a TR) is supposed to be.)  In any of these cases
    the ITR sends the next packet intended for this ETR to the
    Default Mapper instead, and it is the Default Mapper which
    makes the difficult decisions, including by tunneling
    the packet to an alternative ETR (assuming it is reachable
    via BGP) and waiting to see if there are any ICMP messages
    in response.

    I think the way the APT system responds to ICMP messages, at
    least the "Destination Unreachable" messages - which would not
    have any nonce from any APT data packet header (no header
    details are currently available) - makes it an easy target for
    spoofed ICMP messages for a DoS attack.

    Devolving the multihoming link selection problem, and the TE
    functions, to the Default Mapper is a good idea, I think, but
    involves more ICMP packets to ITRs with "updated mapping
    entry" information.  As noted above, I don't see any provision
    in APT for this to be delivered in a reliable manner.  There
    also needs to be some crypto or protection against an attacker
    spoofing packets with the Default Mapper's address, to ensure
    the ITR's cache is not corrupted by someone who wants to steer
    packets to their own address.

    The ITR function of TRs are also required to forward any ICMP
    messages they receive to their Default Mapper - which will use
    these to decide which of the various RLOC mappings are for
    ETRs which are currently reachable.  Again, all these
    communications need to be secured in some way against spoofed
    packets from an attacker.  (This is acknowledged in sect. 7.)

6 - 5.1.3 states that an ETR which can't reach the destination
    host or router will send the packet to its Default Mapper,
    (which has some complex rules about not sending it back to
    the same ETR) as well as sending an ICMP message back to
    the ITR in the sender's network which tunnelled the packet
    in the first place. (Actually, the packet could have been
    tunneled by the Default Mapper in the sender's network too.)

Here are some questions about each scheme, with "LISP" implying
LISP 3.x.  There is no concrete information about LISP 3.x other
than that implied by NERD and CONS that I won't consider how LISP
might work with APT.

Encapsulation of data
---------------------

LISP-NERD/CONS: Not documented yet, but presumably using UDP, with
the outer source address being that of the ITR which encapsulated
the packet. (Outer SA = ITR's address.)  See the recent messages
"ETRs checking src & dest addresses" about how I think this makes
it harder for the ETR's filtering system to protect against
spoofing of local source addresses.

eFIT-APT: Not documented, but APT mentions an ICMP Destination
Unreachable message being generated if the encapsulated packet
does not reach an ETR, so I guess this means UDP encapsulation
with outer SA = ITR (or Default Mapper) address, similar to that
described in LISP-01's description of LISP 1 / 1.5.

Ivip: Currently defined as IP-in-IP with outer SA = inner SA, to
help with the filtering.  However, it could be changed to UDP with
the ITR's address in the payload, with outer SA = inner SA, to
enable unwelcome packets to be traced back to the ITR which
encapsulated them.

Source of mapping data
----------------------

LISP-NERD: A hopefully small number of database authorities.  No
particular relationship to any provider network, as far as I know.
 Various other approaches are considered too.  This seems to be
different from what I call the "Bring-your-own address space"
model of LISP-CONS and maybe eFIT-APT.

LISP-CONS: CAR servers are authoritative.  These are distributed
around the Net and there are two or more in some redundant
arrangement - though it is not clear from the current I-D how a
CDR decides to forward a query to two or more redundant CARs, or
whether both replies are sent back through the CDR mesh to the CAR
which made the query.  I guess the CARs are related to provider
networks and the various LISP-mapped blocks of address space are
controlled by various providers.

eFIT-APT: Provider networks have one or more Default Mappers,
which in addition to many other functions, are the authoritative
source of mapping information for a set of prefixes which are
currently BGP advertised by that provider (but won't be at some
time in the future).  So as with LISP-CONS, it seems the system of
address management of mapped address space which is dependent on
existing provider networks.

If an end user is with provider X, using some of their PA
addresses, could they go to another provider Y for connectivity,
or X and Y or Y and Z for multihoming, and still have to rely on X
to to the mapping the way they want?

What if an AS-end-user with their own PI space is currently
connecting with provider X.  If they want to move to provider Y,
does this means that X's Default Mapper no longer is
authoritative, and that Y's is?  I am confused about exactly how
eFIT-APT works.

Ivip: Multiple independent Root Update Authorisation Systems
devolve responsibility to other systems and then to end-users.
Updates are funneled in real-time to a Replication system which
fans it out to ITRs and QSDs all over the Net.  So the address
space management, mapping changes etc. is not tied to any provider
organisation or to provider devices or networks.  I think
LISP-NERD's organisational aims may be similar.

Speed and method of update propagation
--------------------------------------

LISP-NERD: Slow.  ITRs are "full database" and download files from
each database authority.  The ITRs then poll for changes.
"Updates to the mapping will be relatively rare" and "are not
intended to change when a link either fails or is restored".  So
TE and multihoming service restoration are performed by the ITRs
and ETRs, rather than via changes to the mapping database.  I
guess times of tens of minutes to hours, depending on how busy the
ITR is about polling for changes.  In principle, it can be quite
fast, but that requires a huge burden of polling traffic.

LISP-CONS: Faster than LISP-NERD. All communications via a meshed
TCP-linked CDR network - queries go along it and responses come
back along it, rather than the responses going straight from the
authoritative CAR to the querying CAR.  (I understand this is
because the meshed network is secure and all the TCP sessions are
already running.)  ITRs are query and cache devices, via CARs
which also cache and which are also typically authoritative for
some part of the mapping database.  EID-to-RLOC mappings "are
assumed to change at low frequency".  As with LISP-NERD, TE and
multihoming service restoration are performed by the ITRs and
ETRs, rather than via changes to the mapping database.

eFIT-APT: Very slow indeed.  Default Mappers in each provider
network are authoritative, and push their data to other Default
Mappers via BGP.  Full database push and occasional update push
techniques are used.  "Transient failures do not cause mapping
announcements in APT."  "Permanent mapping changes are unlikely to
occur more than once per month per customer."

Ivip: As fast as possible - maybe a few seconds from the end-user
changing their mapping to all ITRs following the new mapping.
"Notify" messages from QSDs to ITRCs and ITFHs.  This requires an
ambitious Replication network, which will involve authentication.
 Full database downloads via HTTP are used by ITRs and QSDs when
they boot up, or to refresh their copy of each database if there
is corruption.

Method of performing short term MH and TE changes
-------------------------------------------------

LISP-NERD/CONS: The mapping database (really multiple databases)
gives instructions to ITRs, which detect failures and make
moment-to-moment decisions regarding TE and changes to which ETR
for multihoming.  This leads to a complex database, to complex
communications, complex ITR and ETR functions and to greater
difficulty securing these communications against attacks.

eFIT-APT: Similar in principle to LISP in that the mapping
database is not involved in the dynamic responses, and the ITRs
etc. have to work it out amongst themselves.  ITRs (or rather the
ITR functions of TRs, which also have an ETR function) are
involved in detecting failure, and send messages to their own
Default Mapper.  They may also send messages (as an ETR) to the
ITR which encapsulated the packet (and although it is not
mentioned, that encapsulation might have been done by a Default
Mapper in the sender's network, so there is a complex web of
potential communications, which will be difficult to make reliable
and difficult to secure against attack.

Ivip: The Ivip system (Root Update Authority Servers, Replicator
system and ITRs (really ITRs and ITRCs/ITFHs which rely on QSDs
and perhaps QSCs) are not involved at all in failure detection or
any explicit system of TE.  Therefore, the database is very simple
and more suitable for being fully stored in numerous ITRs and
QSDs.  The simpler database is also a lot easier to distribute
updates for.  The Replicator system is the most ambitious part of
the system, and aims to get updates to ITRs etc. very quickly.

TE and responses to mulithoming outages are done by some external
system - the end-user manually, or some automatic system they set
up, including perhaps their host or router or some multihoming or
mobility monitoring system.  So the Ivip system needs to be fast,
but it can be conceptually quite simple and involve very defined
and more easily secured communications than the other systems.
Also, since the control of the mapping is external and not at all
encoded into the Ivip system, it is endlessly flexible, simply by
the end-user giving their credentials to any software system which
controls the mapping the way they want it.

ITR function and placement
--------------------------

With LISP and Ivip, ETR and ITR functions may often be in the same
device.  ETR and ITRs always being in the one device is enforced
by the current definition of eFIT-APT - but I don't see why the
system needs to be so inflexible.  The ITR functions in LISP and
eFIT-APT must be on ordinary BGP reachable addresses.  Ivip ITRs
are typically on BGP reachable addresses, but can be on
Ivip-mapped addresses.  Those on Ivip-mapped addresses would
usually be ITRC and ITFH functions in hosts, rather than the full
database ITRD with its requirement for a constant feed of updates
from typically two Replicators.

LISP-NERD/CONS:  As noted above, ITRs have complex functions,
including making decisions on a packet-by-packet basis for MH
service restoration, TE and I think load balancing functions.  The
ITR may or may not communicate with the ETR, but I think the ITR
is always ready to accept ICMP messages as sign it is tunneling
the data packets to the wrong address.

Since LISP-mapped addresses are not in any prefix which is
advertised in BGP, ITRs must be inside or at the border of
provider or end-user networks.

eFIT-APT: The placement of TRs is specifically limited to the
border routers between providers (defined as any organisation such
as a provider which offers transit of packets through its network
which are not for its directly connected customers) and their
non-provider "customer" networks.  ITRs have complex communication
functions, including detecting failure.  However, they only tunnel
to one RLOC at any one time - the Default Mappers do the hard work
for TE and MH failure restoration - of deciding what the mapping
will be for each ITR.  Default Mappers also perform ITR functions
- usually for packets sent to them by ordinary ITRs which have no
mapping data for them.  Having the ITR and ETR functions fixed at
these routers - Provider Edge routers I think - seems likely to
produce a bottleneck and burden these routers with even greater
workloads.  This may also preclude doing ETR or ITR functions in
servers, which may be more cost effective than routers with all
the new functionality.

Ivip:  ITR functions can be in the sending host in routers in
customer and provider networks - and can be "anycast ITRs in the
core".  Core ITRs are typically full ITRDs.  ITRCs and ITFHs rely
on nearby query servers, of which there are caching and full
database types.  Packets not encapsulated by an ITRC or ITFH can
be left for another ITRC or ultimately an ITRD in the network or
in the core to encapsulate.

Unless I change Ivip so it uses UDP encapsulation to include the
ITR's address, the encapsulation is IP-in-IP, which has less
overhead in bytes and processing than UDP.  The ITR doesn't choose
different addresses to use as the tunnel endpoint - there is only
"RLOC" (LISP terminology) address for every "EID" address or prefix.

The ITR doesn't respond to ICMP messages, or send messages to
anything.  A conventional server could probably be programmed to
perform reasonable speed (500Mbps or more?) ITRD or ITRC
functions.   ITR functions can be performed on hosts and routers
which use Ivip-mapped addresses - but these can't be behind NAT.

ETR function and placement
--------------------------

ETRs must always be on BGP-reachable addresses.  So there are no
ETRs located in networks which themselves have all their addresses
mapped by the LISP/eFIT-APT/Ivip system.

LISP-NERD/CONS: ETRs are located in the provider network or at its
border router, or in the end-user's network or at its border (CE)
with the provider network - as long as the address is BGP
reachable.  I think ETRs have complex communication functions.

eFIT-APT: The placement of TRs is specifically limited to the
border routers between providers and their non-provider "customer"
networks.  ETRs have complex communication functions, including
detecting failure of the link to the end-user's host or router.
They send messages to their local Default Mapper and to the ITR
function of the TR which encapsulated the packet (which can
include the Default Mapper of the sender's network).

Ivip:  ETRs are typically located as per LISP, but there are some
exceptions.  Firstly, a TTR (Translating Tunnel Router) can be
outside the network the end-user's mobile node is connecting with,
with a 2-way tunnel from the mobile node.  Secondly, a host with a
BGP-reachable (care-of) address can perform its own ETR functions.

ETRs are not involved in any communication with ITRs or with the
database system.  They may be involved in failure detection, but
that is outside the scope of Ivip.  As with the other systems,
Ivip ETRs need to know how to get packets to the destination
host/router, based on the inner DA.  See the discussion on "ETRs
checking src & dest addresses" for some simple filtering they do
to drop packets where outer DA != inner DA - but this is part of
supporting the network's filtering of packets with spoofed local
addresses, which is a problem the other proposals have not yet
addressed.  That discussion also concerns why I think ETRs in any
of these schemes need to have an explicit connection (including a
tunnel) to the destination host/router, rather than relying on the
local routing system to know how to get decapsulated packets to
the destination.

Incremental deployability
-------------------------

LISP-NERD/CONS: According to current definitions and all my
off-list attempts to understand LISP, LISP-mapped addresses are
not part of BGP advertised prefixes.  So in order for a host to
send packets to a host on any LISP-mapped address, the sending
host must be in a network with an ITR.  I think this makes LISP
not at all incrementally deployable.  Why would an early adopter
want to use LISP-mapped addresses when it will make their hosts
unreachable for any communication initiated by a host on a
non-LISP-upgraded network?

eFIT-APT: I am still trying to figure out what the transition plan
would be, but maybe it is more incrementally deployable than LISP.

Prefixes which are to be subject to mapping are still advertised
in BGP and the PE routers (where the TR=ITR+ETR functions are
performed) can accept incoming packets both via encapsulation and
by the existing, normal, delivery of raw packets.  However, it
will only be feasible to no longer advertise the prefix in BGP
when all, or virtually all (depending on how many sending hosts
the end-user doesn't care about) provider networks fully implement
eFIT-APT at all their CE routers.  This would take years, since it
involves expensive new functionality in a lot of routers -
probably requiring new routers in many cases.

In the meantime, what benefits would there be for end-user
networks?  They can't gain any portability - unless they accept
that hosts in non-upgradeable networks won't be able to send them
packets.

So this a similar bleak situation to LISP.  LISP provides a
powerful disincentive to early adopters - unreachability from the
all non-upgraded networks.  However, to the extent that LISP is
introduced, it does incrementally decrease the number of prefixes
in the global BGP routing table.  With eFIT-APT, there would be no
benefit for early adopters (no portability without grave loss of
reachability - and TE only for packets from upgraded networks) and
no benefit for the whole network (removal of prefixes from the BGP
routing table) until virtually all networks had upgraded.

One of eFIT-APT's goals is increased security by making provider
addresses unreachable from end-user networks.  However, assuming
full reachability was to be maintained, this could only happen
once every provider had fenced off every single end-user network
with its eFIT-APT-capable CE routers.  Even then, this is a weak
form of security, since a single breach in this global fence will
enable an end-user network to send packets to any transit provider
address, including any ETR (including with spoofed source
addresses in the inner and outer headers) - so the target ETR is
unable to distinguish this from legitimate packets arriving from
other provider network's ITRs and Default Mappers.

Ivip: Every prefix assigned to the Ivip system remains advertised
in BGP.  The idea is that each such prefix be used for more
end-user networks, and that in general bigger (shorter) prefixes
should be assigned to Ivip and used to serve thousands of
end-users.  Even with smaller (longer) prefixes, as these are
assigned and become contiguous, their mapping should be merged
into one RUAS - whereas each smaller (longer) prefix might have
had a separate RUAS initially.  Hosts on Ivip-mapped addresses are
always reachable by hosts from non-upgraded networks, provided
there are sufficient "anycast ITRs in the core".

As with all proposals, there are major challenges in setting up
the infrastructure.  Ivip's Replicator and ITR system is
adventurous, but the ITRs are doing a simpler job and the overall
design is simpler than the designs of other proposals.  The ETRs
are free-wheeling, low-cost devices and require no coordination.
With sufficient provider networks with ETRs, one or more
independent Ivip or Ivip-like systems could be set up, and work
fine alongside each other (each with their own set of core ITRs,
or perhaps all driving data to a common set).  These could
probably run at a profit, because they provide portability,
multihoming (with basic TE) and mobility with full reachability
(and generally pretty good path lengths, if the core-ITRs are well
distributed) from all hosts.

_______________________________________________
RAM mailing list
RAM@iab.org
https://www1.ietf.org/mailman/listinfo/ram