Re: [dhcwg] Load Balancing for DHCPv6

[Andre Kostur <[e-mail]>]

Whups, yep.  Changed that to a 1, and no significant different in the
stddev.  Both still in that 95 - 105 range.

I'm also of the opinion that Pearson is the way to go.  Seems to give
a pretty good spread of values, it's already documented in RFC
(complete with implementation), and any servers or relays that may
have already been doing load balancing for v4 will already have this
algorithm implemented.


On Fri, Sep 21, 2012 at 10:04 AM, Bernie Volz (volz) <[e-mail]> wrote:
> Thanks Andre.
>
> While it would make no difference, it is always a mystery whether DUID will use a hardware type of 1 or 6. Per http://www.iana.org/assignments/arp-parameters/arp-parameters.xml, type 1 is for Ethernet whereas 6 is for IEEE 802.3.
>
> It may well be for a more limited data set (i.e. ASCII strings), FNV1a could be better. I think Pearson was optimized for binary data.
>
> My feeling is we should stick with Pearson and use the entire DUID (no length limit).
>
> - Bernie
>
> -----Original Message-----
> From: Andre Kostur [mailto:[e-mail]]
> Sent: Friday, September 21, 2012 12:44 PM
> To: Bernie Volz (volz)
> Cc: Donald Eastlake; [e-mail]; Ted Lemon
> Subject: Re: [dhcwg] Load Balancing for DHCPv6
>
> I've crafted up a test rig for Pearson vs. FNV1a   (Pearson code from
> the RFC, FNV1a from
> http://isthe.com/chongo/tech/comp/fnv/#FNV-reference-source, with the XOR-folding at http://www.isthe.com/chongo/tech/comp/fnv/index.html#xor-fold).
>
> I generated my DUIDs as a set of DUID-LLs (so the first four bytes are 00, 03, 00, 06).  The next three were taken randomly from IEEE's list of registered OUIs.  The remaining three are rand().
>
> Running those through both Pearson and FNV1a 5 times each (on a set of
> 2,560,000 DUID-LLs) resulted in:
>
> Pearson:
> Min: 9637 - 9750, Max: 10220 - 10318, StdDev: 92.91 - 102.28
>
> FNV1a:
> Min: 9691 - 9754, Max: 10221 - 10379, Stdev: 93.27 - 107.66
>
>
> This seems to suggest that Pearson is better than FNV1a over DUID-LLs.
>
>
> On Thu, Sep 20, 2012 at 5:05 AM, Bernie Volz (volz) <[e-mail]> wrote:
>> Bad test - This is a very limited character set.
>>
>> The data usually used for dhcp is binary data.
>>
>> Sent from my iPad
>>
>> On Sep 20, 2012, at 1:27 AM, "Donald Eastlake" <[e-mail]> wrote:
>>
>>> Well, I have some more statistics. One my co-authors on the draft
>>> whipped up some code that I then extended. The data hashed consisted
>>> of 2,560,000 strings calculated as follows:
>>>        #define RUN 10000
>>>        for(i = 0; i < 256*RUN; ++i)
>>> {
>>>                sprintf(str, "%08d^^%08d", i, i);
>>>                {do hashes, etc}
>>> }
>>>
>>> Each string was hashed with Pearson and with 32-bit FNV-1a. Three
>>> arrays of 256 counters were incremented based on the Pearson hash,
>>> based on the bottom byte of the 32-bit FNV after one 16-bit fold (
>>> hash2 = (hash&0xffff) ^ (hash >> 16) ), and based on the bottom byte
>>> of the 32-bit FNV after an additional 8-bit fold (hash3 =
>>> (hash2&0xff) ^ (hash2 >> 8); the equivalent of xor'ing all four bytes together).
>>> The expected number of hits on each bucket with perfect hashing would
>>> be 10,000. Here are the minimum and maximum number of hits and the
>>> standard deviation:
>>>
>>> Pearson: min=9678 max=19938 std-dev=630.72
>>> FNV-32 1-fold: min=9699 max=10331 std-dev=103.06
>>> FNV-32 2-folds: min=9662 max=10247 std-dev=90.78
>>>
>>> So you now have Brian Carpenter's results, showing FNV to be much
>>> better than a variety of other methods, but not Pearson, on fairly
>>> realistic data. And you have these results showing FNV to be much
>>> better than Pearson on somewhat unrealistic data. ...
>>>
>>> Thanks,
>>> Donald
>>> =============================
>>> Donald E. Eastlake 3rd   [phone] (cell)
>>> 155 Beaver Street, Milford, MA 01757 USA [e-mail]
>>>
>>>
>>> On Fri, Sep 7, 2012 at 6:29 PM, Ted Lemon <[e-mail]> wrote:
>>>> On Sep 7, 2012, at 5:37 PM, Donald Eastlake <[e-mail]> wrote:
>>>>> FNV takes a little more effort than Pearson. It also has a smaller
>>>>> footprint in memory. And I believe it will produce statistically
>>>>> better results. What are the relative weights of these or other
>>>>> factors in this case?
>>>>
>>>> Unfortunately, as far as I can tell neither of the studies you cite compares FNV to Pearson, although the results from Brian Carpenter's study are certainly pretty impressive.    I think more work is worse, smaller footprint probably doesn't matter (this algorithm is being run in DHCP servers, which typically aren't seriously memory-constrained), and statistically better results only matter if it's a pretty big difference, so it's frustrating that we don't have a comparison to the existing algorithm.
>>>>
>>>> To me, the biggest win of using FNV would be if there were an RFC to refer to, but it looks like this is not quite there yet.   So my conclusion is that I certainly don't oppose using FNV instead of Pearson, but I don't see a strong reason to support it either.
>>>>
>
> --
> Andre Kostur

-- 
Andre Kostur