Subject: RE: IPv6 Src/Dst Address Pairing

From: Richard Draves <[email-masked]>
Date: Mon, 9 Aug 1999 20:43:13 -0700

Jim, have you had a chance to review source address selection:
http://www.ietf.org/internet-drafts/draft-draves-ipngwg-simple-srcaddr-01.tx
t

About destination address ordering, to reiterate a point - we are talking
about just changing the order in which getipnodebyname returns addresses. So
this is just an implementation change, it involves no changes to the API or
to applications.

I think the implementation change can be quite simple and low-overhead. The
getipnodebyname() user-space library implementation can make system calls
(ioctls or whatever) to retrieve information about source addresses. To
reduce the overhead of the extra system calls, it can cache the information.
For example cache it for one second. (Getting a sufficiently precise time in
user space does not require a system call in most implementations - it's
often done by reading from memory that is mapped read-only from the kernel.)
This should reduce the added system call burden sufficiently. A few extra
system calls a second will not be measurable.

Thanks,
Rich

> -----Original Message-----
> From: Brian E Carpenter [mailto:[email-masked]]
> Sent: Monday, August 09, 1999 9:49 AM
> To: Jim Bound
> Cc: [email-masked]
> Subject: Re: IPv6 Src/Dst Address Pairing
> 
> 
> Jim,
> 
> > >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
> > 
> > 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.
> 
> 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.
> 
> > 
> > >> 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.
> > 
> > >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?
> > 
> > What do you mean call "open".  This will happen when you call
> > 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.
> > 
> > >> 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.
> > 
> > >I/O access? Why on earth? I'd expect the stack simply to know its
> > >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.
> 
> Understood, ioctl makes sense.
> > 
> > >>... 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?
> > 
> > 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.
> 
> Yes but I agree that's pretty messy. 
> 
> > >>      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
> > >
> > >Yes, for sure
> > 
> > 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.
> > 
> > >> ...and I do not believe that to be
> > >>      optimal.
> > 
> > >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?
> 
> See above, is it on the path to sending the first packet on a socket?
> 
> > 
> > >> ...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.
> > >
> > >I assumed that the stack would simply have this available
> > >anyway for other reasons.
> > 
> > It does but see my comments about stack above.
> 
> Yep
> 
> > 
> > >>  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).
> > 
> > >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.
> > 
> > I am not following your "open" word here?
> 
> I mean it's once per socket not once per packet.
>  
> > >>  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).
> > 
> > >>Yes,  a few more instructions per loop.
> > 
> > >>  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.
> > 
> > >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.
> > 
> > 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.
> 
> 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.
> 
> > 
> > >>> ...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.
> > >
> > >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.
> 
> See previous comment, the idea would be to preserve exactly that.
> 
> > 
> > >> 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.
> > 
> > >It chooses, see above.
> > 
> > That won't work.
> 
> Indeed not, I was wrong. The socket client can't know.
> 
> > 
> > >> Doing this is a very very bad idea because the engineering and
> > >> 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?
> > 
> > Please define what you mean by open.
> > 
> > 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.
> 
> > 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.
> 
> See the explanation at the top.
> 
>    Brian
> --------------------------------------------------------------------
> 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]
> --------------------------------------------------------------------
> 
--------------------------------------------------------------------
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: Jim Bound <[email-masked]>
Date: Tue, 10 Aug 1999 01:06:18 -0400

Rich,

>http://www.ietf.org/internet-drafts/draft-draves-ipngwg-simple-srcaddr-01.tx

Yes but not for this discussion per your note in the draft:

   This document does not address the more general problem of choosing
   the "best" destination address / source address pair for
   communication with another node, given a set of possible destination
  addresses and a set of possible source addresses.

I reviewed it but it needs a thorough engineering review and that I have
not done yet.  But that will get done before the Wash D.C. meeting at my
end for sure.

>this is just an implementation change, it involves no changes to the API or

Yes per Brian and my discussion it does if you use the workaround
discussed, but not as the API works today.  

>system calls a second will not be measurable.

I laid all this out in my mail to Brian and in much greater detail than
you present back to me.  Guess you did not read that mail.  But this is
exactly what I stated.  In fact there is an issue with keeping the cache
updated, and from what I know of most OS's mapping upward from kernel
space to user space is more of a trick than the reverse.  It will have
to read via an ioctl type call.

And the other issues I stated when a net utility changes the src
addresses and the cache you speak of has not been updated.  Also another
statement from your draft applies here:

   The rules specified in this document MUST NOT be construed to
   override an application or upper-layer's explicit choice of source
   address.

This blows away the entire idea to send the dst addresses in a sorted
order if the src selected by the application choice of the source
address is not the same as the one that would have been selected by the
kernel mode.

If the overhead is 2 seconds it is to much.  This has to be measured and
I will not guess what it is and then as I just told Brian when 1000
getipnodenames are called from 1000 threads on a server each of them may
have to deal with this process and that needs to be checked too.
Also don't forget the extra load, store, compare for each address coming
back from DNS this has a cost in the overhead too.

I believe your making assumptions about implementations and performance
that really need to be verified before this is even considered.  And
also the issues around applications that will not support this well by
selecting a contrary source address.  And the net utilities that 
will alter the src address during a getipnodebyname operation right
before the src address was deprecated, invalidated (valid timer
expires), or ifconfig just deletes it.  

But thats why I started this thread so implementors like you can bring
all our knowledge together to discuss it.   Which we are doing now.

thanks
/jim