Subject: RE: src addr sel (was: A6 unreliability) (fwd)

From: "Richard Draves" <[email-masked]>
Date: Wed, 24 Jan 2001 13:06:24 -0800

> 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.

>    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.

>    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
--------------------------------------------------------------------
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]
--------------------------------------------------------------------