Re: [Ideas] Computing collisions

[Tom Herbert <[e-mail]>]

On Tue, Dec 13, 2016 at 10:35 AM, Dino Farinacci <[e-mail]> 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 sounds a lot like what we do in ILA. The identifier is split into
a registry number and identifier within that. In our case each host is
assigned a unique 24 bit registry number, and then each host can
independently create identifiers. For the latter we just take a
timestamp. Assuming a rate of 100 identifiers per second being
allocated we have 21.8 years before wraparound (described appendix B
of ILA draft). We'll also check when the identifier is registered with
the map system, but in this case collisions should pretty much be
nonexistent.

Tom

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