Re: [Ideas] Computing collisions

Here is some results.

On 12/11/2016 12:03 PM, Padma Pillay-Esnault wrote:
> Hello Bob
>
> Thanks for sending this formula.
>
> If we assume that the population is not necessarily a flat space and 
> that it is in different separate instances, this could help reduce the 
> collision.
>
> Per the ideas problem statement draft, we have discussed about the 
> different types of devices and whether we could have some policy on 
> what they can do. Eg. a camera should not be shopping for clothes or 
> access bank accounts .... wouldn't it make sense to put them in 
> different instances with different access policies?
>
> What are your thoughts on this?

Let's work with a 24 bit ID space which is a population of 16,777,216

Let's then assume a random distribution of 2^14 (16,384) devices. This 
is a 99.97% probablity of a collision.  A sure thing.

Now let's assume that there are 256 (2^8) classes of devices and that 
the population is evenly divided.  That is 64 devices per class.  We now 
have reduced our ID space to 16 bits (65,536), but the probablity of a 
collision with only 64 devices is 3.08%!

But if the division is not equal between the classes and one class has 
512 devices the probablity jumps up to 84.67%; again an almost sure thing.

So we can see from this little exercise that dividing our ID space into 
groupings can actually reduce the collision risk.  Two caveats are clear 
though.  How many classes to use (you can see my effort at this in 
draft-moskowitz-hierarchical-hip) and what if one class out classes all 
the rest?

You still need to manage collisions.  You just may be telling fewer 
losers to select a new ID.

Now if instead you are talking about reusing your ID space on the 
assumption that these devices are NEVER interacting and thus never 
'seeing' the inevitable collisions, then, yes, reuse the ID space. But 
we all know what assume also spells.

> Padma
>
> On Thu, Nov 17, 2016 at 1:48 AM, Robert Moskowitz 
> <rgm-ietf@htt-consult.com <mailto:rgm-ietf@htt-consult.com>> wrote:
>
>     Here is the equation:
>
>     probability of collision = 1 - e^{-k^2/(2n)}
>
>     Where n is your max population size (e.g. 2^64)
>
>     and k is your deployed population (e.g. 7B)
>
>     Bob
>
>     _______________________________________________
>     Ideas mailing list
>     Ideas@ietf.org <mailto:Ideas@ietf.org>
>     https://www.ietf.org/mailman/listinfo/ideas
>     <https://www.ietf.org/mailman/listinfo/ideas>
>
>