Subject: Re: survivability, rewriting

From: Iljitsch van Beijnum <[email-masked]>
Date: Sat, 1 Nov 2003 13:58:48 +0100

On 31 okt 2003, at 14:38, marcelo bagnulo wrote:

>> One thing we haven't discussed so far: if upper layers provide us with
>> a hint, what exactly does the multihoming layer do after receiving 
>> such
>> a hint?

> I thought this was what we were discussing with Erik in the Preserving
> established sessiones thread :-)

We may want to do some extra checking before immediately failing over. 
For real time stuff, transport protocols are usually implemented inside 
applications. This means the mh layer may receive far too many hints 
from the transport layer to actually act on each one of them. Also, it 
might be beneficial to find out which alternatives still work before 
selecting them to continue the session over.

I'm thinking along the lines of sending out packets with all possible 
source/dest locator combinations and then see what comes back and how 
fast. Obviously we don't want to set off such a "ping bomb" too often. 
And we very likely don't want to use actual ICMP echos for this, but 
what do we want to use?

> IMHO, i would like to explore alternative approaches first.
> What about when recieving a ULP hint that there is a problem, change 
> both
> source and destiantion locators and send the packet with rewrite ok 
> bit not
> set?
> A more aggresive option would be to send multiple packets in paralel, 
> each
> one with a different combination of source and destiantion address, 
> and see
> which reply comes first.

Yes. But I don't think we want to do this with actual data packets. In 
fact, there may not be any data packets available when this is 
triggered by a hint.

>> However, this doesn't solve what we should do when rewriting isn't
>> permitted. Obviously we could come up with a multihoming mechanism
>> where rewriting is always allowed,

> I don't see how.

If we put a 64 bit identifier in the low order bits of the 128 bit 
address and then either make transport work on these 64 bit ids (a la 
8+8) or we expand the 64 bit id into a 128 bit one as explained in my 
http://www.muada.com/drafts/cryptoid.txt non-draft. Then there is no 
problem with arbitrarily changing source locators. (Except some minor 
security points.)

> I mean, we are going to have two mechanisms, one based on bgp + 
> rewriting
> and the other one is based on ULP hints.

BGP is a non-starter as there can always be failures that don't show up 
in BGP because of aggregation.

> Now it is expected that the ULP hints mechanism will be have a better
> response time i.e. it will detect problems faster, right?

That's the idea.

> However, the ULP hints mechanism works in the host itself and the
> bgp+rewrite mechanism is in the routers. This means that even if the 
> ULP
> hint mechanism has detected a problem and changed the locator, if the 
> final
> word about this belongs to the routing system, the bgp+rewriting 
> mechanism
> will overrule the decisions made by the ULP hint mechanism which is 
> exaclty
> what we don?t want

Indeed.

> So we need a mechanism to force the routing system to accept choices 
> made by
> the host, since the host is better detecting problems in the path.
> Such a mechanism seems to require the capability to express that 
> rewriting
> is not permited.

Or useful.

>> But "legacy" IPv6 also doesn't permit
>> rewriting, so we must be prepared to handle this. The obvious solution
>> is source address based routing, but it doesn't seem like everyone is
>> convinced.

> Well, we could use a routing header.

You mean a routing header indicates permission to rewrite? That seems 
rather extreme. I'd use a different link layer encapsulation (= 
ethertype) or even IP version number first.

> Even we could define a routing headers
> that is elimated by the exit routers, in order to addresss the MTU 
> reduction
> problem.

That would only work if the first hop has a higher MTU than the rest of 
the path... Also removing some data in the middle of a packet is an 
extremely expensive operation in software.

> An obvious comment about source address based routing is that source 
> address
> based routing only has to be implemented within the multihomed site.

Yes. It is not unthinkable that a host or even a small site has 
connections to two or more ISPs and/or larger sites. For instance, a 
laptop may be connected to the multihomed enterprise network while at 
the same time connecting to a GPRS ISP, or a home user could have an 
ISP connection and a VPN back to the multihomed enterprise network. But 
I think source address based routing or rewriting doesn't have to be 
arbitrarily stackable without the layers knowing about eachother.

---

From: "marcelo bagnulo" <[email-masked]>
Date: Sat, 1 Nov 2003 20:07:49 +0100

> from the transport layer to actually act on each one of them.

