Re: [dhcwg] Load Balancing for DHCPv6

"Bernie Volz (volz)" <volz@cisco.com> Thu, 20 September 2012 12:05 UTC

Return-Path: <volz@cisco.com>
X-Original-To: dhcwg@ietfa.amsl.com
Delivered-To: dhcwg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BFB3A21F8686 for <dhcwg@ietfa.amsl.com>; Thu, 20 Sep 2012 05:05:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.57
X-Spam-Level:
X-Spam-Status: No, score=-9.57 tagged_above=-999 required=5 tests=[AWL=-0.771, BAYES_00=-2.599, J_CHICKENPOX_31=0.6, J_CHICKENPOX_33=0.6, J_CHICKENPOX_73=0.6, RCVD_IN_DNSWL_HI=-8]
Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5292v6Ah9Z6F for <dhcwg@ietfa.amsl.com>; Thu, 20 Sep 2012 05:05:17 -0700 (PDT)
Received: from rcdn-iport-7.cisco.com (rcdn-iport-7.cisco.com [173.37.86.78]) by ietfa.amsl.com (Postfix) with ESMTP id AB05421F867E for <dhcwg@ietf.org>; Thu, 20 Sep 2012 05:05:17 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=3198; q=dns/txt; s=iport; t=1348142717; x=1349352317; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=gfafvf+T2x9FG5ED8kkgQpEerl7ZSQUaT2GHgtIlud4=; b=aw0q5l52Wxi1rGJvxAfA+lntlgi5kc5gfOUoRlJpxlJucvDg6eaXUPqh Sey6Es3XqAQh15kt3WhC3aDZeYgzh54uQqfsr/YZdDgHV5RrhM+CqGR+q RkxHWZpPZJlrPFFhNh9L5rnzFFKV+V/QpkfCm+N1DzcxO9pH6zjOgTz1F s=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av8EACcFW1CtJV2b/2dsb2JhbABCA70TgQiCIAEBAQMBAQEBDwEnNAsFCwIBCA4KHhAhBgslAgQOBR4Eh08DCQYLmXSWKw2JTwSKOmIUgwmCRGADlA+BVYsXgyGBaYJmgVo
X-IronPort-AV: E=Sophos;i="4.80,453,1344211200"; d="scan'208";a="123531785"
Received: from rcdn-core-4.cisco.com ([173.37.93.155]) by rcdn-iport-7.cisco.com with ESMTP; 20 Sep 2012 12:05:17 +0000
Received: from xhc-aln-x15.cisco.com (xhc-aln-x15.cisco.com [173.36.12.89]) by rcdn-core-4.cisco.com (8.14.5/8.14.5) with ESMTP id q8KC5HCl024251 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Thu, 20 Sep 2012 12:05:17 GMT
Received: from xmb-rcd-x04.cisco.com ([169.254.8.159]) by xhc-aln-x15.cisco.com ([173.36.12.89]) with mapi id 14.02.0318.001; Thu, 20 Sep 2012 07:05:17 -0500
From: "Bernie Volz (volz)" <volz@cisco.com>
To: Donald Eastlake <d3e3e3@gmail.com>
Thread-Topic: [dhcwg] Load Balancing for DHCPv6
Thread-Index: AQHNlvCUaJ+khP2NkUiXQs2wUqwOeJeTIoPt
Date: Thu, 20 Sep 2012 12:05:16 +0000
Message-ID: <1BB5EDFF-BBA9-4335-BE55-058FACEE30EB@cisco.com>
References: <CAL10_Bqa4ftiVhyyf0ezwKR7mzAEOLNi_K3EJFPFUzPnz7QGPw@mail.gmail.com> <489D13FBFA9B3E41812EA89F188F018E0F4F3093@xmb-rcd-x04.cisco.com> <CAL10_Br=OcWZuar1fDOopevTy_W-3g9TsYqo61rOWm4tKkuYgg@mail.gmail.com> <2D09D61DDFA73D4C884805CC7865E61118003F@GAALPA1MSGUSR9N.ITServices.sbc.com> <CAL10_BpXdx03WfV1PeMKg1zYc1dAFKe1CDNdrcNf45+_EVCBPg@mail.gmail.com> <CDDB9016-BE11-489A-9361-0172D96A464C@nominum.com> <CAOpJ=k2CJS=FuUvFwOq=s2m871_qfo=xROsW=fx0E48w2wxAqQ@mail.gmail.com> <CAL10_BoLsdppYKNSfHheYrZg+SfaggoynQf2X11HEdy=ELFUiQ@mail.gmail.com> <5049C317.7090603@gmail.com> <94FA926F-2432-4AE7-BC20-AE7458AB40D9@cisco.com> <CAF4+nEHqRFHbz9qfQuOqpLCNeZqkT=+f53_eCboECfWX8QCt6A@mail.gmail.com> <71F17433-B2D9-4366-9B32-F0E4D294EDB5@nominum.com> <CAF4+nEE6pbmO_ss+3UEpRG1kh2YD20P2KD4CFQ7LwoRZ6gyxsg@mail.gmail.com> <A563FEA0-0A26-431D-BDAA-AD897F691754@nominum.com>, <CAF4+nEFqLW6p1wE9BWE6c2CqGDwzUQTYom9K4icV1_NjM-nTXg@mail.gmail.com>
In-Reply-To: <CAF4+nEFqLW6p1wE9BWE6c2CqGDwzUQTYom9K4icV1_NjM-nTXg@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-tm-as-product-ver: SMEX-10.2.0.1135-7.000.1014-19194.004
x-tm-as-result: No--52.235900-8.000000-31
x-tm-as-user-approved-sender: No
x-tm-as-user-blocked-sender: No
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Cc: "dhcwg@ietf.org" <dhcwg@ietf.org>, Ted Lemon <Ted.Lemon@nominum.com>
Subject: Re: [dhcwg] Load Balancing for DHCPv6
X-BeenThere: dhcwg@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: <dhcwg.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/dhcwg>, <mailto:dhcwg-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/dhcwg>
List-Post: <mailto:dhcwg@ietf.org>
List-Help: <mailto:dhcwg-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/dhcwg>, <mailto:dhcwg-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 20 Sep 2012 12:05:18 -0000

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" <d3e3e3@gmail.com> 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   +1-508-333-2270 (cell)
> 155 Beaver Street, Milford, MA 01757 USA
> d3e3e3@gmail.com
> 
> 
> On Fri, Sep 7, 2012 at 6:29 PM, Ted Lemon <Ted.Lemon@nominum.com> wrote:
>> On Sep 7, 2012, at 5:37 PM, Donald Eastlake <d3e3e3@gmail.com> 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.
>> 
> _______________________________________________
> dhcwg mailing list
> dhcwg@ietf.org
> https://www.ietf.org/mailman/listinfo/dhcwg