Re: [Ideas] Computing collisions

[Padma Pillay-Esnault <[e-mail]>]

It is interesting to see that with an intelligent spread we actually can
reduce the collision probability significantly.
Will add some text regarding this in the next iteration of the problem
statement.

Padma


On Tue, Dec 13, 2016 at 2:35 PM, Robert Moskowitz <[e-mail]>
wrote:

> 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 <
> [e-mail]> 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
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/ideas
>>
>
>
>