RE: WG ACTION: 2 weeks to discuss [LL62] Do not space probes randomly

>The really important part is the initial randomization. It is then
>important that each successive trial be space by a sufficient delay. But
>it is also important to randomize the second delay to avoid "persistent
>bad luck", i.e. the situation where N hosts pick the same initial delay
>and then all repeat all of their NUM_PROBE packets at the same time.
>Since you need to have a random number generation ready in any case the
>implementation overhead is negligible, so why not do the right thing?

Right: The really important part is the initial randomization.

That's been in since draft-05.

There are many problems with adding successive random intervals to this 
-- misconceptions about the nature of "collisions", added implementation 
cost, lower behavioural predictability, which translates into additional 
burdens at layers above and below, but the biggest problem may be this:

The sum of random variables is LESS random than the individual variables.

Ask any statistician, or do a Google search for "central limit theorem" 
or "strong law of large numbers".

Here's a simple example that should be familiar to everyone:

If you throw one die, the numbers 1,2,3,4,5,6 are all equally likely.

If you throw two dice, and add up the results, then 7 is the most likely 
outcome. You are SIX TIMES more likely to get 7 than either 2 or 12.

When you take two uniform (flat) random distributions and add them 
together, you get a distribution that is sharply spiked in the middle. 
Add three or four, and it gets even worse.

A single uniformly distributed random delay, followed by intervals that 
are fixed, not random, avoids this collapse around a central spike:

For n hosts powered on simultaneously that become ready to probe 
simultaneously, the probability that a probe packet will be transmitted 
(by any host) in the first millisecond is n/1000. The probability that a 
probe packet will be transmitted during the second millisecond is also 
n/1000. The probability that a probe packet will be transmitted during 
any given millisecond within the first second is n/1000. The probability 
that a probe packet will be transmitted during any given millisecond 
within the second or third seconds is also n/1000.

The probability density function looks like this:


    p|
     |
     |
     |    ----------------
     |    |              |
     |    |              |
     |    |              |
     |----|----|----|----|----|----|
    -1    0    1    2    3    4    time (seconds)

In terms of minimizing peak demand on the Ethernet switch, or wireless 
spectrum, or whatever resource we are trying to protect, there is no 
better distribution than a completely flat one.

The moment you start summing uniform random distributions, you get a 
pointy distribution with a peak of exaggerated busyness in the middle. If 
we want to avoid overflowing the buffers in the Ethernet switch, a sharp 
burst of traffic is the worst thing to do. A steady uniformly distributed 
stream of traffic with no sudden peaks is what's least likely to cause 
loss.

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