Subject: [RRG] map change due to a path failure?

From: Brian E Carpenter <[email-masked]>
Date: Tue, 25 Mar 2008 12:48:43 +1300

On 2008-03-23 09:50, William Herrin wrote:
> On Sat, Mar 22, 2008 at 1:24 PM, Tony Li <[email-masked]> wrote:
>>  I'd like to turn now to the issue of the dynamics of the mapping function.
>>  In particular, how fast can we allow the mapping entries to be updated?  Do
>>  we need to constrain the overall flux of the mapping?

<snip>
> 2a. What's the maximum acceptable time in which one EID may be
> inaccessible to another because of a map change due to a path failure?
</snip>

That seems to assume that a failure will produce a map change.
I expect a failure to produce a change in the routing tables,
but why should a (temporary) failure produce any change
in the map? I would expect this would cause the routing
algorithm to be told about the failure and to find an alternative
path involving the same or an alternative map entry.

    Brian

--
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: "William Herrin" <[email-masked]>
Date: Mon, 24 Mar 2008 20:21:19 -0400

>  path involving the same or an alternative map entry.

Hi Brian,

I suppose that depends on how you split the duties between routing and
mapping. With TRRP, path failures between the endpoint and a little
ways upstream of the ETR will be handled by a map change (expressing
which ETRs are currently able to natively reach the endpoint) while
most path failures between the ITR and ETR will be handled by a BGP
route change. In both cases, the question which matters is: how long
does it take to detect the failure and restore service?

Lets rephrase the question so that it's agnostic on the map/route issue:

2a. What's the maximum acceptable time in which one EID may be
inaccessible to another during change propagation due to a path
failure?

Regards,
Bill Herrin

-- 
William D. Herrin [email-masked] [email-masked]
Web: <http://bill.herrin.us/>

---

From: "Stephen Sprunk" <[email-masked]>
Date: Mon, 24 Mar 2008 21:14:36 -0500

Thus spake "William Herrin" <[email-masked]>
> does it take to detect the failure and restore service?

My understanding is that a temporary path failure would _not_ require a 
mapping change in a protocol that provided the complete set of potential 
EID-to-RLOC mappings to the ITR and featured reachability tests.  That is, 
after all, one of the prime reasons to go with multiple mappings.

A mapping change is only required for protocols that provide only a single 
mapping at any given time (like Ivip, and which causes many other problems) 
or does not have the ITR test reachability of the ETRs.

> inaccessible to another during change propagation due to a path

A second or two at most, ideally, because folks are going to try to run VoIP 
over this system.  The good news is that it's not "zero" or "50ms" like it 
would have been a decade ago, as cell phones have conditioned people to 
expect occasional audio loss they wouldn't have accepted when accustomed to 
the general high reliability of the wireline PSTN.

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: Mon, 24 Mar 2008 23:33:47 -0400

>  after all, one of the prime reasons to go with multiple mappings.

Hi Stephen,

Depends. What reachability criteria does the ITR use to determine that
the ETR is still there and still has a valid path to the EID? Can't
depend on the ETR to tell you; it may have turned in to a black hole.

At the moment there are two mechanisms that have been validated which
guarantee that knowledge about reachability reaches the ITR. One is
monolithic push through the map or route system where every change in
ETR availability is distributed to every ITR. The other is pulled
cache with a TTL where the ITR expects to periodically request an
update from the origin map server. Either way it's going to take a
while for all interested parties to get the message.

If you'd like to propose another mechanism which guarantees the
propagation of reachability knowledge, browse on over to
http://bill.herrin.us/network/statechange.html and then send me some
text and analysis that I can add.

>  the general high reliability of the wireline PSTN.

Two seconds is extremely ambitious for any architecture. BGP takes
anywhere from 30 to 120 seconds under normal conditions. I'm not sure
its possible to reliably detect that a path has failed in two seconds,
let alone propagate state change knowledge.

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

---

From: "William Herrin" <[email-masked]>
Date: Mon, 24 Mar 2008 23:40:38 -0400

>  the general high reliability of the wireline PSTN.

Gak; hit the send button early. Okay, lets try that again.

Bear in mind, this question is a two parter. There's also:

2b. What's the maximum acceptable time in which one EID may be
inaccessible to another because of a planned change?

Two seconds might well be a reasonable answer to 2b and 0 seconds may
turn out to be possible.

Regards,
Bill Herrin

---

From: Olivier Bonaventure <[email-masked]>
Date: Tue, 25 Mar 2008 14:51:59 +0100

Stephen,

> A second or two at most, ideally, because folks are going to try to run 
> VoIP over this system.  The good news is that it's not "zero" or "50ms" 
> like it would have been a decade ago, as cell phones have conditioned 
> people to expect occasional audio loss they wouldn't have accepted when 
> accustomed to the general high reliability of the wireline PSTN.

All the work on MPLS and IP-based fast reroute shows that the best way 
to deal quickly with link failures is to recover *locally*. Path failure 
should be solved by the routing system and not affect the mapping 
system. Let's not overload the mapping system...

Olivier

