Subject: [rrg] Concerns about LISP Reachability Bits

From: "Damian Lezama" <[email-masked]>
Date: Thu, 5 Mar 2009 08:41:15 -0800

Hi,

Since mapping versioning has been raised for discussion I'd like to comment
some concerns I have about Lisp Reachability Bits. While versioning seems to
solve part of this I think some issues still remain.

1. Reporting local reachability complicates implementation of ITRs: Every
time an ITR encapsulates a package it needs to report local reachability of
the site's ETRs. Not only ITRs must know it (Map Server proposes lighter
ITRs) but there are also ugly failures to take into account i.e. ITRs in the
site getting isolated one from another but both working.

2. Reachability bits don't solve the problem completely: As this bits detect
only some reachability problems ITRs will also use other mechanisms. To be
on the safe side some ITR implementations will probably send Map Requests
after a short period detecting only outbound traffic to some RLOC (and
repeat as often as the standard allows while this condition continues). Is
it worth having this complicated reachability bits mechanism if it doesn't
help us much?

3. Ugly failures appear also here (from LISP draft)

       The ETRs, at the site with the changed mapping, records the fact
       that the site that sent the Map-Request has received the new
       mapping data in the mapping cache entry for the remote site so
       the loc-reach-bits are reflective of the new mapping for packets
       going to the remote site.  The ETR then stops sending packets
       with the SMR-bit set.

ETRs can never be sure if the remote site received or not the Map Replies.
What if they didn't? What if (or while) some ITRs did and some didn't?
Having an old mapping is bad enough, having reachability bits inconsistent
with the mapping gets the problem worse. Versioning looks good to solve this
one.

Regards,
Damian Lezama

---

From: Robin Whittle <[email-masked]>
Date: Fri, 06 Mar 2009 16:13:07 +1100

Short version:       A core-edge separation scheme such as LISP
                     which does not use real-time mapping
                     distribution to control the behavior of
                     ITRs therefore needs some way each ITR can
                     decide which of multiple RLOCs to use.

                     Attempts to improve this real-time process
                     include the ETR sending locator reachability
                     bits and the use of versioning in the mapping
                     information.

                     LISP also involves ETRs being the authoritative
                     source of mapping information.  This raises
                     further technical and administrative questions
                     about how the ETRs for one end-user network,
                     which are typically in different ISPs, can work
                     together securely and reliably, especially at
                     times of outages and other sources of network
                     instability.

                     With a real-time mapping distribution
                     architecture, as used by Ivip, there is no need
                     for ITRs to make such decisions - and ETRs can
                     be much simpler, with no need to communicate
                     with ITRs at all, and no need for them to be
                     coordinated in any way.  Also, end-user
                     networks can probe reachability and decide which
                     ETR will be used, in real time, with any
                     techniques they like.

Hi Damien,

While I only partially understand this part of LISP, I share your
concerns about ETRs sending real-time reachability information to
ITRs.  Even if it was secure (which I understand it is not) there are
all sorts of problems with different ETRs having a different
understanding of the reachability of all the ETRs for a given EID
prefix, and then the ITR receiving multiple differing sets of locator
reachability bits from different ETRs at different times.

Also, I think there is a problem with the bits needing to refer to a
specific order of RLOC addresses, as defined in the complex mapping
data.  When the ITR receives a mapping reply with a different order
of RLOCs than the one it has cached, then it can be difficult for an
ITR to know whether the bits it receives relate to the current or to
a previous order of RLOCs.

With LISP, I have no idea how the ETRs of a particular end-user
network are supposed to coordinate their activities so as to be able
to do anything consistent or reliable regarding telling ITRs which
ETRs are currently reachable, or at least which are reachable from
the DFZ and are also connected well (not congested) to the
destination network.

These ETRs are going to be in different ISPs, so how are the ISPs
supposed to configure their ETR to communicate reliably and securely
with ETRs in some other ISP, for every single end-user network which
uses that ETR?

When things are getting rough, with outages, traffic flowing in
different ways to get around the outage, congestion, misconfiguration
etc. how are the ETRs supposed to communicate reliably to work
consistently together?

