Subject: Source address selection insufficient?

From: Erik Nordmark <[email-masked]>
Date: Tue, 2 Mar 2004 21:29:03 -0800 (PST)

When reading draft-huitema-multi6-hosts-03.txt (which is good because
it works out enough details to raise questions) I wonder
if address selection can solve ingress filtering.

Taking the canonical picture from the draft
             /-- ( A ) ---(      ) --- ( C ) --\
   X (site X)             ( IPv6 )              (Site Y) Y
             \-- ( B ) ---(      ) --- ( D ) --/

This has 4 locator pairs: 
	A:X-C:Y
	A:X-D:Y
	B:X-C:Y
	B:X-D:Y

The set of locator pairs that work when sending out from site X
might be A:X-C:Y and B:X-D:Y
but the set of locator pairs that work when sending from site Y might
be the other two: A:X-D:Y and B:X-C:Y.

Thus the intersection of the two ingress filtering constraints is the empty
set.

This can happen due to normal routing as far as I can tell.
The constraints for X appear if X routes packet to C out through A
and packets to D out through B.
The constraints for Y appear if Y routes packets to A out through D
and packets to B out through C.

Am I missing something?

If the above is true it seems like we need something other than
source address selection (relaxed filtering, source-based routing,
or locator rewriting).

  Erik

---

From: Pekka Savola <[email-masked]>
Date: Wed, 3 Mar 2004 10:10:02 +0200 (EET)

> be the other two: A:X-D:Y and B:X-C:Y.

I think what you're assuming that ingress filtering is recursive: it's 
done further down the IPv6 cloud from the both sides, rather than only 
at the edge.

This is done today, and is feasible.  
(dtaft-savola-bcp38-multihoming-update-03.txt, in RFC ed queue),
discusses this a bit.

But I see no problem.  You're assuming that someone down towards the 
IPv6 cloud has broken ingress filtering (such a case would be noticed 
today as well).  When the correctly-sourced packet has went from the 
edge site to the first ISP, it already has the correct address, 
corresponding the address block of the ISP.  If an ISP's upstream does 
not allow the ISP to send traffic from its own addresses, the upstream 
ISP is hosed.

So, I don't see the problem here -- could you elaborate?  Maybe I 
didn't understand your scenario?

-- 
Pekka Savola                 "You each name yourselves king, yet the
Netcore Oy                    kingdom bleeds."
Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings

---

From: Pekka Savola <[email-masked]>
Date: Wed, 3 Mar 2004 12:49:16 +0200 (EET)

Sorry -- I was confused, reading "source address based routing" rather
than "source address selection".

Policy-based routing works, has been widely implemented (multiple for
v6 as well), and works quite well.  You don't even have to do that on
other than site border routers unless you want to.

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 3 Mar 2004 03:03:40 -0800 (PST)

> done further down the IPv6 cloud from the both sides, rather than only 

No, it's about the ingress filtering at site X and site Y.

The initiator at site X can explore using all 4 locator combinations
(e.g. for the TCP SYN) and 2 of those pairs will make it out pasts
the ingress filtering of X's ISPs.
There is no filtering between those ISPs and site Y thus the SYN makes
it to the peer.
But the peer responds (with the SYN ACK) and has no choice on the addresses -
it must respond using the addresses that was in the SYN.

When these (SYN ACK) packets hit the ingress filter in Y's ISPs they are
filtered out.

As a result none of the 4 locator pairs work.

  Erik

---

From: Francis Dupont <[email-masked]>
Date: Wed, 03 Mar 2004 12:35:48 +0100

In your previous mail you wrote:

   Policy-based routing works, has been widely implemented (multiple for
   v6 as well), and works quite well.

=> I disagree a little because Cisco policy-based routing and Juniper
filter-based forwarding share the same problem: they are based on ACLs
and lack of dynamic capabilities. In fact they are only useful in the
ingress filtering context.

Regards

[email-masked]

PS: I can share my experience of this. As far as I know, there is
no concrete available examples...

---

From: Pekka Savola <[email-masked]>
Date: Wed, 3 Mar 2004 13:47:03 +0200 (EET)

> ingress filtering context.

What kind of dynamic capabilities would you looking for?  Reaction to 
the routing table?

But this is out of scope, so maybe you should follow up off-list.

The point is that you can match against the source prefix, which is 
what is required here.

---

From: Francis Dupont <[email-masked]>
Date: Wed, 03 Mar 2004 13:53:39 +0100

=> exactly. This can save existing connections on some limited but
important in some cases (after some previous arrangements with your
ISPs).

=> I agree..

