Subject: Implementation worries about default address selection

From: Pekka Savola <[email-masked]>
Date: Sun, 6 Oct 2002 12:20:16 +0300 (EEST)

Hello,

Recently I discussed default address selection a bit with implementation 
folks who were unwilling to put (already implemented) default address 
selection into the OS.

The main reason was that, as currently specified, default address
selection seems like something that can't be implemented AS-IS without a
big performance degradation.

The thing is, it seems like this (IMO relatively complex) iterative
comparison algorithm must be run for every outbound packet (one might be
able to optimize a bit with connection-oriented protocols).

An alternative seems to be to implement some form of (unspecified --
caching is only discussed in the context of dst address selection)
optimizations.  One example of optimization could be putting the
to-be-used source address in the routing table, and refresh it always when
rtable or any address of the node changes or changes state
(deprecated/preferred, home address etc.), but these might have their own
problems.

My worry is, is it useful to specify a mechanism for selection default
addresses that can't really be used without critical optimizations?

====

A few comments I came across -- the second at least, IMO, requires a 
clarification.

1. another issue struct me while re-reading: the draft discusses
source/destination address selection separately: with S, select D from
D_1, D_2, ..., D_n, or with D, select S from S_1, S_2, ..., S_n. If I
understood correctly a fairly common case of S_1, S_2, ..., S_n *AND* D_1,
D_1, ..., D_n was not elaborated more (a brief mention in section 2?).

2. IMO, I think sections 3.2 and 3.3 may be a bit ambiguous wrt. mapped
addresses and scopes.  Is it supposed to say that if I have configured
'::ffff:10.0.0.1' on an interface (for some reason..), treat it as global
(per 3.3), but if I'm communicating via IPv4 (and it was just added to
destination address selection as a mapped address ::ffff:10.0.0.1, treat
is as site-local (per 3.2))?!?  This surely got me confused!

-- 
Pekka Savola                 "Tell me of difficulties surmounted,
Netcore Oy                   not those you stumble over and fall"
Systems. Networks. Security.  -- Robert Jordan: A Crown of Swords

--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page:                      http://playground.sun.com/ipng
FTP archive:                      ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [email-masked]
--------------------------------------------------------------------

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 9 Oct 2002 23:32:05 +0200 (CEST)

> able to optimize a bit with connection-oriented protocols).

I think connection oriented protocols effectively require that
the source address (or addresses in the case of SCTP) be selected
when the connection is created. Thus trying to do this for every packet
would be the wrong thing in that case.

For connection-less protocols where the application doesn't specify
the source address in the bind() call, performance can benefit from
caching the source address selected for a given destination much the
same way that performance benefits from caching routing information for
a given destination.

> addresses that can't really be used without critical optimizations?

I'm not worried about this. We have exactly the same issue for routing table
lookup in hosts and routers; there is no specification that states how
to implement caching schemes.

   Erik

---

From: Pekka Savola <[email-masked]>
Date: Thu, 10 Oct 2002 16:02:21 +0300 (EEST)

> would be the wrong thing in that case.

Agreed.

[...]
 
> to implement caching schemes.

We haven't really specified the source address selection like this for 
IPv4 either, I believe.  Have I missed something?

Routing table lookup is very simple compared to this I think.

---

From: Brian Haberman <[email-masked]>
Date: Thu, 10 Oct 2002 09:32:20 -0400

> On Wed, 9 Oct 2002, Erik Nordmark wrote:

[snip]

> Routing table lookup is very simple compared to this I think.

Have you looked at the routing/forwarding sections of the scoped
addressing architecture?  It used to be simple.

Brian

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 10 Oct 2002 16:12:48 +0200 (CEST)

> IPv4 either, I believe.  Have I missed something?

That wasn't what I said. I said that IETF specifications don't
go into details on how to cache things, whether it is for "routing"
or "source address selection".

I suspect IPv4 implementations which allow more than one IP address
per interface have some mechanism by which the source IP address
is selected, since it can't just be the single IP address assigned to
the outgoing interface.

> Routing table lookup is very simple compared to this I think.

Conceptually simple, yes. Making it perform, combining the routing table
with the arp/nd cache for performance, etc makes it more complex.
Source address selection is also conceptually simple. And making it
perform well makes life more complex.

  Erik

---

From: YOSHIFUJI Hideaki / 吉藤英明<[email-masked]>
Date: Fri, 11 Oct 2002 00:31:57 +0900 (JST)

