Subject: IPv6 Src/Dst Address Pairing

From: Jim Bound <[email-masked]>
Date: Thu, 05 Aug 1999 12:10:32 -0400

We have an issue that 6to4 in ngntrans and some believe in Multihoming
that hosts (clients) should pair Dst addresses with correct Src
addresses.

This thread should not discuss the present src address selection drafts which
do not address this specific issue.  But just a node selecting src
addresses for dst addresses passed to the transport of an IPv6
implementation and the tools and parts we must use to select the src
address and scoping.  That should have a different thread.

The issue here is DNS returns addresses.  When that happens some suggest
that the client when sending a packet the client "somewhere" have a
piece of software that takes each dst address and maps the best src
address to each dst address, and then use the best src/dst address pair
for packet transmission.

First DNS does not or cannot do that today from the DNS server for the
client so thats not an option as the DNS server does not know all the
clients source addresses.  Also the DNS server has no way of ordering
the DST addresses in any meaningful way except maybe for scoping like
site addresses if we permit them in the DNS.

So this means a client would take 1 to N DST addresses given to them
from the DNS while the client is awaiting a response from
getipnodebyname or getaddrinfo, and do this processing while the client
waits.

Here is what the ramifications are to implementations:

 1.  The client takes 1 to N addresses off the DNS set returned and
     performs an I/O access to the place in the IPv6 implementation
     to access all potential src addresses on the platform. This is
     most likely multiple reads and causes a context switch on
     the platform.  Unless one keeps an updated file to be read 
     on the client of src addresses available.  If such a file is 
     kept then it will add new code to every utility that adds or
     alters or deletes addresses on the platform and in many places
     for many implementations and I do not believe that to be 
     optimal.  I suppose an implementation could map the interface
     structures to a file via a memory mapping but it is not
     100% full proof to be guranteed.

 2.  Once the client now has those src addresses start the compare
     using longest match or some other algorithm to find the 
     best src address to match a dst address.  Then store that 
     result with some kind of weight in some datastructure.  Then
     proceed to compare the next dst address in a loop (might 
     be able to be done recursively).

 3.  During step 2 above also do the src address selection criteria
     specified in the std src address selections being proposed (e.g.
     scoping, deprecated, interface index).

 4.  Now pass back the pair to the client application?  But there
     is no API to do this today but could be done in getaddrinfo
     possibly.  But if the client does not want to send the src
     address when sending the packet then after step 3 that software
     would have to update the implementation kernel stack to know 
     to use this src address with this particular client send
     operation.

I will note doing steps 1-3 inside the kernel of implementations where
the stack resides is not an option as DNS libs are not available they 
would have to be pushed into the stack (the 1 to N) DST addresses
returned from DNS.  Then do steps 1-3 in the kernel.  But then the
client may not know what DST address was used.

Please lets discuss the entire issue.  I think there are many reasons we
have not done this already for TCP/IP and DNS address returns.  It is
just to much of a burdeon for IP Hosts and for routers even worse.

Doing this is a very very bad idea because the engineering and
performance costs are to high for the benefit.  

I have more to say but will stop here.

/jim

--------------------------------------------------------------------
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: Brian E Carpenter <[email-masked]>
Date: Thu, 05 Aug 1999 17:59:22 -0500

Jim,

> that hosts (clients) should pair Dst addresses with correct Src

The reason I'm pushing this is that I see it as a serious
operational issue once we start having multiple prefixes, which
IMHO we certainly will get sooner or later. If we don't do it
right we will end up with very non-optimal routing. This matters
just as much as host (in)efficiency so we have to find the right
tradeoff

> site addresses if we permit them in the DNS.

Absolutely. Asking DNS to do anything other than return an unordered
list of addresses would be crazy.

> getipnodebyname or getaddrinfo, and do this processing while the client

Exactly, i.e. this process is added to the generic DNS overhead
befor you get to call open(). Can you quantify this? Given that DNS 
lookups take up to seconds, how much extra overhead time are we
talking here?

>      the platform.  

I/O access? Why on earth? I'd expect the stack simply to know its
current interface/address pairings in a (small) table.

>... Unless one keeps an updated file to be read

You don't mean a disk file do you? Why not a simple data structure
in the stack?

>      for many implementations 

Yes, for sure

> ...and I do not believe that to be
>      optimal.  

Is this an overhead that matters? Is it on any critical paths?

> ...I suppose an implementation could map the interface

I assumed that the stack would simply have this available
anyway for other reasons.

>      be able to be done recursively).

Correct. This is also where you would insert heuristics and maybe
refer to some current "network weather" info to choose a path.
But it is on the path to open() not per-packet.
>      scoping, deprecated, interface index).

Yes,  a few more instructions per loop.

