Subject: Re: Near-Unique Site-Local Identifier draft

From: "Matt Crawford" <[email-masked]>
Date: Thu, 01 Mar 2001 11:25:45 -0600

Take it one more step, Christian:

> You wrote:
> 
> 	The probability of a duplicate assignment somewhere is
> N^2/2^38...
> 
> which is not quite correct.  ...
> ...
> Thus
> 	(1-P) ~= e^-(N.N-1/2.X) ~= e^-(N^2/2.X)
> 	P ~= 1 - e^-(N^2/2.X) if N^3 << X^2

          ~= 1 - ( 1 - (N^2/2X) ) = (N^2)/2X

awfully close, after all your approximations, to what was given.
There's no use quibbling over a factor of 2 in these very small
numbers when, as the next paragraph says, this is not at all an
interesting question, and the real question of interest yields a
probability far far smaller.

--------------------------------------------------------------------
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: Robert Elz <[email-masked]>
Date: Mon, 01 Mar 1993 14:42:26 +0700

Date:        Thu, 01 Mar 2001 11:25:45 -0600
    From:        "Matt Crawford" <[email-masked]>
    Message-ID:  <[email-masked]>

  | awfully close, after all your approximations, to what was given.

I'm not going to start arguing mathematics with my betters, but ...

  | There's no use quibbling over a factor of 2 in these very small
  | numbers when, as the next paragraph says, this is not at all an
  | interesting question, and the real question of interest yields a
  | probability far far smaller.

most likely yes - but I realised this morning that the analysis in
that paragraph is flawed.

It isn't sufficient to not have a duplicate with anyone you communicate
with, you also need to not have a duplicate with anyone that any of
them communicate with (or they will see duplicate site-ids at
different sites).

Fortunately, no further steps out are needed, or we'd end up with a
requirement for global uniqueness.

That is, if A communicates with B, and B communicates with C and
C communicates with D, A B and C must all be different, B C and D
must all be different, but it is harmless if A == D.

I'll leave it for those who can do the probability theory to calculate
the risks of collisions for different numbers of peers/site.

But when that is done, do keep in mind that a likely potential use for
this kind of thing is for "groups" of related organisations to set up
a VPN - eg: (say) a fast food chain and all of its franchisees, and its
suppliers - and the suppliers with everyone they supply (etc).  The
numbers involved there (even instantaneously, not over an extended period)
can get quite large - 10K is probably not stretching the limits.

kre

---

From: "Paul Francis" <[email-masked]>
Date: Sat, 3 Mar 2001 10:05:33 -0800

> can get quite large - 10K is probably not stretching the limits.

Keep in mind that communicating sites can also use globally aggregateable
addresses as well.

PF