Subject: Re: [Ideas] Computing collisions

From: Padma Pillay-Esnault <[email-masked]>
Date: Sun, 11 Dec 2016 09:03:09 -0800

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?
Padma

On Thu, Nov 17, 2016 at 1:48 AM, Robert Moskowitz <[email-masked]>
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
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ideas
>

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 13 Dec 2016 08:35:40 -0500

Here is some results.

On 12/11/2016 12:03 PM, Padma Pillay-Esnault wrote:
> 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.
>
> 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?
>

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 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     Here is the equation:
>
>     [email-masked] <mailto:[email-masked]>
>     <https://www.ietf.org/mailman/listinfo/ideas>
>
>

---

From: Stewart Bryant <[email-masked]>
Date: Tue, 13 Dec 2016 14:09:49 +0000

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:
>> that it is in different separate instances, this could help reduce 
>> the collision.
>>
> 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%!
>
> 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?
>
> 'seeing' the inevitable collisions, then, yes, reuse the ID space.  
> But we all know what assume also spells.
>
>
>> Padma
>>

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 13 Dec 2016 10:35:43 -0800

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.

Dino

> On Dec 13, 2016, at 5:35 AM, Robert Moskowitz <[email-masked]> wrote:
> 
> Here is some results.
> 
>> 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?
>> 
> 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 <[email-masked]> wrote:
>> Here is the equation:
>>

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 13 Dec 2016 14:12:40 -0500

> 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.

---

From: Padma Pillay-Esnault <[email-masked]>
Date: Tue, 13 Dec 2016 23:47:25 +0100

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 <[email-masked]>
wrote:

> 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.
>
> 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
>

---

From: Tom Herbert <[email-masked]>
Date: Tue, 13 Dec 2016 15:48:08 -0800

> 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

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 13 Dec 2016 20:33:23 -0800

> the map system, but in this case collisions should pretty much be

A good algorithm. Nice job.

Dino