CAKE w/ Adaptive Bandwidth [August 2022 to March 2024]

moeller0 · 2023-07-29T17:00:26.074Z

Lynx:

shaper_rate_max_adjust_down_bufferbloat=0.90 # how rapidly to reduce shaper rate upon detection of bufferbloat

That is the one... as we know that even for a fixed rate our shaper setting might be off by 100-75=25% we should be prepared to undo all of that damage in one swoop, no? Especially with the adaptive reduction step size this maximal reduction step should rarely materialize...
Alternatively we could simply increase the load% on which we increase the shaper rate from 75 to 80% then the 0.9 default above would give us the maximally 50% reduction step...
This is likely going to be in the noise (the true over-setting of the shaper is somewhere between the limits). Just keep this in mind as something to test...

Lynx:

Crude test:

Hard to interpret... this functionality is not a 'game-changer' but also does not seem to be worse than the old method if appropriately configured...
I think it might be time to give this a longer time test and see how it feels and preforms in daily use, especially with your dual 4K streaming use-case, or 4K streaming while video conferencing...

Lynx · 2023-07-29T17:03:27.340Z

So from my testing:

shaper_rate_max_adjust_down_bufferbloat=0.75

seems to work well - shall I make that the default?

Here is a run with the present defaults, but with the above change.

Waveform

Bufferbloat Test Result: B

View the full results, and test your own bufferbloat

Any other changes to defaults? The defaults right now favour bufferbloat B and circa 200ms for 95th percentile latency, at least on my connection. I think that represents a good compromise between latency and bandwidth. Naturally the latter only really applies during high load. During normal use (light browsing, etc.) cake-autorate will dial things back to the base bandwidth.

Few more tests in the post above by the way.

moeller0 · 2023-07-29T17:32:23.218Z

Lynx:

seems to work well - shall I make that the default?

I would really think this needs some testing fiirst. As I tried to explain I think setting this to the same value as high_load_thr=0.75 # % of currently set bandwidth for detecting high load makes theoretical sense, and how hard it bites really depends on how Xl_avg_owd_delta_thr_ms is set...
Looking at traces I think that during rate ramp ups the achieved load stays in the 75% of shaper rate regime... once we hit the maximum rate that obviously is not true any more, but even then if there was a steep step (with resulting high delays) we want a noticeable drop in shaper rate...

I guess this could use some testing with the maximum rate set lowish so that this condition triggers often enough to be able to get a feel whether a 25%-age point rate drop is acceptable here...

Lynx · 2023-07-29T17:41:23.075Z

Added to the 'improve-controller' branch for incorporating in the draft pull request for now:

github.com/lynxthecat/cake-autorate

Improve controller

lynxthecat:master ← lynxthecat:improve-controller

opened 10:38AM - 28 Jul 23 UTC

lynxthecat

+73 -26

This pull request is intended to capture improvements to the controller includin…g detection of bufferbloat and adjustments to the shaper rates. Addresses https://github.com/lynxthecat/cake-autorate/issues/225.

All such changes can be easily undone or tweaked now that I've got a reasonable understanding of how to use git (via /tmp on my router - go OpenWrt!).

dlakelan · 2023-07-29T17:47:54.016Z

Another way to go would be to keep statistics on how much time you spend bufferbloated, and how much bandwidth you achieve during bandwidth seeking periods, and then try to "learn" the best values for the parameters that maximize the "utility" of the achieved controller performance.

One way to potentially do this would be via offline learning... Collect the data and output it to csv files, have a periodic process that does the estimate of the "ideal" parameter values, and then writes a new config file and restarts the autorate.

The offline process could be done in a separate language. Though I still think there's not much available where it'd be "fun" to write that in a way it could run on a resource constrained router. Python would probably be your best bet, but if you're going to install python then you might as well do the whole thing in python.

You could try to do some online algorithm in bash, where during bufferbloat you accumulate "points against" and during bandwidth seeking you accumulate points-for in proportion to the achieved bandwidth, and then you adjust the down-step to larger step size if you get too many points against, and you adjust the up-step upward if you get too few points for, and you try to maximize the points for - points against or something. You'd need to have rules for both increasing and decreasing the step sizes otherwise it's a ratchet.