>      possibly.  

The idea was to pass back an ordered list of addresses from
getipnodebyname() and suggest that the upper layer uses the
first one unless it wants to override. That way the API
doesn't change one bit.

> ...But if the client does not want to send the src

Exactly, that would be another problem if changing the API.
> client may not know what DST address was used.

It chooses, see above.

> just to much of a burdeon for IP Hosts and for routers even worse.

Routers don't have to do this, except when acting as hosts themselves.

> performance costs are to high for the benefit.

I'd like numbers: what's the % overhead on a complete DNS lookup
followed by an open?

   Brian

---

From: Jim Bound <[email-masked]>
Date: Fri, 06 Aug 1999 17:04:44 -0400

Brian,

>just as much as host (in)efficiency so we have to find the right

I simply don't any issues at all that cannot be resolved without what
your asking.  

Maybe if you could articulate exactly the problems you see we can have
that discussion, as of right now I don't see why your concerned and it
could be I assume a different fix.  

>lookups take up to seconds, how much extra overhead time are we

What do you mean call "open".  This will happen when you call
getipnodebyname or getaddrinfo?

>current interface/address pairings in a (small) table.

Brian bare with me here.  That stack is in the kernel.  Any OS I have
ever worked with as an engineer divides the OS into 

   User Space  (DNS, APIs, Telnet)

   -------------------------------

   Kernel Space  (IP RFCs, IF-Datastructures etc)

What I mean't here was an "ioctl" to access the interface structures in
the kernel.   They are not sitting in user space today like many other
config parameters on a platform.  The stack also lives in kernel space
not user space, for future discussion.

>You don't mean a disk file do you? Why not a simple data structure

One option would be to keep a file or datastructure in user space to
read within the DNS application the address pairs.  As opposed to
accessing the kernel each time for each API setting this mechanism off.

>>      alters or deletes addresses on the platform and in many places

That will takes years to get fixed as note is my guess.  Just like the
way everyone ignored the IETF on storing static stuff in their
implementations for renumbering.  Which I agree is a bad thing but
engineering managers are not going to fix it unless customers ask for it
not because we ask for it in the IETF.  Likewise for src/dst addr compares.

>Is this an overhead that matters? Is it on any critical paths?

Its the overhead mostly.  Not sure what you mean by critical path in
this context?

>anyway for other reasons.

It does but see my comments about stack above.

>But it is on the path to open() not per-packet.

I am not following your "open" word here?  

>first one unless it wants to override. That way the API

Sure it does.  Right now hostent only contains a singluar ordered list
of addresses it does not denote the concept of any tuple.  
This is definitely a change to the API.
There is a workaround though.

>Exactly, that would be another problem if changing the API.

But the API does change Brian.
Also most apps let the kernel pick the src address and do not send it to
the kernel where the stack lives.

>It chooses, see above.

That won't work.

>I'd like numbers: what's the % overhead on a complete DNS lookup

Please define what you mean by open.

I will think about a % for you.

I will also add that this is a lot of software logic to put into a
critical path application set on our platforms when you have not stated
in detail the reason this is even required.  I will analyze the cost of
code per CPU cycles you go tell us why you want this in detail OK.

/jim

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 09 Aug 1999 11:49:08 -0500

Jim,

> could be I assume a different fix.

An IPv6 network is supposed to have aggregator-based addressing,
which means that we should be *much* closer than today to a simple
mapping of addresses to topology, as long as we stay "below"
the default-free part of the address hierarchy. In other words,
if you take any two IPv6 addresses and look for their longest
common prefix, the longer that common prefix is, the closer
the two hosts are in the topology. For better performance
we should (in general, not always) use topologically shorter
paths. 

That means, I believe, that given a choice of destination addresses
from a given source, we can & should optimise paths (assuming rational
routing tables) by choosing the destination address with the
longest match prefix. Given a choice of both source and destination
addresses the same is basically true. [I'm ignoring the scope issues
but they don't change the argument much. It's also a fact that
6to4 has a basic problem if we don't address this.]

This can't be free and given TLA addressing I don't see it can be done
anywhere but in the host, so as noted below there is a tradeoff here.

> getipnodebyname or getaddrinfo?

Sorry, using personal shorthand. In plain English I mean when you
send the first packet, i.e. you've also done a socket call and
then either a connect or a write. What I'm interested to 
understand is the overhead both in processor time and in real time
of running this extra algorithm as part of the total time
to send the first packet.
>    User Space  (DNS, APIs, Telnet)

Understood, ioctl makes sense.
> accessing the kernel each time for each API setting this mechanism off.

Yes but I agree that's pretty messy. 

> Its the overhead mostly.  Not sure what you mean by critical path in

See above, is it on the path to sending the first packet on a socket?

> It does but see my comments about stack above.

Yep

> I am not following your "open" word here?

I mean it's once per socket not once per packet.
 
> There is a workaround though.

I think I meant the workaround:-)

