Subject: Source address selection in IPv6 multihomed multi-addressed sites

From: Cedric de Launois <[email-masked]>
Date: Wed, 16 Jul 2003 17:04:16 +0200

These are my random thoughts about source address
selection in IPv6 multihomed multi-addressed sites.

I believe this problem needs to be resolved to get
a complete IPv6 multi-addressing multihoming solution.
We assume here that the providers perform ingress
filtering.
I'm here only looking to solutions where the source
address selection is not made by applications, but it
is done "automagically". However, for all these solutions,
it is possible to imagine some mechanism where the
applications can overload the automatic behaviour.

Here is my understanding of the different solutions
proposed.

* A solution is to perform source address based routing
   inside the multihomed site. The packets are always
   routed to the site exit router corresponding to the
   source address used.

   Pros: - no new option/protocol
         - no modification to hosts
         - no tunnel
         - routing efficiency (dumb routing) ?

   Cons: - possibly very bad load-balancing if all the
           hosts choose the same source address (and this
           is what they'll do with RFC3484 !) +
           no way to engineer the traffic if no additionnal
           mechanism is used
         - source address based routing has probably
           much more implications than what it is
           expected. This needs to be studied further.

   My point of view : maybe source address based routing
   is not something desirable. Anyway, source address based
   routing alone is not sufficient.

* Another solution is to establish tunnels between the
   site exit routers. When a packet with a wrong source
   address is received by a site exit router, it is
   tunneled to the right exit router.

   Pro : no modification to hosts
   Cons: - a tunnel, reducing the MTU
         - no way to engineer the traffic

   My POV: I think this solution is too rigid and
   that a solution based on an ICMP source redirect can
   lead to a better solution without adding much more
   cost.

* A third solution is that a host first try a source
   address (at random?). If the source address is not
   correctly chosen (e.g. the link is down), then a
   new source ICMP redirect is sent by the site exit
   router to the host.
   This ICMP message tells the host which source address
   to use.

   Pro : no tunnel
   Cons: - modifications needed on the hosts
         - at first look, difficult to engineer the
           traffic with this mechanism

   My POV: I think this solution is the most credible
   when the site is small and doesn't need complex
   policies. However I think the ICMP source redirect
   message should also contain a prefix associated to the
   source, like in the NAROS response messages. This would
   allow the host to fill its policy table step by step.
   This approach has to be reserved for small sites with
   few requirements.

* A fourth solution is that a service (NAROS) tells the
   hosts which source address to use.

   Pro : - the most complete solution since it allows any
           kind of traffic engineering
         - no tunnel
   Cons: - also the most complex solution since it
           requires changes in the hosts and to set up
           a new service
         - implies source address based routing

   My POV: isn't that too complex for small sites ? Maybe.
   Is there a need to manage complex requirements is
   host-centric multihomed sites ? Probably. Anyway, the
   solution has the advantage of being rather complete. At
   the price of complexity.

* A fifth solution is that the hosts know which source
   address to use thanks to DHCP. When they boot, they
   receive a full policy table from their DHCP server.
   This policy table contains informations about which
   destination is accessible through which site exit router
   etc.

   Pros: - no tunnel
         - easy configuration
   Cons: - requires a new DHCP option. Modifications to
           host are needed
         - complex traffic engineering not supported
         - no dynamic, how to react to a failure ?
         - implies source address based routing

   My POV: seems to rigid for me. At almost the same price,
   we can get the same features + dynamic with the ICMP
   solution.

* A sixth solution is that a host tries to detect
   by itself which source address to use. A proposition
   is that a host maintain by itself one or more full BGP
   tables so that it can deduce the source address to use.

   Pro : no tunnel
   Cons: - waste of computer resources (how much ?)
         - no easy configuration

Any comment/suggestion/correction ?

Cédric

---

From: lek <[email-masked]>
Date: Thu, 17 Jul 2003 14:27:11 +0700 (SE Asia Standard Time)

Hello Cedric,

    I wonder in any solution impling source address based routing
that is it possible to use routing header instead of using
source address based routing. If it could, I think using routing
header is easier than source address based routing.
    Please correct me if I misunderstood.

Regards,
Pornpitak.

---

From: Francis Dupont <[email-masked]>
Date: Thu, 17 Jul 2003 10:13:28 +0200

In your previous mail you wrote:

=> you seem to like the second meaning of "source routing"...
IMHO we don't want to put the decision in the hands of hosts
(in this case it should be easier to use the "right" source address)
as the routing header is end-to-end. In fact, routing headers are
well suit for another class of problems: policy routing, i.e., one
may put the anycast address of a transit ISP in a routing header in
order to enforce the path though this ISP.

Regards

[email-masked]

PS: cf. RFC 2526. BTW the last time I checked the support of IPv6
subnet anycast addresses in common routers was very bad.

---

From: "Kenji Ohira" <[email-masked]>
Date: Thu, 17 Jul 2003 17:20:24 +0900

Cedric,

----- Original Message ----- 
From: "Cedric de Launois" <[email-masked]>
Subject: Source address selection in IPv6 multihomed multi-addressed sites

> applications can overload the automatic behaviour.
First of all, I think that source address selection should be made by each 
application/transport layer.

>    routing alone is not sufficient.
We are interested in application-level load sharing more than that of site-level.
I think that it is related to QoS issue, too.
If an application wants to use all bandwidth of all external connection, it is able by 
selecting all address which the host has.
If QoS parameters of each path are differ, an application can select the best suited 
path which it needs.

If an application has no special requirements for any QoS parameters, the application
can leave this selection to transport layer protocol as like as SCTP.
In this case, at the timing of establishing a connection, transport layer protocols on both 
end hosts negotiate all addresses which each host has, and each host select the best pair 
of src/dst addresses in according to RTT.

As another solution, an application or a protocol of transport layer can select a path in 
according to the longest match between source address and destination address.
In order to talk about this, I talked about 3-level hierarchical network model.
As more other solution, an application or a protocol of transport layer can select route in 
according to the external database as like as NAROS.

Anyway, a selection of source address can be and should be resolved in layer 4 or above.
For this reason, IP layer should be simple as possible in order to select correct site-exit 
router which is corresponding to a source address selected in layer 4 or above.

July 17, 2003 (JST +0900)
----
Kenji Ohira
Graduate School of Informatics, Kyoto University, JAPAN
mailto: [email-masked] / [email-masked]

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 17 Jul 2003 11:22:54 +0200

Kenji Ohira wrote:
...
> application/transport layer.

As I and Keith Moore and Christian Huitema have been trying to say, 
this is not realistic as a general case. In some special cases we can 
expect upper layers to be able to do this, but it has to be handled
by default in the IP layer.

   Brian

---

From: Xiaowei Yang <[email-masked]>
Date: Thu, 17 Jul 2003 12:45:36 -0400

>    Cons: - waste of computer resources (how much ?)

I do not see why a host needs to maintain the full BGP tables.  For
source address selection, it seems to me a host only needs to know the
provider-level route a source address represents, i.e., the chain of
providers that allocate a source address to the site/host. Suppose the
source address allocation chain on average has a depth of three. A
network on average takes source addresses from five providers. Then
the number of providers concerning a site's source addresses is about
5^3.  If a graph is used to represent these providers, the resources
required to store this graph and update it should be much less than
keeping an updated full BGP table that has 100,000+ entries.

The destination address selection is also a problem. To send the first
packet to a multi-homed destination, a host needs to pick a valid
destination address. This picking is less important because once the
first packet reaches the destination, the destination host may switch
to a different address in its reply packets that fits its QoS
requirements. Therefore, a host may random pick a destination
address. If it doesnot work, the host could try the a different
destination address.

Obtaining the provider information concerning source addresses of a
host requires a new network service.  Source address selection implies
provider selection, which has the potential to increase competition
among providers and discipline the ISP market. From this aspect, it is
important for a user to make an informed choice rather than a random
choice. Thus, the effort to provide a new network service to
disseminate provider information may be worthwhile.

My thesis work is right on this topic. If anyone is interested, a
short paper describing my work can be found at
http://www.isi.edu/newarch/DOCUMENTS/yang.nira.pdf

Xiaowei

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 18 Jul 2003 14:56:29 +0859 ()

Cedric;

> Any comment/suggestion/correction ?

You completely misunderstand the role of BGP.

See my draft stating:

   However, to enable source address filtering to discard packets with
   source addresses not belonging to an ISP, it is useful to enable a
   host, not some intelligent intermediate router, select a source
   address compatible with an outgoing ISP.  For that purpose, intra
   domain routing protocols or something like that should maintain
   routing table entries with not only preference values of an external
   routes, but also proper prefixes to be selected for source addresses,
   if the entries are chosen by a host.

It should be noted that it is already doable with the current OSPF spec.

							Masataka Ohta

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 18 Jul 2003 15:05:12 +0859 ()

Brian;

> by default in the IP layer.

IP layer can not select a destination address, though it can make
a suggestion to the upper layers.

Transport layer can not select a source address at all unless we
are doing QoS routing.

Ohira-san may be confused, because a scalable implementation of
QoS routing (designed by me and others) is running around him.

But, for most of you, it is extremely special.

							Masataka Ohta

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 20 Jul 2003 14:37:09 +0200

On woensdag, jul 16, 2003, at 17:04 Europe/Amsterdam, Cedric de Launois 

> a complete IPv6 multi-addressing multihoming solution.

[...]

> Any comment/suggestion/correction ?

I think your remarks on the mechanisms you mention are (nearly) all 
good points.

However, I think we need to take a step back and consider the more 
fundamental problem. The fundamental problem is that we really need to 
avoid source address spoofing, as this makes certain kinds of abuse 
nearly impossible to stop. (I.e., people can launch DoS attacks and the 
attacked systems can't see where the attack came from and they can't 
filter out the abusive traffic.)

So it is assumed that ISPs will filter their customer's traffic and 
only let packets with valid source addresses through. This gives us a 
range of options:

1. do nothing (what we do today) -> traffic will regularly not make it 
through -> a lot of unhappiness
2. ask ISP to let traffic through -> ISP may say no -> much unhappiness 
or upstream ISP filters -> also unhappiness
3. figure out the right source address (sort of happens today 
automatically sometimes) -> traffic will get through, but if the 
destination is rerouted over the other link the session breaks -> still 
considerable unhappiness
4. do source address dependent routing -> easy when only one box does 
this, harder in sites where there is internal routing, still problems 
with routing changes

If we get to change source addresses for existing sessions, we still 
need to do 3 or 4 but then we get to survive routing changes without 
breaking sessions, or we can rewrite the source address on egress and 
we're done. This has the advantage of being very once it is implemented 
in all border routers, but I'm afraid of problems in getting to that 
situation. Also, source address dependent routing gives the host more 
control over the path the traffic takes, which is good for performance 
and redundancy.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 20 Jul 2003 15:09:44 +0200

On vrijdag, jul 18, 2003, at 07:57 Europe/Amsterdam, Masataka Ohta 

> It should be noted that it is already doable with the current OSPF 

Hm, how would that work? In BGP you could see the next hop AS number 
and map this to a source address, but in OSPF there is no obvious way 
to do this. (Although I'm sure a non-obvious way can be created.)

However, I certainly wouldn't want hosts to interact with OSPF as this 
is a somewhat fragile protocol. In RIP you can simply ignore what hosts 
have to say and in BGP you can filter it, but in OSPF as-is you can 
only hope the host don't send any information that screws up the 
routing table.

And then there is still the problem of how useful this information is. 
Even today with BGP is is fairly common that BGP selects a very bad 
route because A and F can either communicate through B and C or through 
D and E. As far as BGP is concernet the paths are equally preferable: A 
- B - C - F or A - D - E - F. What BGP doesn't know is that the 
interconnect between B and C is 500 km away while the interconnect 
between D and E is on another continent. Obviously this problem is only 
going to get worse as the routing table becomes smaller. That's why I 
think that there will always be upward pressure for the routing table 
size.

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 21 Jul 2003 16:17:14 +0200 (CEST)

> this, harder in sites where there is internal routing, still problems 

And 5: have the site border router rewrite the source locator.
This assumes that id/locators are split, that the rewriting doesn't
effect "legacy packets" (without the id/loc split), and that the system
for securely verifying the id/locator relationship can handle
such rewriting.

Thus understanding the tradeoff between source locator rewriting and other
parts of the system is important.

  Erik

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 24 Jul 2003 11:52:28 +0859 ()

Iljitsch;

> and map this to a source address,

And the information is carried by IGP as has been stated in my draft.

> but in OSPF there is no obvious way 

You should check the format of AS-external-LSAs, of, say, RFC2740,
where there is a place to hold addresses of outgoing routers.

> only hope the host don't send any information that screws up the 

The paragraph above contains so much errors to worth commenting.

> route

You can use whatever EGP you like, though BGP practically is the
only solution.

> What BGP doesn't know is that the 
> between D and E is on another continent.

Relying on ASPATHLEN does not address the issue.

On the other hand, BGP administrators know that the interconnect
between B and C is 500 km away while the interconnect between D and
E is on another continent.

However, BGP administrators feel difficulty to grasp connections
between neighbor ASes, if there are so many neighbor ASes.

> Obviously this problem is only 

The smaller routing table allows more policy based control,
not blindly relying on ASPATHLEN.

							Masataka Ohta