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

[Simon Kelley]

Paul Smith wrote:
> 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.

Excellent! That's good work.
> 
>> 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.
>>

Only is N machines hash to the same MAC address: you can have lots of
two-way collisions in the first round and the have them all complete in
the second round providing that the first round allocations for other
hosts don't take up the A+1 slots.

>> 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 :-)) 
OK, I should think more before I post :-)

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

It's not important to preserve reproducibility in this case, once you
have collisions you've lost that anyway. What is important is that:

1) In the case that there is only one free address, the rehash should
eventually find it and terminate.

2) Even if there are no free addresses, the algorithm should terminate.

2) can be done by keeping a count of free addresses, but producing
something amenable to static analysis to prove 1) is difficult.


I'm not convinced that this is a problem once the initial hash is fixed:
the really nasty behaviour comes from collisions of three or more MAC
addresses, and that becomes much less likely if uniform distribution if
achieved.

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

Again, I don't think this is much of a problem if the initial hash
function works well, and it seems you have cracked that problem.


Cheers,

Simon.