1. During getipnodebyname, the API runs the full heuristic and chooses
a src/dest pair.

2. But getipnodebyname returns exactly what it does today, a list
of dest addresses - the only difference is that it is sorted.

3. When the first packet comes down through the socket, the src
address is selected as per Rich's draft. If the app has used the
*first* dest address from the list, it will get the same src address
as in step 1.

> the kernel where the stack lives.

See previous comment, the idea would be to preserve exactly that.

> >> client may not know what DST address was used.

Indeed not, I was wrong. The socket client can't know.

> I will think about a % for you.

As noted, the correct question is what's the overhead on the
complete path from calling getipnodebyname to sending the first
packet. And what's the overhead in real time, given a typical
DNS wait.

> code per CPU cycles you go tell us why you want this in detail OK.

See the explanation at the top.

   Brian

---

From: Jim Bound <[email-masked]>
Date: Tue, 10 Aug 1999 00:45:29 -0400

Brian,

>anywhere but in the host, so as noted below there is a tradeoff here.

6to4 will work without this major fix to the hosts.  But the issue is
far beyond just 6to4.  In the interim a fix is for nodes to not use
multiple addresses for destinations in the DNS.  Then src addr selection
will work.

It certainly cannot be a MUST in 6to4 IMO.  

>to send the first packet.

OK I now see your term.  There are 3 approaches to resolve this each
with different affects to the system.

>See above, is it on the path to sending the first packet on a socket?

Yes definitely.

>I mean it's once per socket not once per packet.

Yes once per socket.  But imagine a server that opens 2K sockets and
this is small for some servers.  The cost is 2K times what-we-add-to-do
-this.  This is something I find very frustrating trying to bring
implementation performance issues to some discussions.  The performance
cost is exponential as that cost is activiated, until we all really
figure out how to use SMP and Parallel Processing better and we have not
yet in the industry though it is beginning to happen now, but not
typically in the network stack arena on hosts.

>*first* dest address from the list, it will get the same src address

Yes that is the workaround.

>See previous comment, the idea would be to preserve exactly that.

As long as part of your "open" the client does not want to hard code the
source address and some apps do that today.

>packet. And what's the overhead in real time, given a typical

Agreed.

Also all apps that exist today that select a src address this will not
work until they are ported to change.

Note this strategy also says nodes applications cannot select a src
address, and that is not going to fly IMO.

thanks
/jim

---

From: Jim Bound <[email-masked]>
Date: Tue, 10 Aug 1999 21:37:00 -0400

Hi Brian,

In the interest of doing something very cool with IPv6 that cannot be
ported to as quickly or as efficiently with IPv4 for a moment I will
concede that we need src/dst address compares for src addr selection
given the following caveats from the recent technical discussion on this
subject thread.  This is a postualte OK.  I still think we need to verify
the performance implications and provide an implementation scenario
which I have now done offline to support this.  At the end I also give
you a suggested fix for the two-way connectivity problem for 6to4 if
this was not done or is deployed before vendors can add it to IPv6
product efforts in process now for the wave of releases of IPv6 products
where we would like to support 6to4.

src/dst caveats for disucssion:
The src/dst address match algorithm would be a knob that SHOULD be
implemented by any node supporting multiple prefixes on an interface, OR
is multihomed.

The src/dst address match algorithm would be a knob not have to be 
turned on when a node does not support the two premises above 
(multiple prefixes or multihomed).

If a node exists in a DNS implementation where the server orders the
addresses returned for load balancing or some other reasons then the
node should realize using the src/dst match algorithm knob will most
likely result in the order provided by the DNS server as null and void.

If a node has an application that selects the src address (not
considering the src/dst address algorithm) then the result to the
src/dst address match algorithm behind getipnodebyname or getaddrinfo
may be voided when the packet is sent to the stack in the kernel.

Thoughts?

Fix for 6to4 Two-Way-Connectivity Issue:

The fix for 6to4, if the src/dst match was not deployed is to state in
6to4 that all nodes must support in the kernel (use better words here
but I mean in the stack where the src addr is selected), "A 6to4
implementation, if src/dst match is not supported, MUST check that a
TLA624 prefix src is used to send a packet to a TLA264 dst address.".

Also we need a health warning in 6to4 that if an application sends to a
6to4 prefix and selects its own src address it two-way-connectivity may
be lost in 6to4.  This will apply even if src/dst match is implemented.

Comments?

/jim

---

From: Robert Honore <[email-masked]>
Date: Wed, 11 Aug 1999 12:16:01 -0400

