Subject: RE: automatic enterprise-scale rendezvous [Re: mboned: Interest in working on multicast address rendezvous?]

From: <[email-masked]>
Date: Thu, 10 Feb 2005 15:38:26 +0200

> -----Original Message-----
> From: Marshall Eubanks [mailto:[email-masked]]
> > > >
> > > >Maybe this isn't a problem. The identifier might actually be
> > > >something like "Acme Inc, Lightsensor 678P". They can then find
> > > >eachother based on that name, and it's pretty well guaranteed
> > > >that no one else uses the same"...
> > > 
> > > Right.  The goal is to keep it dirt simple.  I think 
> unique names of 
> > > sufficient length should be more than adequate.
> > 
> > To fully automate this you could make hash from the 
> identifier and use that as a multicast group
> > address. If there is no overlap with the identifier name 
> space, then it's very unlikely that you
> > have same group addresses between different applications. 
> And no one has to manage the available
> > addresses and identifiers. And you can properly scope those 
> addresses as well.
> > 
> 
> Collisions will have to be addressed.

I was thinking more or less IPv6 while writing this, but of course this method might be applicable to IPv4, if the collisions are addressed.

> 
> Probability of collision goes as something like n (n-1) / 2N 
> (the "Birthday attack"), where n is the
> number of users, and N is the size of the address space.
> 
> Suppose that there is a /16 allocated to this :
> 
> 10 users  -> P(collision) = 7 x 10^-4
> 100 users -> P(collision) = 8 %
> 
> Even for a /8 allocated to this
> 
> 100 users  -> P(collision) = 3 x 10^-4
> 1000 users -> P(collision) = 3 %
> 
> None of these are so low that collisions are unthinkable 
> (unlike for unhacked MD5 or for SHA-1).

I was thinking about hashing the application identifier, so the number of users should be replaced with number of different application identifiers using this method. If we use 239/8 for this, then the probability of collisions is rather small e.g. running 100 different applications. If collision happens, you can still differentiate with port numbers (not the best alternative though).

> 
> So, we will need some sort of collision detection & retry if 
> this path is taken. 
> This could be done like Ethernet - say, any application 
> setting up a new hashed group address starts
> listening to that group once the hashed address is obtained 
> and also sends  
> a special packet "claiming" the group to the group, i.e. a 
> registration packet, waits 0.5 seconds
> while listening, then
> repeats this twice more. If it hears any other multicast 
> traffic on the group from another
> application during this
> 1.5 second registration process, it backs off and tries 
> another hash, say by concatenating
> "+1" to its ID (then "+2", "+3", etc.).
> 
> But then, how does an application being turned on know which 
> hashed group address to use ? (I.e.,
> how does it join a previously existing group ?)
> So, the registration packets would need to be sent regularly 
> and the application needs to listen to
> its hashed address. If the application hears nothing, it 
> could set up the group registration itself
> if appropriate for the application protocol. If it hears the 
> registration packet for its
> application, cool, it's on the right address. (There could be further
> handshaking or authentication set up by the application 
> protocol, of course.) If it hears another
> application's registration packets, then it concatenates "+1" 
> to its ID, and then repeats.
> 
> So, it could be done, but some additional complexity would 
> have to be present. (Note that this would
> look something like DNS
> to an application writer, who would hopefully send and 
> receive from something like
> "acme.com.multicast", while all of
> these details would be taken care of by a shim or by the OS).

Haven't thought enough about the details, but I think there are more simpler ways around this.

-Rami

_______________________________________________________________
user interface: http://darkwing.uoregon.edu/~llynch/mboned.html
web archive:  http://darkwing.uoregon.edu/~llynch/mboned/

---

From: "Marshall Eubanks" <[email-masked]>
Date: Thu, 10 Feb 2005 09:12:05 -0500

Dear Rami;

If you are going to put this into /239, you also have to allow for collisions with existing
(manually allocated) groups. Suppose that there are m such, then

P(collision) = n ( m + (n -1)/2 ) / N

(for n <<N; m << N), with N = 2^24. So, if m is equal in size to n, you've tripled your probability
of collision.

If we can use port numbers to distingiush between collisions, why do we need multicast address
assignment at all ? I don't think that will fly.

Basically, I take this as a problem of success - so we cannot count on either n or m remaining
small.

I agree that in IPv6, if you get a decent sized address block, collisions may be ignorable.
Suppose you had a /64  for this, and n = m = 10,000. Then
 
P(collision) = 10^-12, which is pretty small. Even n = 10 million would not be too worrisome.

Regards
Marshall

On Thu, 10 Feb 2005 15:38:26 +0200
 <[email-masked]> wrote:
> I was thinking more or less IPv6 while writing this, but of course this method might be
> applicable to IPv4, if the collisions are addressed.
> 
> > 
> I was thinking about hashing the application identifier, so the number of users should be
> replaced with number of different application identifiers using this method. If we use 239/8 for
> this, then the probability of collisions is rather small e.g. running 100 different applications.
> If collision happens, you can still differentiate with port numbers (not the best alternative
> though).
> 
> >