-- 
http://inl.info.ucl.ac.be , UCLouvain, Belgium

---

From: [email-masked] (Noel Chiappa)
Date: Tue, 25 Mar 2008 10:20:32 -0400 (EDT)

> From: Brian E Carpenter <[email-masked]>

    > That seems to assume that a failure will produce a map change. I expect
    > a failure to produce a change in the routing tables, but why should a
    > (temporary) failure produce any change in the map?

Because it's a lot less overhead to the system (overall) to change a mapping
entry, and then change it back when the failure has been remedied?

Of couse, if the failure affects *lots* of entries, then it's cheaper overall
to have the routing deal with it. However, it all depends on the exact nature
of the failure (which wasn't specified).

Unfortunately, we don't have any way (or tools) that would allow us to decide
whether it made more sense to handle something in one subsystem (mapping) or
another (path-selection).

    > I would expect this would cause the routing algorithm to be told about
    > the failure and to find an alternative path involving the same or an
    > alternative map entry.

In a perfect world, with a more rational routing (path-selection)
architecture, maybe. With the one we have, it does its thing without any real
interaction with its users. The existing system does its thing, and hands the
results down on stone tablets, take it or leave it.

	Noel

---

From: Xu Xiaohu <[email-masked]>
Date: Tue, 25 Mar 2008 15:49:13 +0100

> another (path-selection).

How about having the authoritative ETR to update the status of the EID->RLOC
mapping in the mapping system automatically according to the connectivity
between the ETR and the site network, while having the routing system to
determine the reachability of the ETR?

Best wishes,
Xiaohu XU

---

From: "William Herrin" <[email-masked]>
Date: Tue, 25 Mar 2008 10:51:30 -0400

>  system. Let's not overload the mapping system...

Olivier,

Don't you think that's a more appropriate argument for the merits of
one approach versus another? The goal on this thread is to come up
with a set of minimum standards that all approaches should meet in
order to be considered. Fast recovery for what we expect to be an
achievable definition of fast is an appropriate minimum standard.
Local recovery is one possible method for achieving that standard, not
a standard itself.

Regards,
Bill Herrin

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 26 Mar 2008 10:54:26 +1300

On 2008-03-26 03:49, Xu Xiaohu wrote:
...

> determine the reachability of the ETR?

However, we want to avoid map flapping by design (you will remember
that BGP4 route flapping was a big problem).

I would set a quite different timescale for status updates
in the mapping system - if we followed your suggestion, I would
suggest that a loss of connectivity should persist for
a long time, maybe 30 minutes, before the ETR changes the
map. I'd expect BGP to handle any outages on a shorter timescale.
If we set the timers in the mapping system to the same order
of magnitude as those in the routing system, we're likely
to see some horrible interactions between map flapping
and route flapping.

    Brian

---

From: "William Herrin" <[email-masked]>
Date: Tue, 25 Mar 2008 18:48:19 -0400

>  that BGP4 route flapping was a big problem).

Brian,

At the risk of picking nits, we want to avoid the single-device update
rate and system convergence problems associated with route flapping.
That doesn't necessarily mean we need to avoid map flapping itself,
just that it can't be allowed to cause those systemic problems.

In TRRP, for example, a map which is flapping consumes almost the same
resources as one which is not. The ITR is going to re-query the map
after the TTL expires regardless and the processing difference between
verifying the map and updating the map is not much. Even that is
limited to the ITRs actively communicating with the flapping origin.

>  I would

More path failures happen in the last mile than anywhere else. When
the path between you and one of your ETRs breaks, BGP can't do
anything about it. You either change the map to reflect that the lost
ETR is no longer a valid waypoint for your packets or you implement
some very complex technology in the ETR so it notices and tries to
reincapsulate and reach you via one of the other ETRs that you've
listed.

Not that the latter is a bad idea per se, but it will tend to be less
reliable than updating the map.

Regards,
Bill Herrin

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 26 Mar 2008 13:31:47 +1300

> reliable than updating the map.

You've got me worried.

Yes, assuming that the most likely point of link failure is between
ETR and the user site border, then BGP in the RLOC space isn't
going to help. And if the sender notices that the receiver, which
it only knows by its EID, has gone unreachable, there is nothing
it can do about it; there's nobody to complain to.

But if we fix that by having the ETR send a map update (actually
a map withdrawal) and we need that to propagate in less than the
TCP timeout, haven't we just turned the mapping system into
a dynamic routing protocol? However, it has to handle
several orders of magnitude more entries than BGP.

    Brian

---

From: "William Herrin" <[email-masked]>
Date: Tue, 25 Mar 2008 21:12:13 -0400

Hi Brian,

Well, yes. Isn't that the whole idea?

We have this large and growing FIB and it's hideously expensive any
time we have to implement it on traffic flows which are larger than
what a generic x86 can handle. So we move the bulk of that "routing"
out to ITRs at the edge where the traffic flows are small and the only
thing we keep in the high-rate FIBs is the knowledge necessary to get
from the ITRs to the ETRs.

