From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk0-x22b.google.com (mail-qk0-x22b.google.com [IPv6:2607:f8b0:400d:c09::22b]) (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 725473B29E for ; Sun, 29 Oct 2017 18:20:03 -0400 (EDT) Received: by mail-qk0-x22b.google.com with SMTP id y23so14017844qkb.10 for ; Sun, 29 Oct 2017 15:20:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=eVnJ55Ey0jzi/s2E47On/6QD8I3sdz5c24PMgcYvbhA=; b=ErMIPT3ueyFMX8BuEriHgl/LDPfD5EdKjWSI1vmvmDewfGJDaAVjRAVi5+hUlGh4Tt PxjPCtPhf7tn39DI546CMyd49/iEnbWlbHXF9JVgUwrvxvhDQ5Pp1z4KGtMV0jJA90ib xHqoZfbNcmFkUbjtSO/KGqQU8CcQ02RPwk/Dl3ZEpJ0oGUHX1nz842HdV/mFXFlA4ehU Hb+GN2wEVI3zdrNEhnKwn4KnyOkNT+micwHLkh1fTyFYgX7o3uXGZgIR5VqZ5mtuJIhM q8mhk2UACmlmoF+F9/PJddnAJEypshEe6ggwSvrrgWW4e++r/O881ESUMXaRoxTT/R/W JmUg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=eVnJ55Ey0jzi/s2E47On/6QD8I3sdz5c24PMgcYvbhA=; b=J6tbQvvEkF/QO9ZD9mEXVf7f0WS7+nRstB2bCRgKkw1hpXn13jacvwnMMtYfe8TyzQ yJlrnZiDZr5HHgcSYWyvAHgXhIaD+rCLoJSw1tUnwhIqEaq8QeGEjLp8sMdhv6Aa9jeV jJQ+UEiN+qqbahL3kK5NoJEqQOa7L09A2NlxeVrOf9UMZcMhnJVXQmR6ot0FPRtgaZ16 YY3VnYEV0BaKCrjnpWxcDgNVKg0EhvbzTkqqMsogHK5mfjRTy2cX8L6wYoqNFiNfkgiZ cBtujC/7yfiMBYM4biU16g+y3wmuf3MP/BtRrvxgcdWD/poiGJYvr/CPUU3c7CazMi4n VHsg== X-Gm-Message-State: AMCzsaV68DKH3KvHiH7aTfQmQLTyd/2tCzwmPBccdCBEYpDKId6U+CYn UG5WRvpqt3KYrLEvJWKieTGOIBe+nyoyb0jVAFQ= X-Google-Smtp-Source: ABhQp+TsuFHG+wFmma068Ka80bZs4/yuJxMu1ig4NjJbzelq5LGrn8WiguL4aUPKJZvRZOLAh2hjvR6+jiYXIA+yEio= X-Received: by 10.55.133.71 with SMTP id h68mr10080183qkd.17.1509315603092; Sun, 29 Oct 2017 15:20:03 -0700 (PDT) MIME-Version: 1.0 Received: by 10.12.209.200 with HTTP; Sun, 29 Oct 2017 15:20:02 -0700 (PDT) In-Reply-To: References: From: Dave Taht Date: Sun, 29 Oct 2017 15:20:02 -0700 Message-ID: To: Adrian Popescu Cc: Jonathan Morton , Cake List Content-Type: text/plain; charset="UTF-8" Subject: Re: [Cake] CAKE set-associative hashing 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: Sun, 29 Oct 2017 22:20:03 -0000 Much of the queuing literature involving fair queuing to date has involved either the assumption of a perfect hash, or a one way direct hash, cake does indeed innovate here. set associative caches, on the other hand, are well explored in CPU designs, where a 2 or 4 way set is most common. An open question is how many levels of associativity relative to "ideal" and aqm'd queue depth, number of queues, and bandwidth is "ideal". I suspect 1024 queues is low for 10GigE, high (with 8 way set associativity) for under a gbit. It would be nice to have a formula to calculate these relations. More complicated is that all the 10GigE capable hardware has a low number (often 64) of built-in direct hash mapped hardware queues, which does re-introduce the birthday problem at a level that cake doesn't handle, as on a hardware mq'd device, we end up with 64 cake instances. Some gigE hardware has 4-8 hardware queues, where the birthday problem rears it's head almost immediately.