CAKE w/ Adaptive Bandwidth [October 2021 to September 2022]

[moeller0]

I still do not undersand what the novel part is (had to pause the video for family reasons, will take a ew hours to find time to finish the last 50 minutes or so)

[stry]

So I made the change to the script and I'm now getting more consistent speed with max_delta_RTT= set to 50. Oscillation at peak bandwidth seems to be at an interval of about 20 secs.

Definitely a positive result. More stable speed and less overshoot on the up's and downs.

[Lynx]

Any chance you could provide some data?

You should try the lua version and compare. A lot of work has gone into that.

[moeller0]

Great talk. Now funnily he takes knowledge of the bottleneck rate as a given, indicating his solution might not be ideal for variable rate links, which he openly described as such in the talk.
He did offer though an elegant solution for the 'curse of delay based congestion control approaches', or rather to detect when one gets punished for being too reactive to be able to switch modes to less reactive to not get crowded out by less considerate competitors.

[Lynx]

Yesterday I developed a new branch of the shell code (experimental-rapid-tick), which employs simply regular RTTs, but in which the pings are now made asynchronous with the main loop. By spacing out the regular pings temporally, it is possible to vastly increase the tick rate. The main loop reacts to the higher frequency, spaced out pings as they become available.

As it is based on the 'experimental' branch, this branch keeps the CAKE bandwidth at a set base bandwidth absent load. Excursions are permitted from the base bandwidth in dependence upon load and RTT deltas, and, following an excursion, without load the bandwidth will decay back to the base bandwidths.

However, unique to this branch excursions have now been made subject to hard minimum and maximum bounds. For asymmetric cases such as mine where upload is rather more tightly bound than download, the loss of directionality does not seem to degrade performance significantly.

It still needs optimizing, but seems promising. The rate adjustment parameters need tweaking for the connection / tick rate. I still need to make these dependent upon tick rate.

It is available here for anyone interested to try it out:

GitHub - lynxthecat/sqm-autorate at experimental-rapid-tick

[Reeves0724]

#!/bin/sh

# automatically adjust bandwidth for CAKE in dependence on detected load and RTT

# inspired by @moeller0 (OpenWrt forum)
# initial sh implementation by @Lynx (OpenWrt forum)
# requires packages: iputils-ping, coreutils-date and coreutils-sleep

debug=1

enable_verbose_output=1 # enable (1) or disable (0) output monitoring lines showing bandwidth changes

ul_if=wan # upload interface
dl_if=ifb4wan # download interface

max_ul_rate=37000 # maximum bandwidth for upload
min_ul_rate=35000 # minimum bandwidth for upload

max_dl_rate=37000 # maximum bandwidth for download
min_dl_rate=35000 # minimum bandwidth for download

tick_duration=16 # seconds to wait between ticks

alpha_RTT_increase=0.005 # how rapidly baseline RTT is allowed to increase
alpha_RTT_decrease=0.9 # how rapidly baseline RTT is allowed to decrease

rate_adjust_RTT_spike=0.05 # how rapidly to reduce bandwidth upon detection of bufferbloat
rate_adjust_load_high=0.005 # how rapidly to increase bandwidth upon high load detected
rate_adjust_load_low=0.0025 # how rapidly to decrease bandwidth upon low load detected

load_thresh=0.5 # % of currently set bandwidth for detecting high load

max_delta_RTT=50 # increase from baseline RTT for detection of bufferbloat

# verify these are correct using 'cat /sys/class/...'
case "${dl_if}" in
    \veth*) 
        rx_bytes_path="/sys/class/net/${dl_if}/statistics/tx_bytes"
    	;;
    \ifb*) 
        rx_bytes_path="/sys/class/net/${dl_if}/statistics/tx_bytes"
    	;;
    \wan*) 
        rx_bytes_path="/sys/class/net/${dl_if}/statistics/rx_bytes"
	;;
esac

case "${ul_if}" in
    \veth*) 
        tx_bytes_path="/sys/class/net/${ul_if}/statistics/rx_bytes"
    	;;
    \ifb*) 
        tx_bytes_path="/sys/class/net/${ul_if}/subsystem/br-lan/statistics/rx_bytes"
    	;;
    \wan*) 
        tx_bytes_path="/sys/class/net/${ul_if}/statistics/tx_bytes"
	;;
esac

if [ "$debug" ] ; then
    echo "rx_bytes_path: $rx_bytes_path"
    echo "tx_bytes_path: $tx_bytes_path"
