Subject: [rrg] Locator Path Liveness concerns

From: RJ Atkinson <[email-masked]>
Date: Tue, 09 Dec 2008 09:00:09 -0500

Off the top of my head, it seems to me that this issue already exists
in the deployed IPv4 Internet and also in the deployed IPv6 Internet.

If one considers a multi-homed end-system (i.e. one that is
directly connected to multiple IP subnetworks), that host needs
to make a decision about which source IP address to use
to communicate.

If it is communicating with a remote node that is also multi-homed
(same definition), then it needs to make a decision about which
destination IP address to use to communicate (typically this is
a choice from the set of A/AAAA records that the first host found
in the DNS for the remote node).

Few multi-homed hosts participate in intra-domain routing.
Fewer participate in inter-domain routing.  So nearly all hosts
wanting to correspond cannot use knowledge from the routing
system to make a better informed decision about either the
source address to use or the destination address to use.

To the extent that folks agree with the above, it would be helpful
to add discussion of this as a current issue in the Meyer & Lewis
draft.

To the extent that folks disagree with the above, then it would
be helpful if the Meyer & Lewis draft explained why folks believe
the existing deployed Internet does not have the same issue,
and at least describe why the scenario outlined above doesn't.

Cheers,

Ran
[email-masked]

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

---

From: Scott Brim <[email-masked]>
Date: Tue, 9 Dec 2008 09:08:26 -0500

> source address to use or the destination address to use.

This is a good point -- individual devices that are multihomed already
face that situation.  Is there any deployed use of multiple
simultaneous paths?

What is new is the opportunity to do something more with it given
locator/identifier separation.  "Here's this cool new tool, but to use
it you have to install new wiring in your house and by the way your
electric bill will double."

Scott

---

From: RJ Atkinson <[email-masked]>
Date: Tue, 09 Dec 2008 09:19:52 -0500

> face that situation.  Is there any deployed use of multiple

We should all think about that question.

A quick answer is that at least deployments of applications
using SCTP will use multiple paths today.  A basic multi-path
multi-homing capability has been in SCTP all along.  More
recently, dynamic multi-homing capability has been added.
If I understood my namesake when I last chatted with him,
SCTP's dynamic multi-homing capability has multiple independent
implementations already.

SCTP is not the most widely used transport protocol.
However, it is deployed and it has real-world use today.
I am reliably told that the multi-homing capability is
critical to most currently deployed uses of SCTP.

I am also mindful of Mark Handley's proposal for a multi-homed,
multi-path TCP extension.  Such an extension seems sensible to me,
at least conceptually, particularly given that there are now
experimental results from SCTP indicating that such a thing
can work reasonably well.

> locator/identifier separation.

Hmm.  I'm not quite sure.

> "Here's this cool new tool, but to use

(I haven't finished my coffee yet, so maybe it is just me,
but I have no idea what that quoted text means. :-)

Cheers,

Ran
[email-masked]

---

From: David Meyer <[email-masked]>
Date: Tue, 9 Dec 2008 07:46:18 -0800

Hey Ran,

