<div dir="ltr"><div dir="ltr"><div dir="ltr">We could reliably say that most of the cost comes from DRR.<div><br></div><div>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.</div><div>DRR as designed by Varghese provided a good approximation with O(1) cost. So you're not wrong Dave</div><div>at least for DRR. But I don't see any other cost to add to the check list.</div><div>Of course every algorithm can come with a different constant in terms of cost but that is really implementation dependent.</div><div><br></div><div>SFQ in Linux is using Longest Queue Drop which brings back non constant delay cost because</div><div>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).</div><div>Smaller than start time fair queuing.</div><div><br></div><div>But DRR, as implemented in fq_codel, does not do that as there is a single AQM per queue.</div><div>Which brings more cost in terms of memory but not in terms of time.</div><div><br></div><div>I'm not sure about the DRR implementation in CAKE, but there should be no differences in terms of complexity.</div><div><br></div><div><br></div><div><span style="color:rgb(0,0,0);font-family:Times;font-size:medium">M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit round-robin," in </span></div><div><em style="color:rgb(0,0,0);font-family:Times;font-size:medium">IEEE/ACM Transactions on Networking</em><span style="color:rgb(0,0,0);font-family:Times;font-size:medium">, vol. 4, no. 3, pp. 375-385, June 1996. </span><span style="color:rgb(0,0,0);font-family:Times;font-size:medium">doi: 10.1109/90.502236</span><br></div><div><font color="#000000" face="Times" size="3"><a href="https://www2.cs.duke.edu/courses/spring09/cps214/papers/drr.pdf">https://www2.cs.duke.edu/courses/spring09/cps214/papers/drr.pdf</a></font><br></div><div><br></div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Aug 26, 2019 at 6:28 AM Dave Taht <<a href="mailto:dave.taht@gmail.com">dave.taht@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">In my rant on nqb I misspoke on something, and I feel guilty (for the<br>
accidental sophistry) and want to express it better next time.<br>
<br>
<a href="https://mailarchive.ietf.org/arch/msg/tsvwg/hZGjm899t87YZl9JJUOWQq4KBsk" rel="noreferrer" target="_blank">https://mailarchive.ietf.org/arch/msg/tsvwg/hZGjm899t87YZl9JJUOWQq4KBsk</a><br>
<br>
I said:<br>
<br>
"Whether you have 1 queue or thousands in a fq'd system, the code is<br>
the same as is the "complexity" for all intended<br>
purposes."<br>
<br>
But I'm wrong about the "complexity" part of that statement,<br>
particularly if you are thinking about pure hardware. pie/codel are<br>
O(1) for purely marked traffic. For dropping, well, it's easier to<br>
reason about random drop probabilities and extrapolate out to some<br>
number of loops to bound at some value (?) where you just give up and<br>
deliver the packet, based on however much budget you have between<br>
packets in the hw. (we have so much budget in the bql and wifi world<br>
I've never cared) It's harder to reason about codel, but you can still<br>
have a bounded loop if you want one.<br>
<br>
fq_codel is selecting a queue to dequeue - so it's not O(1) for<br>
finding that queue.  Selecting the right queue can take multiple loops<br>
through the whole queue spaces, based on the quantum, and then on top<br>
of that you have the drop decisionmaking,<br>
so you have best case (1), worst case (?) and average/median, whatever....<br>
<br>
So if you wanted to put a bound on it (say, you were writing in ebpf<br>
or the hw) "for the time spent finding a packet to deliver",<br>
how would you calculate a good time to give up in any of these cases<br>
(pie, codel, fq_codel, pick another fq algo...), and just deliver a<br>
packet.<br>
<br>
(my gut says 6-11 loops btw and it's not tellling me why)<br>
<br>
But if you bounded the loop seeking the right queue what would happen?<br>
<br>
But if you bounded the loop, as to giving up on the drop decision what<br>
would happen?<br>
<br>
This is giving me flashbacks to "the benefit of drop tail" back in 2012-2014.<br>
<br>
-- <br>
<br>
Dave Täht<br>
CTO, TekLibre, LLC<br>
<a href="http://www.teklibre.com" rel="noreferrer" target="_blank">http://www.teklibre.com</a><br>
Tel: 1-831-205-9740<br>
_______________________________________________<br>
Ecn-sane mailing list<br>
<a href="mailto:Ecn-sane@lists.bufferbloat.net" target="_blank">Ecn-sane@lists.bufferbloat.net</a><br>
<a href="https://lists.bufferbloat.net/listinfo/ecn-sane" rel="noreferrer" target="_blank">https://lists.bufferbloat.net/listinfo/ecn-sane</a><br>
</blockquote></div>