Subject: RE: On the use of multiple PA prefixes or a single PI prefix for IPv6 multihoming

From: <[email-masked]>
Date: Sat, 23 Oct 2004 09:00:58 +0300

Jari, Marcelo,

> > So we don't really need to know information about all the possible 
> > complete paths, just the ingress and egress parts of the path. I guess 
> > that this problem is more reduced and less ambitious than the general one.
> 
> Right.
> 
> The other reduction is that I'm not sure we need to solve
> the "best path" problem but solving even the "a working
> path" problem might be sufficient. That's at least my
> preference.

Exactly; my thought has always been that we need to avoid
the non-working path(s) & that would be sufficient.

John

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 24 Oct 2004 22:48:56 +0200

> the non-working path(s) & that would be sufficient.

Avoiding non-working paths goes to the core of what's multihoming all 
about, so this is something we absolutely need. But I'm not sure it's 
all we need. What I'm worried about is the situation where there are 
multiple working paths, but there is a large difference in quality 
between them. For instance, one path has a capacity of 100 Mbps and 
another a capacity of 1 Mbps. In this case, selecting the latter path 
as part of regular operation would hardly be acceptable.

We _may_ be able to bring this problem back to manageable proportions 
by taking advantage of the information both ends have. So if either end 
knows that the second path is much slower, they'll avoid it as long as 
the first path is operational. This leaves only the cases where there 
is congestion in the core, which is pretty rare these days. (But this 
hasn't always been the case...)

Note that the whole reachability detection problem isn't as simple as 
it may seem at first, especially when we want to make use of 
unidirectional paths. Until not very long ago, I was favoring a 
"cartesian ping bomb" approach where there are reachability probes for 
all { src, dst } combinations. However, this can cause massive 
congestion when a link fails for a busy site, and it's also complex and 
most likely slow.

My current homework for the design team is to look how protocols such 
as OSPF and especially STUN implement similar features and see what we 
can borrow there. Unless this provides significant new insights I want 
so see if we can make a "be optimistic but check first" approach work. 
This means that when the reachability heuristics determine that there 
may be a path failure, we check the current path. If there is a 
failure, we check the next best path (for whatever "best" means 
locally) and so on, until we find one that works. In order to detect 
unidirectional reachability without excessive numbers of packets, each 
probe contains information about the last few multihoming signaling 
packets received from the other side. So unidirectional reachability 
won't be detected as fast as bidirectional reachability, but eventually 
it will.

I think we can probably tune this process such that significantly 
better (= lower RTT) paths are often discovered without any additional 
effort. This would be accomplished by having an artificially low 
timeout for the initial reachability test. (Successive ones should 
probably use an (exponential?) backoff.) So we send probe A->X and then 
25 ms later B->Y. If the difference between RTT is bigger than 25 ms, 
the second probe will be answered first and we're in business. But if 
the RTT difference is smaller than 25 ms we'll still get a reply for 
the second probe after the reply for the first probe was received, as 
long as this one took longer than 25 ms. This works pretty well for a 
certain range of RTTs, only with very short ones we don't see better 
paths and with very long ones we send too many packets. If we can make 
the initial timeout a function of a previously established RTT we can 
probably get around this.

Another way to get around selecting a working, but non-optimal path is 
allowing applications to set an "impatient" flag which then triggers 
more extensive path evaluation.  :-)

---

From: Jari Arkko <[email-masked]>
Date: Mon, 25 Oct 2004 08:27:15 +0300

Iljitsch van Beijnum wrote:

> another a capacity of 1 Mbps. In this case, selecting the latter path as 
> part of regular operation would hardly be acceptable.

I agree that we have some remaining issues. To give you
another example, switching from a 50 Mbps LAN to a 20 Kbps
GRPS might be needed when the LAN goes down at some point.
However, what do we do when the LAN comes back up again later?
The slower interface still works, so there's no need to do
failover. But you'd really want to switch...

> We _may_ be able to bring this problem back to manageable proportions by 
> taking advantage of the information both ends have. So if either end 
> the first path is operational. This leaves only the cases where there is 
> congestion in the core, which is pretty rare these days. (But this 

Hmm... I guess the issue is whether either end knows. I'm not
sure the assumption that you know/test what the L2 does is any better
than the assumption that you know/test what the core does.

I'm not really afraid of testing the speed of a path, but what
I am afraid is the interaction with ULPs. We really don't want
Multi6 and TCP and whatnot testing all the same thing and second
guessing each other.

> Note that the whole reachability detection problem isn't as simple as it 
> may seem at first, especially when we want to make use of unidirectional 
> paths. Until not very long ago, I was favoring a "cartesian ping bomb" 
> approach where there are reachability probes for all { src, dst } 
> combinations. However, this can cause massive congestion when a link 
> fails for a busy site, and it's also complex and most likely slow.

Yes. In http://www.arkko.com/publications/multi6/faildet.html#anchor9
we did the math, and with the quite reasonable assumption of exponential
back-off, testing all combinations of addresses with just four addresses
on each side would last 3200 seconds.

> My current homework for the design team is to look how protocols such as 
> OSPF and especially STUN implement similar features and see what we can 
> borrow there. Unless this provides significant new insights I want so 
> see if we can make a "be optimistic but check first" approach work. This 
> means that when the reachability heuristics determine that there may be 
> a path failure, we check the current path. If there is a failure, we 
> check the next best path (for whatever "best" means locally) and so on, 
> until we find one that works. In order to detect unidirectional 
> reachability without excessive numbers of packets, each probe contains 
> information about the last few multihoming signaling packets received 
> from the other side. So unidirectional reachability won't be detected as 
> fast as bidirectional reachability, but eventually it will.

This is the algorithm in
http://www.arkko.com/publications/multi6/faildet.html#sketch

The part about using heuristics to try the address (pairs) is
good.

But I think the worst case behaviour is still bad. Remember that
even getting a packet from A to B means that you both have to have
the source set so that its currently routable, the destination
so that its currently routable, and that its routable from this
source.

> more extensive path evaluation.  :-)

Do you mean the "I am in a hurry, screw the others if this
causes congestion" -flag? ;-)

I fear that the things that we want to do would really require
better good knowledge of the current RTTs of the paths. This
can be measured, but there's a tradeoff in how far we want
to venture in the territory of TCP vs. how good our information
is.

--Jari