Lynx · 2023-07-29T17:55:07.999Z

That makes me think of the remote SQM concept evenroute seem to have in mind:

IQrouter

And reminds me about the discussion we had about their patent application and the anonymous third-party observations I raised against it back in December 2021.

patents.google.com

WO2017058657A1 - Automatic qos optimization in network equipment -...

Systems, methods, and software for automatically optimizing QoS configuration in networking equipment. A network device determines performance measurements for a network connection of the network device. The performance measurements are sent by...

https://register.epo.org/application?number=EP16852344&lng=en&tab=doclist

The Examiner actually ran with my argument:

image796×332 25.7 KB

And since then there has not been much activity - looks like this application might ultimately get abandoned.

dtaht · 2023-07-30T02:08:22.321Z

I enjoy everyone´s enthusiasm here. I was wondering if minstrelś drunken walk had been fiddled with?

blog.cerowrt.org

On the Minstrel Wifi Rate Controller - http://blog.cerowrt.org/

Wireless rate selection is *hard* and deeply misunderstood...

moeller0 · 2023-07-30T09:06:07.556Z

I am not sure minstrel is facing a similar enough problem to be closely applicable here. In WiFi you need to pick a modulation coding scheme for any individual transmission, but the flip side is that on every transmission you essentially can pick one as you desire, allowing you to test hypothesis (like MCS N worked OK, MCS N+2 probably does not, so see whether that is true) and/or build a database of known working MCS schemes in the recent past (which on a high level is close to what @dlakelan proposed/described above). And if you intersperse a MCS 1 transmission into a series of MCS 99 (making up numbers here as usual), the average rate will still heavily skew towards MCS 99 and a few tested hypothesis (transmissions at higher or lower rates) will not result in feed-back to the traffic sources.
Autorate does not really have that luxury, any change will take quite a while before its consequences are known, and for some changes the real consequences are never known (think the shaper gets set to X, the bottleneck rate is at Y but the organic load at Z, if X > Y > Z we might think that X was a useful shaper setting, sure looking at the achieved rate can offer heuristics of disambiguating such situations somewhat, but that is still different from WiFi where an MCS is tried and there will be an ACK telling the sender whether the transmission was received correctly).
Or, I might simply be to narrow-eyedly focused on the current approach to see what to 'scavenge' from minstrel?

Lynx · 2023-07-30T09:39:24.127Z

The thought just struck me. Right now we compensate the OWD delta thresholds for low bandwidth. Should we do the same with the average OWD delta thresholds?

github.com

