From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail.taht.net (mail.taht.net [IPv6:2a01:7e00::f03c:91ff:feae:7028]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id E041A3B2A4; Wed, 28 Nov 2018 23:38:05 -0500 (EST) Received: from dancer.taht.net (unknown [IPv6:2603:3024:1536:86f0:eea8:6bff:fefe:9a2]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.taht.net (Postfix) with ESMTPSA id B23F921B39; Thu, 29 Nov 2018 04:38:03 +0000 (UTC) From: Dave Taht To: Jonathan Morton Cc: Stephen Hemminger , codel@lists.bufferbloat.net, bloat References: <20181126200805.1393645e@xeon-e3> <5CA2D845-508D-421C-AF38-E2B5AE0E54B2@gmail.com> Date: Wed, 28 Nov 2018 20:37:52 -0800 In-Reply-To: <5CA2D845-508D-421C-AF38-E2B5AE0E54B2@gmail.com> (Jonathan Morton's message of "Tue, 27 Nov 2018 06:17:19 +0200") Message-ID: <87ftvkzefz.fsf@taht.net> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Codel] [Bloat] found another good use for a queue today, possibly X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 29 Nov 2018 04:38:06 -0000 Jonathan Morton writes: >>> "polylog(n)-wise Independent Hash Function". OK, my google-foo fails >>> me: The authors use sha1, would something lighter weight suit? > >> The current favorite in DPDK land seems to be Cuckoo hashing. >> It has better cache behavior than typical chaining. > > That paper describes an improved variant of cuckoo hashing, using a > queue to help resolve collisions with better time complexity. The > proof relies on (among other things) a particular grade of hash > function being used. SHA1 is described as being suitable since it > offers cryptographic-level performance=E2=80=A6 We actually need two hash= es > with independent behaviour on the same input, one for each table. > > If we were to assume table sizes up to 64K, using both halves of a > good 32-bit hash might be suitable. It may be that plain old Jenkins > hash would work in that context. Supplement that with a 64-entry > queue with linear search (in software) or constant-time CAM search (in > hardware). I was aiming for 2million routes. I gave up trying to wade through it and pinged the authors. fiddling with blake at the moment > > - Jonathan Morton > > _______________________________________________ > Codel mailing list > Codel@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/codel