From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x62e.google.com (mail-ej1-x62e.google.com [IPv6:2a00:1450:4864:20::62e]) (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 888F33B29E for ; Wed, 12 Oct 2022 13:35:47 -0400 (EDT) Received: by mail-ej1-x62e.google.com with SMTP id w18so13064352ejq.11 for ; Wed, 12 Oct 2022 10:35:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=BBkOnbhPXv0ZcAedg8Wsl8rahS7xMUP+9KGeYRvvGJM=; b=jgry/BOe0/lRbQWmyHQkiLp87rtWffZ0vwO42HAvDKedhiprHWYBh0Pm8hOqkD79xh GaFLqI7bpAaPYCRW4LExOL2uQgadbBmGIaj8xatiENr7Kh5n6rGN49oJhYtVtb6TWokL rsTF+29ZGXDBRWnt6JKKe9Xj6zt1oJCShQautDiftWP9+zo960tle/GRGwUN6hJHZdWi ++EFJ7f7CfasayBLuzc9WFAQU+SKg3/M80Oz3GYYXsIA0HoydZmt/be0rxbumJCfUW/T h2OI2nueEMaUuz+CK5MgysWPjjWn/UiNA7hqwJJ6CNvf9Ar703Tsx5LW9LbRFZ2GxuWW Pvug== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=BBkOnbhPXv0ZcAedg8Wsl8rahS7xMUP+9KGeYRvvGJM=; b=KI+Qz3NUDf1YgGqqOQ78qup7pyiXt4OYgnEowQkFmFp5xlhDxuumSzUdRI7EzQj5Ve rvJOxutc5VeSKjMt77E/qFaWouvwiw94tCWaDCGqPI2B/cTieq2gFwdQG9h2WxKb6Aq0 PejrqUSHPOWcZi4mPwf1X/KRjkHWYUNPS8QvCq6QNZnXY+cA/xZmtPt1JmeB8zfofy1x ZqLP20GFyZ16R2YT44TyDyBOE/gBu/zoJOpjXqTsO/prxWhxw2McIoUmJu67OHNoneIq cifMgx1gYpWWB4DsV5y69bHHGRK6SZXe0+K1E+iV7CQXzcq0EKOqV9c1BFO4fY/lIryp ZDiw== X-Gm-Message-State: ACrzQf1DsVXtr/7ZhhMsv708ZnEjMOGUijU47ZVhSVE1DrH4/CSootTV kDE+MLMs1UdMRDlqIxDVAV/6eXlEk57J3vXEmck6iByQ X-Google-Smtp-Source: AMsMyM5kkgXYppkxySX+qmrnI0n0c/dZL0g8cGiS/0wPgXKEGJRhkSE/96JLlBVGMom67V6ZFbrCEtB4FRP7RIVMDWk= X-Received: by 2002:a17:907:a044:b0:78d:9180:125c with SMTP id gz4-20020a170907a04400b0078d9180125cmr18673394ejc.247.1665596146101; Wed, 12 Oct 2022 10:35:46 -0700 (PDT) MIME-Version: 1.0 References: <8E7E8800-E411-4098-AFEC-4B24FA34335C@gmx.de> In-Reply-To: From: Maximilian Bachl Date: Wed, 12 Oct 2022 19:35:34 +0200 Message-ID: To: Dave Taht Cc: bloat Content-Type: multipart/alternative; boundary="000000000000a0b70c05ead9d28f" Subject: Re: [Bloat] Fair queuing detection for congestion control X-BeenThere: bloat@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: General list for discussing Bufferbloat List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Oct 2022 17:35:47 -0000 --000000000000a0b70c05ead9d28f Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Building upon the ideas and advice I received, I simplified the whole concept and updated the preprint (https://arxiv.org/abs/2206.10561). The new approach is somewhat similar to what you propose in point 3). True negative rate (correctly detecting the absence of FQ) is now >99%; True positive rate is >95% (correctly detecting the presence of FQ (fq_codel and fq)). It can also detect if the bottleneck link changes during a flow from FQ to non-FQ and vice versa. A new concept is that each application can choose its maximum allowed delay independently if there's FQ. A cloud gaming application might choose to not allow more than 5 ms to keep latency minimal, while a video chat application might allow 25 ms to achieve higher throughput. Thus, each application can choose its own tradeoff between throughput and delay. Also, applications can measure how large the base delay is and, if the base delay is very low (because the other host is close by), they can allow more queuing delay. For example, if the base delay between two hosts is just 5 ms, it could be ok to add another 45 ms of queuing to have a combined delay of 50 ms. Because the allowed queuing delay is quite high, throughput is maximized. On Sun, Jul 3, 2022 at 4:49 PM Dave Taht wrote: > Hey, good start to my saturday! > > 1) Apple's fq_"codel" implementation did not actually implement the > codel portion of the algorithm when I last checked last year. Doesn't > matter what you set the target to. > > 2) fq_codel has a detectable (IMHO, have not tried) phase where the > "sparse flow optimization" allows non queue building flows to bypass > the queue building > flows entirely. See attached. fq-pie, also. Cake also has this, but > with the addition of per host FQ. > > However to detect it, requires sending packets on an interval smaller > than the codel quantum. Most (all!?) TCP implementations, even the > paced ones, send 2 1514 packets back to back, so you get an ack back > on servicing either the first or second one. Sending individual TCP > packets paced, and bunching them up selectively should also oscillate > around the queue width. (width =3D number of queue building flows, > depth, the depth of the queue). The codel quantum defaults to 1514 > bytes but is frequently autoscaled to less at low bandwidths. > > 3) It is also possible, (IMHO), to send a small secondary flow > isochronously as a "clock" and observe the width and depth of the > queue that way. > > 4) You can use a fq_codel RFC3168 compliant implementation to send > back a CE, which is (presently) a fairly reliable signal of fq_codel > on the path. A reduction in *pacing* different from what the RFC3168 > behavior is (reduction by half), would be interesting. > > Thx for this today! A principal observation of the BBR paper was that > you cannot measure for latency and bandwidth *at the same time* in a > single and you showing, in a FQ'd environment, that you can, I don't > remember seeing elsewhere (but I'm sure someone will correct me). > > On Sun, Jul 3, 2022 at 7:16 AM Maximilian Bachl via Bloat > wrote: > > > > Hi Sebastian, > > > > Thank you for your suggestions. > > > > Regarding > > a) I slightly modified the algorithm to make it work better with the > small 5 ms threshold. I updated the paper on arXiv; it should be online b= y > Tuesday morning Central European Time. Detection accuracy for Linux's > fq_codel is quite high (high 90s) but it doesn't work that well with smal= l > bandwidths (<=3D10 Mbit/s). > > b) that's a good suggestion. I'm thinking how to do it best since also > every experiment with every RTT/bandwidth was repeated and I'm not sure h= ow > to make a CDF that includes the RTTs/bandwidths and the repetitions. > > c) I guess for every experiment with pfifo, the resulting accuracy is a > true negative rate, while for every experiment with fq* the resulting > accuracy is a true positive rate. I updated the paper to include these > terms to make it clearer. Summarizing, the true negative rate is 100%, th= e > true positive rate for fq is >=3D 95% and for fq_codel it's also in that > range except for low bandwidths. > > > > In case you're interested in reliable FQ detection but not in the > combination of FQ detection and congestion control, I co-authored another > paper which uses a different FQ detection method, which is more robust bu= t > has the disadvantage of causing packet loss (Detecting Fair Queuing for > Better Congestion Control (https://arxiv.org/abs/2010.08362)). > > > > Regards, > > Max > > _______________________________________________ > > Bloat mailing list > > Bloat@lists.bufferbloat.net > > https://lists.bufferbloat.net/listinfo/bloat > > > > -- > FQ World Domination pending: > https://blog.cerowrt.org/post/state_of_fq_codel/ > Dave T=C3=A4ht CEO, TekLibre, LLC > --000000000000a0b70c05ead9d28f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Building upon the ideas and advice I received, I simp= lified the whole concept and updated the preprint (https://arxiv.org/abs/2206.10561= ). The new approach is somewhat similar to what you=C2=A0propose in point 3= ). True negative rate (correctly detecting the absence of FQ) is now >99= %; True positive rate is >95% (correctly detecting the presence of FQ (f= q_codel and fq)). It can also detect if the bottleneck link changes during = a flow from FQ to non-FQ and vice versa.=C2=A0

A new concept is that each application can choose its maximum all= owed delay independently if there's FQ. A cloud gaming application migh= t choose to not allow more than 5 ms to keep latency minimal, while a video= chat application might allow 25 ms to achieve higher throughput. Thus, eac= h application can choose its own tradeoff between throughput and delay. Als= o, applications can measure how large the base delay is and, if the base de= lay is very low (because the other host is close by), they can allow more q= ueuing delay. For example, if the base delay between two hosts is just 5 ms= , it could be ok to add another 45 ms of queuing to have a combined delay o= f 50 ms. Because the allowed queuing delay is quite high, throughput is max= imized.=C2=A0



On Sun, Jul 3, 2022 at 4:49 PM Dave Taht <dave.taht@gmail.com> wrote:
Hey, good start to my saturday!

1) Apple's fq_"codel" implementation did not actually impleme= nt the
codel portion of the algorithm when I last checked last year. Doesn't matter what you set the target to.

2) fq_codel has a detectable (IMHO, have not tried) phase where the
"sparse flow optimization" allows non queue building flows to byp= ass
the queue building
flows entirely. See attached. fq-pie, also. Cake also has this, but
with the addition of per host FQ.

