Subject: RE: src addr sel

From: Mauro Tortonesi <[email-masked]>
Date: Fri, 26 Jan 2001 14:46:01 -0500 (EST)

On Thu, 25 Jan 2001, Richard Draves wrote:

first of all, thank for your reply. although i am surely not an expert
kernel-level programmer, i am very interested in this argument.

> [Resending from my Hotmail account. I fear the original did not make it out 
> to the list.]

maybe because of problems with the net at your workplace, lately? ;-)
don't be offended, it happens to everyone :-(

> >i wonder if there is a working implementation of dest/src address
> >selection that is fully conformant to this spec. i'd really like to know 
> >how the implementation issues have been solved.
> 
> Yes, I have implemented it. It's pretty easy to implement. Basically when 
> getaddrinfo gets more than one address back from DNS, it uses an ioctl to 
> call down to the IPv6 stack to sort the addresses. Then all the real work is 
> in the IPv6 stack, where there is direct access to information like the 
> interfaces, addresses, routing table, etc.

is there an opensource or free-software implementation? i'd REALLY like to
take a look a it. i guess you have implemented this feature only in w2k,
haven't you?

> Another solution is to keep an invalidation counter 

this is a much more performant and interesting strategy than resorting
a list every second. maybe you can add these considerations in the next
version of your paper. 

-- 
Aequam memento rebus in arduis servare mentem...

Mauro Tortonesi			[email-masked]
Ferrara Linux User Group	http://www.ferrara.linux.it
Project6 - IPv6 for Linux	http://project6.ferrara.linux.it

--------------------------------------------------------------------
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: "Richard Draves" <[email-masked]>
Date: Thu, 25 Jan 2001 17:02:19 -0800

>    The destination address selection algorithm needs information about
>    potential source addresses. One possible implementation strategy is
>    for getipnodebyname() and getaddrinfo() to call down to the IPv6
>    network layer with a list of destination addresses, sort the list in
>    the network layer with full current knowledge of available source
>    addresses, and return the sorted list to getipnodebyname() or
>    getaddrinfo(). This is simple and gives the best results but it
>    introduces the overhead of another system call. One way to reduce
>    this overhead is to cache the sorted address list in the resolver,
>    so that subsequent calls for the same name do not need to resort the
>    list.
>  imho this is not so simple to implement. it requires a tight coupling
>between the network layer (kernel space) and the networking stuff of the C 
>library (user space), and a very careful design of the caching
>policy (especially if we have to handle temporary, preferred and
>deprecated addresses).

It is in fact simple to implement. One simple strategy for having the 
resolver cache a sorted list is to resort the list if it was last sorted 
more than some short time ago, like a second.

>    Another implementation strategy is to call down to the network layer
>    to retrieve source address information and then sort the list of
>    addresses directly in the context of getipnodebyname() or
>    getaddrinfo(). To reduce overhead in this approach, the source
>    address information can be cached, amortizing the overhead of
>    retrieving it across multiple calls to getipnodebyname() and
>    getaddrinfo().
>
>this is a simpler solution, as it requires only a minor interaction
>between kernel- and user-space. but the complexity of the caching
>algorithm is not reduced, and this implementation introduces another
>problem:

I disagree, I think this is a much more complicated implementation strategy 
because you have to pull lots of information into the user space context to 
do the sort there. But to each his own: the draft is explicitly not 
mandating an implementation strategy. It is trying to point out some 
possibilities.

>    In this approach, the implementation may not have
>    knowledge of the outgoing interface for each destination, so it MAY
>    use a looser definition of the candidate set during destination
>    address ordering.
>
>and this is surely a negative point.

Yes, another reason I didn't choose this implementation strategy myself.

>moreover, there are lots of other problems to be solved. in particular:
>
>  1) performance. it cannot be allowed by using cached data, as caching
>     is very difficult to do. and the spec says:
>
>    In any case, if the implementation uses cached and possibly stale
>    information in its implementation of destination address selection,
>    or if the ordering of a cached list of destination addresses is
>    possibly stale, then it should ensure that the destination address
>    ordering returned to the application is no more than one second out
>    of date. For example, an implementation might make a system call to
>    check if any routing table entries or source address assignments
>    that might affect these algorithms have changed.
>
>     because cached data is valid for no more than 1 sec., and the
>     implementation of a correct caching algorithm is VERY difficult,     
>caching is more a problem than a solution.

There are many ways to implement this. One solution is just to resort if 
more than one second has gone by, in other words assume that any information 
more than one second old is stale. Another solution is to keep an 
invalidation counter in the stack. The counter is incremented any time there 
is change in relevant state, like the routing table or address assignments. 
Then when you cache information dependent on that state, you save a copy of 
the counter. You can later check the cached counter value against the 
current value to see if the cached computation result is stale.

>  2) handling the policy table. it should be kept in kernel-space, but     
>designing a simple and safe way to edit it is surely not a trivial
>     task.

It was a trivial task. The policy table is much like a routing table and I 
based the ioctls that retrieve/update the policy table on the routing table 
ioctls.

Thanks,
Rich

_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com