fi


# list of reflectors to use
read -d '' reflectors << EOF
1.1.1.1
8.8.8.8
71.10.216.1
71.10.216.2
EOF

RTTs=$(mktemp)

# get minimum RTT across entire set of reflectors
get_RTT() {

for reflector in $reflectors;
do
        echo $(/usr/bin/ping -i 0.00 -c 10 $reflector | tail -1 | awk '{print $4}' | cut -d '/' -f 2) >> $RTTs&
done
wait
RTT=$(echo $(cat $RTTs) | awk 'min=="" || $1 < min {min=$1} END {print min}')
> $RTTs
}


call_awk() {
  printf '%s' "$(awk 'BEGIN {print '"${1}"'}')"
}

get_next_shaper_rate() {
    local cur_delta_RTT
    local cur_max_delta_RTT
    local cur_rate
    local cur_rate_adjust_RTT_spike
    local cur_max_rate
    local cur_min_rate
    local cur_load
    local cur_load_thresh
    local cur_rate_adjust_load_high
    local cur_rate_adjust_load_low
    
    local next_rate
    
    cur_delta_RTT=$1
    cur_max_delta_RTT=$2
    cur_rate=$3
    cur_rate_adjust_RTT_spike=$4
    cur_max_rate=$5
    cur_min_rate=$6
    cur_load=$7
    cur_load_thresh=$8
    cur_rate_adjust_load_high=$9
    cur_rate_adjust_load_low=${10}


	# in case of supra-threshold RTT spikes decrease the rate unconditionally
	if awk "BEGIN {exit !($cur_delta_RTT >= $cur_max_delta_RTT)}"; then
	    next_rate=$( call_awk "int(${cur_rate} - ${cur_rate_adjust_RTT_spike} * (${cur_max_rate} - ${cur_min_rate}) )" )
        else
	    # ... otherwise take the current load into account
	    # high load, so we would like to increase the rate
	    if awk "BEGIN {exit !($cur_load >= $cur_load_thresh)}"; then
                next_rate=$( call_awk "int(${cur_rate} + ${cur_rate_adjust_load_high} * (${cur_max_rate} - ${cur_min_rate}) )" )
	    else
	        # low load gently decrease the rate again
		        next_rate=$( call_awk "int(${cur_rate} - ${cur_rate_adjust_load_low} * (${cur_max_rate} - ${cur_min_rate}) )" )
        fi
	fi

	# make sure to only return rates between cur_min_rate and cur_max_rate
        if awk "BEGIN {exit !($next_rate < $cur_min_rate)}"; then
            next_rate=$cur_min_rate;
        fi

        if awk "BEGIN {exit !($next_rate > $cur_max_rate)}"; then
            next_rate=$cur_max_rate;
        fi
        echo "${next_rate}"
}


# update download and upload rates for CAKE
function update_rates {
        cur_rx_bytes=$(cat $rx_bytes_path)
        cur_tx_bytes=$(cat $tx_bytes_path)
        t_cur_bytes=$(date +%s.%N)
        
        rx_load=$( call_awk "(8/1000)*(${cur_rx_bytes} - ${prev_rx_bytes}) / (${t_cur_bytes} - ${t_prev_bytes}) * (1/${cur_dl_rate}) " )
   	tx_load=$( call_awk "(8/1000)*(${cur_tx_bytes} - ${prev_tx_bytes}) / (${t_cur_bytes} - ${t_prev_bytes}) * (1/${cur_ul_rate}) " )

        t_prev_bytes=$t_cur_bytes
        prev_rx_bytes=$cur_rx_bytes
        prev_tx_bytes=$cur_tx_bytes

	# calculate the next rate for dl and ul
	cur_dl_rate=$( get_next_shaper_rate "$delta_RTT" "$max_delta_RTT" "$cur_dl_rate" "$rate_adjust_RTT_spike" "$max_dl_rate" "$min_dl_rate" "$rx_load" "$load_thresh" "$rate_adjust_load_high" "$rate_adjust_load_low" )
	cur_ul_rate=$( get_next_shaper_rate "$delta_RTT" "$max_delta_RTT" "$cur_ul_rate" "$rate_adjust_RTT_spike" "$max_ul_rate" "$min_ul_rate" "$tx_load" "$load_thresh" "$rate_adjust_load_high" "$rate_adjust_load_low" )



        if [ $enable_verbose_output -eq 1 ]; then
                printf "%s;%14.2f;%14.2f;%14.2f;%14.2f;%14.2f;%14.2f;%14.2f;\n" $( date "+%Y%m%dT%H%M%S.%N" ) $rx_load $tx_load $baseline_RTT $RTT $delta_RTT $cur_dl_rate $cur_ul_rate
        fi
}

