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

From: "Christian Huitema" <[email-masked]>
Date: Tue, 4 May 2004 16:45:33 -0700

> [LL62]
> 
> Description of Issue:		Do not space probes randomly
>
> ...
> 
> Why space probes randomly? I have still not seen any credible
> justification for this, neither credible theoretical analysis, nor
> experimental data. This text was introduced because of a
misunderstanding
> of something Christian Huitema said a year ago, and it's been in the
> document ever since. An initial random delay is justified. Further
> randomness is just voodoo.
> 
> [Erik]
> 
> This was debated frequently in the WG over the past year and in each
> case the delay was kept in the document. If you really believe that
the
> current text is not reasonable, please contact Christian and see if he
> agrees with you.  As I recall, the WG agreed with Christian, who
> supported this text and we ended with rough consensus, with you in a
> dissenting position. See LL31.

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?

-- Christian Huitema

---

From: Ralph Droms <[email-masked]>
Date: Tue, 04 May 2004 21:25:19 -0400

I agree with Christian; randomizing the successive probes may be
superstition ("voodoo" seems a little harsh), but it also is common practice
and I don't think it hurts to specify it here.

BTW, are we assuming the link layer takes care of collisions or should there
be some explicit provision for retransmitting if one of the probes suffers a
collision?

- Ralph

---

From: "Elder, Alex" <[email-masked]>
Date: Tue, 4 May 2004 21:29:26 -0700

I made this point as well in December.

I think that an initial random delay is sufficient
to avoid excessive collisions (i.e., to avoid a
storm during a network power-on event).  The subsequent
randomness is unnecessary.

					-Alex

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On
> Behalf Of Erik Guttman
> Sent: Tuesday, May 04, 2004 6:12 PM
> To: [email-masked]
> Cc: [email-masked]
> Subject: WG ACTION: 2 weeks to discuss [LL62] Do not space probes
> randomly
> 
> 
> Please post discussion of this issue to the mailing list over the 
> next two weeks
> ending May 18, 2004.  In order to accept this issued, we will 
> need a strong WG
> consensus given that this is very late in the process.
> 
> Please see http://www.drizzle.org/~aboba/ZEROCONF/issues.html 
> for a list of
> current issues and their status.
> 
> [LL62]
> 
> Submitter Name:                 Stuart Cheshire
> Submitter Email Address:        [email-masked]
> Date first submitted:           04 May 04
> Reference:			LL31
> Comment Type ['t'ech|'e'dit]:	t
> Prio ['S' Must|1 should|2 may]:	s
> Section:			2.2.1
> Rationale/Explanation:
> Lengthy Description:
> 
> [Stuart]
> 
> >    When ready to begin probing, the host should then wait 
> for a random
> >    time interval selected uniformly in the range PROBE_MIN 
> to PROBE_MAX
> >    seconds, and should then send NUM_PROBES probe packets, spaced
> >    randomly, PROBE_MIN to PROBE_MAX seconds apart.
> 
> case the delay was kept in the document. If you really 
> believe that the
> [Stuart]
> I disagee.
> I asked frequently for credible debate, but never got any, and the
> *misplaced randomness* was kept in the document. (My objection here is
> not the delay, or even the randomness; it's the pointless 
> inappropriate
> misplaced randomness.)
> 
> I did ask Christian Huitema repeatedly, in public and in 
> private, if he
> was willing to defend this statement that had been attributed 
> to him, but
> he never responded to any of the requests.
> 
> [Erik]
> 
> Requested Change:
> 
> TEXT NEEDED
>

---

From: Stuart Cheshire <[email-masked]>
Date: Thu, 6 May 2004 23:01:02 -0700

>BTW, are we assuming the link layer takes care of collisions or should
>there be some explicit provision for retransmitting if one of the probes
>suffers a collision?

The reason for having three probes is to mitigate the effects of 
undetected loss.

Most links like 802.11 and 802.3 have some low-level loss detection to 
mask some (but not all) losses.

If the link could guarantee to report or recover from *all* losses, there 
wouldn't be any undetected loss, so one probe would be enough.

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

---

From: "Elder, Alex" <[email-masked]>
Date: Fri, 7 May 2004 07:14:38 -0700

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

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

---

From: "Christian Huitema" <[email-masked]>
Date: Fri, 7 May 2004 13:50:06 -0700

