Subject: [lisp] Locator liveness problem

From: Olivier Bonaventure <[email-masked]>
Date: Sun, 18 Jan 2009 12:12:24 +0100

Hello,

draft-meyer-loc-id-implications-00 discusses the locator liveness
problem and several possible solutions. I think that there are several
related issues that need to be discussed :

1- What are the types of failures that we consider and want to be able
to detect :

a. Failure of an ETR

b. Failure of (one of the link) directly attached to an ETR to its provider

c. Failure or misconfiguration of some intermediate links that causes
some ETR to become unreachable from some ITRs although the ETR and its
links are up.

Failures of type C are the more general, but also the most complex to
handle. There has been some work on detecting such
failures/misconfigurations ( see e.g.
A. Dhamdhere, R. Teixeira, C. Dovrolis, and C. Diot -
"NetDiagnoser:Troubleshooting network unreachabilities using end-to-end
probes and routing data", in Proc. of CoNEXT, December 2007 )
, but I don't think that we could reliably detect them in a LISP world.
I would suggest to focus the discussion on failures of type A and type B.

2- The focus of LISP should be to forward packets despite of failures of
 an ETR or failures of a link that is attached to an ETR and not to
detect failures.

I think that we should also consider network design best practices and
fast reroute techniques that could allow the EIDs served by the ETR to
remain reachable although an ETR or a link failed.

First, if a set of EID prefixes is served only by a single-homed ETR,
then the failure of the ETR or of the link that attaches the ETR to its
provider will cause a failure of the EID. Such a failure will be
eventually detected by ICMP destination unreachable messages. This is
the same case as today when a router attached to a single subnet which
is part of a larger aggregate fails. In this case, BGP does not inform
the entire Internet about the failure as the aggregate remains reachable.

Second, we should consider dual-homed ETRs. There are two subcases :
a- Two ETRs attached to the same provider
b- Two ETRs attached to different providers

In subcase a, the two ETRs could be configured in anycast so that the
provider redirects the packets to the other ETR in case of failure of
one ETR or one of its links.

In subcase b, a cooperation among the two providers could ensure that
the two RLOCs remain reachable even if one of the links or one of the
ETR fails. A possible solution to this problem could be based on the BGP
fast reroute technique described in
http://inl.info.ucl.ac.be/publications/achieving-sub-50-milliseconds-recove-0
but other solutions are possible as well

I think that we should explore the utilisation of such network design
and fast reroute techniques to ensure that LISP encapsulated packets are
delivered even in case of failures instead of discussing the detection
of the failures themselves. If we cannot find enough network design and
fast reroute techniques, then we'll have to define ways to detect failures.

Best regards,

Olivier

-- 
http://inl.info.ucl.ac.be , UCLouvain, Belgium
_______________________________________________
lisp mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/lisp

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 19 Jan 2009 16:32:24 -0800

> related issues that need to be discussed :

Olivier, see my comments inline.

> b. Failure of (one of the link) directly attached to an ETR to its  

These are covered by the loc-reach-bits and have been in the LISP spec  
for quite a long time. I think dating back to the -02 draft.

> some ETR to become unreachable from some ITRs although the ETR and its

We need to distinguish between the term "reachable" and "alive". And  
the mechanisms for "reachability" or "liveness" need to be clearly  
decoupled and analyzed independently. Today a BGP router believes a  
destination is alive because it is reachable. Being "reachable" here  
means there is a route (in the DFZ is it a more specific route and not  
a default route) in the local RIB.

"Liveness" is usally what a ping echo-reply would tell you. And we all  
know there is nothing protocol-wise in the core that tests for liveness.

The reason I say this is because, with good approximation and  
probability, a reachable prefix is one that usually is alive. If we  
didn't believe that, the Internet wouldn't be reliable today.

So the question I keep challenging people with is, with LISP loc-reach- 
bits and BGP route existence (i.e. "reachability"), is this good  
enough. Is this enough tools for an ITR to know when to switch RLOCs.  
If the ITR is running BGP, I think we are in a good position to day yes.

When the ITR is not running BGP, and there are many cases for it not  
to run BGP to lower the opex cost of running the ITR on a CPE router,  
is there an inadequate reachability capability. That is the question.

I do have some ideas to solve this low-opex ITR case. And they are  
light-weight.

> I would suggest to focus the discussion on failures of type A and  

Those are handled. The case is where a peering connection goes down  
and an alternate path is not available because the transit policy for  
an RLOC is quite different than for an EID. That is, a transit ISP  
cannot tell it's customer is behind an RLOC supported by another ISP.  
And the EID is not known to the core (for good reasons) so we could  
sever connectivity which previously was not before we introduced the  
level of indirection.

Having said that, c is the issue at hand here and not a and b.

> an ETR or failures of a link that is attached to an ETR and not to

But having an alternate path locally and not using could be question  
of "a good feature we cannot scale".

> remain reachable although an ETR or a link failed.

Fast reroute mechanisms in the xTRs? Or, alternately in core, they are  
already there. There is also the case how fast the IGP can switch to  
another exit ITR.

> then the failure of the ETR or of the link that attaches the ETR to  

If the site is single homed and the ETR goes down, there is no reason  
to fix this, because you cannot. Just like routers can't switch  
packets without the power on.  ;-)

