Re: [Ideas] Computing collisions

Of course there cannot be any human intervention in the selection 
process or the odds of a collision will go up hugely.

Stewart

On 13/12/2016 13:35, Robert Moskowitz 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 
>> <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>
>>
>>
>
>
>
> _______________________________________________
> Ideas mailing list
> Ideas@ietf.org
> https://www.ietf.org/mailman/listinfo/ideas