How are they supposed to decide what the real reachability situation
is?  Likewise the mapping information?  There might be three ETRs in
different ISPs, each in some way configured by one or more ISPs
and/or in some way controlled by the end-user network in terms of the
mapping information they send out to the APT network (or register
with their respective Map Servers which do this).

But what if ETR-A becomes isolated from the end-user network?  The
end-user network might configure (or ask its ISPs to configure) the
other two - ETR-B and ETR-C - with some different mapping
information, such as new RLOCs, deleted RLOCs or rearranged RLOCs.
But ETR-A will not have this new configuration and so will be causing
different mapping and/or different locator reachability bits to be
sent out via the ALT network or to ITRs.

Versioning may be more secure than the ETR sending locator
reachability bits, and it may involve the ETR in less complexity.
However, I think the whole business of involving ETRs in matters
concerning reachability and mapping is a problem for LISP.

During times of disruption, when they most need to communicate, ETRs
will often be unable to communicate reliably.

In Ivip, ETRs do two things:

  1 - For encapsulation:  Decapsulate packets

      Modified header forwarding:  Restore original IP headers

      Then the ETR forwards the packets to the destination network
      by some locally configured means.

  2 - For encapsulation only, the ETR engages in a protocol by which
      the ITR can reliably and rapidly determine the Path MTU
      to that ETR:

         http://www.firstpr.com.au/ip/ivip/pmtud-frag/

ETRs might be involved in probing of reachability, by whatever
external system the end-user network hires (or deploys themselves).

Ivip has no reachability testing or ETR decision making functions at
all.  It is up to the end-user network to do this, however they
choose, and to use that information to change the mapping of each of
their micronets (EID prefix, but with arbitrary start point and
length) to a single ETR address, in real-time.

The reachability probing system would be multiple servers in the DFZ,
operating as a coordinated system.  The end-user network may well
give the operators of this system the authority to make decisions
about which ETR(s) traffic should flow to, so the reachability
probing network would actually control the mapping of their micronets
in real time.  This reachability probing network could also
coordinate with a router in the destination network, or be under
manual control, to spread traffic over multiple ETRs to achieve
incoming TE.  This would be by splitting the servers which receive
the incoming packets over multiple IP addresses so they could be in
separate micronets, each separately mappable to a different ETR.

While the reachability probing system might specifically probe ETRs,
a more likely scenario doesn't directly involve the ETR at all.

   Probe Servers        ISP1       Destination end-user network

       PS1 -----------  ETR1-----\  /
              \   /              CER1---
       PS2 -----------  ETR2-----/  \

                        ISP2

Two probe servers in the DFZ can send packets to either ETR.  They
can probe the full status of the ETR without probing it directly.  To
do this, they act like an ITR, by encapsulating a probe packet
addressed to the CER1 end-user router, or to some other router or
host within the end-user network.  They can encapsulate it with the
address of either ETR1 or ETR2.  Each probe carries a nonce and there
needs to be a response returned from the target device - which could
be as simple as a ping response with enough of the original packet to
include the nonce.

This way, each individual probe server can probe full reachability of
the end-user network via either ETR.  The ETR would have no special
functionality to support this, and does not need to be configured in
any way regarding the probe network.

The same system would apply for modified header forwarding - instead
of encapsulation.  The probe servers would create the modified
headers so the probe packet would be forwarded via one ETR or the other.

The probe servers would communicate their results to some central
server system in the probe network, which would make decisions about
changing mapping in real time whenever it appeared that one or the
other ETRs was unable to get packets to the destination network.

All core-edge separation schemes need ITRs and ETRs.  However, with a
real-time mapping distribution architecture such as used with Ivip,
the ITR does not make any decisions about which ETR to send packets
through, because the Ivip architecture externalises the probing and
decision-making system from the core-edge separation scheme itself,
and require end-user networks to do it themselves.  This reduces the
probe traffic, compared to every ITR doing its own probing, and
enables an endless choice of probe techniques and decision making
logic to be employed.

It also means the ETRs can be very simple indeed.