Just one comment.

> D_1, ..., D_n was not elaborated more (a brief mention in section 2?).

D then S.

|5. Source Address Selection 
|
|   The source address selection algorithm produces as output a single 
|   source address for use with a given destination address. This 

-- 
Hideaki YOSHIFUJI @ USAGI Project <[email-masked]>
GPG FP: 9022 65EB 1ECF 3AD1 0BDF  80D8 4807 F894 E062 0EEA
--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page:                      http://playground.sun.com/ipng
FTP archive:                      ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [email-masked]
--------------------------------------------------------------------

---

From: Pekka Savola <[email-masked]>
Date: Fri, 11 Oct 2002 09:24:04 +0300 (EEST)

> |   source address for use with a given destination address. This 

Yes, that is clear (the algorithm must have only one destination), but the 
question arises how much this makes sense (as the destination address may 
already have been selected using some arbitrary source address for 
comparing against the destination address).

The extra steps may not harm of course (extra work..).  One possibly
interesting scenario could be when source or destination address selection
has been upgraded to honor this but the other isn't.

---

From: Pekka Savola <[email-masked]>
Date: Fri, 11 Oct 2002 09:35:30 +0300 (EEST)

> addressing architecture?  It used to be simple.

It has seemed relatively simple to me, except for the parts with 
site-local addressing.. :-(

---

From: Pekka Savola <[email-masked]>
Date: Fri, 11 Oct 2002 09:54:55 +0300 (EEST)

> or "source address selection".

Perhaps we should have been more careful when discussing "how/when" to use 
caching.

But well, 'htsearch' on RFC's for "cache" at http://rfc.eunet.fi (for
example) returns 520 RFC's.

I think there are examples of some caching specification, as well (e.g.  
neighbor discovery, multicast, ...).  The level of detail is of course
imporant.  At least, very many specifications say, like "this and this
part is critical and should [or SHOULD] be cached".

One of my main worries was that it seemed that nobody even bothered to 
mention that the steps could be complex and some caching mechanism 
(possibly with some examples) should be implemented.

---

From: Sebastien Roy <[email-masked]>
Date: Fri, 11 Oct 2002 11:16:37 -0400

> comparing against the destination address).

I'm not sure I understand your last parenthesized comment.  Are you
worried that an application could choose a destination address based
on source address assumptions that are different than those of the
kernel's default source address selection mechanism?  In that case,
the application should bind to the source address to be sure it gets
the one it wants right?  I could be misunderstanding what you've said.

> has been upgraded to honor this but the other isn't.

The source address selection mechanism is still useful in the absence
of the destination address ordering.  In any case, there is no
guarantee that applications will use the destination addresses in the
order returned from name lookups.  Also, users or administrators may
want the ability to turn off the destination address ordering
mechanism in order to preserve some sort of ordering returned by the
server (DNS round-robin for example).

The destination address ordering mechanism needs some deterministic
source address mechanism to use as input, otherwise only rules 1, 6,
7, and 8 make any sense.  So perhaps a subset of the destination
address ordering mechanism would be useful without the source address
selection bits.

-Sebastien

---

From: Randall Stewart <[email-masked]>
Date: Fri, 11 Oct 2002 10:24:20 -0500

> is selected, since it can't just be the single IP address assigned to

Having implemented this for SCTP I can tell you that normally if
more than one address exists for an interface you end up picking the
first source address on the interface (assuming it is not restricted
i.e. the application has this address in its bound list and the
peer knows about the address). This works for both V6 and V4 and
scoping must be done for both V4 and V6 addresses... since we
have this little ugly thing called NAT in V4....

Generally you do the route lookup and then cache the route. The
route has a pointer to the interface and you pick up the first
address on the interface.. not complex but it can get tricky
when the first address is restricted :-0

> perform well makes life more complex.

You got that right :-0

R

-- 
Randall R. Stewart
[email-masked] 815-342-5222 (cell phone)

---

From: Keith Moore <[email-masked]>
Date: Fri, 11 Oct 2002 12:04:31 -0400

>  In any case, there is no
> order returned from name lookups.

that's okay, the idea that DNS knows which addresses are better is
a delusion anyway.

Keith

---

From: JINMEI Tatuya / 神明達哉<[email-masked]>
Date: Wed, 16 Oct 2002 14:27:03 +0900

