From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lb0-x234.google.com (mail-lb0-x234.google.com [IPv6:2a00:1450:4010:c04::234]) by lists.bufferbloat.net (Postfix) with ESMTPS id C55853B2D2 for ; Fri, 8 Jan 2016 16:16:02 -0500 (EST) Received: by mail-lb0-x234.google.com with SMTP id oh2so231331796lbb.3 for ; Fri, 08 Jan 2016 13:16:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=aLeS5tCvXWAIP2co2GGuaWqcTg6omy2XaAgBjkm1SbU=; b=qNk+H9OOaQP0lRiKOdyotMPfUDUTJuS4IpvWXm/QSoURmEMHeqk/wRmAXJ9u04TVx7 8PxQar+tDNotQ1L7XELAacLYP7H5qHcL2vAz7fjt5JjpMnceXoft3dKYWS2EeV9oGmFf p/TnGrmq+T5592vdZ6o0gVZ4ls2BzAgs3cAo5Z4Yf1yVJDg9ylUIUUp3NvQ9pW0csCbn /o21VdBvax/mEFwlC8rbk1UNZtsDNdE0FzowRUNKkAnVGiB0JVBRMJe623G57GJeLoE0 uKXoIk+2/Yv2DjUdL8vAmHW/EGDA/I/jEDrDpOXh47gcTsOI6WqRSZZV2o4u2rFDgrNY Hayw== X-Received: by 10.112.16.231 with SMTP id j7mr21376911lbd.72.1452287760875; Fri, 08 Jan 2016 13:16:00 -0800 (PST) Received: from bass.home.chromatix.fi (37-33-99-74.bb.dnainternet.fi. [37.33.99.74]) by smtp.gmail.com with ESMTPSA id zu7sm8839000lbb.36.2016.01.08.13.15.59 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 08 Jan 2016 13:16:00 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\)) From: Jonathan Morton In-Reply-To: Date: Fri, 8 Jan 2016 23:15:56 +0200 Cc: cake@lists.bufferbloat.net Content-Transfer-Encoding: quoted-printable Message-Id: <498376FB-98D0-4A71-9C50-24C0B5B6CDAD@gmail.com> References: To: Dave Acker X-Mailer: Apple Mail (2.3112) Subject: Re: [Cake] Fwd: curious about hashing comments on cake X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 08 Jan 2016 21:16:03 -0000 > On http://www.bufferbloat.net/projects/codel/wiki/CakeTechnical, it > says that the hash used by fq_codel had various issues and that "we > have also found that the hash function fq_codel relies on is > suboptimal." I believe that fq_codel uses the Jenkins hash like many > other parts of linux. What was suboptimal about it? The page notes > the birthday problem but was there anything else? In some tests, we were seeing a higher rate of collisions than even the = birthday theorem would predict. That generally points to a hash = function insufficiently indistinguishable from white noise, at least = when truncated for use in a small table. I don=E2=80=99t think there=E2=80=99s anything fundamentally wrong with = the Jenkins hash, but there are possibly limitations with the input = conditioning, especially with IPv6 addresses. Cake does still use the Jenkins hash directly when compiled for older = kernels, but that=E2=80=99s a backwards compatibility measure. For = newer kernels, Cake uses whichever hash function is supplied as part of = the new flow-dissection API. It strikes me that this would probably be = updated in future if a serious weakness was discovered, and probably = uses better input conditioning than the old system. The birthday paradox is the big one, though, and this is what the = set-associative hash function addresses directly. - Jonathan Morton