For modified header forwarding, there is no PMTUD stuff to do, and
the ETR simply restores the format of the packet to a normal IP
format.  It then forwards the packet to the correct destination
network by some means.  That's it.  The ETR only needs to be
configured to recognise that certain address ranges in the restored
packet's destination address correspond to destination networks which
it can forward the packet to.

As long as LISP and APT or any other core edge separation scheme rely
on a slow mapping distribution system, there are going to be complex
tasks for the ITRs in determining which of the multiple ETRs' RLOC
addresses to use.

For LISP (including OpenLISP, which is independent of the main
LISP-ALT project), the attempts to handle this real-time problem
include locator reachability bits and versioning.  Both of these
involve ETRs being highly complex and also working in a coordinated
manner with the ETRs of other ISPs.

Ivip requires none of this because the real-time mapping system tells
all the ITRs exactly what to do for each micronet (EID prefix):
tunnel the packet to just one ETR address.  Consequently the Ivip
ITRs and ETRs are much simpler than would be possible in a fully
developed LISP or APT system (APT's ITR functions are split between
the ITR and the Default Mapper).

 - Robin

---

From: Robin Whittle <[email-masked]>
Date: Fri, 06 Mar 2009 19:50:40 +1100

I have been told offlist that with LISP, the ETRs are at the site of
the end-user network.  I will confirm this and write something
separate about it.

Assuming LISP ETRs are always located at, and run by, the end-user
network, the critique I wrote in my previous message about
difficulties coordinating ETRs does not apply.

I will respond to Dino's reply to my "LISP Map Server I-D ..."
message once I am clear about where LISP ETRs are located.

  - Robin

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 8 Mar 2009 12:46:34 -0700

Sorry for the delay on this response.

> site getting isolated one from another but both working.

This is really easy to implement. You decide what the reachability is  
and then you set the bit-string. Once you have this bit-string it is  
stored as part of a MAC re-write string when you decide to  
encapsulate. So the forwarding engine, by no means, is figuring out  
reachability at packet forwarding time.

> only some reachability problems ITRs will also use other mechanisms.  

Right, we have been saying that since we created them. See the Santo  
Domingo Nanog slide-set on LISP. The loc-reach-bits handle 3 types of  
failures, 1) xTR going down, as discovered by the other xTRs in the  
site, 2) CE-PE link goes down attached to an xTR, or 3) the PE box  
goes down that is attached to an xTR.

So, let's make this clear, we have always said the loc-reach-bits are  
a *hint*. They don't tell you about up reachability, but do tell you  
about down reachability. An xTR that receives loc-reach-bit changes  
could react to them right-away if it wanted to trust the site. An xTR  
could verify the loc-reach-bits to make sure they are in fact valid  
and from the right source.

The R-bit per locator entry in the locator-set from a Map-Reply are  
authoritative and can be trusted.

The ITR doesn't need per-packet time status of an RLOC. Having it in  
the data plane provides the opportunity. And we have found some Data  
Center applications that will use this feature but for the capital-I  
Internet, cautious use of loc-reach-bits should be considered.

> it worth having this complicated reachability bits mechanism if it  

They are not complicated. They are a compressed way to give you  
information about many RLOCs in the data-plane. To get the  
compression, you need the bit-string to refer to the Map-Reply order  
of RLOCs. Those don't change often so this isn't really a problem.

>       going to the remote site.  The ETR then stops sending packets

We have outlined that SMRs don't have to be sent often. Removing RLOCs  
from a locator-set can be flagged as down and the ITRs using the map- 
cache entry for this site can quickly change to new RLOCs. Add RLOCs  
are appended to the end so if a site with an old map-cache entry sees  
a loc-reach-bit that is set for a locator-set it has as "shorter" it  
can ignore it.

The SMR processing needs to only be used when you have to do  
"compaction" for the above two cases.

> with the mapping gets the problem worse. Versioning looks good to  

They won't be inconsistent. The xTR that gets the SMR-bit makes sure  
that it gets a Map-Reply by rate-limiting the retransmission of the  
Map-Request.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 8 Mar 2009 12:59:07 -0700