Good point.
I guess that the M6 layer will have to react to a hint and then ignore the
next hints for a certain period

> Also, it

Ok, but wouldn't this delay the reovery? i.e. the response time would be
worse
(see below)
> And we very likely don't want to use actual ICMP echos for this, but
[...]

> fact, there may not be any data packets available when this is

I can think of two types of hints:
- a first type where the sending endpoint timeouts, so it detects the
failure by itself. This is the case where ack are used such as tcp. In this
case the ULP of the endpoint that is sending hints the M6 layer of the
sending endpoint (this is the easy case, i guess)
- a second type where no ack are used, so the ones that detects the failure
is the receiving end who detects the failure because it no longer receives
packets at the expected rate. In this case, the receiving end has to
communicate the problem to the sending endpoint. So in this case, the ULP of
the receiving endpoint has to hint the M6 layer of the sending endpoint.

Does thus makes sense? can you think of other scenarios?

Then in the first case, the sending enpoint always has packets, since it has
detected the failure because of retransmissions, i guess. So, why don't you
think it should not try every possible path with data packets?

In the second case, in order to discover which path is working, you will
need a message exchange, since probably there will be no packets back from
the receiving endpoint to the sending endpoint that allow the sending
endpoint to find out which is the combination of source and destination
address that it is actually working. So i guess that in this case, it would
make sense to have a protocol in the M6 layer to perform the available path
discovery.

[...]

> in BGP because of aggregation.

IMHO BGP is too slow, as we already agreed, but i am not uderstanding your
point about the aggregation.
I do understand it when you use bgp from the sending endpoint, so you cannot
see if the target endpoint is really reachable because aggregation hides it
from you.
But if you use BGP plus rewriting as Erik suggests, then aggregation is not
a problem, because you use bgp as a mean to discover the available path, not
to see which address you should use. The information about what address to
use is carried in the source address field of the received packet.
Anyway, could you put an example where tha aggregation cause the problems
that you mention? (sorry to ask you this, but i really fail to see the
problem here)

[...]

> You mean a routing header indicates permission to rewrite?

No. sorry for not being more explicit.
I was suggesting using a routing header to allow the host to force the exit
ISP i.e. as an alternative to the source address based routing

> That seems

Yes, but isn't this the most usual case?

> arbitrarily stackable without the layers knowing about eachother.

I think that i agree with you. I think that we need a mechanism to allow the
host to indicate if it allows rewriting in the packets, is this what you
mean?

Regard, marcelo

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 4 Nov 2003 13:29:12 +0100

> Ok, but wouldn't this delay the reovery? i.e. the response time would 

That is a possibility, but on the other hand rehoming in the blind also 
has its risks. For instance, if an upper layer protocol provides too 
many hints, we could be rehoming when there was just some incidental 
packet loss. I'm pretty sure rehoming will have to trigger slow start 
in TCP, which is not something you want to happen if isn't absolutely 
necessary. Or, in the case of a relatively large number of possible 
paths, several paths may share some infrastructure and go down at the 
same time. In that case, checking all paths helps avoid choosing a 
backup path that is also down. If we indeed go for the ping bomb 
approach there is the advantage that we immediately see which path is 
fastest, which is also a good feature and it only takes a single round 
trip.

> the receiving endpoint has to hint the M6 layer of the sending 

Hm, doesn't the other side determine that something is wrong because it 
doesn't see any acks? If the ULP supports nacks then the receiving end 
can send those to get the message across sooner.

> Does thus makes sense? can you think of other scenarios?

Another possibility would be that a receiver sees consistent duplicate 
packets, which indicates that the acks aren't getting back to the 
sender.

We may also want to trigger re-evaluation of reachability in some other 
cases. For instance, when a session has been idle for a long time, or 
upon some kind of hardware or routing event.

> think it should not try every possible path with data packets?

Might be an implementation issue. Might not be a problem, though.

> make sense to have a protocol in the M6 layer to perform the available 

Yes.

> see if the target endpoint is really reachable because aggregation 

Right, that was my point.

> to see which address you should use.

Ah, I see: the host selects a destination address, then the router uses 
BGP to determine which ISP would be the best one to use to reach this 
address. Yes, this makes sense. However, there are two problems that 
are somewhat related to this:

1. the source address may be incompatible with the exit ISP
2. the destination address may be unreachable

