Subject: [rrg] Let me see if I can summarize my concern with Locator Liveness

From: David Meyer <[email-masked]>
Date: Mon, 22 Dec 2008 12:51:52 -0800

Folks,

	Let me try my explaining my issue with Locator Liveness
	from a slightly different perspective.  

	Summary
	-------

	These are the differences the proposals I've seen to date
	induce on the Internet (detail below): 

	(i).	Complexity of finding a usable <src,dest> address
		pair goes from today's O(M) to O(N^2), 

	(ii).	New failure modes are introduced if the searching
		(or something) isn't done, 

	(iii).	In addition, GSE doesn't have the option of
		searching, due to knowledge asymmetry inherent in
		the design. As a result, GSE has no apparent way
		to fix the locator liveness problem, even with
		brute force searching. Again, this is because the
		GSE rewriting element doesn't have the
		information necessary to do the searching.   

	More detail
	----------

	Today, a host generally queries the DNS and gets one or
	more A records for the destination in response. When it
	tries say, to put up a TCP connection to the remote side,
	it either connects (gets a SYN-ACK) or it times out. It
	can go ahead and try other addresses if it likes, since
	it can see them (to the extent that the DNS works, etc). 
	The host uses the source address of the interface used
	send the packet to the destination (at least that's how
	the unix boxes I have [Ubuntu, MAC OS, Fedora, and
	Gentoo] have behave, with a few twists around multiple
	default routes and different interface speeds).

	As a result, finding a working destination is today at
	worst linear in the number of A records for the
	destination; call it O(M) for M possible destinations. Of
	course, if the host participates in routing (say the
	site's IGP), then that is a different case which we can
	discuss if you like. However, I want to stay on the
	simple case for now.  

	So let's take a look at how the various loc/id separation
	schemes find working destinations (or <src,dest> pairs if
	that turns out to be necessary), and why they are
	different than what we see today.

	(i).	In the the SHIM6 or HIP version IPv6 world,
		I have multiple addresses per interface. Those
		addresses may be PA or PI addresses. In any
		event, I need to figure out which combinations  
		work, since if I latch on one that doesn't work
		I'll wind up with a persistent/non-recoverable
		failure. Where I have N source addresses and M
		destination addresses, this is easily shown to be
		O(N*M). So If N > M, just call it O(N^2).

		This situation is different than what we
		experience in today's Internet architecture,
		because today hosts only have to search O(M)
		destinations, not the cross product. Further, if
		you don't do the search and you latch on a
		non-working pair, you have a persistent
		failure. That is different from today, and is
		precisely the case that the REAP protocol was
		designed to prevent. 

	(ii).	In the GSE world, you can't do the O(M*N) search
		because you don't know M. So you can fail (hard)
		by having the rewriting element choose the wrong
		source RG. All the host can do here is time
		out. So this is O(M) from the hosts perspective,
		but the might not find a working pair even though
		one exists. So now you have a new failure
		mode. Of course, the rewriting element might try
		to do the searching, but without snooping on the
		data path it cant tell which ones work and which
		ones don't. So GSE can't really fix this problem
		(at least not as Mike defined it).

		On the complexity side, in general, network-based
		schemes have the following complexity: If I have
		N IDs (or whatever you want to call them, ULD,
		HIT, EID, ID) and M source locators (in this
		case, the network element is M-way
		multihomed). The network element could be
		rewriting element (such as GSE, in which case the
		host specifies N), or it could be map-n-encap
		(like Ivip, eFIT, LISP, ...), but that doesn't
		matter for this argument. 

		Simply, if L_i is the number of locators for ID
		N_i, then the complexity is bounded by O(P),
		where   

                  P = M*sum(L_i), i = 0...N-1
		
		Back to the GSE case: The difference here is that
		the complexity is increased from O(M) to O(P)
		(again, you could say O(N^2) if you like), and
		because of the asymmetric distribution of
		knowledge defined in the "GSE-classic spec", the
		host has half the knowledge and the rewriting
		element has the other half, and this introduces
		an a new (and persistent) failure mode. 

	(iii).	In a map-and-encap scheme, where the host has no
		visibility into the locator space (contrast GSE,
		where the host sees the "destination locator"),
		it can still try the O(M) destination addresses
		(EIDs in this case), but in this case each of the
		M destination EIDs could map to a different
		locator. So the mapping agent might in the worst
		case try O(P) <source,dest> locator pairs. 

		So like in the GSE case, if the mapping agent
		latches on to one that doesn't work, you have a
		persistent failure. Map-and-encap schemes don't
		share the asymmetry problem with GSE, so the
		mapping agent here can in theory solve this
		problem since it has the requisite information. 

	Hopefully this gives some idea of the differences between
	today's behavior and the behavior of the different
	proposals, as well as where my concern lies. There are
	more cases (and different security properties,
	etc). However, I hope this is enough to start a more
	detailed discussion.  

	Hope this helps.

	Dave

_______________________________________________
rrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/rrg

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 23 Dec 2008 11:17:56 +1300

Dave,

> Where I have N source addresses and M
> O(N*M). 

Well, not quite, if you have an address selection algorithm
that excludes some combinations up front. Also, do we expect
N or M to be >3 in many cases, or even >2 in most cases?

So I think the practical value will be less than you fear,
typically 4, and >9 would be very rare. Not that this is
negligible, but it's not unthinkable either.

draft-ietf-shim6-locator-pair-selection and
draft-ietf-shim6-failure-detection talk about example mechanisms
for this, by the way.

    Brian

---

From: David Meyer <[email-masked]>
Date: Mon, 22 Dec 2008 15:01:49 -0800

Brian,

> that excludes some combinations up front. 

	With all due respect, what I said holds. I wasn't talking
	about optimizations, engineering considerations, or other
	constants (which I know you understand is what the 
	notation I used is intended to convey). Its O(N^2), just
	like pairwise anything. 

> Also, do we expect

	Ok, you say > 9 is rare, and maybe that's true, I have no
	clue. Sitting here today if each address represented an
	ISP, then it does seem like greater than some number
	would be rare (I would think 5 or so; who has 5 ISPs
	today?)   

	BTW, can you support your assertion that > 9 is rare in
	any way?.  

	So the problem is this: We say that > 9 is very
	rare. But suppose its not, and you and your correspondent
	both have 10 ISPs, or some combination of your ISPs gives
	you 10 addresses (10 makes for easy arithmetic, and is
	one more than your number [9]). In this case  M=10 and
	N=10, and if you take the typical TCP timeout (3 sec in
	every *nix I have access to), then it takes 
	(10*10*3)/60 = 5 minutes to determine that the host
	isn't reachable. Today a host can do the same thing in
	about 30 seconds. 

	So yes, there are engineering assumptions that can be
	made, but the calculation still holds. That is the
	problem, not the list of all things that could go right.

	Dave

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 22 Dec 2008 18:25:24 -0500

Actually, there is at least one important additional factor.
It is not clear that it is necessary to find all working paths.
Given one working path, one might want to find a second early.
Given a suspicion that the two may have commonality, a background search 
for more, while using the ones that work, is understandable.

But communication does not need to wait on the O(n^2) search unless 
finding pairs that work is rare.  One does hope that normally most pairs 
work.  THis is actually a question about design targets.  If we assume 
that most paths are bad / non-working, then one needs lots of paths, and 
some way to search among them very fast.
But I don't think that is our design center.

Joel

David Meyer wrote:
> ------------------------------------------------------------------------
>

---

From: David Meyer <[email-masked]>
Date: Mon, 22 Dec 2008 16:20:12 -0800

> It is not clear that it is necessary to find all working paths.

	I'd put it differently. Its pretty clearly not the case. 

> for more, while using the ones that work, is understandable.

	Sure.

> finding pairs that work is rare.

	I would expect only a mis-implementation to try to
	enumerate all of the pairs before communicating.

> One does hope that normally most pairs  

	I agree. As I said, when things are working as expected,
	everything works. I would hope that we have that property.

> But I don't think that is our design center.

	Not sure what you meant by that.

	Dave

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 23 Dec 2008 13:21:39 +1300

Agreed, and if something like Mark Handley's multipath transport
is in use, several paths can be exploited in parallel without
upper layer impact, and without even knowing whether they all work.

Dave is correct though that this assumes an engineering tradeoff;
but surely we don't have to design for the worst case as if it
was the typical case?

   Brian

On 2008-12-23 12:25, Joel M. Halpern wrote:
>>     constants (which I know you understand is what the     notation I
>> used is intended to convey). Its O(N^2), just
>>     like pairwise anything.
>>> Also, do we expect
>>     every *nix I have access to), then it takes     (10*10*3)/60 = 5
>> minutes to determine that the host

