Subject: LL31 Probing Interval

From: Stuart Cheshire <[email-masked]>
Date: Wed, 4 Jun 2003 18:55:11 -0700

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-masked]>
 * Wizard Without Portfolio, Apple Computer, Inc.
 * www.stuartcheshire.org

---

From: Robert Elz <[email-masked]>
Date: Thu, 05 Jun 2003 17:16:19 +0700

Date:        Wed, 4 Jun 2003 18:55:11 -0700
    From:        Stuart Cheshire <[email-masked]>
    Message-ID:  <[email-masked]>

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

I actually doubt that that one was in anyone's mind here - as you
say, for this, you need a continual stream of packets over time,
and that doesn't exist here.

Rather, I suspect the intent was to avoid having situations arise
where (by whatever chance) several hosts all probe at the same time,
and then continue to all retry at identical times because the
specification allows no method of escape.

The problem is that there can be sudden packet bursts, which can
overwhelm receivers (too many too quickly to receive) - so some
receivers never see some of the probes, and because after the
first attempt, everything repeats identically for each new attempt,
the same nodes keep on not seeing the same probes on every attempt.
That means that the probing isn't really being done at all.
Randomising the retry prevents this kind of synhcronisation from
happening, and makes it very likely that every node will have a
chance to see every other nodes probes, at least for some of the
attempts.

You're correct that as written, the text allows for a host waiting
for 0 time - but if it was observed doing that, I think one could
conclude with a high degree of certainty, that it was in fact broken.
The chances of any random number generator over the interval [0,1]
always generating 0 (or generating continuous 0's over any sample
more than a few) are so small that if that is observed, you can
reasonably claim something is broken (either no random numbers are
being used at all, or the random number generator is defective).

I wouldn't object to fixing the text, but I'd do so by requiring
a wait for a reasonable time for a reply, before probing again.
So, rather than "then send three probe packets, spaced randomly,
zero to one seconds apart" perhaps "then send three probe packets,
spaced randomly 0.1 to one seconds apart".

kre