Oh, and others have asked me to make packets go faster than the speed  
of light too.  ;-)

> eventually detected by ICMP destination unreachable messages. This is

Another comment I have. Can all of us please stop talking about ICMP  
Unreachables. We can't rely on them. They are not dependable. They are  
off by default in core IOS routers. They are filtered by NATs and  
other firewalls.

All designs should spec that if an Unreachble is received, you can use  
it but you can't base a design on using ICMP unreachables. Even if  
they were turned on, there are too many security implications. Also,  
ICMP unreachables don't contain mask-lengths, so this contributes to  
it's unscalablility.

> the entire Internet about the failure as the aggregate remains  

Yes, another problem with Unreachables.

> provider redirects the packets to the other ETR in case of failure of

That all depends on where in the region of that ISP they connect. An  
ISP is not going to want to carry host routes across their core.

> the two RLOCs remain reachable even if one of the links or one of the

There is never cooperation like this between two SPs. My definition of  
inter-SP cooperation is agreeing to BGP peer with each other and the  
manual exchange of peering addresses.

This is why the LISP authors think the sweet-spot for a LISP xTR is at  
the CPE router.

> fast reroute techniques, then we'll have to define ways to detect  

We should definitely discuss. But I hope we can make hard decisions as  
well.

> Best regards,

Thanks for the thought provoking email Olivier.

Dino

---

From: Olivier Bonaventure <[email-masked]>
Date: Tue, 20 Jan 2009 22:42:20 +0100

> for quite a long time. I think dating back to the -02 draft.

There are some issues with loc-reach-bits that are part of the LISP spec :
- The support for more than 31 locators is cumbersome (maybe 31
locoators is sufficient for most deployments, including experimental
ones, but I don't think that it's future proof)

- They assume that there is an ordering among the ETRs such that each
ETR knows the position of all other ETRs in the loc-reach bits. This
ordering should be preserved everytime an ETR is added or removed to
serve a given EID prefix and the ordering must remain consistent among
all ETRs that serve each EID prefix. This issue has not been discussed
in details until now.

> We need to distinguish between the term "reachable" and "alive". And the
> mechanisms for "reachability" or "liveness" need to be clearly decoupled
> and analyzed independently. Today a BGP router believes a destination is
> alive because it is reachable. Being "reachable" here means there is a
> route (in the DFZ is it a more specific route and not a default route)
> in the local RIB.
> 

I agree

> So the question I keep challenging people with is, with LISP
> loc-reach-bits and BGP route existence (i.e. "reachability"), is this
> good enough. Is this enough tools for an ITR to know when to switch
> RLOCs. If the ITR is running BGP, I think we are in a good position to
> day yes.

LISP ETRs will be mainly deployed by stub networks. Consider that AS1
and AS2 are two large T1 ISPs with thousands of stub customers. For
scalability reasons, the RLOCs attached to the ETRs of their customers
are all inside a large prefix announced by BGP (say 1.0.0.0/16 for AS1
and 2.0.0.0/16 for AS2). In this case, a BGP withdraw will only be sent
if the entire RLOC prefix fails, which is unlikely. I'm not sure that
BGP gives you mugh more information, unless we expect to see short RLOC
prefixes advertised with BGP, which does not scale.

> When the ITR is not running BGP, and there are many cases for it not to
> run BGP to lower the opex cost of running the ITR on a CPE router, is
> there an inadequate reachability capability. That is the question.

The target should be xTR without the full BGP routing tables.

> Those are handled.

The paper considers much more general failure cases than the loss of a
peering.

> The case is where a peering connection goes down and
> an alternate path is not available because the transit policy for an
> RLOC is quite different than for an EID. That is, a transit ISP cannot
> tell it's customer is behind an RLOC supported by another ISP. And the
> EID is not known to the core (for good reasons) so we could sever
> connectivity which previously was not before we introduced the level of
> indirection.
>
> But having an alternate path locally and not using could be question of
> "a good feature we cannot scale".

Sorry, but I don't see why a local alternate cannot scale

> already there. There is also the case how fast the IGP can switch to

I agree, when the two ETRs that serve an EID prefix are attached to the
same provider, then failures can be handled by the provider's IGP.

> If the site is single homed and the ETR goes down, there is no reason to
> fix this, because you cannot.

What I mean is that if an EID prefix is served by a single-homed xTR,
then there is no need to spend time/packets/cpu to detect the
reachability of this xTR.