---

From: David Meyer <[email-masked]>
Date: Mon, 22 Dec 2008 16:36:40 -0800

> but surely we don't have to design for the worst case as if it

	I agree with that. The concern (at least to me) is that
	if you don't somehow assess whether a locator is
	reachable, these schemes have the potential to latch on a
	"down locator" (initially, or after a failure), and that
	can cause a persistent failure. That failure is a new
	failure mode for the Internet.  

	I'm also guessing that the procedure used to asses
	locator liveness can use hints to avoid the asymptotic
	bound (at least I would hope so). The "Possible
	Optimizations" section of the draft outlines a few of
	these. 

	I'll just note here that I'm not the only one concerned
	with this property of loc/id split; draft-ietf-shim6-failure-detection
	is designed to address exactly this concern. 

	Dave

---

From: "Teco Boot" <[email-masked]>
Date: Tue, 23 Dec 2008 08:46:43 +0100

|> Where I have N source addresses and M
|> destination addresses, this is easily shown to be
|> O(N*M).
|
|Well, not quite, if you have an address selection algorithm
|that excludes some combinations up front. Also, do we expect
|N or M to be >3 in many cases, or even >2 in most cases?
|
|So I think the practical value will be less than you fear,
|typically 4, and >9 would be very rare. Not that this is
|negligible, but it's not unthinkable either.
|
|draft-ietf-shim6-locator-pair-selection and
|draft-ietf-shim6-failure-detection talk about example mechanisms
|for this, by the way.

 This is exactly the problem I am interested in.
 - Shall the routing system be responsible for handling all cases?
 - Prohibits the routing system hosts to select the exit path to DFZ?
 - How is the host informed what SA is optimal? Probing or signaling?

 BRDP provides locator liveness information to hosts with path metrics.
 Hosts select one or two SA and probe (e.g. first responder on TCP SYN).
 Probing is O(M) or 2*O(M). 
 Caching on M helps reducing probing overhead. And a name resolving system
 may (should ?) help in selecting the best M. 

 Mobility or SA-swap after ISP link failure is to be solved by
 another mechanism, BRDP is not the complete solution. It is the missing 
 piece of the jigsaw puzzle. Other mechanisms work fine with BRDP
 (MIP, SHIM6, HIP, and all translator and map&encap solutions).

 I still believe in the end-to-end principle and the cooperative model !

 Teco.