ietf
[Top] [All Lists]

Re: Gen-ART Review of draft-ietf-trill-pseudonode-nickname-05

2015-09-19 11:18:18
Jari,

I think you’re referring to the “birthday problem,” i.e. in a room of 23 
randomly selected people, there’s a 50% probability that two people will have 
the same birthday (month and day, not year).

For populations of other sizes, the probability is related to the square root.  
For example, if you create three letter acronyms at random, the probability of 
collision reaches 50% somewhere just above 150 TLAs.

This math comes into play in the design of hash algorithms.  If you want to 
keep the probability of finding two messages with the same hash below, say, 
1/2^128, then you need a 256 bit hash.

Steve



On Sep 18, 2015, at 9:49 AM, Jari Arkko <jari(_dot_)arkko(_at_)piuha(_dot_)net> 
wrote:

Donald,

(Maybe this helps: I’m not actually sure why in a k-element set you order 
them based <something> mod k because that would seem to produce likely 
duplicates. Since your backup option in the case of duplicates is proper 
numeric sort, why just not do that and only that? E.g. "RBridges are sorted 
in byte string ascending order by their LAALP IDs, or if they are equal, by 
their System IDs considered as unsigned integers.” But it could also be 
that it is too early and I have not yet had enough Diet Coke…)

I believe the idea is to quasi-randomize the order. The DF election is
per VLAN and a goal is to spread the multicast traffic across the
RBridges in the active-active edge group.

It is a fine goal to randomise the order.

My only observation of the current setup is that if you randomise a
k-element group through "mod k” operation, you will likely have
some number of collisions in the result. I don’t know enough
about math to calculate the percentage. But for the sake of
argument, if k=2 it seems that the likelihood of collision is 50%.

And for every collision, your order becomes no longer random
but simply numerical order of the identifiers. In our degenerate
k=2 example it seems that in 50% of the cases you have a random
order and 50% of the cases you have numerical order. I’m sure
there would be other ways to randomise the order with less
collisions, if avoiding numerical order is important.

Jari