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

From: Stuart Cheshire <[email-masked]>
Date: Thu, 6 May 2004 22:54:56 -0700

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

---

From: "Philip Nye" <[email-masked]>
Date: Fri, 7 May 2004 09:34:35 -0000

> From: "Stuart Cheshire" <[email-masked]>
> 
> ...but the biggest problem may be this:
> 

Stuart,

This is a completely spurious statistical argument I'm afraid. If you want to use the dice example - here is the scenario:

You an I both generate a series of 4 numbers. The first value is generated by throwing a single die.

case A. Each subsequent value is generated by adding 4, 3 and 4 respectively to the preceeding value.

case B. Each subsequent value is generated by throwing the die again and adding that value to the preceeding value.

Now the probability that you are talking about is that you and I agree on AT LEAST ONE value in our series which does increase in case B. It is 1/6 for A and approximately 0.52 for B.

However that is irrelevant, the chance we need to avoid is that you and I both agree on ALL FOUR values in our series. For A this probability is 1/6 while for B it is 1/(6^4) = 1/1296.

Returning to the computer algorithm, given the fact that in many implementations a "random" delay is likely to be quantised to the inherent tick frequency of the operating system, then the probability of an initial delay in the range 0..1 second being the same for two hosts is not very low (1/100 for a typical OS and as big as 1/20 for some). Making subsequent delays also random drastically increases the chances that at least some of the probes will not clash.

What is the reason for sending four probes? In the case of only the initial delay being randomised, the extra ones merely guard against the possibility that probes may be dropped or lost. In the case of consecutive random delays this still applies but they have the added benefit of reducing the chances of all probes being lost because of timing clashes.

In conclusion. I agree with Christian that the initial wait should be in the range 0..(PROBE_MAX - PROBE_MIN) which is different from the current draft. I also agree with him that the subsequent delays should be randomised exactly as in the current draft.

Philip

---

From: Ralph Droms <[email-masked]>
Date: Fri, 07 May 2004 11:33:59 -0400

I agree with Philip's reasoning - the subsequent randomization addresses the
(admittedly small, assuming good random number generators) problem that two
hosts might pick an initial delay within a collision window of each other.
If there is no randomization of subsequent probes, there is no point in
specifying multiple probes.

- Ralph

At 09:34 AM 5/7/2004 +0000, Philip Nye wrote:
>This is a completely spurious statistical argument I'm afraid. If you want 
>to use the dice example - here is the scenario:
>
>case B. Each subsequent value is generated by throwing the die again and 
>adding that value to the preceeding value.
>
>Now the probability that you are talking about is that you and I agree on 
>AT LEAST ONE value in our series which does increase in case B. It is 1/6 
>for A and approximately 0.52 for B.
>
>However that is irrelevant, the chance we need to avoid is that you and I 
>both agree on ALL FOUR values in our series. For A this probability is 1/6 
>while for B it is 1/(6^4) = 1/1296.
>
>Returning to the computer algorithm, given the fact that in many 
>implementations a "random" delay is likely to be quantised to the inherent 
>tick frequency of the operating system, then the probability of an initial 
>delay in the range 0..1 second being the same for two hosts is not very 
>low (1/100 for a typical OS and as big as 1/20 for some). Making 
>subsequent delays also random drastically increases the chances that at 
>least some of the probes will not clash.
>
>What is the reason for sending four probes? In the case of only the 
>initial delay being randomised, the extra ones merely guard against the 
>possibility that probes may be dropped or lost. In the case of consecutive 
>random delays this still applies but they have the added benefit of 
>reducing the chances of all probes being lost because of timing clashes.
>
>In conclusion. I agree with Christian that the initial wait should be in 
>the range 0..(PROBE_MAX - PROBE_MIN) which is different from the current 
>draft. I also agree with him that the subsequent delays should be 
>randomised exactly as in the current draft.
>
>Philip