[Dnsmasq-discuss] Why is dnsmasq handing out the same IP to different MACs?

[Paul Smith]

On Mon, 2010-04-12 at 17:47 -0400, Paul Smith wrote:
> > If you can fiddle with that, and get something which works better, I'd
> > be interested to see the patch. 
> 
> I'll poke at it although obviously what works for my environment might
> not be so useful to others, with different MAC distributions.

I looked around at straightforward hashing algorithms, especially
looking for ones that were rumored to give good dispersion for similar
values.  FNV gave a great result, but then I realized I had used the
offset basis instead of the prime in the multiplication and after I
fixed it, it wasn't so great anymore :-p :-)

But, on my test of 192 MACs, the sdbm hash function worked perfectly: I
got 192 unique IP address offsets.  Funnily enough of all the hash
functions this one is closest in concept to your current one... but it
uses shifts of 6 bits and 16 bits (plus a subtract) instead of 8 and 16.

I'll send a patch later tonight so you can see it.

> I do wonder whether we can improve things on the NAK end, though: it
> seems like it would be nice to improve the failure case so that it
> wasn't pathological: first round we get N collisions with 1 success and
> N-1 failures; the failures all add one to their IP addresses and we get
> N-1 collisions on the second round, etc., which basically means we'll
> have to run N rounds of NAK resolution before everyone has their own IP.
> 
> Couldn't we add a random number to this on NAK, or maybe add the least
> significant octet in the MAC (+1 in case the value is 0 :-)) instead of
> adding 1, or something like that, so we are less likely to collide?

I really think solving this problem is even more important though: a
hash is a hash and you'll likely get some collisions.  If we could find
a way to obtain a better result here I'd be a lot happier.  A single
retry is one thing: N retries for an N-collision result is quite
another.

Is it important to preserve reproducibility in this case?  Would a
random number be OK?  In order to ensure good behavior I recommend that
we add a random number then, if that's taken, start adding 1 until we
find a free spot.

The other option is to remember IPs handed out during DISCOVER/OFFER to
avoid duplicates.  That would 100% solve the problem and guarantee no
duplicates at all, but at the cost of complexity in the server.