Subject: RE: Comments on draft-ietf-ipv6-unique-local-addr-00.txt

From: "Chirayu Patel" <[email-masked]>
Date: Mon, 1 Sep 2003 12:40:02 +0530

> 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)

Seems incorrect.

Assuming that the pool size is "n", where n = 2^40.

As per your formula the probability of choosing two unique numbers is (n-1)/n,
and of three unique numbers is ((n-1)/n)*((n-1)/n).

As per Geoff, the probability of choosing two unique numbers is (n-1)/n, and
of three unique numbers is ((n-1)/n)*((n-2)/n). 

Since the space from which you can choose a unique number diminishes by one
with each draw. I think Geoff's formula is correct in this regards. 

CP

--------------------------------------------------------------------
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-masked]
--------------------------------------------------------------------

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 04 Sep 2003 16:44:13 +0200

below...

> with each draw. I think Geoff's formula is correct in this regards.

No. The space does not diminish at all in the local assignment method, since
every draw is totally independent of every other draw.

The space diminishes by one in the central assignment method, but it
doesn't matter since collisions are excluded by construct in that case.

   Brian

---

From: "Chirayu Patel" <[email-masked]>
Date: Thu, 4 Sep 2003 22:37:56 +0530

> every draw is totally independent of every other draw.

If n = 5, and the set of numbers is {1, 2, 3, 4, 5}

Assume that the first number chosen is "3".
The probability that the second number is unique is (5-1)/5 = 4/5, because
four unique numbers are available - {1, 2, 4, 5}

Assume that the second number chosen is "5".
The probability that the second number is also unique is (4/5)*(3/5) because
three unique numbers are available - (1, 2, 4}.

The total number space (which is 5) does not diminish with every draw.
However, the space from which *unique* (from all the previous draws, and not
only the first one) numbers are chosen *does* diminish by one with each draw.

> doesn't matter since collisions are excluded by construct in that case.

Agree.

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 05 Sep 2003 13:33:04 +0200

> only the first one) numbers are chosen *does* diminish by one with each draw.

OK, if the property of interest is the probability that two (or more) members
of a set sites have chosen the same number, I guess that is correct.

For n = 2**40, how large is that set to give one chance in a million of
a collision?

   Brian