Subject: [NSIS] [NSIS]: identifiers with global scope

From: "Geib, Ruediger" <[email-masked]>
Date: Tue, 1 Jul 2003 09:22:50 +0200

Melinda, Henning

thanks for your clarifications. I fully agree with Melinda that the issue of "identifiers with global scope" needs some more discussion. Melinda mentions that there's "some agreement that [global IDs are] needed". And "there hasn't been sufficient discussion of namespace collision avoidance and there hasn't been discussion of how to avoid a proliferation of identifiers, the latter of which is a potential problem."

What is lacking seems to be a concept how to make "identifiers with global scope" operational. There may be more "next steps of NSIS", but to me that is one which is important (I also like these identifiers). Should we solve the problem right now and go on? Or just define some "parameter" space and look for details later? In the latter case I'd prefer to have a "plan B", to be able to continue work if global IDs don't work.

Practical solutions to the global ID scheme? A 32 bit number, globally unique. Should there be a fixed "per operator" code (AS number, country code, IP address/prefix, other) and a variable one? Only a variable one? How's the latter organised (I've got no expertise and the sole statement that 32 bit coding space is sufficient to avoid collisions doesn't help to much, even if I believe it). Or did I miss something and the 32 bit number is valid only in combination with an address or the like?

Regards, Rudiger

_______________________________________________
nsis mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/nsis

---

From: Melinda Shore <[email-masked]>
Date: Tue, 01 Jul 2003 07:04:37 -0400

> Practical solutions to the global ID scheme? A 32 bit
> number, globally unique. Should there be a fixed "per
> operator" code (AS number, country code, IP
> address/prefix, other) and a variable one? Only a variable
> one? How's the latter organised (I've got no expertise and
> the sole statement that 32 bit coding space is sufficient
> to avoid collisions doesn't help to much, even if I
> believe it). Or did I miss something and the 32 bit number
> is valid only in combination with an address or the like?

A 32-bit number on its own is unfortunately insufficient to
provide reasonable protection against collisions on its own.
I think there are things we can do with high-resolution
timestamps or cryptographically, but we're going to need
more bits (potentially a lot more bits).  This is not an
uncommon problem and I expect there's been some useful work
done already; a literature search is probably a good next
step.

I should add that I am not comfortable with a scheme that
relies on a central registry.

Melinda

---

From: Henning Schulzrinne <[email-masked]>
Date: Tue, 01 Jul 2003 11:06:37 -0400

I've talked about that in depth at the interim meeting. This is a 
well-known problem, also known as the "birthday problem". I picked a 128 
bit random number as a reasonable compromise where the collision 
probability is way below the '5 nines' reliability threshold.

For example, I computed the collision probability (using bc, the 
extended-precision library on Unix) for the case of d=2^127 and 
n=10,000, i.e., 10,000 simultaneous sessions in a node, using my 
suggested identifier length of 128 bits. The collision probability is 
approximated according to Eq. (5) in 
http://mathworld.wolfram.com/BirthdayProblem.html as

.0000000000000000000000000000002938436127

Thus, this probability is far smaller than, say, the probability of 
winning the Powerball lottery (which is approximately
.00000000125). For 32 bits, the collision probability increases to
.011 (roughly, 1%), which is clearly too large. 64 bits yields 
.0000000000027102343806669673910162993043, which is also way below any 
other likely error contribution.

I think I've gone through the other plausible alternatives for defining 
identifiers in an earlier message, and they all have fatal flaws in 
practical networks. (Plausible does not include a central mechanism for 
doling out numbers....) There is one other reasonable approach that 
combines a random, locally-unique identifier with a host IP address. 
This works as long as the host is not on an RFC-1918-addressed device. 
If we assume that the number of such devices is much smaller than the 
number of nodes overall, one could pick a combination of a short random 
identifier with the IP address. This seems dicier to me since there may 
well be two very large 1918-style networks that have a lot of flows 
between them.

Henning