From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-io1-xd41.google.com (mail-io1-xd41.google.com [IPv6:2607:f8b0:4864:20::d41]) (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 882FB3CB35 for ; Tue, 27 Aug 2019 23:10:42 -0400 (EDT) Received: by mail-io1-xd41.google.com with SMTP id 18so2831181ioe.10 for ; Tue, 27 Aug 2019 20:10:42 -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=7AuuxlXd4ngTYZqjimQEK6cSS/LNu4j4LH+QwIXXd4o=; b=cIffv+KM1QOJJQS87gtUFPmN2uVjXOXXh2cwkUkDpRLa+Q8zph4uHMns4b7vr9Ax2l 4tv/beE6sXI1KgruKO0EQ4QzPfCdCe4iK/umhcEfu5UFdRSrytkxPy8wejkjRH4Ndrfe f83W+iwC/KEiGbgoKUKXS+Ph8TuCi7s4SXNDL7nikR1LIA0QOBLQhwsfo6zWcuItaDYv ZbRz2AxPkd+H0qIdxi+snEk6L/dEmvyMmDvVUvWZeOSB7rOQmtnB+Pq5v7IGYgNy4nIs Mo3Zf8brTu1yiHhyJHpccZS0REE8d3LYmZcGa15cbhZuN/dGfVkGyIfKDYbNKzGCCNYm W7kA== 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=7AuuxlXd4ngTYZqjimQEK6cSS/LNu4j4LH+QwIXXd4o=; b=L0p9bFnKlZrkSJTWUkNLNZNuFrnFmv1k7qsfrNJFRK5zIuHFGk+oUtafq/b4H74P9A PCtmt/fU0edv+W/HtnlYQ6POdLJvRAwymAAuwqT9p3c+AKgBArwA0cpkk9jFbnhSi2P4 /x00PaRv4I1DQss1bkGaQnDFtS0xVBLnw4ipTxkV4nLQxf9hHVoGenVmvR+6qrqKnfkp rFQ5qlKLnonG7KicX9khEsi9E5ZiE8YLF9hUOPHqyyz9G5JXlD9VLDoehStkp1yIlYh4 f5eq3OhQiF8F7SGo5a6aqCtaz9cklxaz0kuaXSigLd5czLAbTONe09P/ZeTTVuUi0Q22 dxoQ== X-Gm-Message-State: APjAAAWL48912Bf0woiKDmXlZYZCH9HZvc28PeOA4IQwk+XOdeiKGzmg +GHHplo3U8y91pwVRcgHg+zRQ8KNTBMTMiIKn/A= X-Google-Smtp-Source: APXvYqx/FbJWmzjMBsKll+H1h9K0EFSkLt5LxhL8a3DxbW1eISnZ1T+0EDCbtD5s8RTXLdwBPhden2xMb09hu4svRyY= X-Received: by 2002:a5e:8344:: with SMTP id y4mr1769631iom.213.1566961841822; Tue, 27 Aug 2019 20:10:41 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Dave Taht Date: Tue, 27 Aug 2019 20:10:30 -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 03:10:42 -0000 On Tue, Aug 27, 2019 at 7:57 PM Dave Taht wrote: > > On Mon, Aug 26, 2019 at 7:43 AM Luca Muscariello w= rote: > > > > 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) wher= e 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) cos= t. So you're not wrong Dave > > at least for DRR. But I don't see any other cost to add to the check li= st. > > 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(); > } > } oops I hit send too early: skb =3D dequeue_from_drr(); for(i =3D 0; skb && i < 6; i++) { if (had_to_drop(skb)) skb =3D dequeue_from_drr(); else { i =3D 6; break; } } Or another way: now =3D gettime(); budget =3D now + (time_left_to_deliver_the_previous_packet) skb =3D dequeue_from_drr(); ok =3D false; while (budget > now && !ok && skb) if (had_to_drop(skb)) { // pseudocode that drops the skb if needed skb =3D dequeue_from_drr(); now =3D gettime(); } else ok =3D true; } time_left_to_deliver_the_previous_packet =3D calc_it_from_size_and_remaining_budget(skb); return skb; (I make no warranties for code I write in a browser, I'm hoping my intent is clear) > > 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 o= f cost but that is really implementation dependent. > > > > SFQ in Linux is using Longest Queue Drop which brings back non constant= delay cost because > > it has to search the longest queue, which give O(log F) (worst case) wh= ere 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 sin= gle 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 rou= nd-robin," in > > IEEE/ACM Transactions on Networking, vol. 4, no. 3, pp. 375-385, June 1= 996. 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/hZGjm899t87YZl9JJUOWQq4KBs= k > >> > >> 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 201= 2-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 > > > > -- > > Dave T=C3=A4ht > CTO, TekLibre, LLC > http://www.teklibre.com > Tel: 1-831-205-9740 --=20 Dave T=C3=A4ht CTO, TekLibre, LLC http://www.teklibre.com Tel: 1-831-205-9740