=> my concern is that it is very hard or impossible to get more :-(

Regards

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 04 Mar 2004 14:16:14 +0900

Erik;

Yes, it is so for your proposal, which is why I asked that
you assume symmetric routing in Minneapolis.

						Masataka Ohta

---

From: "marcelo bagnulo" <[email-masked]>
Date: Thu, 4 Mar 2004 14:52:31 +0900

Hi Erik,

thanks for reading the draft

> and packets to B out through C.

I guess you are not, IMHO your analysis is correct.

The problem concerns what it is called in the draft "source address
discovery"
In this option, it is proposed that when a packet that does not comply with
ingress filtering arrives to the site exit router, the router informs the
host about the correct source address to use with a given destination.

A big assumption made in this scenario is that the host *can* change the
source address.
This may be more or less simple when the host is initiating a communication,
since when the hosts received the icmp error informing about the proper
source address, the host may be able to retransmit the packet with a
different source address.

However, when the host within the multihomed site is replying to a received
packet, the host cannot change the source address because the reply packet
would have a different address than the initial packet, so it wouldn't be
recognized as a reply of the initial packet by the initiator host.

Note that this situation is not restricted to the case when two multihomed
sites interact, but it is also possible when a non multihomed hosts
initiates a communication with a multihomed host.
For instance suppose a non multihomed host with address H1 and a host H2 in
a multihomed site with addresses A:H2 and B:H2.
Host H1 initiates a communication using as destination address A:H2 and
source address H1
Host H2 will reply using the same addresses so, source address A:H2 and
destination address H1

Now if the multihomed site is using source address discovery and internal
routing within the multihomed site has determined that the route to get to
H1 is through IPSB, then the reply packet will not make it and a icmp packet
will be sent back to H2 informing that it has to use prefix B in the source
address. Clearly H2 cannot do that and the communication will fail

Possible solutions for this were considered as using HoA dest option, but
this is no good because HoA dest option are only processed if a BCE exists.
In any case, this wouldn't really be source address discovery anymore.

So, i guess that at this point, it seems to me that the more reasonable
thing to do would be to honor the host source address choice, and adapt
routing to it

Regards, marcelo

---

From: "marcelo bagnulo" <[email-masked]>
Date: Thu, 4 Mar 2004 15:32:36 +0900

Forgot to reply this part...

> source address selection (relaxed filtering, source-based routing,

The draft also considers another option that is called site exit discovery.

In this case, the routers inform the hosts about the appropriate site exit
through which the host has to send the packet so that it can reach the
selected destination with the selected source address.

The host then tunnels the packet through the proper exit router.

This would be more like source routing rather than source address based
routing, and this solution honors the source address selection performed by
the host (it shouldn't have the problems of the other case)

regards, marcelo

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 3 Mar 2004 23:53:29 -0800 (PST)

> address. Clearly H2 cannot do that and the communication will fail

Yes, but in that case wouldn't the initiator retry with the other destination
address?

   Erik

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 4 Mar 2004 00:22:56 -0800 (PST)

> thing to do would be to honor the host source address choice, and adapt

That seems to be the robust approach.

> the host (it shouldn't have the problems of the other case)

I think this is just a particular implementation of source-based routing -
implemented using an overlay between the hosts and the border routers.

If we are going down the source-based routing architecture path, I think
it is desirable to do this the right way by starting with tunnels between
border routers and then increasing the domain of routers that 
do source-based routing following this picture in the draft:

                 Multiple site exits
                 |     |     |     |
            -----+-----+-----+-----+-----
           (                             )
           ( Source based routing domain )
           (                             )
            ----+----+----+----+----+----
           (                             )
           (   Generic routing domain    )
           (                             )
            -----------------------------

The host-to-border overlay is undesirable because you have to change all
the hosts, and once you've put this part of routing in the hosts it will
be hard to evolve the routing and the adminstrator might loose policy
control as a result.

But that is mostly my gut feel.

  Erik

---

From: Antonio Tapiador del Dujo <[email-masked]>
Date: Thu, 4 Mar 2004 11:51:18 +0100

> recognized as a reply of the initial packet by the initiator host.

What about marking packets that may be source-address-corrected, 
using an extension header, or maybe a single bit?

The multihomed host knows which packets can be corrected, and which 
ones must not.
Legacy hosts would not be corrected, their traffic would be source
address routed or managed by other site exit solution. 

Upper layers solutions may use this mark for their own needs.

Greetings,
	Antonio.

-- 
EuropeSwPatentFree - http://EuropeSwPatentFree.hispalinux.es

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 05 Mar 2004 10:30:34 +0100

> address routed or managed by other site exit solution.

I definitely feel that marking packets would make this type of solution
more robust in some ways, but it has distinct problems - we don't
have a bit for this, and we really want to avoid extension headers
if we can (MTU size issues, etc.)
> Upper layers solutions may use this mark for their own needs.

I suspect ULPs will want to avoid knowing anything about MH events,
unless you include the transport layer as a ULP.

   Brian

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sat, 6 Mar 2004 13:37:34 +0100

> This has 4 locator pairs:

Ugh, is it just me or is the A:X notation (rather than X:A) very 
counter-intuitive?

> be the other two: A:X-D:Y and B:X-C:Y.

What you are saying is that X wants to reach Y over either the path 
A->C (1) or the path B->D (2), while in the other direction the path is 
D->A (3) or C->B (4). The address permutations in the packets are then 
as follows (!I means ingress filtered):

address pair	X->Y direction	Y->X direction
A/C				(1)					(3) !I
A/D				(2) !I				(3)
B/C				(1) !I				(4)
B/D				(2)					(4) !I

> Thus the intersection of the two ingress filtering constraints is the 
> empty set.

:-(

This means our address agility mechanisms must support packet flow 
where the src/dst addresses in packets in one direction don't 
correspond to the src/dst addresses in opposite direction. In the above 
example X may send out packets with A/C while Y responds with packets 
containing D/B.

Unfortunately this still breaks all non-address agile protocols, most 
notably current TCP and UDP but also many proposed solutions in their 
compatible or negotiation phase.

> Am I missing something?

The only way this can happen during "normal" routing is when the two 
destination addresses for a correspondent are routed differently. When 
this isn't the case (for instance, when a default route is in effect) 
the problem should only occur when there are outages but current TCP 
and UDP are dead in the water in that case anyway. We have to look at 
the possibilities of setting up new sessions (with a multihoming 
solution in effect) under these circumstances, though.

I guess this means that trying different source addresses CAN be 
sufficient but it's far from ideal because it can't live together with 
existing traffic engineering techniques.

But maybe the problem isn't as bad as it would seem at first glance: 
for small sites, source address based routing is fairly trivial and it 
provides decent overal traffic engineering (although individual streams 
may suffer) while only larger sites are going to run BGP in order to do 
traditional traffic engineering anyway, and presumably, those sites are 
in the position to get ingress filtering relaxed. (We need to document 
this very well at some point because this is still imcompatible with 
ingress filtering further downstream.)

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 06 Mar 2004 12:35:25 -0500

I think that this is getting more complex than necessary.
It is true that routing is frequently asymmetric.
However, that is a very different statement from saying that connectivity 
is asymettric.  While the routing path among ISPs for a given address pair 
(src, dst) may be different in the forward and reverse direction, it would 
take a very strange situation for a pair to work one way, and not when 
reversed.  It would take an even stranger situation for there to be no pair 
that worked in both directions.

As such, I think we ought to be able to assume that there exists (at any 
given time) an address pair that is useable in both directions.  (The 
packets using that pair may not take the same path forward and backward, 
but will use the same ingress / egress points on each end.

Situations where the connectivitiy / path changes are so fast that you can 
not find such a pair probably need very different techniques (just as MANET 
is looking for different techniques than MobileIP.)

Yours,
Joel M. Halpern

At 01:37 PM 3/6/2004 +0100, Iljitsch van Beijnum wrote:
>What you are saying is that X wants to reach Y over either the path A->C 
>(1) or the path B->D (2), while in the other direction the path is D->A 
>(3) or C->B (4). The address permutations in the packets are then as 
>follows (!I means ingress filtered):
>
>This means our address agility mechanisms must support packet flow where 
>the src/dst addresses in packets in one direction don't correspond to the 
>src/dst addresses in opposite direction. In the above example X may send 
>out packets with A/C while Y responds with packets containing D/B.
>
>this isn't the case (for instance, when a default route is in effect) the 
>problem should only occur when there are outages but current TCP and UDP 
>are dead in the water in that case anyway. We have to look at the 
>possibilities of setting up new sessions (with a multihoming solution in 
>effect) under these circumstances, though.
>
>But maybe the problem isn't as bad as it would seem at first glance: for 
>small sites, source address based routing is fairly trivial and it 
>traditional traffic engineering anyway, and presumably, those sites are in 
>the position to get ingress filtering relaxed. (We need to document this 
>very well at some point because this is still imcompatible with ingress 
>filtering further downstream.)
>

---

From: Masataka Ohta <[email-masked]>
Date: Sun, 07 Mar 2004 08:51:41 +0900

Joel M. Halpern;

> I think that this is getting more complex than necessary.

Because of the introduction of connection at the IP layer, yes.

The issue is simple if you accept the IP layer is connectionless
and unidirectional.

> However, that is a very different statement from saying that 
> connectivity is asymettric.  While the routing path among ISPs for a 
> given address pair (src, dst) may be different in the forward and 
> reverse direction, it would take a very strange situation for a pair to 
> work one way, and not when reversed.  It would take an even stranger 
> situation for there to be no pair that worked in both directions.
> 
> given time) an address pair that is useable in both directions.

That is a useful property because it makes ICMP returned most of
the time, though we shouldn't rely on them too much (that is,
PMTUD is not a good idea).

However, as the destination locator is chosen by the source
local policy, bidirectional transport layer can not assume
the locator pairs are same for the both directions.

							Masataka Ohta

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 7 Mar 2004 09:46:57 +0100

> I think that this is getting more complex than necessary.

This isn't complexity invented by us; it's just reality that we have to 
deal with.

> connectivity is asymettric.

Asymmetric routing + ingress filtering = asymmetric connectivity.

> While the routing path among ISPs for a given address pair (src, dst) 
> may be different in the forward and reverse direction, it would take a 
> very strange situation for a pair to work one way, and not when 
> reversed.

See Erik's original example or my interpretation of it in my message 
that you superfluously quoted in its entirety.

---

From: Masataka Ohta <[email-masked]>
Date: Sun, 07 Mar 2004 18:40:26 +0900

Iljitsch;

> Asymmetric routing + ingress filtering = asymmetric connectivity.

An interesting implication is that site internal routers
must use proper source address for ICMP reply to a host in
a peer site, which makes connection oriented maintenance
of source address impossible.

Of course, for those believing in NAT or connection oriented
IP layer, it is not impossible but just to make all the routers
maintain transport layer states without having any knowledge
on transport layer connectivity.

						Masataka Ohta

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 8 Mar 2004 11:13:34 -0800 (PST)

> example X may send out packets with A/C while Y responds with packets 

If you need that level of address agility underneath the transport protocols
you need to modify the hosts at both ends.
Once you modify the hosts at both ends why not also provide connection
rehoming? (There seems to be a large class of connection rehoming mechanisms
that can live with source locator rewriting instead of ingress filtering,
but that's the subject of a different email.)

> ingress filtering further downstream.)

I agree that source based routing and relaxed filtering both work.
What is tricky is the middle between the small and the large; too small
a site to be able to convince the ISPs to relax ingress filtering
and too large a site for source based routing to be trivial.

  Erik

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 8 Mar 2004 14:34:18 -0800 (PST)

> that worked in both directions.

Things might be a bit subtle - perhaps we don't understand well
enough the interaction between routing, source address selection,
and ingress filtering yet.

A few observations:
1. If you ignore the effect of the source addresses and ingress filtering,
   all paths between A and B work in both directions in my example.
   Thus there is no need for unidirectional failures of links to get into
   this state.
2. Each link between a site and their ISPs can have
   packets pass in both directions in the example; there exist a <src,dst> 
   address pair which makes packets traverse a particular site/ISP link.
3. One perspective is that we get in trouble due to the assumption by the 
   transport protocols that the same address pair is used in both directions;
   the assumption seems counter to the loose notion of "address selection" -
   only one end of the communication can select address.
   (Another perspective is that ingress filtering doesn't fit.)

> but will use the same ingress / egress points on each end.

I don't understand.
From the fact that communication is possible in both directions, both e2e and
over each of the site/ISP links, it doesn't follow that an adress pair exists
that can be used in both directions.
Can you clarify?

  Erik

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 9 Mar 2004 00:13:02 +0100

On 8-mrt-04, at 20:13, Erik Nordmark wrote:

>> correspond to the src/dst addresses in opposite direction.

> you need to modify the hosts at both ends.

Any level of address agility greater than 0 requires this.

> rehoming?

Sure. But how does this relate to the problem at hand currently?

> (There seems to be a large class of connection rehoming mechanisms

Unfortunately we still have to deal with the packets that can't be 
rewritten and I'm not sure if expecting all routers to be upgraded to 
support this is reasonable.

> and too large a site for source based routing to be trivial.

For mid-sized sites the "use a default only" policy wouldn't be ideal, 
but it should at least make sure there is always a working path. For 
small sites the default-only policy has the disadvantage that only one 
external link will be used for outgoing traffic, but in a site that has 
several routers and subnets, different routers/subnets could use 
different external connections so rudimentary load balancing would 
still happen.

The main problem of this approach is the fact that unfortunate source 
address choices lead to blocked packets/sessions because of ingress 
filtering. However, mechanisms to overcome this problem can largely be 
implemented unilaterally, especially for outgoing sessions.