> the DFZ and are also connected well (not congested) to the

They are configured the same way.

> with ETRs in some other ISP, for every single end-user network which

ETRs reside at sites. The IGP helps each of them determine the up/down  
status of the routers.

> etc. how are the ETRs supposed to communicate reliably to work

There is no solution to this today with existing protocols. But you  
have to think about a network that is designed that would cause a site  
to completely partition. That is typically known as a dumbbell  
topology. Where there is a lot of redundant topology on each side of  
the dumbbell but for some reason there is only a single set of links  
connecting both ends.

No one would design a dumbbell topology and haven't seen one for about  
15 years. So we have to choose what failure cases we want to solve and  
which ones we should leave alone.

> concerning reachability and mapping is a problem for LISP.

Versioning creates the opportunity of having to keep many sets of  
mappings. Plus the spec encourages use of it more so then we encourage  
use of SMRs. So I would conclude that there could be more cases and  
more complexity with versioning. We did consider versioning and  
realized we'd have to probably implement similar mechanisms as how BGP  
uses versioning for it's RIB.

>      by some locally configured means.

With all due respect Robin, this description lacks any details to  
allow me to believe you solved the problem.

> external system the end-user network hires (or deploys themselves).

Probing just doesn't scale for the scale of any-to-any connectivity we  
have planned.

Let me put it this way. Just think about a Google DNS server having to  
probe every system that has ever sent it a DNS query. And when you  
have to probe that many systems from many different places, the only  
way you can scale it is temporally. And when you do that, the  
usefulness of switchover is lost (takes too long).

Dino

---

From: Robin Whittle <[email-masked]>
Date: Mon, 09 Mar 2009 19:27:29 +1100

Hi Dino,

> They are configured the same way.

OK, I now understand LISP ETRs reside at the end-user network, and so
can be controlled directly there without the ISPs knowing or caring
about them.

> mappings. Plus the spec encourages use of it more so than we encourage
> use of SMRs. 

I just wrote a separate message on how I think the Versioning system
would work in circumstances where the Solicit-Map-Request wouldn't.

> So I would conclude that there could be more cases and more
> complexity with versioning. We did consider versioning and realized we'd
> have to probably implement similar mechanisms as how BGP uses versioning
> for it's RIB.

OK - Ivip doesn't have complexities such as Locator Reachability
Bits, Versioning or Solicit-Map-Requests.

>> will often be unable to communicate reliably.

I understand now that in LISP this is unlikely to be the case, since
the ETRs are supposed to be in the end-user network, not in the ISPs.

> With all due respect Robin, this description lacks any details to allow
> me to believe you solved the problem.

I was trying to keep it brief . . .

ISPs and end-user networks can make their own arrangements for
ISP-based ETRs forwarding packets to destination networks, including
tunnels, dedicated links or whatever.  It is beyond the scope of Ivip
to say what those should be, but there may well be reasons for
standardising some approaches if anything new is needed.

In Ivip, the ETR can be anywhere - it does not have to be at the ISP
or at the end-user network.  The ETR may have no relationship with
the access network of the destination network, especially if the
destination network is a Mobile Node.  The MN's owner may employ a
Translating Tunnel Router company to supply TTRs and other services
close to wherever they happen to be:

  http://www.firstpr.com.au/ip/ivip/#mobile

The MN makes a two-way encrypted tunnel to a preferably nearby TTR,
from wherever it is, including behind one or more layers of NAT.
Incoming and outgoing packets traverse the tunnel and the TTR also
acts as an ITR for any outgoing packets which need to go to
Ivip-mapped micronet addresses.

> Probing just doesn't scale for the scale of any-to-any connectivity we

The idea is to have some specialised company with a bunch of probing
servers distributed around the Net.  These work as a team, and
according to whatever the end-user network wants, probes reachability
of their network by whatever means and frequency they desire.