However to detect it, requires sending packets on an interval smaller
than the codel quantum. Most (all!?) TCP implementations, even the
paced ones, send 2 1514 packets back to back, so you get an ack back
on servicing either the first or second one. Sending individual TCP
packets paced, and bunching them up selectively should also oscillate
around the queue width. (width =3D number of queue building flows,
depth, the depth of the queue). The codel quantum defaults to 1514
bytes but is frequently autoscaled to less at low bandwidths.

3) It is also possible, (IMHO), to send a small secondary flow
isochronously as a "clock" and observe the width and depth of the=
queue that way.

4) You can use a fq_codel RFC3168 compliant implementation to send
back a CE, which is (presently) a fairly reliable signal of fq_codel
on the path. A reduction in *pacing* different from what the RFC3168
behavior is (reduction by half), would be interesting.

Thx for this today! A principal observation of the BBR paper was that
you cannot measure for latency and bandwidth *at the same time* in a
single and you showing, in a FQ'd environment, that you can, I don'= t
remember seeing elsewhere (but I'm sure someone will correct me).

On Sun, Jul 3, 2022 at 7:16 AM Maximilian Bachl via Bloat
<bloat@= lists.bufferbloat.net> wrote:
>
> Hi Sebastian,
>
> Thank you for your suggestions.
>
> Regarding
> a) I slightly modified the algorithm to make it work better with the s= mall 5 ms threshold. I updated the paper on arXiv; it should be online by T= uesday morning Central European Time. Detection accuracy for Linux's fq= _codel is quite high (high 90s) but it doesn't work that well with smal= l bandwidths (<=3D10 Mbit/s).
> b) that's a good suggestion. I'm thinking how to do it best si= nce also every experiment with every RTT/bandwidth was repeated and I'm= not sure how to make a CDF that includes the RTTs/bandwidths and the repet= itions.
> c) I guess for every experiment with pfifo, the resulting accuracy is = a true negative rate, while for every experiment with fq* the resulting acc= uracy is a true positive rate. I updated the paper to include these terms t= o make it clearer. Summarizing, the true negative rate is 100%, the true po= sitive rate for fq is >=3D 95% and for fq_codel it's also in that ra= nge except for low bandwidths.
>
> In case you're interested in reliable FQ detection but not in the = combination of FQ detection and congestion control, I co-authored another p= aper which uses a different FQ detection method, which is more robust but h= as the disadvantage of causing packet loss (Detecting Fair Queuing for Bett= er Congestion Control (https://arxiv.org/abs/2010.08362)).
>
> Regards,
> Max
> _______________________________________________
> Bloat mailing list
> Bloat= @lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat


--
FQ World Domination pending: https://blog.cerowrt.or= g/post/state_of_fq_codel/
Dave T=C3=A4ht CEO, TekLibre, LLC
--000000000000a0b70c05ead9d28f--