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

Simon Kelley simon at thekelleys.org.uk
Tue Apr 13 21:39:11 BST 2010


Paul Smith wrote:
> On Tue, 2010-04-13 at 09:22 +0100, Simon Kelley wrote:
>>> 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 don't think so actually: you just add a random number on the first
> iteration through the loop, then add 1 every time after that.  You have
> to mod by the size of the result set of course, but if you know where to
> stop you're guaranteed to walk each address once (with the exception of
> the original hash result which you'll hit twice but no big deal).
> 
> "Knowing where to stop" can be accomplished by either remembering the
> first random address and stopping when you hit it again, or, as you say,
> counting how many you've tried.
> 
> I think it would be pretty straightforward to implement, looking at the
> code, but if you don't think it's worthwhile that's OK too.
> 
I understand.  A better hash function probably renders this moot, but it
can't hurt and would be simple, as you say. I'll look at adding it.


Cheers,

Simon.




More information about the Dnsmasq-discuss mailing list