> in the DNS for the remote node).

	The difference is has three dimensions: what information
	about which source addresses and which destination
	addresses are available, the knowledge symmetry of that
	information (i.e., what do hosts know and what does
	routing known about the which <source,destination> pairs
	will be used). and where the decision as to which
	<source,destination> pairs to use is made.  

	In today's world, hosts have pretty much complete
	information about which <source,destination> pairs are
	available. The decision as to which <source,destination>
	pair is to be used is made by host, and again the host
	has visibility into the alternatives (or even that there
	are alternatives). So it can try them by whatever
	algorithm it desires (linear, round-robin, etc). This is
	generally O(N) in today's world (where there are N
	destination addresses). No new news there.

	In the case of host-based schemes like shim6 which
	postulate multiple PA addresses per host, you just probe
	the entire <src,dest> space mod the utilization of
	heuristics like if you've received traffic, etc (i.e., in
	a scheme such as REAP). This is generally O(N*M), where
	there are N source addresses and M destination
	addresses.

	In  map-and-encap schemes, the host doesn't know how many
	"ways" there are to reach a remote ID (i.e., how many
	RLOCs there are, or if they are reachable), so it can't
	implement a strategy test reachability to the
	correspondent (note that even TCP timeout doesn't help
	here, unless there the host  finds another EID that maps
	to a different RLOC set). 

	Specifically, if the network element that is doing the
	mapping chooses a <src,dest> pair that is not reachable
	(note that the <src,dest> pair is in the locator space,
	into which the host has no visibility), the host will not
	have connectivity to the correspondent host, even though
	there may be workable alternaltives (i.e., other RLOCs in
	the EID-to-RLOC mapping). The mapping entity needs to
	asses locator liveness somehow.  

	In hybrid network-based rewriting schemes (e.g., GSE),
	the host doesn't know what source is being used, so while
	it knows the destination ingress points (those are in the
	DNS), it doesn't what source is being used to attempt to
	reach the correspondent host. So it also can't implement
	a strategy to search the space of available <src,dest>
	pairs for a workable pair. 

	I mentioned in the private email, another way to look at
	this is that the host can't explore the <src,dest> space
	for reachibility because it doesn't know what the its
	(src) RGs look like (or how many there are). The point
	here is that there may be a source RG selected (by
	routing) which *does not* work with the dest D-RG||D-EID
	(concatenation of the dest RG and dest ID, what's in the
	DNS) selected by the host, but the host can't tell why
	(or test whether its D-RG||D-EID works, since, again, it
	doesn't know what source RG is being selected). 

> source address to use or the destination address to use.

	Right.

> to add discussion of this as a current issue in the Meyer & Lewis

	Be glad to, to the extent that I agree. 
> and at least describe why the scenario outlined above doesn't.

	See above. Most of that text is already in the
	draft. What could be added is how hosts work today
	(without any loc/id split technology). Is that what you
	are looking for? That seems a good idea if so.

	Dave

---

From: RJ Atkinson <[email-masked]>
Date: Tue, 09 Dec 2008 10:59:59 -0500

> 	pairs for a workable pair.

OK.

Would you agree that: IF the host selects the Source Locator,
which (as you say) is NOT what the GSE documents say, then
the source host could use the same strategy as in today's Internet
(e.g. search the space of available <s,d> pairs to find a workable  
pair).

> 	Be glad to, to the extent that I agree.

Thanks.

> 	are looking for? That seems a good idea if so.

Adding discussion of how things work today, including when a
multi-homed source talks with a multi-homed destination (where
multi-homed means that a node has connections to more than one
IP subnet at the same time) would be really great.

Having the current deployment case presented and discussed
provides a nice baseline for comparison.

Thanks very much,

Ran
[email-masked]

---

From: Scott Brim <[email-masked]>
Date: Tue, 9 Dec 2008 11:04:39 -0500

Excerpts from RJ Atkinson at 09:19:52 -0500 on Tue 9 Dec 2008:
> SCTP is not the most widely used transport protocol.  However, it is
> deployed and it has real-world use today.  I am reliably told that
> the multi-homing capability is critical to most currently deployed
> uses of SCTP.

Please refresh my memory: Does SCTP test liveness of inactive src/dst
pairs on an ongoing basis?  If TCP and UDP were replaced by SCTP,
would the core be flooded with probe packets?

> experimental results from SCTP indicating that such a thing can work
> reasonably well.

My favorite way of getting Mark to speak up is to speak for him,
incorrectly, so here goes: It seems that their solution is to use
src/dst pairs that give them good throughput, and also to keep a
trickle of probes going on all others, even if they never get anything
back.  I don't know how they deal with asymmetric flows, which may be
the critical issue.

> > "Here's this cool new tool, but to use it you have to install new
> > wiring in your house and by the way your electric bill will
> > double."
> 
> (I haven't finished my coffee yet, so maybe it is just me, but I
> have no idea what that quoted text means. :-)

Sorry.  I mean we give a host this wonderful new tool called
locator/identifier separation, but in order to use it it has to change
its stack, change its API, implement at least one new control
mechanism at some layer, maintain more state and exchange more control
traffic.

Scott

---

From: David Conrad <[email-masked]>
Date: Tue, 9 Dec 2008 08:56:14 -0800

Dave,

On Dec 9, 2008, at 7:46 AM, David Meyer wrote:
> 	available.

Not to do my Bill Manning imitation, but I suspect this isn't fully  
accurate.  We have a set of assertions about destinations that may or  
may not be accurate at any given point in time, constrained by BGP  
propagation delays, IGP convergence, DNS cache expiration, DNS  
authoritative updates, etc.

In the steady state, I would agree with your statement.  However, in  
the steady state, it doesn't matter all that much.  Where stuff gets  
interesting is when you've got (lots of) transitions.  Much (all?) of  
the concern regarding locator path liveness in is detecting these  
transitions and providing sufficient information to active path  
components to make alternative decisions in some reasonable amount of  
time.  My impression is that one of the drivers behind concerns about  
routing system scaling is, in fact, the worry that the time to  
converge on an alternative will become unreasonable.

> 	to a different RLOC set).

