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

From: "Hancock, Robert" <[email-masked]>
Date: Thu, 3 Jul 2003 11:14:32 +0100

hi all,

There appear to be two or three different issues on the table here.

The one identifier that we know needs global scope is the session 
identifier (f/w section 4.6.2). I believe (like Henning) that uniqueness 
problems for these can be solved by providing more bits and using 
good random number generators. (Essentially I believe this for the 
same reason that I believe that cryptographic security is possible
without using one-time pads). That doesn't mean there are no issues
with the session identifier, and Hannes has written a draft recently
specifically about them (they are mainly security related).

However, the session identifier format and generation mechanism shouldn't
have much impact on the NTLP design.

The origin of this particular discussion is a different identifier,
the MESSAGE_ID in the shore draft. I have to confess to being unclear
about the role it is supposed to play, but on the assumption that
the NTLP role is just to deliver messages between adjacent NSIS nodes,
I'd be rather shocked to find
a) global scope was needed, or
b) it was visible outside the NTLP.
The message ID needs to be qualified with some message source identification,
but hopefully this shouldn't be as hard as wanting (a). The main problem would
be NAT traversal (as usual).

There is a more general (and more fundamental) point here: in discussions up
to now we have aimed for both a fairly strict NTLP/NSLP separation, and also
for a fairly strict 'locality' of NTLP operation (i.e. between adjacent peers
only). These are not just theological obsessions, they are the fundamental
mechanisms to enable us to have a protocol suite which can evolve (by adding
new signalling applications, or by improving NTLP performance, or whatever)
without needing coordinated upgrades across the whole Internet.

Remember, the main reason we are doing this work this way at all is that 
RSVP has proven impossible to extend in this way because the layering of it
is not so strict. (And this also implies - at least to me - that directly 
re-using protocol components out of 2961, which is equally un-layered, is
not likely to be the best approach. We have to re-use the ideas, of course.)

If anyone thinks this is all wrong or misguided, they could comment to 
that effect on the relevant sections of the framework draft
(currently -03 version).

see you all in Vienna.

robert h.

> -----Original Message-----
> From: Henning Schulzrinne [mailto:[email-masked]]
> Sent: Tuesday, July 01, 2003 16:07
> To: Melinda Shore
> Cc: Geib, Ruediger; [email-masked]; [email-masked]
> Subject: Re: [NSIS] Re: [NSIS]: identifiers with global scope
> 
> 
> 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
> 
> 
> Melinda Shore wrote:
> 
> >>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
> > 
> > 
> > _______________________________________________
> > nsis mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/nsis
> 
> 
> _______________________________________________
> nsis mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/nsis
> 

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

---

From: Melinda Shore <[email-masked]>
Date: Thu, 03 Jul 2003 08:00:10 -0400

MESSAGE_ID is, indeed, hop-by-hop in 2961.  It's used to
support summary refreshes.  I don't see an obvious reason
why we would need an identifier with global scope, which
isn't to say that there's not one lurking out there
somewhere (mobility people might have some thoughts on
that).  In any event it certainly shouldn't be visible
outside the NTLP.

As far as NAT, the issue with source identification isn't
NAT traversal but uniqueness.  

Melinda

---

From: Henning Schulzrinne <[email-masked]>
Date: Thu, 03 Jul 2003 16:43:32 -0400

> have much impact on the NTLP design.

We should agree on a general approach. I don't think having half a dozen 
options in one protocol to choose from adds much value for this element. 
(I'm all for toolbox approaches elsewhere.)

> be NAT traversal (as usual).

A message identifier would be used (in both drafts) for correlating 
messages in both directions, for example. However, this is much more 
similar to a sequence number, since this is strictly between two nodes. 
I'm unclear why this needs a global uniqueness scope of any sort, 
whether generated randomly or otherwise. This is similar to a 
transport-protocol sequence number, e.g., in TCP or SCTP.

Henning