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 244103CB35 for ; Tue, 27 Aug 2019 22:57:45 -0400 (EDT) Received: by mail-io1-xd33.google.com with SMTP id p12so2859131iog.5 for ; Tue, 27 Aug 2019 19:57:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=AVniE6yEJHwWGO2H/7vJQ8bqLWlVNspBU5DVAJPNCYA=; b=QMIhuFoIMerzLzQQ94L9ws84Nl9/xEzACPerNSa1hNSHnBw3SE1w6GyQFzB4m+vOiK zWDXpZjyZAnK99DNqCDs5BVTFaonNoL2ltvg/uLMCbVibB8bJggl7VZdki8Z3xymKzDZ 01DjnwiGUs8YasKl3W+U5dbPl3rXJmSXz2TaGFSotpf2IvXUQdgU4PPQTP4fWCXNJS3o 23Fiu4ELMMPJ6Jzq+dqZZ43tvrOMzyXTjAE5tEWfaLyVOxopC5Jj9zX/QDYW2h/K/UAl zhpmzd4e2cvRmSqyFniPLksld5wg/8PhqARcbF42y9557EYBy3m3ASJ2HPpTBqDwLQLV 6NEA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=AVniE6yEJHwWGO2H/7vJQ8bqLWlVNspBU5DVAJPNCYA=; b=pL9DtmICrzuMkXhBplfalcGSrbV287BJ6Fyv4Z0pW4C71g+4qCE3DjIG/QBoESZJCD /zDe4Bo7LPz4vEpOiUWjacnTWtIB8bocm+fqPTUJItF4uyZcj5VP7mAyMBuYR6ez0Vnn MTAkYqn50IsyXMuBq0mfPMaBBuzCBbj3KRpzPEDtOgm5VUZNgoGON14Jik8Anh1Pzh3g UAUPrvOFBNHj9dL8xnoOZvKP3LO3X+byvJ6qKFvDGWq6iktaDH2Tqs0FQ74NFKveOxWQ bNFvGy8APgDpcrb6mjiXegdhY9A6EVSzKlnVsg43ohU7ag/MXgSC3wDGoG0Qkgjcn9F0 QAGg== X-Gm-Message-State: APjAAAW9tfN420jrli7xJTS4Csqov53UJ5LX2cxnVIk3RIl7hhQM41Dl bvgMf3jZ43xK2o7YyivggxuqtfeS0Jbomff5Gd0= X-Google-Smtp-Source: APXvYqwUdM67ogbblML+Qu3LAZXUxtpsJpMXnZpe0oFL7yFR22jeBpWdSkQ6MfXbHR2x57N+gmCHPJQEw+AM0bH/9mM= X-Received: by 2002:a02:c992:: with SMTP id b18mr2188715jap.128.1566961064194; Tue, 27 Aug 2019 19:57:44 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Dave Taht Date: Tue, 27 Aug 2019 19:57:32 -0700 Message-ID: To: Luca Muscariello Cc: ECN-Sane Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Subject: Re: [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: Wed, 28 Aug 2019 02:57:45 -0000 On Mon, Aug 26, 2019 at 7:43 AM Luca Muscariello wro= te: > > We could reliably say that most of the cost comes from DRR. yep. Particularly as we tend to overuse small quantums and don't really have anything other than gut feel as to how to scale it. I'm not fond of - as we use in wifi - 300 as the quantum - as that's kind of expensive in terms of loops through the algo - however it does optimize for small packets really well, and as a wireless-n aggregate has a 64 packet (oft much less) limit to the number of packets in it makes sense to interleave as much as .you can. I am thinking we should scale this differently for ac and later. https://sci-hub.tw/10.1109/LCOMM.2012.081612.120744 > FQ based on virtual times, such as start time, would cost O(log N) where = N is the number of packets in the queuing system. Hmm... and EDF? > DRR as designed by Varghese provided a good approximation with O(1) cost.= So you're not wrong Dave > at least for DRR. But I don't see any other cost to add to the check list= . The thing that I'm strugglng to express is the codel or pie bit - let me use pie. Assume we have a drop probability of 50%. (not doing wifi here...) You can say that on average you are going to drop every other packet, but probability could be coming up 1 for a potentially infinite number of tries. So, if we were running WAY closer to the hw and we had a budget of X ns to get the next packet onto the wire, we need to give up on dropping anything and just deliver a packet and hope we do more of the right thing next time. Now the act of putting in a budget actually heisenbugs the calc more. bql needs a bound (or used to) skb =3D dequeue_from_drr(); for(i =3D 0; skb && i < 6; i++) { if (had_to_drop(skb)) { skb =3D dequeue_from_drr(); } } You can accept (as we do in bql) a standing queue that's pretty tiny (2-3k at 100mbit, 36k or so at a gbit) you can try (in hw) to process several queues in parallel with, say a 3 (x?) deep pipeline you can do the dequeue and always have one "ready to go" you can process everything simultaneously (edf) and I used to know how qfq worked but now forget Did I miss any options here? (in hw?) How about using some ai technique that's likely to attract grant money? :) . > Of course every algorithm can come with a different constant in terms of = cost but that is really implementation dependent. > > SFQ in Linux is using Longest Queue Drop which brings back non constant d= elay cost because > it has to search the longest queue, which give O(log F) (worst case) wher= e F is the number of active flows (with at least one packet in the queue). > Smaller than start time fair queuing. > > But DRR, as implemented in fq_codel, does not do that as there is a singl= e AQM per queue. > Which brings more cost in terms of memory but not in terms of time. > > I'm not sure about the DRR implementation in CAKE, but there should be no= differences in terms of complexity. > > > M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit round= -robin," in > IEEE/ACM Transactions on Networking, vol. 4, no. 3, pp. 375-385, June 199= 6. doi: 10.1109/90.502236 > https://www2.cs.duke.edu/courses/spring09/cps214/papers/drr.pdf > > > On Mon, Aug 26, 2019 at 6:28 AM Dave Taht wrote: >> >> 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-= 2014. >> >> -- >> >> Dave T=C3=A4ht >> CTO, TekLibre, LLC >> http://www.teklibre.com >> Tel: 1-831-205-9740 >> _______________________________________________ >> Ecn-sane mailing list >> Ecn-sane@lists.bufferbloat.net >> https://lists.bufferbloat.net/listinfo/ecn-sane --=20 Dave T=C3=A4ht CTO, TekLibre, LLC http://www.teklibre.com Tel: 1-831-205-9740