>>>>> On Fri, 11 Oct 2002 09:54:55 +0300 (EEST), 
>>>>> Pekka Savola <[email-masked]> said:

> (possibly with some examples) should be implemented.

IMO, it is not necessarily a problem that nobody bothered.  I've not
bothered (though I've made some comments on the draft) about the
complexity because I didn't think it was a problem of the document
based on my experiences on implementing and operating with the
specification.

In general, whether or not we need a cache depends on how severe the
related performance issue is.  And the performance in this case
depends on several parameters such as the number of addresses and how
many times each selection rule applies.

Please let me explain my own environments.  My laptop usually has
quite a large number of addresses, and the property of the addresses
varies much; it has 12 (unicast) addresses as of writing this,
including the loopback, link-local, site-local, and global ones.  It
also has temporary addresses for privacy extension, and some of the
temporary addresses are often deprecated due to the short lifetimes.
(note: the number "12" will be much increased in a few days.  I
rebooted my laptop last night, so it has only one temporary address
for each autoconfigured prefix.  More and more new temporary addresses
will come.)

A few days ago, I checked statistics on the source address selection
on the laptop.  By then it had been running for 6.5 days.  According
to the statistics, about 76.8% of the pair-wise address comparisons
had been broken by the rule 2 (Prefer appropriate scope) and the rule
3 (Avoid deprecated addresses).  IMO, the rules 1-3 are quite simple
and light, and do not affect the performance much.

I don't have a quantitative result on the performance, but at least
I've never felt untolerable performance degradation that can be
considered due to the complexity of the source address selection.  I
can expect counterarguments against the analysis above; "it is just a
single, personal, and limited environment." "perhaps your laptop has a
fast CPU.  Think about poor devices." "just because you don't feel
degradation does not mean the performance issue is not a problem",
etc...  I understand all of them.  But I'd say this comes from a
*real* experiences on implementation and operation, not just from
reading the specification.  If you want to make the document include
caching, please show us how the selection rules badly affect the
performance and how the caching improves the performance degradation
*with a working implementation*.  (However, I must also say that it is
not always the case that the requirement to implement caching comes
from actual experiences with working implementations.  So I may be a
bit unfair here.)

As a result, I don't think it is necessary to require (either SHOULD
or MUST) caching in the address selection draft.  I don't oppose to
mentioning the fact that caching may improve the performance, though.

					JINMEI, Tatuya
					Communication Platform Lab.
					Corporate R&D Center, Toshiba Corp.
					[email-masked]
--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page:                      http://playground.sun.com/ipng
FTP archive:                      ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [email-masked]
--------------------------------------------------------------------

---

From: JINMEI Tatuya / 神明達哉<[email-masked]>
Date: Wed, 16 Oct 2002 16:27:20 +0900

>>>>> On Wed, 16 Oct 2002 09:49:30 +0300 (EEST), 

> The problems are likely to be seen with high use of UDP/ICMP, e.g. 
> sending a Gigabit/FastEthernet full of UDP and checking how much that 
> affects performance.

(if you're not requiring to add caching as MUST or SHOULD, I don't
care, but) such an environment will cause other performance issues as
well.  I guess you cannot convince others to make an additional
requirement just by warring about a special case.
 
BTW (this is almost an off-topic though): one of practical examples of
this is a heavily busy DNS server.  However, the source address
selection does not matter at least for a widely used implementation,
BIND.  It explicitly specifies the source address to make it sure that
the query's destination address equals to the reply's source address.

> I don't think we should require anything: if an implementation wants to do 
> it the simple way, that's fine.  But I believe there should be some more 
> statements in the Implementation Considerations section, at least.

If you're not requiring anything, I'm just fine.  I made comments here
because you actually seemed to require caching in the address
selection draft.  And, it seems to me that's why others objected to
your messages (at least to some extent) in this list.

I don't see the need for the additional consideration in the
Implementation Considerations section either, but I don't oppose to
mentioning this there.  Considering implication much is in general a
good thing.  Perhaps this is up to the author (who have not appeared
in this thread...).

					JINMEI, Tatuya

---

From: Pekka Savola <[email-masked]>
Date: Wed, 16 Oct 2002 09:49:30 +0300 (EEST)

> based on my experiences on implementing and operating with the

It surely isn't a problem that John Doe Network User is likely to face, I 
agree -- the algorithm is not _that_ complex.