From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x435.google.com (mail-wr1-x435.google.com [IPv6:2a00:1450:4864:20::435]) (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 158CF3B2A4 for ; Mon, 26 Aug 2019 10:43:05 -0400 (EDT) Received: by mail-wr1-x435.google.com with SMTP id q12so15552675wrj.12 for ; Mon, 26 Aug 2019 07:43:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ieee.org; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=CtJBLWZBN9XIY/5K1ZtLbNnFCCWSNnYhy5OTGHcpvWk=; b=Cd3jh8js5r5wAzgxHetVgT0RcRMdvW8NiBJRFlDpjp5Umg+FTxULzAF6HwSZmbjI8+ j3A0tFzUT4kpjimj9npx9J8lMjYlxXfyg3EmvKKORzZjrKL3DKkBYNqeCNzRvKlp6e1Q kK3GQe8HA6T7eMbJeZkBRZ/uiEZ/f8JdOR9Cg= 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; bh=CtJBLWZBN9XIY/5K1ZtLbNnFCCWSNnYhy5OTGHcpvWk=; b=fZ7FpcYrYpNLu6l07UslPfodhTkutrw7Wi5ws7rOCLa516lNWVMj22v/ZHaYfpViVz r6kUCtuc/5vk8P1cYyLVERC9RYgY2G4FlLjZ4s7QQu3vSbD+nqnlXEdQdCMcoewU2lSG t+e8nUKZb3uNAoSj/CZsfr7OzxpuVSwYnM00fhClObcGfq7loZvWOF4F1/TrjBve4wsK brzJUzb7ZJ14KQ4LPm921WUwHK/3yA57gM6KsEUgr+/sgyfxAxES630hAxUeBUOPcxcQ NF6pyWjV2dNQ7bBd/3ZJm2v0N8JVlSWWk2QXOp8RvicCcQHhIVz2gDwFItqtu7hATg8+ 5Jlg== X-Gm-Message-State: APjAAAWz++HUQcb7ELzhPLDui3HgriaDDeX07eaUTZkKut/GUT+vgpoD GGagCZWMSyeheNvGx75tSz6FucHtSvfnQ0AXY4zVZg== X-Google-Smtp-Source: APXvYqyWSAd4RNHYfk7vVvZTRN7dhunq4aH45tB1sMzU0t47H3+w2YJ4Vzv/7ois2yEEZFtQaNM5pUbgAQILvmlbOTM= X-Received: by 2002:adf:9222:: with SMTP id 31mr23621039wrj.93.1566830584152; Mon, 26 Aug 2019 07:43:04 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Luca Muscariello Date: Mon, 26 Aug 2019 16:42:53 +0200 Message-ID: To: Dave Taht Cc: ECN-Sane Content-Type: multipart/alternative; boundary="000000000000646a980591062c2e" 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: Mon, 26 Aug 2019 14:43:05 -0000 --000000000000646a980591062c2e Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable We could reliably say that most of the cost comes from DRR. 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. 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. 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 delay cost because it has to search the longest queue, which give O(log F) (worst case) where 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 single 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 1996. 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 > --000000000000646a980591062c2e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
We could reliably say th= at most of the cost comes from DRR.

FQ based on virtual = times, such as start time, would cost O(log N) where N is the number of pac= kets in the queuing system.
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 l= ist.
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 delay cost because
it has to search the longest queue, = which give O(log F) (worst case) where F is the number of active flows (wit= h at least one packet in the queue).
Smaller than start time fair= queuing.

But DRR, as implemented in fq_codel, doe= s not do that as there is a single AQM per queue.
Which brings mo= re 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 ro= und-robin," in=C2=A0
IEEE/ACM Transactions on Networking<= span style=3D"color:rgb(0,0,0);font-family:Times;font-size:medium">, vol. 4= , no. 3, pp. 375-385, June 1996.=C2=A0doi: 10.1109/90.502236

On Mon, Aug 26, 2019 at 6:28 AM Dave Taht <dave.taht@gmail.com> wrote:
In my rant on nqb I misspok= e 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,<= br> 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 st= ill
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.=C2=A0 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....<= br>
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 i= n 2012-2014.

--

Dave T=C3=A4ht
CTO, TekLibre, LLC
ht= tp://www.teklibre.com
Tel: 1-831-205-9740
_______________________________________________
Ecn-sane mailing list
Ecn-san= e@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/ecn-sane
--000000000000646a980591062c2e--