The first can be fixed by rewriting. The second must be handled by the 
host. But if the host must handle selecting a destination address 
anyway, why not slightly extend this capability and let the host select 
a source/destination combo?

Assume hosts X and Y, X has ISPs A and B, Y has C and D and R means 
"rewriting allowed". Assume BGP prefers path X->A->C->Y and 
X->B->E->F->D->Y.

1 = routers with no special capabilities
2 = routers support source address based routing but not rewriting
3 = routers support source address based routing and also rewriting

               1   2   3
X(A)->Y(C):   +   +   +
X(A)->Y(D):   -   +   +
X(B)->Y(C):   -   +   +
X(B)->Y(D):   +   +   +
X(R)->Y(C):   -   -   +
X(R)->Y(D):   -   -   +

I think it's pretty clear that situation 1 is very sub-optimal but the 
added value of the rewriting feature is quationable. In situation 2 all 
the paths that are available in situation 3 are also available, it just 
may take a little longer to find the best one.

> ISP i.e. as an alternative to the source address based routing

That wouldn't work, as "legacy" IPv6 hosts would have to insert such a 
header in order to function in a multihomed site.

Iljitsch

---

From: "marcelo bagnulo" <[email-masked]>
Date: Tue, 4 Nov 2003 15:57:54 +0100

> fastest, which is also a good feature and it only takes a single round

Agree.
My question is why don't just send a replicated data packet instead of
pings?
I mean, i have a hint that something is wrong, so if i have data packet
available, i send it replicated as many times as possible source dest
address combinations i have available.

> doesn't see any acks?

I am supposing a communication that don't use acks, data streaming and the
like.

> If the ULP supports nacks then the receiving end

I am considering a communication that don't use nack neither, just one way
stream.

> upon some kind of hardware or routing event.

Ok

> a source/destination combo?

You don't have to convince me :-)

> 3 = routers support source address based routing and also rewriting

I guess that X(A)-> Y(C) means that you are using as as source address the
address of X containing the prefix delegated from ISPA and as destination
address the address of Y with prefix delegated by ISPC, right?
and, what do you mean by + and -?

> header in order to function in a multihomed site.

Well, if we restrict ourselves only to legacy IPv6 host compatible
mechanisms, i guess that the only options is some form of source address
based routing (whether in all the site or only in the exit routers), which
is fine by me :-)

More seriously, i think that this is a relevant point to evaluate different
approaches:
Different approaches to deal with ingress filtering can be compatible with
legacy internal hoats and legacy external hosts.
Source address rewriting is not compatible with none of them i.e. you need
modification in both ends to support it, so you need an additional mechanism
to deal with ingress filtering in those cases.
Source address based routing is compatible with both internal and external
legacy hosts
A routing header, as you note, is compatible with external legacy hosts but
not with internal legacy hosts

Regards, marcelo

---

From: "Spencer Dawkins" <[email-masked]>
Date: Tue, 4 Nov 2003 22:41:50 -0600

Just a minor comment:

----- Original Message ----- 
From: "Iljitsch van Beijnum" <[email-masked]>
To: <[email-masked]>
Cc: "Multi6 Mailing List" <[email-masked]>
Sent: Tuesday, November 04, 2003 6:29 AM
Subject: Re: survivability, rewriting
> necessary.

In some unrelated conversations in TRIGTRAN, we were saying that Slow
Start is conceptually the right thing to do for path changes, but Slow
Start works fine if you lose something - why not wait to see what you
lose, and only Slow Start if you need to?

If you lose packets during rehoming, you'll fast retransmit/fast
recover at a minimum, so it's not like you're switching paths at the
same sending rate.

But this is probably a good TSVWG question.

Spencer

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 5 Nov 2003 11:05:15 +0100 (CET)

> address combinations i have available.

That can work as long as you can tell from the returned packets which
of the replicated data packets made it.
I think this is hard. If you take a ULP packet and send it with different
src/dst locators and then after one RTT there is a response (a ULP ack for
instance) how can you tell which of the src/dst locator pairs worked?

The scheme does work when the ULP has been designed with this in mind
as in SCTP, but for other ULPs I think you need to add something
akin to the icmp echo sequence number that would be returned in the responses.

It might be easier to just use separate packets for the "pings".

  Erik

---

