Geoff's initial comment included the classic birthday paradox formula,
which would indeed apply if we were to use the randomly generated
addresses as global site identifiers valid across the Internet. The
practical consequence is that we should be extremely clear about the
usage limitation: randomly assigned addresses should in no way be used
as site identifiers. This should not even be left for further study, it
is just wrong.
The usage that is actually envisaged is more limited: an identifier that
provides disambiguation in a limited environment, normally a single
site, possibly a small number of sites directly linked by VPN-like
relations. In that scenario, the collisions that matter are those that
occur within this "working set" of connected sites. The probability of
such a collision is determined by the probability of collision "x"
between two identifiers (x = 2^-40 in our example) and by the size "W"
of the working set. The probability that single site does not collide
with any member of a working set is:
P(collision in a set of size W) = 1 - (1-x)^(W-1)
There will be a large number of these working sets, probably as many as
there are sites -- each site will participate in average to W sets. The
probability that a given site observes a collision in one of its working
sets will be:
P(collision in one of W sets) = 1 - (1-x)^(W*(W-1))
If we have N sites, the probability of observing one collision on the
Internet will be:
P(collision in N sites with W sets) = 1 - (1-x)^(N*W*(W-1))
Given x=2^-40, the number N for which this probability equals .5 varies
with W as:
W N
50 311070769
100 76982160
200 19148829
500 3054603
1000 762886
2000 190626
5000 30491
10000 7622
Bottom line: using the random allocation in large working sets is a bad
idea. If people want to do that, they should register a unique
allocation instead.
One possible way to improve the situation is to have a provision for
small sites, in which we use a 56 bits random number to identify a link,
rather than a 40 bits random number identifying a site.
-- Christian Huitema
--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page: http://playground.sun.com/ipng
FTP archive: ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [EMAIL PROTECTED]
--------------------------------------------------------------------