> Just like routers can't switch packets
> without the power on.  ;-)
> 
> Oh, and others have asked me to make packets go faster than the speed of
> light too.  ;-)
> 
> off by default in core IOS routers. They are filtered by NATs and other
> firewalls.
>
> it but you can't base a design on using ICMP unreachables. Even if they
> were turned on, there are too many security implications. Also, ICMP
> unreachables don't contain mask-lengths, so this contributes to it's
> unscalablility.

I agree that we cannot rely only on ICMP, but we cannot ignore them
neither. We should not assume that core routers will send ICMP
unreachable, but a PE attached to a CPE could easily send ICMP unreach
when the attached CPE fails. ICMP could be off on core routers, but be
on or rate limited on edge routers. I agree with the security concern
and upon reception of an ICMP unreachable, an ETR should send a probe
message to check the unreachability of the ITR's RLOC before considering
the RLOC to be unreachable.

> That all depends on where in the region of that ISP they connect. An ISP
> is not going to want to carry host routes across their core.

Other solutions than anycast are possible.

> manual exchange of peering addresses.

Paying customers can "encourage" network providers to cooperate to
provide better/combined services.

> This is why the LISP authors think the sweet-spot for a LISP xTR is at

I agree

Olivier

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 21 Jan 2009 23:15:01 -0800

>>> able

That was removed in -11.

> ETR knows the position of all other ETRs in the loc-reach bits. This

That's the price of compression. And it's not that bad. See Luigi for  
my reasons. I have commented on other designs about this matter.

> all ETRs that serve each EID prefix. This issue has not been discussed

Yes, but RLOCs are not going to change much. If we want to the total  
system to scale we have to keep the update rate low-enough. So we  
don't need heavy-weight solution. Please have a detail look at SMRs in  
the latest spec and give us comments about that design.

> prefixes advertised with BGP, which does not scale.

Agree, but probing is a non-starter.

We can handle a class of failures if major peerings go down because  
the entire aggregate goes away. But if a more specific goes away, then  
there will probably be some sort of rerouting happening closer to the  
customer stub network, probably in the customer's SP network.

We are not talking about anything new here. That is the way the BGP  
routing system works today. We don't rely on unreachables, we either  
have rerouting occur close to where the failure is or we blackhole.

The same is going to happen for LISP RLOCs.

> Sorry, but I don't see why a local alternate cannot scale

It all depends if you want to confirm reachability before you switch  
to a new RLOC. Doing that requires polling from lots of places to each  
xTR. Which also takes time, so you don't have the best of convergence.  
And then when you have confirmed the path, before you start using it  
(before the next packet comes for encapsulation) the path might have  
already changed.

> reachability of this xTR.

Right, agree. Would have to argue for the same for the multi-homed case.

>> other
>> they

The -11 spec says you should switch RLOCs if you get an ICMP  
Unreachable.

> when the attached CPE fails. ICMP could be off on core routers, but be

If the CPE fails, the other xTRs in the site will find out faster and  
they reflect the change by zeroing the loc-reach-bit for the CPE.

> provide better/combined services.

Well, that hasn't happen up to now.  ;-)

This comment is way "easier said than done".

Dino

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 22 Jan 2009 22:12:40 +0100

>> ones, but I don't think that it's future proof)

I missed this update in December. I'm now reading version 11 in details
and will provide more feedback next week.

Olivier

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 22 Jan 2009 22:18:01 -0800

any LISP related specs.

Dino

On Jan 22, 2009, at 1:12 PM, Olivier Bonaventure wrote:

> Dino,

---

From: Luigi Iannone <[email-masked]>
Date: Fri, 23 Jan 2009 18:14:49 +0100

> my reasons. I have commented on other designs about this matter.
True. But I still think that will be impossible to maintain this
ordering coherent among all xTRs when scale to the size of the Internet
and mapping changes happen.

Luigi

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 23 Jan 2009 09:56:40 -0800

> and mapping changes happen.

First off, the number of xTRs at a site are going to be a small  
number. So they can stay in sync and get into sync over a shorter  
period of time.

Second, an xTR at a site knows who it is talking to and knows what it  
sent it last, so a 32-bit value per mapping entry tells you what the  
loc-reach-bits setting should be for a given site you are talking to.

Dino

---

From: Shane Amante <[email-masked]>
Date: Fri, 23 Jan 2009 14:30:43 -0700

Dino,

On Jan 23, 2009, at 10:56 AM, Dino Farinacci wrote:
> Second, an xTR at a site knows who it is talking to and knows what  
> it sent it last, so a 32-bit value per mapping entry tells you what  
> the loc-reach-bits setting should be for a given site you are  
> talking to.