Dear Jim,

Agreed.

Agreed.

> likely result in the order provided by the DNS server as null and void.

Why should it render the order provided by the DNS Server as null and void?  The
fact that this node is querying the DNS indicates that it is preparing to
initiate a transmission (possibly creating a new connection) to the node that is
the subject of the DNS query.  That is, these addresses are all candidates to be
selected by the originating node as a destination address.  In that case, how
does choosing one of the addresses as the destination address from the list
returned by the DNS Server invalidate the order provided by the DNS server?  It
is still possible that the originating node would choose to use the candidate
address at the top of the list returned by the DNS server.

> may be voided when the packet is sent to the stack in the kernel.

This is true.

> Thoughts?

Yours sincerely,
Robert Honore.

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 11 Aug 1999 16:01:58 -0500

Jim,

I think we're getting there. If your approach can be fitted into
the post-Oslo multihoming proposal, we should be OK. That's not on my
personal to do list.

I was concerned not to have any special-case handling in hosts for
6to4; otherwise I would probably never have got interested in
this topic. But what you suggest is not so different from what
the 6to4 draft already says, and we may have to live with
that much of a special case I guess.

Thanks for listening.

   Brian

---

From: Jim Bound <[email-masked]>
Date: Thu, 12 Aug 1999 11:35:02 -0400

Hi Robert,

>Why should it render the order provided by the DNS Server as null and void?  
>The fact that this node is querying the DNS indicates that it is preparing to
>initiate a transmission (possibly creating a new connection) to the node 
>that is the subject of the DNS query.  That is, these addresses are all 
>candidates to be selected by the originating node as a destination address.  
>In that case, how does choosing one of the addresses as the destination 
>address from the list returned by the DNS Server invalidate the order 
>provided by the DNS server?  It is still possible that the originating node 
>would choose to use the candidate address at the top of the list returned 
>by the DNS server.

In this case I mention (very specific too) the DNS is sending back an
ordered list of addresses to you use in hostent with the best load
balancing information it has at this time.  So for example the query
returns:

 3ffe:134::1 (best node to use for performance via load)
 3ffe:103::4
 4ffe::2
 5ffe::6     (worst node to use for peformance via load)

But the src/dst match reorders the return after matching src addresses
in the hostent structure back to getipnodebyanme as follows:

 5ffe::6     (worst node to use for peformance via load)
 3ffe:103::4
 4ffe::2
 3ffe:134::1 (best node to use for performance via load)

What has happend is this.  We now have the optimal src/dst match going
to the kernel first as getipnodebyname will use 5ffe::6, but now the
worst dst interface to use as far as DNS load balancing was concerned when
it responded to the query.  Hence, making it null and void for sending
it anyway.

/jim

---

From: Robert Honore <[email-masked]>
Date: Thu, 12 Aug 1999 13:12:46 -0400

Dear Jim,

> it responded to the query.  Hence, making it null and void for sending

Now I see what you mean.  I was thinking that I can use the Src/Dst address
pairing algorithm to choose one of the candidate destination addresses returned
by DNS and one of my interface addresses for use in this new transmission.  I
was not necessarily considering altering the order in which the addresses were
presented by the DNS.

But then that begs the question.  If the DNS in question uses the ordering of
the addresses, to facilitate load-balancing or any other such favourable
objective, is it not also possible to bias the address selection algorithm to
take that ordering into account as well?  What I am thinking about here is there
is a (conceptual?) matrix M[i,j] of weights such that each M[i,j] represents the
degree of "goodness" of the address pair Src[i] and Dst[j].  What we can then do
is to multiply each M[i,j] by some biasing factor dependent upon the position of
the particular destination address appeared in the list returned by the DNS. 
Also, this would require that all DNS implementations apply the same meaning to
the ordering of the addresses they return.

I know that using a bias in the address selection process to take into account
the order in which the addresses were returned by the DNS does not completely
answer the question of invalidating the order returned by the DNS, but it does
not completely ignore it either.

Yours sincerely,
Robert Honore.

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 19 Aug 1999 15:00:14 -0700 (PDT)

Jim,

I don't think the performance overhead of sorting the list returned 
by getipnodebyname is significant.
In fact, we've sorted the list of IPv4 addresses returned by gethostbyname
for many years in Solaris (so that addresses on a directly attached subnet
appears first in the list).
At least in IPv4 in most cases there is only one address thus there is
no sorting needed.
And if you run a local caching resolver (or something similar - we have
something called nscd which caches for DNS, NIS, etc) the caching process
can ask the kernel for its list of IP addresses once and do the work in 
user space.

But it would be good to do some performance studies - something we never did
for our gethostbyname code.

   Erik