From: "marcelo bagnulo" <[email-masked]>
Date: Wed, 5 Nov 2003 11:29:26 +0100

> It might be easier to just use separate packets for the "pings".

Ok, what about replicating data packets and include in them a M6 destiantion
option that means the ping?
So, if there are data packets available we can piggyback ping into data
packets (both forward and reverse path)
My concern is about the sending host having to wait until the ping reply is
received.
An additional concern is that i don't think that we could trust ICMP end to
end, becuase of icmp filtering.

Regards, marcelo

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 5 Nov 2003 11:42:45 +0100

> instance) how can you tell which of the src/dst locator pairs worked?

Right. Also, data packets are presumably large, while probe packets can 
be small. Sending four 80 byte probes to test four combinations of two 
sources and two destinations is less expensive than sending one 500 or 
1500 byte data packet. On low bandwidth links having small probes also 
means the RTT for the reply is much faster: on a 56k link 80 vs 1500 
bytes makes a 400 ms difference.

These savings are especially significant when the active path is still 
available after all.

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 5 Nov 2003 12:50:25 +0100 (CET)

> option that means the ping?

Could do that or other forms of piggybacking (an extension hdr which is
followed by the payload packet) if there is a need for this.

> My concern is about the sending host having to wait until the ping reply is

Why would it have to wait?
It can be optimistic (the same way e.g. neighbor unreachability detection
is optimistic) by sending the data packet and separately sending the
reachability test packet. Whether optimizing that to be one larger packet
instead of two is worth-while is a detail we need to talk about once we
understand the bigger picture choices.

> end, becuase of icmp filtering.

Agreed they might not be reliably delivered.

  Erik

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 5 Nov 2003 13:14:51 +0100

> Agreed they might not be reliably delivered.

People who filter ICMP get what they ask for... Alternatively, we can 
ask ULPs to supply a probe packet along with the hint. For instance, 
TCP could make a very small packet that triggers an ack from the other 
side. The mh layer can then send out these probes with some additional 
info needed to see what works and what doesn't in an option/header. If 
the ULP doesn't supply a probe (or a hint, for that matter) the mh 
layer sends just the option/header with no upper layer, the 
option/header with an ICMP echo request or an UDP packet that addresses 
the mh layer on the other side.

Iljitsch

---

From: Masataka Ohta <[email-masked]>
Date: Tue, 11 Nov 2003 14:13:30 +0900

Spencer;
 
> Start is conceptually the right thing to do for path changes,

Agreed.

However, path changes at the middle of the path are not noticable
by end systems.

Considering the diameter of the Internet and assuming that reliability
of backbone and local ISPs are same, such path changes are expected
to occur more often than rehoming.

In addition, rehoming is a subset of path chang.

So, we, multi6, are not required to address the issues related to
path changes.

Right?

> But this is probably a good TSVWG question.

How about let routers accumulate (with XOR or something like
that) link CRC (or some psuedo random number involving link
specific numbers such as MAC addresses of a hop) into (so far
useless) flow label field to let upper layers notice the path
change to trigger the transport layer?

I myself am afraid that it is too late to change IPv6 router
behaviour. So, I never proposed any multihoming solution involving
router changes.

However, I know transport people are actively proposing to change
router behaviour to help TCP and they have better chance with IPv6. :-)

						Masataka Ohta

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 11 Nov 2003 00:00:16 -0600

> change to trigger the transport layer?

Similar to the record route option.

> behaviour. So, I never proposed any multihoming solution involving

Another way to detect path changes, but not a very reliable one, is to 
monitor the hop limit value in incoming packets. And of course the 
round trip time.

> router behaviour to help TCP and they have better chance with IPv6. :-)

Hm, maybe we can make a deal so that they change TCP behavior to help 
routers...

---

From: Masataka Ohta <[email-masked]>
Date: Tue, 11 Nov 2003 15:45:14 +0900

Iljitsch;

> Similar to the record route option.

The essential difference is to resuse a fixed length field without
burdening routers.

> monitor the hop limit value in incoming packets. And of course the round 
> trip time.

Surely, they can be helpful but are not so reliable.

> Hm, maybe we can make a deal so that they change TCP behavior to help 

I'm, and most of transport layer people, are talking about behaviour
at the IP layer, even though the bhaviour may be meaningful for
connection oriented transport layers.

						Masataka Ohta