From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-io1-xd33.google.com (mail-io1-xd33.google.com [IPv6:2607:f8b0:4864:20::d33]) (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 BB37B3B29E for ; Mon, 26 Aug 2019 00:28:14 -0400 (EDT) Received: by mail-io1-xd33.google.com with SMTP id 18so34077288ioe.10 for ; Sun, 25 Aug 2019 21:28:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=WbMreZVfqPUH4myaDcUHWs4MshDV3I7RW3LDVcEPXUo=; b=WPSCFGx3xKlc+fYAxm6vHxKopPG2dhEAr6FnaL7UDvytW18CeYoBUhmk0haG7dkm8S RakckjvEy5uZsro4uu7v+an0cD7in2rK202bkWhNFmbLPCCzrW3Orq7lnCtZsmeWznZG 8O/mP7ba/5UwAyD6Mgy+/Dyt+0OVe0BsVmyqgDLvL/RFSMMMParR4d2IPmgOEepY4g3o 9cae4cAWzoFmyuND8FRHdxChcWW2OoQosTa0Z9/4z8Cd0h+vKsRk8rgCXWa8d5nlwQFi RY14ptPGwQoKrGLZIoF1Um1tRaJWXo+vhDYmZoa43Sx+BEAWAqefBMqxGsnvHcjE2ipq wsPA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=WbMreZVfqPUH4myaDcUHWs4MshDV3I7RW3LDVcEPXUo=; b=cm7VZ9vGVZOA3Q0nW1yfxldg9akjDfRql2HCcueTik8jDr8X4zr4ud8SrgGXMRugFf Q1x38hRFYzLCL1QjZcrafMIOOd5wl4HilkskWiZZU0Sw4Q/eltccWwSPXtAdK+HUpng1 OE87e9qUglGDbpNzs9cy8Z97j2nxBHCOT95M6Zvk5Ny16lumwhhx1RoLRMpv/SK5lZ/p X9wGaQlhKFRjmq2N8V1ozlBFpZsb8S7hA3HBbEctwXxfN9rVY1RQsnRpvLvBHT2hrDDG 7U+o4jZf8XuVmZHZE05srkaSqyo/dozMD9jLvsIDgWLrJHBEsUVPDAj2Ibno3aePNa7X yDqQ== X-Gm-Message-State: APjAAAU1YOUvUA7eSnXBaFP+oZhqkf9pIJDFivUV7i2caz0RiMW85NeM FbQBk4XD38HLAEo4dqrp2nhlujSxKPZg66qdFms= X-Google-Smtp-Source: APXvYqy8zZGn0iSzX7qvGUuMY0vIsjG/krJZBFyr2XZoLZUnSmV/PT+vb/RdxY4K2L28jleRIFiWyVIoCTBhvNUQ90E= X-Received: by 2002:a05:6638:45:: with SMTP id a5mr15577295jap.61.1566793694058; Sun, 25 Aug 2019 21:28:14 -0700 (PDT) MIME-Version: 1.0 From: Dave Taht Date: Sun, 25 Aug 2019 21:28:03 -0700 Message-ID: To: Luca MUSCARIELLO , ECN-Sane Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Subject: [Ecn-sane] complexity question X-BeenThere: ecn-sane@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Discussion of explicit congestion notification's impact on the Internet List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 26 Aug 2019 04:28:14 -0000 In my rant on nqb I misspoke on something, and I feel guilty (for the accidental sophistry) and want to express it better next time. https://mailarchive.ietf.org/arch/msg/tsvwg/hZGjm899t87YZl9JJUOWQq4KBsk I said: "Whether you have 1 queue or thousands in a fq'd system, the code is the same as is the "complexity" for all intended purposes." But I'm wrong about the "complexity" part of that statement, particularly if you are thinking about pure hardware. pie/codel are O(1) for purely marked traffic. For dropping, well, it's easier to reason about random drop probabilities and extrapolate out to some number of loops to bound at some value (?) where you just give up and deliver the packet, based on however much budget you have between packets in the hw. (we have so much budget in the bql and wifi world I've never cared) It's harder to reason about codel, but you can still have a bounded loop if you want one. fq_codel is selecting a queue to dequeue - so it's not O(1) for finding that queue. Selecting the right queue can take multiple loops through the whole queue spaces, based on the quantum, and then on top of that you have the drop decisionmaking, so you have best case (1), worst case (?) and average/median, whatever.... So if you wanted to put a bound on it (say, you were writing in ebpf or the hw) "for the time spent finding a packet to deliver", how would you calculate a good time to give up in any of these cases (pie, codel, fq_codel, pick another fq algo...), and just deliver a packet. (my gut says 6-11 loops btw and it's not tellling me why) But if you bounded the loop seeking the right queue what would happen? But if you bounded the loop, as to giving up on the drop decision what would happen? This is giving me flashbacks to "the benefit of drop tail" back in 2012-201= 4. --=20 Dave T=C3=A4ht CTO, TekLibre, LLC http://www.teklibre.com Tel: 1-831-205-9740