get_baseline_RTT() {
    local cur_RTT
    local cur_delta_RTT
    local last_baseline_RTT
    local cur_alpha_RTT_increase
    local cur_alpha_RTT_decrease
    
    local cur_baseline_RTT
    
    cur_RTT=$1
    cur_delta_RTT=$2
    last_baseline_RTT=$3
    cur_alpha_RTT_increase=$4
    cur_alpha_RTT_decrease=$5
        if awk "BEGIN {exit !($cur_delta_RTT >= 0)}"; then
		cur_baseline_RTT=$( call_awk "( 1 - ${cur_alpha_RTT_increase} ) * ${last_baseline_RTT} + ${cur_alpha_RTT_increase} * ${cur_RTT} " )
        else
		cur_baseline_RTT=$( call_awk "( 1 - ${cur_alpha_RTT_decrease} ) * ${last_baseline_RTT} + ${cur_alpha_RTT_decrease} * ${cur_RTT} " )
        fi
    
    echo "${cur_baseline_RTT}"
}



# set initial values for first run

get_RTT

baseline_RTT=$RTT;

cur_dl_rate=$min_dl_rate
cur_ul_rate=$min_ul_rate
# set the next different from the cur_XX_rates so that on the first round we are guaranteed to call tc
last_dl_rate=0
last_ul_rate=0


t_prev_bytes=$(date +%s.%N)

prev_rx_bytes=$(cat $rx_bytes_path)
prev_tx_bytes=$(cat $tx_bytes_path)

if [ $enable_verbose_output -eq 1 ]; then
        printf "%25s;%14s;%14s;%14s;%14s;%14s;%14s;%14s;\n" "log_time" "rx_load" "tx_load" "baseline_RTT" "RTT" "delta_RTT" "cur_dl_rate" "cur_ul_rate"
fi

# main loop runs every tick_duration seconds
while true
do
        t_start=$(date +%s.%N)
	get_RTT
	delta_RTT=$( call_awk "${RTT} - ${baseline_RTT}" )
	baseline_RTT=$( get_baseline_RTT "$RTT" "$delta_RTT" "$baseline_RTT" "$alpha_RTT_increase" "$alpha_RTT_decrease" )
        update_rates

	# only fire up tc if there are rates to change...
        if [ "$last_dl_rate" -ne "$cur_dl_rate" ] ; then
    	    #echo "tc qdisc change root dev ${dl_if} cake bandwidth ${cur_dl_rate}Kbit"
    	    tc qdisc change root dev ${dl_if} cake bandwidth ${cur_dl_rate}Kbit
        fi
        if [ "$last_ul_rate" -ne "$cur_ul_rate" ] ; then
    	    #echo "tc qdisc change root dev ${ul_if} cake bandwidth ${cur_ul_rate}Kbit"
    	    tc qdisc change root dev ${ul_if} cake bandwidth ${cur_ul_rate}Kbit
        fi
        # remember the last rates
	last_dl_rate=$cur_dl_rate
	last_ul_rate=$cur_ul_rate

        t_end=$(date +%s.%N)
	sleep_duration=$( call_awk "${tick_duration} - ${t_end} + ${t_start}" )
        if awk "BEGIN {exit !($sleep_duration > 0)}"; then
                sleep $sleep_duration
        fi
done

This is really good for docsis 3.1 spent lots of hours to get here lol... Performance in games is amazing just saying!!!!

[Lynx]

To be fair with those rates you may as well just set CAKE fixed on upload and download to 35MBit/s - the 2 Mbit/s is not worth the bufferbloat risk.

[Reeves0724]

ok tks i appreciate you very much!!!!

[Lynx]

To verify, just set bandwidth to 35 Mbit/s in CAKE then download three .ISO files simultaneously - let the downloads reach their limit, and make sure you don't see any ping increase when running the waveform bufferbloat tests here:

Bufferbloat Test by Waveform

The ping should remain steady throughout, and at all times of the day, with different congestion etc.

Otherwise 35 Mbit/s is too high