Right, since the host is 'protected' from knowledge of the underlying  
topology.  Looking at this simplistically, assume you have a locator  
routing system that looks like today's routing system and a mapping  
system that fetches statically configured EID to (one or more) RLOC  
mappings.  At any point within the source locator to destination  
locator path, routers make decisions based on the destination locator  
according to information propagated via BGP.  If a BGP update  
indicates that the destination locator is no longer available, the  
router doing the forwarding has two choices:

1) drop the packet on the floor and wait for someone upstream (e.g.,  
the originating ITR) to notice (perhaps after being prodded) and stop  
using the bad destination locator
2) pop the encapsulation (keeping the source locator), re-do the  
lookup of the destination EID to discover all possible locators, use  
information at that router to pick a new destination locator and, if a  
viable one exists, re-encapsulate using the new destination locator  
and the original source locator.

[waiting while the screams of horror and outrage at choice 2 die down.]

My impression is that efforts on LOC/ID separation have been focused  
on the first choice (for valid reasons), however the second choice  
more closely mirrors the behavior of the existing routing system in  
which every router can make routing decisions based on the destination  
_identifier_.

Regards,
-drc

---

From: David Meyer <[email-masked]>
Date: Tue, 9 Dec 2008 09:29:51 -0800

Dave,

> authoritative updates, etc.

	Ok, two loose usages on my part here: First, by
	"available",  I meant published in DNS (contrast
	"reachable"). Second, DNS may not be accurate. Maybe
	third, "complete" might be too strong. 

	So point taken.

	I don't think, however, that this alters my argument.

> In the steady state, I would agree with your statement.  However, in the 
> steady state, it doesn't matter all that much.  Where stuff gets  
> time. 
	Yes, but I'm missing the point. You seem to be saying
	that if things are working, then things are working.

> My impression is that one of the drivers behind concerns about  
> routing system scaling is, in fact, the worry that the time to converge 
> on an alternative will become unreasonable.

	Agreed.

> mappings.  At any point within the source locator to destination locator 
> path, routers make decisions based on the destination locator according 
> to information propagated via BGP.  

	Right, but one point about "routing". In most (most)
	cases, routing is carrying a prefix that is shorter than
	/32 (or /128 if you like). So what routing tells you is
	that someone has in the recent past advertised a prefix
	covering a destination host's address; it doesn't tell
	you whether that destination is up or otherwise
	reachable. 

> If a BGP update indicates that the destination locator is no
> longer available, the router doing the forwarding has two
> choices:
>
> 1) drop the packet on the floor and wait for someone upstream (e.g., the 
> originating ITR) to notice (perhaps after being prodded) and stop using 
> the bad destination locator

	Sure.

> 2) pop the encapsulation (keeping the source locator), re-do the lookup 
> of the destination EID to discover all possible locators, use  
> viable one exists, re-encapsulate using the new destination locator and 
> the original source locator.

	Again, it is the details of "if a viable one exists" that
	is my point. 

> My impression is that efforts on LOC/ID separation have been focused on 
> the first choice (for valid reasons), however the second choice more 
> closely mirrors the behavior of the existing routing system in which 
> every router can make routing decisions based on the destination  
> _identifier_.

	Sure, but AFAICT this doesn't solve the locator path
	liveness problem ("if a viable one exists...").

	Good discussion, thnx.

	Dave