lynxthecat/cake-autorate/blob/20ee39ade74ef1332e56715b0d703375df5fe510/cake-autorate.sh#L1556


      
          	# atm compensation = 53*ceil(X/48) bytes = 8*53*((X+8*(48-1)/(8*48)) bits = 424*((X+376)/384) bits
          	[[ "${BASH_REMATCH[1]:-}" == "atm" ]] && max_wire_packet_size_bits=$(( 424*((max_wire_packet_size_bits+376)/384) ))
          }
          
          update_max_wire_packet_compensation()
          {
          	# Compensate for delays imposed by active traffic shaper
          	# This will serve to increase the delay thr at rates below around 12Mbit/s
          
          	# compensated OWD delay thresholds in microseconds
          	compensated_dl_owd_delta_thr_us=$(( dl_owd_delta_thr_us + (1000*dl_max_wire_packet_size_bits)/shaper_rate_kbps[dl] ))
          	compensated_ul_owd_delta_thr_us=$(( ul_owd_delta_thr_us + (1000*ul_max_wire_packet_size_bits)/shaper_rate_kbps[ul] ))
          
          	max_wire_packet_rtt_us=$(( (1000*dl_max_wire_packet_size_bits)/shaper_rate_kbps[dl] + (1000*ul_max_wire_packet_size_bits)/shaper_rate_kbps[ul] ))
          	
          	printf "SET_VAR max_wire_packet_rtt_us %s\n" "${max_wire_packet_rtt_us}" >&"${maintain_pingers_fd}"
          }
          
          verify_ifs_up()
          {
          	# Check the rx/tx paths exist and give extra time for ifb's to come up if needed

moeller0 · 2023-07-30T09:58:07.598Z

Lynx:

Should we do the same with the average OWD delta thresholds?

This depends how low rates we consider to be par for the course... Let's start without doing this and just add it to the list of things to keep in mind as future modifications should issues arise...

Lynx · 2023-07-30T10:04:02.164Z

I feel it would help symmetry though. We'd add the same amount on I think?

And then add the average and compensated average to the DATA lines.

moeller0 · 2023-07-30T10:23:30.600Z

Lynx:

I feel it would help symmetry though. We'd add the same amount on I think?

Let's test this first, please, symmetry alone is not a good reason here...

Lynx · 2023-08-07T07:32:08.792Z

If anyone fancies testing out the latest cake-autorate code, we have implemented a few changes to the controller in cake-autorate that seem to improve performance - see: https://github.com/lynxthecat/cake-autorate/pull/248.

Results from a few comparative tests on a 4G connection can be seen here:

github.com/lynxthecat/cake-autorate

Comment by bairhys to Improve controller

lynxthecat:master ← lynxthecat:improve-controller

I did some back to back testing comparing v3.0.1 to this branch `improve-control…ler` and later no sqm. Testing setup was - `improve-controller` branch in /root/cake-autorate - I downloaded `3.0.1` release, put this at /root/cake-autorate-v.3.0.1, - changed `cake-autorate.sh` to look at folder `PREFIX=/root/cake-autorate-3.0.1` - both settings were same, see end of post for settings for both - 2 ssh sessions, left session to run `v3.0.1`, right to run `improve-controller` - 2 chrome windows, left for `v3.0.1` tests, right for `improve-controller` tests - after each test, switched cake-autorate version Results All results summarized here with a score given to all tests. I defined one as overall score `download speed` * `upload speed` / (`download lat` * `upload lat`) Then another as a throughput score `download speed` * `upload speed` And last as latency score `download lat` * `upload lat` | V3.0.1 | | | | | | | |--------------------|------|--------|--------|----------------------------------------------|--------------------------------|---------------------------------------| | dl | up | dl lat | ul lat | Rating 1 (dl*ul/dl_lat/ul_lat) higher better | Rating 2 (dl*ul) higher better | Rating 3 (dl_lat*ul_lat) lower better | | 66.7 | 5.64 | 17 | 14 | 1.5806218487395 | 376.188 | 238 | | 52.3 | 5.69 | 14 | 15 | 1.41708095238095 | 297.587 | 210 | | 65.8 | 8.25 | 18 | 14 | 2.15416666666667 | 542.85 | 252 | | 66.5 | 8.23 | 16 | 12 | 2.85049479166667 | 547.295 | 192 | | | | | TOTAL | 8.00236425945378 | 1763.92 | 892 | | improve-controller | | | | | | | | 73 | 5.7 | 19 | 13 | 1.68461538461538 | 416.1 | 247 | | 70.1 | 7.84 | 18 | 13 | 2.34864957264957 | 549.584 | 234 | | 68.6 | 8.25 | 16 | 14 | 2.5265625 | 565.95 | 224 | | 66.7 | 8.56 | 17 | 14 | 2.39895798319328 | 570.952 | 238 | | | | | TOTAL | 8.95878544045823 | 2102.586 | 943 | | No-sqm | | | | | | | | dl | up | dl lat | ul lat | | | | | 79.1 | 8.31 | 62 | 234 | 0.0453074855252275 | 657.321 | 14508 | The extra latency between the `improve-controller` and `v3.0.1` tests are similar even though `v3.0.1` is a bit better. `improve-controller` had slightly better throughput initially then they started to converge. Overall the difference in additional latency is minimal so based on throughput `improve-controller` looks to have a slight edge but need more tests to confirm. I could see this test becoming automated to give better and less time consuming long term test results. raw data test 1 `v3.0.1` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/c642fa1e-dd30-469e-b5f5-09acba9c965f) test 2 `improve-controller` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/d617716d-29ab-4205-974e-4d13c9d38d93) test 3 `v3.0.1` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/9226c752-8a52-4d5d-ba3c-7807df36ebb7) test 4 `improve-controller` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/35abb132-da02-4723-8b2e-3de6ba62856d) test 5 `v3.0.1` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/ba2e1527-f619-4a78-a75c-fca5a2475367) test 6 `improve-controller` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/1594d44e-91a5-40ad-beb7-fd7440138798) test 7 `v3.0.1` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/c8a8d508-08a5-450f-8e58-b40bd7abfee3) test 8 `improve-controller` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/290c714e-239e-4b0f-b750-d67b1954232f) test 9 `no-sqm` ![image](https://github.com/lynxthecat/cake-autorate/assets/33058425/8ac307e7-90f7-49f7-949f-ccccfc12b050) ``` #!/bin/bash # *** STANDARD CONFIGURATION OPTIONS *** output_processing_stats=1 # enable (1) or disable (0) output monitoring lines showing processing stats output_load_stats=1 # enable (1) or disable (0) output monitoring lines showing achieved loads output_reflector_stats=1 # enable (1) or disable (0) output monitoring lines showing reflector stats output_cake_changes=1 # enable (1) or disable (0) output monitoring lines showing cake bandwidth changes debug=1 # enable (1) or disable (0) out of debug lines ### For multihomed setups, it is the responsibility of the user to ensure that the probes ### sent by this instance of cake-autorate actually travel through these interfaces. ### See ping_extra_args and ping_prefix_string dl_if=ifb4wan # download interface ul_if=wan # upload interface # Set either of the below to 0 to adjust one direction only # or alternatively set both to 0 to simply use cake-autorate to monitor a connection adjust_dl_shaper_rate=1 # enable (1) or disable (0) actually changing the dl shaper rate adjust_ul_shaper_rate=1 # enable (1) or disable (0) actually changing the ul shaper rate min_dl_shaper_rate_kbps=30000 # minimum bandwidth for download (Kbit/s) base_dl_shaper_rate_kbps=50000 # steady state bandwidth for download (Kbit/s) max_dl_shaper_rate_kbps=100000 # maximum bandwidth for download (Kbit/s) min_ul_shaper_rate_kbps=4000 # minimum bandwidth for upload (Kbit/s) base_ul_shaper_rate_kbps=6000 # steady state bandwidth for upload (KBit/s) max_ul_shaper_rate_kbps=15000 # maximum bandwidth for upload (Kbit/s) # *** OVERRIDES *** randomize_reflectors=0 pinger_binary=tsping ```

The changes can be tested using:

./setup.sh lynxthecat/cake-autorate improve-controller

And to revert:

./setup.sh lynxthecat/cake-autorate master

If you previously specified a custom dl_delay_thr_ms or ul_delay_thr_ms those have changed to dl_owd_delta_thr_ms and ul_owd_delta_thr_ms , and in that case you may also want to specify your own values for dl_avg_owd_delta_thr_ms and ul_avg_owd_delta_thr_ms that are around twice whatever you set for the owd_delta_thr_ms values. Albeit the default values for both the owd delta thresholds and average owd delta thresholds (30ms and 60ms) will likely work fine on most connections.

moeller0 · 2023-08-07T08:04:13.828Z

To elaborate a tiny bit, instead of using a fixed shaper-rate reduction percentage on detected bufferbloat events, the new method will now linearly scale the reduction from zero % reduction to by default 25% reduction step IIRC once the measured average delta delay reaches Xl_avg_owd_delta_thr_ms.
So this actually allows to set Xl_delay_thr_ms a bit lower than before (as for low magnitude bufferbloat event the controller will only mildly change the rate if at all) setting Xl_avg_owd_delta_thr_ms is a bit trickier as the default reduction of 25%-age points is relatively large. The lower this number is the faster the "hammer" we apply scales up...
Personally my hunch is, that Xl_avg_owd_delta_thr_ms likely should not be set as a fixed fraction of Xl_delay_thr_ms, but rather as a fixed delay budget, but I have no intuition what exact number to plug in there. That said, my gut feeling is decent values probably are in the 10-50ms range.
For A/B testing, setting Xl_avg_owd_delta_thr_ms to zero should result in the old behavior of applying a fixed rate reduction percentage step.

Lynx · 2023-08-07T09:55:08.359Z

moeller0:

For A/B testing, setting Xl_avg_owd_delta_thr_ms to zero should result in the old behavior of applying a fixed rate reduction percentage step.

Yes it should:

github.com

lynxthecat/cake-autorate/blob/afcb283834c6852fd1c095b2cd72b8bbee652d0b/cake-autorate.sh#L381


      
          			shaper_rate_kbps["${direction}"]="${min_shaper_rate_kbps[${direction}]}"
          			;;
          		# download Starlink satelite switching compensation, so drop down to base rate for download through switching period
          		dl*sss)
          			shaper_rate_kbps["${direction}"]=$(( shaper_rate_kbps["${direction}"] > base_shaper_rate_kbps["${direction}"] ? base_shaper_rate_kbps["${direction}"] : shaper_rate_kbps["${direction}"] ))
          			;;
          		# bufferbloat detected, so decrease the rate providing not inside bufferbloat refractory period
          		*bb*)
          			if (( t_start_us > (t_last_bufferbloat_us["${direction}"]+bufferbloat_refractory_period_us) ))
          			then
          				if (( avg_owd_delta_thr_us["${direction}"] == 0 ))
          				then
          					shaper_rate_adjust_down_bufferbloat_factor=1000
          				elif (( avg_owd_delta_us["${direction}"] > 0 ))
          				then
          					shaper_rate_adjust_down_bufferbloat_factor=$(( (1000*avg_owd_delta_us["${direction}"])/compensated_avg_owd_delta_thr_us["${direction}"] ))
          					(( shaper_rate_adjust_down_bufferbloat_factor > 1000 )) && shaper_rate_adjust_down_bufferbloat_factor=1000
          				else
          					shaper_rate_adjust_down_bufferbloat_factor=0
          				fi
          				shaper_rate_adjust_down_bufferbloat=$(( 1000000-shaper_rate_adjust_down_bufferbloat_factor*(1000-shaper_rate_max_adjust_down_bufferbloat) ))