Keep us posted.

[tievolu]

I just added over 13,000 reflectors to my list.

I think that's probably enough for now

Edit: I also added country codes (where available) taken from https://db-ip.com/db/download/ip-to-country-lite

tievolu/timestamp-reflectors/blob/main/reflectors.csv

[AlanDias17]

So I've a fiber connection link speed 10mbps both ingress and egress but for google services like YouTube, drive etc I get whooping 100mbps speed. I tried this adaptive bandwidth script to see how well it can handle/shape the bandwidth without the bufferbloat. I know this script isn't made for this purpose but even though when I did changes like below:

ul_if=pppoe-wan # upload interface
dl_if=br-lan # download interface

max_ul_rate=96000 # maximum bandwidth for upload
min_ul_rate=9800 # minimum bandwidth for upload

max_dl_rate=96000 # maximum bandwidth for download
min_dl_rate=9800 # minimum bandwidth for download

tick_duration=1 # seconds to wait between ticks

alpha_RTT_increase=0.001 # how rapidly baseline RTT is allowed to increase
alpha_RTT_decrease=0.9 # how rapidly baseline RTT is allowed to decrease

rate_adjust_RTT_spike=0.05 # how rapidly to reduce bandwidth upon detection of bufferbloat
rate_adjust_load_high=0.005 # how rapidly to increase bandwidth upon high load detected
rate_adjust_load_low=0.0025 # how rapidly to decrease bandwidth upon low load detected

load_thresh=0.5 # % of currently set bandwidth for detecting high load

max_delta_RTT=10 # increase from baseline RTT for detection of bufferbloat

But for some reason the speed never goes beyond 9800kbps when it's under heavy load.
Also when I use SQM my game feel a little sluggish. With no SQM in idle gameplay is smooth and shots are instant at 12ms ping

[dlakelan]

@AlanDias17

speed never goes beyond 9800kbps

Well you have 10Mbps access to the internet so yeah that's what you expect. In fact this minimum is way too high, it should be more like 5000.

[AlanDias17]

@dlakelan

it should be more like 5000

But the bufferbloat test shows A+ ? Also I tried setting it to 3000kbps. The speed stayed the same never went above 3000

[moeller0]

@AlanDias17

max_delta_RTT=10 # increase from baseline RTT for detection of bufferbloat

Probably this is too small.

Here is what I would do to figure out a usable max_delta_RTT (see https://forum.openwrt.org/t/cake-w-adaptive-bandwidth/108848/2288?u=moeller0):

1. install gping on one of your computers

2. running gping -b 60 8.8.8.8 somewhere, where you can see it

3. rund a speedtest (e.g. fast.com configured like:
   

   

4. look at how the delay changed from its baseline during both the download and upload section of the test. That will give you an idea how much your RTT changes under load and also how much it fluctuates without load. Pick max_delta_RTT such that true saturating loads yield higher RTT increases, but the normal fluctuation without load stays below this value.

[AlanDias17]

[moeller0]

The gping result looks terrible... but I think 8.8.8.8 might not be the correct reflector, instead use one of the reflectors you used in the script (or use gping towards the fastest of the reflectors you used in the script).

[AlanDias17]

@moeller0

but I think 8.8.8.8 might not be the correct reflector

I used 1.1.1.1 lol not 8.8.8.8 I'll try with 8.8.8.8 too. Wait..

Btw tested with SQM disabled

Under load ping stays stable around 80ms (initially 4ms) for 1.1.1.1 but for 8.8.8.8 there's no difference 3ms (I get higher speed for google servers)

[_FailSafe]

Who is your ISP? That preferential shaping (preferring Google servers) is really unfortunate. I have other opinions about that which I will save for another day and another thread.

[moeller0]

Mmmh so gping defaults to fast ping (0.2seconds interval) and looks much worse than the windows ping, but that is considerably slower (1second) can you play with slow and fast ping from a unix host like your router (this requires iputils-ping, in case you do not have that use opkg update ; opkg install iputils-ping):
#slow:
time ping -i 1 -c 100 8.8.8.8
#fast:
time ping -i 0.2 -c 100 8.8.8.8

And do this with and without saturating your network, please.

[moeller0]

Also, please post the output of:
mtr -ezbw -c 100 1.1.1.1
mtr -ezbw -c 100 8.8.8.8

to get an idea how these paths actually look. (Yes we only see one direction, but at least that is a start)