Re: Collision free Ids: Call-ID, icid-value, Session-ID

On Mon, 2009-12-07 at 14:11 +0530, Gaurav Nangla wrote:
> Is there an approppriate algorithm like the 'Session-ID generation algorithm'
> proposed in http://tools.ietf.org/html/draft-kaplan-sip-session-id-02, for
> the Call-ID header and icid-value (P-Charging-Vector) param.
> 
> If another developer attempts to generate an id (vis-a-vis the Call-ID
> header and icid-value (P-Charging-Vector) param) using a different algorithm
> than the one I've cooked up, I'll have collisions with their ids, i.e. they
> will no longer be globally unique.

As long as the identifier you generate has at least 64 bits of
statistically random information, then the probability of one of your
identifiers colliding with *any* identifier that another system creates
(according to *any* method) is <= 2^-64.

According to the "birthday paradox", if you create a set of such
identifiers, it will have to contain 2^32 of them before there is a
reasonable chance of any collision.

The Kaplan draft proposes to use 128-bit random identifiers, which
changes those numbers to "2^-128" and "2^64", respectively.

Dale