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

Stuart is right that the sum of randomness
leads to less randomness.  However Philip is
right that it doesn't really apply here, since
by definition we're dealing with a case in which
a probe resulted in a collision (i.e., two hosts
picked the same initial delay).

My contention has been that the initial random
delay is sufficient to address this collision
issue, provided the range of that delay is big
enough that the number of quantized "slots"
therein is adequate.  Going back to the dice
example, it's rolling a 12-sided die once
instead of a 6-sided die twice.

(Also, again, the purpose of this delay is
different from the purpose of the probe interval,
so should be defined independent from PROBE_MIN
and PROBE_MAX.)


					-Alex

> -----Original Message-----
> From: [email protected] [mailto:[email protected]]On
> Behalf Of Philip Nye
> Sent: Friday, May 07, 2004 4:35 AM
> To: Stuart Cheshire; [email protected]
> Subject: Re: WG ACTION: 2 weeks to discuss [LL62] Do not space probes
> randomly
> 
> 
> > From: "Stuart Cheshire" <[email protected]>
> > 
> > ...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.
> 
> 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
> 
>