Stuart makes the point that throwing dices several times in sequence
makes the sum more predictable. That is however not entirely true. The
law of big numbers predicts that the standard deviation of the average
is inversely proportional to the square root of the number of trials.
However, we are not concerned here with the value of the average, but
rather with the value of the sum. According to the law of big numbers,
the standard deviation of the sum does not decrease: it increases
proportionally to the square root of the number of trials. 

In the case of N trials between 0 and 1 (first trial) or between 0.5 and
1.5 (successive trials) the average total delay will be 0.5*(N-1)+0.5*N
= (N-1)+0.5; the average variance of this total delay will be N/4; the
standard deviation of the last trial will be sqrt(N)/2.

In the case of N trials where the first one is randomized between 0 and
1 and the later ones repeated 1 second after the 1st one, the average
total delay will be 0.5 + (N-1); the average variance of the delay will
be 1/4; the standard deviation will be 1/2.

That is, a sum of multiple random picks does indeed result in more
randomization than a single random pick. 

-- Christian Huitema

---

From: Stuart Cheshire <[email-masked]>
Date: Fri, 7 May 2004 15:57:10 -0700

>makes the sum more predictable. That is however not entirely true.

Christian, we can answer this very simply. I gave a little picture 
showing the probability density function for the simple scheme as we had 
it two years ago:

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

Can you send us a little picture showing the probability density function 
for the scheme you're proposing?

It has to be:
(a) wider (takes longer to complete), or
(b) taller (peak traffic burst is higher), or
(c) both

Which is it?

---

From: Stuart Cheshire <[email-masked]>
Date: Fri, 7 May 2004 16:04:57 -0700

>If that host just happens to be the one that
>has the same address as the one being probed by the packet that is
>lost (on reception, not on the wire) every time, then the protocol
>fails.

Complete nonsense. Of course it doesn't fail. All this posturing ignores 
the fact that WE'VE BEEN SHIPPING PRODUCTS FOR SIX YEARS. This claimed 
failure is pure invention. In the vanishingly unlikely event of repeating 
identical packet loss, the conflict is subsequently detected and resolved 
a few seconds later when subsequent ARP packets are sent, and the hosts 
then pick new addresses and immediately re-probe.

The real point is that increased randomness buys us nothing worthwhile, 
and has a cost, in the form of increased variability in total address 
acquisition time, which which impacts the layers below and above:

Below: When a switch vendor asks, "How quickly do I have to bring port on 
line to be sure I don't miss all the ARP probes?" that answer becomes 
*shorter* than it would otherwise be. This tighter constraint may make 
the switch design harder.

Above: When an application writer asks, "How long should I expect address 
acquisition to take, before concluding that there may be some unusual 
error condition?" that answer becomes *longer* than it would otherwise 
be. This longer timeout results in degraded user experience.

These costs are paid by *every* host using IPv4LL, *every* time it has to 
acquire an address.

And for what?

To protect against an event that never happens, and wouldn't really 
matter even if it did.

There's a famous old quote from Antoine de Saint-Exupery which applies to 
protocol design:

<http://dictionary.reference.com/search?q=elegant>

>A designer knows he has achieved perfection not when there is
>nothing left to add, but when there is nothing left to take away.

I'm not trying to propose any radical new things here. I thought draft-07 
was pretty good. My concerns are all the weird stuff that's appeared 
since then that no one can really justify, except with answers like, "I 
think someone else wanted it."

---

From: "Christian Huitema" <[email-masked]>
Date: Fri, 7 May 2004 17:21:05 -0700

> showing the probability density function for the simple scheme as we
had

If I understand correctly, the scheme that you describe here assumes an
initial spacing over 1 second, followed by two repetitions spaced one
second apart. You measure the probability that a packet be sent on any
given second. Since in your scheme each second is a perfect repeat of
the previous one, the scheme is indeed flat. However, having each second
be a perfect repeat of the previous one is not a very desirable
characteristic.

The scheme that I described would indeed have a different curve -- just
as wide, but taller. It will however minimize the probability of
collisions.

If you do want a scheme that is also flat but random, then you can do
the following:

	Wait R1 = random(0..1) before the 1st try;
	Wait R2 = 1+random(0..1)-R1 before the second try;
	Wait R3 = 2+random(0..1)-R2 before the third try.

It produces the same flat distribution that you find desirable, without
the correlation between the consecutive intervals.

-- Christian Huitema