I mean, we get one, possibly two orders of magnitude on the RIB just
by moving it to multicore servers with lots of ram, devices in the $8k
range. RIB growth may be superlinear but it's slower than Moore's Law.

The bottleneck is the FIB, specifically on devices with a
larger-than-COTS traffic flow. Right?

Regards,
Bill Herrin

---

From: Scott Brim <[email-masked]>
Date: Tue, 25 Mar 2008 22:09:13 -0400

> another (path-selection).

Help me understand.  I thought that when Brian said "routing" he was 
referring to routing between routed locators, within the topologically 
aggregated core, i.e. for example ITRs and ETRs.

I don't see how you can have a choice between fixing failures in mapping 
or in routing.  They are orthogonal.  The mapping system gives you a set 
of routed locators that you can send your packet toward in order to get 
to a destination that is not routed.  Routing gives you paths to 
anything that is in fact "routed" (i.e. a path can be discovered via 
routing).  So how you deal with a failure depends on the failure, but 
you don't have a choice.

So clearly I missed what you meant.

>     > the failure and to find an alternative path involving the same or an

Suppose there is a failure of an intermediate router, between two 
domains in the DFZ.  They know nothing of mapping/unmapping, and mapping 
knows nothing of them.  This is handled by BGP right now.  Are you 
suggesting that changes in BGP paths across the DFZ should be 
communicated to the mapping points, or perhaps to the mapping 
distribution/discovery system, so that they can change their preferred 
mappings?

Or, suppose there is a failure of a de-mapping point (ETR).  At least in 
LISP, that will very probably not be seen in mainstream BGP -- its RLOC 
is just a single address in PA space.  Any failure here is not a concern 
of mainstream routing, and will be taken care of in the mapping system.

> to see some horrible interactions between map flapping

The current LISP trick is the "locator reachability" bits piggybacked on 
data packets.  You can separate operational changes (the kind subject to 
flaps) from configuration changes.  There is no need for mappings to 
change due to operational problems, nor timers etc.  I still don't 
understand why you think BGP would be involved.  Are you presuming that 
we are going to run BGP between nodes that are not globally routed?  Why 
would DFZ BGP even know that an ETR was dead?

Scott

---

From: "Hongbin Luo" <[email-masked]>
Date: Wed, 26 Mar 2008 11:01:59 +0800

On 3/25/08 10:20 AM, Noel Chiappa allegedly wrote:
>      > From: Brian E Carpenter  <[email-masked] >
> 

          agree

On 3/25/08 5:54 PM, Brian E Carpenter allegedly wrote:
> > How about having the authoritative ETR to update the status of the EID- >RLOC

Perhaps it would be a good approach to set, for each mapping entry, a timer and let each end host (or ETRs) send mapping updates to the mapping system?

Hongbin

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 26 Mar 2008 16:43:52 +1300

On 2008-03-26 15:09, Scott Brim wrote:
...
> would DFZ BGP even know that an ETR was dead?

Right. I was momentarily confused by the scary idea of
connectivity failures at the edge resulting in map updates.
I don't think the reachability bits are a trick - it seems
to me essential to separate short-lived connectivity
failures from long-term topology changes.

    Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 26 Mar 2008 16:45:26 +1300

> Well, yes. Isn't that the whole idea?

Yes, but *without* several orders of magnitude more update
traffic. See Scott Brim's message re reachability bits.

    Brian

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 26 Mar 2008 11:22:13 +0100

Hi Brian,

IMO, the major reason that the flap damping is a dilemma in BGP is that it's
hard to distinguish the real flap and the path hunting. On the contrary,
it's safer to enable flap damping in the mapping system since there is no
such problem.

> would DFZ BGP even know that an ETR was dead?

Hi Scott,

To some extent, ETR plays the same role of PE in BGP/MPLS VPN. So we can use
a /32 IPv4 loopback interface address of ETR as RLOC and advertise those /32
IPv4 prefix in BGP without aggregation. In this way, the reachability of ETR
will be seen in the routing system. Of course, it will depend on the total
amount of ETR in the Internet.

If you use the "locator reachability" bits piggybacked on data packets, does
this require the intermediate router, which drops the unroutable LISP
packets, to send some ICMP unreachable like msg to the ITR? This is not the
default behavior for some routers which have switched off this function for
some reason.

The connectivity between the ETR and the site network is better to be
embodied in the mapping system. Otherwise, the cheating risk will be
introduced if ITR depends on the ETR to tell him the availability of the
EID-RLOC mapping. Authentication of ETR can be easily implemented by the
mapping system compared to the ITRs. 

Best wishes,
Xiaohu XU

---

From: Eliot Lear <[email-masked]>
Date: Fri, 28 Mar 2008 14:16:21 +0100

> it's safer to enable flap damping in the mapping system since there is no

That's because you'd not be using BGP as a routing protocol but as a 
simple reachability protocol.  Not what it was designed for, but perhaps 
reasonable technology re-use.

Eliot

---

From: Xu Xiaohu <[email-masked]>
Date: Fri, 28 Mar 2008 14:24:13 +0100

> reasonable technology re-use.

Exactly.

Best wishes,
Xiaohu XU