LL31 Probing Interval

Right now, the document says:

   When ready to begin probing, the host should then wait
   for a random time interval selected uniformly in the range
   zero to one seconds, and should then send three probe
   packets, spaced randomly, zero to one seconds apart.

This means that, technically, if a device waits zero seconds, sends three 
ARP Probes spaced zero seconds apart, and then immediately begins using 
the address, that's legal.

It is clear that after waiting a total of zero seconds the host has NOT 
established to the required degree of certainty that the address is not 
already in use.

It may be *unlikely* for a properly implemented device to do this, but if 
you use a packet sniffer and observe a device do this, you can't say 
categorically that the device does not implement the specification 
properly. Indeed, every device that were to implement this random 
interval between probes would sometimes exhibit extremely short probing 
times.

I see that this text was offered by Christian Huitema, and the random 
spacing was proposed to "avoid synchronization effects".

This is, I believe, a misapplication of a common design principle. The 
common design principle that's being misapplied is that in a continuing 
ongoing periodic process on multiple machines, you should take care to 
avoid synchronization. The canonical example of this that's taught to 
computer science students is the synchronization of periodic DECnet 
routing messages. The canonical research paper on the subject is 
"Synchronization of Periodic Routing Messages" by Sally Floyd and Van 
Jacobson (do a Google search for "DECnet synchronization").

The problem in DECnet was that the device would do its work, then sleep 
for 120 seconds, then repeat. If it took time epsilon to do its work, 
this meant that the time between packets was epsilon+120seconds. Time 
epsilon was influenced by how many pages faults the process took, which 
was influenced by how long it was since it last ran, which was influenced 
by how long it was since it last received a packet from a peer. Devices 
that had just recently received a packet would tend to run faster and 
'catch up' with the device ahead; devices that had not recently received 
a packet would tend to run slower and let the others 'catch up' with 
them. It's not hard to see how over a period of time this would result in 
all the packets becoming synchronized into a monster packet blast every 
two minutes. The solution is to use a drift-free time model, so that 
execution time epsilon does not influence the overall time interval, and 
to introduce just the right amount of randomness to make sure the devices 
de-correlate and stay de-correlated.

This is all very interesting, but what has it got to do with link-local 
devices sending three probes? ABSOLUTELY NOTHING.

The document should simply say:

   When ready to begin probing, the host should then wait for a random
   time interval selected uniformly in the range zero to one seconds,
   and should then send three probe packets spaced one second apart.

Christian Huitema is a very well-known and widely respected academic in 
computer science; I'll hope he'll agree in retrospect that applying the 
DECnet de-synchronization principle to three probe packets is a mistake, 
and withdraw the suggestion.

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