[ntp:questions] NTP over redundant peer links, undetected loops
Terje Mathisen
"terje.mathisen at tmsw.no" at ntp.org
Sun Feb 15 21:55:57 UTC 2009
Joseph Gwinn wrote:
>> It depends on the size of the network. The chances of a duplicate
>> 32-bit number on a network including 65000 hosts is about 40%. The NTP
>> Pool network, which comprises at least 10^6 hosts, for example, would
>> have collision probability very close to 1.
>
> How did you compute that? Given that 2^32= ~4*10^9, it's hard to see
> how 10^6 hosts spread at random in a 10^9 codespace could achieve 100%
> collision probability.
The Birthday Paradox. Google it!
As soon as you have approx sqrt(N) samples out of universe of N values,
the chance of at least one collision breaks 50%.
As soon as you get significantly past that sqrt(N) number, i.e. 64K IP
addresses, you pass that 50% chance.
With 1e6 random 32-bit numbers the odds are so close to 100% as makes no
difference at all.
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
More information about the questions
mailing list