---

From: David Meyer <[email-masked]>
Date: Tue, 9 Dec 2008 09:35:40 -0800

Hey Ran,

> (e.g. search the space of available <s,d> pairs to find a workable  

	Yes, but then the value of GSE would be somewhat (if not
	totally) diminished, at least if you believe that hiding
	the source RG is fundemental to being able to do
	aggregation at the scale we're interested in. At that it
	would seem that you've given up on the core of what GSE
	is trying to do.

	But yes, if you convert GSE into something like SHIM6 (by
	letting hosts know their source RG), then the locator
	path liveness problem is something like O(n^2).

>> 	Be glad to, to the extent that I agree.

	Sure, its a good suggestion.

> provides a nice baseline for comparison.

	Good feedback. I'll see that it gets into the next rev.

	Thanks,

	Dave

---

From: "William Herrin" <[email-masked]>
Date: Tue, 9 Dec 2008 14:22:06 -0500

>        information about which <source,destination> pairs are

That really isn't true in *today's world.* Even in the best case
scenario, the application (NOT the host) only knows the destination
addresses which provide a given service. The app has no idea whether
those destinations are a single host where the addresses could
reasonably be interchangeable, multiple hosts where the app is
expected to connect to one of them and stick to it or some combination
of the two. In IPv4 the host also has no clue which of the source
addresses besides the primary one on the exit interface are valid
candidates for remote operation.

>        path liveness problem is something like O(n^2).

Not necessarily. You may be able to compute the path-source-liveness
separately from the path-destination-liveness and let the host
scholastically converge on the currently-optimal pair from the two
separate functions. If so then the overall path liveness problem is
only O(n).

Think about it: a dead destination adds relatively evenly to the
source deadness function. Only source deadness adds unevenly to the
source deadness counter, identifying a source that can be excluded.
Even in the worst case where each source works with one, only one and
exactly one destination, the randomness in the function will push
convergence towards one of the sources which will feed back into the
destination function so that it likes the matching destination.

Same for the destination function.

On Tue, Dec 9, 2008 at 10:59 AM, RJ Atkinson <[email-masked]> wrote:
> (e.g. search the space of available <s,d> pairs to find a workable pair).

How do you determine "workable pair" in a stateless protocol like UDP?

Regards,
Bill Herrin

-- 
William D. Herrin ................ [email-masked]  [email-masked]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004
_______________________________________________
rrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/rrg

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 10 Dec 2008 12:18:31 -0800

> If a BGP update indicates that the destination locator is no longer  
> available, the router doing the forwarding has two choices:
>
> the originating ITR) to notice (perhaps after being prodded) and  
> stop using the bad destination locator

Agree and simple.

> information at that router to pick a new destination locator and, if  
> a viable one exists, re-encapsulate using the new destination  
> locator and the original source locator.
>

I couldn't scream because you made me pass out.  ;-) You really don't  
want to do this or else every router on the path between two sites  
would have to store mappings. And if you did that, it would be per-EID  
state. Which is exactly what we have today without the encapsulation  
step.

So you really don't want to do this.

And if you aggregated many EID-prefixes into a handle of some sort and  
wanted per-packet rerouting, that handle would be called a label and  
we have that with MPLS today.

> which every router can make routing decisions based on the  
> destination _identifier_.

When a packet is encapsulated from ITR to ETR, you still have the  
rerouting system available, it's just not based on the host endpoint  
but the site endpoint.

Dino

---

From: Thomas Narten <[email-masked]>
Date: Wed, 10 Dec 2008 17:08:01 -0500

Ran,

> critical to most currently deployed uses of SCTP.

It would be useful to get a short report on SCTP's overall deployment
status. I.e., what are the key implementations, where are they used
(i.e, in what production environments), size of installed based, what
features they use (and which they do not), etc.

I hear a lot of snippets and hints about SCTP, and what features it
has, etc., but they are mostly anecdotes.

What I'd really like is to understand what works, what doesn't and the
lessons learned from actual usage of SCTP's multihoming aspects.

Anyone have such info?

Thomas