From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf0-x241.google.com (mail-lf0-x241.google.com [IPv6:2a00:1450:4010:c07::241]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id A4CB93B29E for ; Thu, 2 Mar 2017 19:00:46 -0500 (EST) Received: by mail-lf0-x241.google.com with SMTP id v2so619939lfi.2 for ; Thu, 02 Mar 2017 16:00:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=1+R9Zy7PZx84WHONqHpF50cUaBsL2l9OKCni0iZPDeE=; b=gDawBvi+zCNQwTZqsd3nOXK8ewnvOHM3eOnaSe/L98w7xefO7OAuRmrwWwuA2owq3V 5jeL+zANx1jhG4ltdvN39cVuc7Jj9S2VnzovlFq7CE2YZiXL/k8bS8Kk2XSl0zGOKqu8 q+tbNHx8Rqo4j7ItcQnHxRHjRUv0V9IA2k+WrUn/gsvatiV7Id8Bv86dXvqRAV/YHuCo gOcEYk95UKff8Z+JBoMrdekz/6UE3ugiFN1EpBxf0wlx7703qmPPAUkn1AL9Hmps2ktd fMsJcGuJ0n5FWJhlOHEprw9Tu33Fup9Sex50lklkTLiwGkYAhWTFtG7jMC6ITHiBmBSg GAbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=1+R9Zy7PZx84WHONqHpF50cUaBsL2l9OKCni0iZPDeE=; b=PmxLZIQJmtzxEA08qOPBk8sFQfNYkzfgCkm3DWqgbd+CTaxQ/bzIhFd6tgHpyjRVXO ABqzrNcvr1GfFXFr8T5ZolmsfWPVADvOzKP+magqGzio3NULIWh3lZsW5ky/CUosNxpi 7ZF9x71SdawXzKCkWCvQ7X43FqB8J4UoCPvjkzM6cqszYjQNKDn09LCZrt8zF+yzG4Ih ikno/N8Lrwxm6MD45BV7HtA7mCGlMg9Y7Vee1Y3MpV8/H1oiWJosC+KJJABSufOisvyX 7XihOvz5ncj6kYneSbrC3UVGnQDYHWJaPx+MxpyGtk8jblv0/yF8nbQy0GUZfmjzO7AK bogQ== X-Gm-Message-State: AMke39nsxas9eBMEO6f+Xy6Ri2EQ6EVVVtA+mljfl0ovlUgG6SsfpNZ8y0kUYkdHdhwaCg== X-Received: by 10.25.129.149 with SMTP id c143mr5325673lfd.15.1488499245510; Thu, 02 Mar 2017 16:00:45 -0800 (PST) Received: from [192.168.100.16] (37-219-206-78.nat.bb.dnainternet.fi. [37.219.206.78]) by smtp.gmail.com with ESMTPSA id m27sm1917789ljb.24.2017.03.02.16.00.44 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Thu, 02 Mar 2017 16:00:44 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\)) From: Jonathan Morton In-Reply-To: Date: Fri, 3 Mar 2017 02:00:41 +0200 Cc: =?utf-8?Q?Dave_T=C3=A4ht?= , cake@lists.bufferbloat.net, lede-dev@lists.infradead.org Content-Transfer-Encoding: quoted-printable Message-Id: <3A9C046E-DE4C-4D97-BC47-2AD00D4F6A79@gmail.com> References: <07479F0A-40DD-44E5-B67E-28117C7CF228@gmx.de> <1488400107.3610.1@smtp.autistici.org> <2B251BF1-C965-444D-A831-9981861E453E@gmx.de> <1488484262.16753.0@smtp.autistici.org> To: John Yates X-Mailer: Apple Mail (2.3124) Subject: Re: [Cake] [LEDE-DEV] Cake SQM killing my DIR-860L - was: [17.01] Kernel: bump to 4.4.51 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, 03 Mar 2017 00:00:46 -0000 > On 3 Mar, 2017, at 01:16, John Yates wrote: >=20 > What are the requirements for this hashing function? > - How much data is being hashed? I am guessing a limited number of = bytes rather than an entire packet payload. Generally it=E2=80=99s what we call the =E2=80=9C5-tuple=E2=80=9D: two = addresses (which could be IPv4, IPv6, or potentially Ethernet MAC), two = port numbers (16 bits each), and a transport protocol ID (1 byte). In Cake, the hash function is by default run three times, in order to = get separate hashes over just the source address and just the = destination address, as well as the full 5-tuple. These are necessary = to operate the triple-isolate algorithm. There may be an opportunity = for optimisation by producing all three hashes in parallel. > - What is the typical number of hash table buckets? Is it prime or a = power of 2? It=E2=80=99s a power of two, yes. The actual number of buckets is 1024, = but Cake uses the full 32-bit hash as a =E2=80=9Ctag=E2=80=9D for hash = collision detection without having to store and compare the entire = 5-tuple. - Jonathan Morton