Typically this would be four to eight or whatever globally dispersed
probe servers sending a nonce-carrying ping packet to one or more
routers or hosts in the end-user network, but first encapsulating
(for map-encap) the packet so it goes via one ETR or another.  For
modified header forwarding, the probe servers also behave like ITRs
and convert the packet's header to include the ETR address (IPv4) or
enough of the ETR address (IPv6) - so the upgraded DFZ and other
routers to forward the packet to one or another of the ETRs.

This way, without the ETRs being explicitly involved in probing (they
 don't have to recognise or respond to probe packets - but they
could), their connectivity from various places in the Net and their
connectivity to the end-user network can be probed with whatever
frequency the end-user network specifies.

The end-user network would also typically give a (revocable) mapping
control username and password to the reachability probing company so
this company could control the mapping of the end-user network's
micronets (EIDs)  Then the end-user network would give the company
instructions on how long to wait, in the even of an apparent outage
(detected by probe packets not acknowledged), before changing the
mapping to the ETR which does appear to be working, from the one
which was being used, but is now no longer reachable from a
sufficient number of probe servers for it to be considered not worth
using for traffic.  In Ivip, the mapping for any one micronet
consists of a single ETR address, so the ITRs have no decisions to
make and the mapping is simple and short.

In principle, this Ivip approach is less finely adaptable to outages
which are localised in some parts of the DFZ, than would be the
approach used by LISP or any other system where the ITRs individually
decide which ETR to use.

However, I doubt this will be a show-stopper.  It would only be an
advantage to LISP, over Ivip, when both ETRs were partially affected,
so that each one had a different section of the Net which could not
reach it, and when the affected ITRs could figure this out in time.

Assuming the mapping of a micronet is currently to ETR A:  As long as
one of the ETRs (B) is reachable from the entire Net, then as long as
the proposed external probing and decision making system indicates
this is the case, and also detects that ETR A is partially or
completely unreachable from various places in the DFZ, then the
mapping will be changed in a few seconds so all ITRs will tunnel
packets to ITR A.

At times of both ETRs being unreachable from different parts of the
Net, I doubt if the average LISP ITR is going to be able to do a
significantly better job than a well designed, individually
customised, distributed prober company system as I describe.

I imagine that situations where neither ETR is reachable from the
entire DFZ would be short-lived, since the BGP system will be busy
adapting to whatever has happened and will fix it pretty quickly.

I don't think any core-edge separation can prevent outages of a few
seconds to 30 seconds or whatever.  With Ivip, the response time
depends on how frequently the probing is done and how twitchy the
decision making process is.  I think the Ivip system should be able
to change the behavior of all currently involved ITRs in a few seconds.

I see the purpose of multihoming and the other benefits of the new
kind of address space (I call it Scalable PI space) not so much as
trying to prevent short glitches, but in recovering quickly from
outages which go on for more than 20 seconds, a minute or whatever -
and which might go on for hours, including especially technical or
business failure in one of the ISPs.

> probe every system that has ever sent it a DNS query. And when you have
> to probe that many systems from many different places, the only way you
> can scale it is temporally. And when you do that, the usefulness of
> switchover is lost (takes too long).

I don't understand how this relates to what I am trying to explain
about how with Ivip, the end-user network typically appoints a
separate, specialised, company to continually probe its network via
how ever many ETRs it has.

That probing and the resulting mapping decision making can be
customised in any way, by agreement between the probing company and
their customer, the end-user network.  This is not part of Ivip.  So
any frequency, any protocol, any number of probing servers in any mix
of locations, any decision making algorithm at all can be chosen and
finely adapted until the end-user network is happy about the
responsiveness to outages and with the frequency of probing.

For any network with significant incoming traffic, this burden of
probe packets will be far less than whatever probing, or attempts at
sending traffic packets, the ITRs of LISP or APT make, since there
are potentially thousands of such ITRs sending packets at any one time.

You can't rely with LISP or APT on getting any messages to these ITRs
about real-time changes in reachability.  For one thing, it may not
scale to try to send a message to them all.  Secondly, you can't
easily secure such a message.  Thirdly, you can't necessarily
piggyback a Solicit-Map-Request on a traffic packet going back to the
site with the ITR, since the sending host might not be on an EID
address.  Also, there could be one-way traffic flows.

  - Robin