Subject: Re: New issue: When to configure a LL address

From: Stuart Cheshire <[email-masked]>
Date: Wed, 12 Mar 2003 23:26:37 -0800

Philip Nye wrote:
>What Mika is rightly looking for is a sensible indication of
>when to decide that a routable address is "not working". This
>would seem easy enough at first sight but is actually quite
>difficult.

No argument there.

>Perhaps active testing of the available connectivity (ARPing the
>gateway, pinging the DHCP server etc) should only take place if
>no unicast packets from other hosts (possibly just routable
>addresses) are received for some idle time. This would mean that
>if existing connections are up and running, then the host isn't
>going to suddenly reconfigure, but on start-up or after sleep
>etc, the interface will have been idle for a while and testing
>can proceed immediately.

Those of us who have spent years thinking about this problem all seem 
eventually to come to the same conclusion:

The one-and-only truly accurate way to determine whether operation A will 
succeed is to try doing operation A, and see if it succeeds. (Those with 
a formal computer science background will recognize this as a trivial 
re-statement of the halting problem.)

Any attempt to determine whether operation A (e.g. connect to 
www.amazon.com) will succeed by first performing some different operation 
B (e.g. ping the DHCP server) is plagued by false positives and false 
negatives.

False positive: Just because the DHCP server responds doesn't mean you 
have a path all the way to www.amazon.com and back.

False negative: Just because the DHCP server doesn't respond doesn't mean 
you *don't* have a path all the way to www.amazon.com and back.

Therefore, the best and simplest test to see whether a routable address 
will work is to try it, and if it does not work, to try an alternative 
instead. Another corollary of the halting problem is that in general you 
can't prove that something won't succeed eventually, if you wait long 
enough. Therefore, you can't try the alternatives serially, waiting for 
one to fail before you try the next. You have to be able to try them in 
parallel, and take the first success you get (they don't have to start 
simultaneously, but additional attempts do have to be able to run 
concurrently in the event that the first attempt does not yield a quick 
result).

The conclusion to all this is that *if* you want to make a truly reliable 
system, then it has to be willing to have both a routable and an LL 
address at the same time, and advertise both to its peers, and its peers 
have to be willing to try both -- possibly concurrently -- in order to 
determine which, if either, will work. Note that I said "*if*" in the 
sentence above. The constraints imposed by existing deployed software may 
make this solution hard to do in practice, but if the goal were to make 
truly reliable systems, this is the way to do it.

Stuart Cheshire <[email-masked]>
 * Wizard Without Portfolio, Apple Computer, Inc.
 * www.stuartcheshire.org