WNKLER · 2023-08-08T15:23:39.364Z

Is bandwidth-utilization the primary determinant of latency changes? Or, is it a proxy for some other underlying mechanism?

For instance:
Starting from a bufferbloated state, if utilization drops to zero (or below the bufferbloat threshold) should latency instantaneously return to normal? Or, is there something else upstream that needs to resolve first?

moeller0 · 2023-08-08T15:42:03.821Z

If latency increased because at the bottleneck link a queue built up, increased delay will persist* even if the continuous load sent to the bottleneck is below the (current) bottleneck rate until that queue is fully serviced (that is packets are either transmitted or dropped).

*) The magnitude of that queueing delay will change in accordance with the egress/ingress ratio of the queue. For variable rate links this can mean that if say the link rate jumps from 1 to 100 Mbps the existing queue might "evaporate" almost immediately, but that is the rare positive case (not worth/possible optimizing for since we only know after the fact).

Clap · 2023-08-09T08:38:32.795Z

I'm unable to test the following right now but would the cake_autorate script still work when the qdisc is set to fq_codel w/conspiring qos script or does it break the functionality of the autorate?

moeller0 · 2023-08-09T08:44:54.000Z

Clap:

when the qdisc is set to fq_codel w/conspiring qos script or does it break the functionality of the autorate?

So this script currently requires cake as traffic shaper otherwise it will not work. In theory this could be made to work with any of the other traffic shapers, like TBF, HTB, CBF, for a single tier shaper config this should work, but to change the rate in a 4 tier HTB shaper tree one would need to first adjust the rates of the leaf shapers and the the root shaper. ATM cake-autorate will not do this at all. (If you use a single tier-shaper adjusting this script should be relatively straight forward, but unlike with cake changing shaper rates on the fly has to my knowledge not been tested recently).

Lynx · 2023-08-12T19:02:33.727Z

Hey @moeller0, something I can't figure out is that if I set the cake bandwidth to unlimited in both directions and set my cake-autorate config so as not to adjust cake bandwidths and use tsping, I see the download OWD increase on download (to above 100ms) and the upload OWD only increase a little - as expected. But if I then set my cake-autorate config so as to adjust the cake bandwidths, then I see dramatic increases in the upload OWD (to above 100ms).

Any idea what might explain this? I presume it is something that my ISP is responsible for? Is there any sense in which drops on download could result in upload delays?