Re: [Ideas] Computing collisions

[Robert Moskowitz <[e-mail]>]

On 12/13/2016 01:35 PM, Dino Farinacci wrote:
> In LISP, an xTR registers with a 128-bit xTR-ID. This is not the EID. So we could have an xTR register with a random EID it chooses. Then the map-server determines it is a collision because another xTR-ID has registered with that same EID. The map-server could select a random EID and check locally if it collides. If it doesn’t, then the xTR registers with a new EID (and makes appropriate interface address assignments locally).
>
> Note the draft-farinacci-lisp-eid-anonymity-01 specs that ephemeral-EIDs can be used. So when an xTR decided to choose a random IPv6 address as an EID and registers. It can ask the map-server if it collides. Today, the map-server Acks Map-Register messages, but it could Nak and say “go get a new random ephemeral-EID”. I like this approach better because the allocation happens at the sites within their own address prefix range and gives you some obfuscation at the same time.
>
> If people thing the second approach makes sense, I can spec out in the above draft how Map-Servers could NAK when there are collisions. Please comment.

That is basically what I do with Hierarchical HITs.  The device 
registers its HIT with the owner of the Hierarchy point.  The owner 
(HDA) then either accepts the HIT or rejects with a 'Hierarchical HIT 
Already Registered' message  (see sec 6.4).

Since it might be the case that device is registering, there is a 
difference between duplicate HI (Either a register, so something bad is 
happening to make it possible for two devices to select the same HI) and 
HIT collision with different HI.

Note that it is possible for a device to register one HI to two 
different HDAs.  Due to the algorithm for HIT generation, these will not 
only have different HDA values, but the hash component will be 
different.  However a device may well choose different HIs for different 
registrations for privacy reasons.


>
> Dino
>
>> On Dec 13, 2016, at 5:35 AM, 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
>>>
>> _______________________________________________
>> Ideas mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/ideas