Re: your 2nd point ... does this take into account asymmetric paths?   
IOW, given the following topology:

         cust1
           |
	xTR-1
        /     \
       Internet
       /       \
     xTR-2    xTR-3
      |         |
    --+---------+--
          |
        cust2

Let's say that cust1 has selected to send traffic to cust2 through  
xTR-2.  So, traffic flows as flows: cust1 -> xTR-1 -> xTR-2 -> cust2.   
However, cust2 has a medium- to large-ish network and it's IGP has  
selected xTR-3 for all hosts to use as its "default" route back out to  
the Internet due to cost, policy or other "administrative" reasons.   
Therefore, return traffic flows from cust2 -> xTR-3 -> xTR-1 ->  
cust1.  If xTR-2 is not xmit'ing back toward xTR-1, in the data-path  
at least, how does xTR-3 know what to set loc-reach-bits to (what  
protocols/processes/methods are used) and how fast will that occur?

Anyway, just trying to understand if and/or how this applies given  
asymmetric paths are a common occurrence and I don't see that  
diminishing in an ID/LOC split world.

-shane

---

From: John Zwiebel <[email-masked]>
Date: Fri, 23 Jan 2009 11:47:10 -1000

Shane

FWIW:

I have this running on a small topology.

In our current implementation xTR2 and xTR3 will have the same ETR  
database:

   ETR Database:
     EID-prefix: 20.0.0.0/8
       Locator: 100.1.45.4, priority: 10, weight: 1, state: down
       Locator: 100.1.235.2, priority: 10, weight: 1, state: up, local
       Locator: 2001::0100:0001:0045:0004, priority: 10, weight: 1,  
state: down
       Locator: 2001::0100:0001:0235:0002, priority: 10, weight: 1,  
state: up, local

This information is communicated via the IGP across the EID-site.
(running ospf)

There is that period of time between the RLOC going down (in this  
case 100.1.45.4)
and the other xTR getting the information which means a packet from  
cust1
could be replied to so that xTR3 sends the wrong loc-bits.  But that  
is a very brief
period.

Hope this helps.

On Jan 23, 2009, at 11:30 AM, Shane Amante wrote:

>> it sent it last, so a 32-bit value per mapping entry tells you  
>> what the loc-reach-bits setting should be for a given site you are  
>> talking to.
>
> Re: your 2nd point ... does this take into account asymmetric  
> paths?  IOW, given the following topology:
>
>         cust1
>           |
> 	xTR-1
>        /     \
>       Internet
>       /       \
>     xTR-2    xTR-3
>      |         |
>    --+---------+--
>          |
>        cust2
>
>
> xTR-2.  So, traffic flows as flows: cust1 -> xTR-1 -> xTR-2 ->  
> cust2.  However, cust2 has a medium- to large-ish network and it's  
> IGP has selected xTR-3 for all hosts to use as its "default" route  
> back out to the Internet due to cost, policy or other  
> "administrative" reasons.  Therefore, return traffic flows from  
> cust2 -> xTR-3 -> xTR-1 -> cust1.  If xTR-2 is not xmit'ing back  
> toward xTR-1, in the data-path at least, how does xTR-3 know what  
> to set loc-reach-bits to (what protocols/processes/methods are  
> used) and how fast will that occur?
>

---

From: Dino Farinacci <[email-masked]>
Date: Sat, 24 Jan 2009 07:43:22 -0800

> toward xTR-1, in the data-path at least, how does xTR-3 know what to  
> set loc-reach-bits to (what protocols/processes/methods are used)  
> and how fast will that occur?

As JohnZ said, xTR-3 knows by running an IGP with xTR-2 that either 1)  
it has gone down, 2) it's CE/PE link as gone down, or 3) the PE router  
has gone down. All these cases cause either a default route to be  
withdrawn from the IGP or an external route that xTR-3 can track. When  
this occurs, xTR-3, when it encapsulates packets, will clear the loc- 
reach-bit associated with xTR-2.

So even when there are asymmetric paths, as long as one xTR at a  
destination site is returning traffic to ta source site, the xTR will  
always provide liveness (specifically local liveness) of all xTRs at  
it's site.

Hope this helps.

Thanks,
Dino

---

From: Luigi Iannone <[email-masked]>
Date: Mon, 26 Jan 2009 11:00:04 +0100

> number. So they can stay in sync and get into sync over a shorter
Agreed. My point was more on the fact that even if you have a limited
number of xTRs, your site can be contacted by a very large number of
other sites, with which you have to maintain coherence.

> loc-reach-bits setting should be for a given site you are talking to.
Wait.
You are saying that to each entry in your cache you add a 32-bit value
that tells the loc-reach-bit you sent to that site the last time you
sent  a packet toward it?
Is this what you meant?

Thanks

Luigi

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 26 Jan 2009 12:00:11 -0800

> that tells the loc-reach-bit you sent to that site the last time you

Yes, but I haven't implemented this yet.

Dino