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

Lynx · 2021-10-19T21:09:19.867Z

Anyone know how to get pings to run in parallel? Would I need to fork each ping to background and output to tmp file and then read tmp file?

#!/bin/sh

read -d '' reflectors << EOF
1.1.1.1
8.8.8.8
EOF

no_reflectors=$(echo "$reflectors" | wc -l)

RTTs=$(mktemp)

for reflector in $reflectors;
do
        echo $(ping -i 0.2 -c 10 $reflector | tail -1 | awk '{print $4}' | cut -d '/' -f 2) >> $RTTs&
done
wait
echo $(cat $RTTs) | awk '{ total += $2; count++ } END { print total/count }'

Lynx · 2021-10-20T06:51:16.797Z

@moeller0 I am implementing your algorithm in ash using bc.

You proposed always updating the moving average of the RTT average to subtract from the current RTT average to get the delta RTT. I understand the point about setting alpha such that bufferbloat encountered will not unduly raise the baseline.

I just wanted to check with you your thoughts on not always updating the RTT average and only updating when load is below a threshold. If that would be better would you still recommend using exponential moving average with alpha for when it is updated?

Otherwise any comments on what I have so far?

root@OpenWrt:~/sqm-autorate# cat sqm-autorate
#!/bin/sh

read -d '' reflectors << EOF
1.1.1.1
8.8.8.8
EOF

no_reflectors=$(echo "$reflectors" | wc -l)

alpha=0.1

max_delta_RTT=20

rx_bytes_file="/sys/class/net/wan/statistics/rx_bytes"
tx_bytes_file="/sys/class/net/wan/statistics/tx_bytes"

RTTs=$(mktemp)

function get_avg_RTT {

for reflector in $reflectors;
do
        echo $(ping -i 0.2 -c 10 $reflector | tail -1 | awk '{print $4}' | cut -d '/' -f 2) >> $RTTs&
done
wait
avg_RTT=$(echo $(cat $RTTs) | awk '{ total += $2; count++ } END { print total/count }')
> $RTTs
}

get_avg_RTT

prev_avg_RTT=$avg_RTT;

while true
do
        t_start=$(date +%s)
        get_avg_RTT
        delta_RTT=$(echo "scale=2; $avg_RTT - $prev_avg_RTT" | bc)
        prev_avg_RTT=$(echo "scale=2;(1-$alpha)*$prev_avg_RTT+$alpha*$avg_RTT" | bc)
        echo $delta_RTT
        echo $max_delta_RTT
        if (echo "$delta_RTT > $max_delta_RTT" | bc -l); then
                echo "bufferbloat detected!!!"
        fi
        sleep 2 # work in progress 
done

moeller0 · 2021-10-20T07:06:47.758Z

Have a look at https://github.com/richb-hanover/OpenWrtScripts/blob/master/betterspeedtest.sh for how to handle pings in the background and how to robustify your script.

If you only update the reference RTT under load it will not reflect the shortest currently possible RTT and if you only update if the load is below a threshold you might not update it for a long time, if say you download a multi-gigabyte software update. But the proof is in the pudding here....

Lynx · 2021-10-20T11:13:25.429Z

Thanks. Will keep programming.

Am I right about the 82 above by the way?

moeller0 · 2021-10-20T12:33:40.094Z

It depends, when I run the numbers to get from the pre-encrypted IP payload to the full IP packet size:

ICMP payload + ICMP header + IPv4 header + plus documented wireguard per-acket overhead:
(pre-encrypted IP payload) + pre-encripted IP header + wireguard overhead
(1234 + 8) + 20 + 60 = 1322
which seems 2 byte shorter than what you measure, so I would go with your higher number (because to fight bufferbloat err on the side of too much overhead). cake on the pre-encrypted interface will handke the IP header size just fine, so 62 bytes is the number

But you still need to add the additional overhead on top of the encrypted encapsulated IP packet, which for LTE is complicated especially because it is unclear to me which oherhead we can safely ignore....

Lynx · 2021-10-20T13:11:04.619Z

I also came across this:

image1112×810 13 KB

semanticscholar.org

Table 1 from The LTE link-layer design | Semantic Scholar

Table 1. Protocol overhead in LTE assuming IPv4. - "The LTE link-layer design"

I used to actually work on Intel/Samsung LTE patent applications, but every single application was on one very detailed aspect. I recall so many hacks to make each new innovation work with the (revised) 3GPP standard. Anyway that was a fair while ago now.

I also have the fun complexity that I am applying CAKE to interfaces (veth-lan for download, and wan for upload) that see both WireGuard and non-WireGuard traffic.

So presumably I should go for worst case with VPN and should set 82 + 10 = 92? Or just 100 because it is a nice number and with this variable and uncertain 4G LTE connection, approximation rather than precision seems apt?

Very much enjoying working on this script. Thank you so much for taking the trouble to write out the algorithm above. I feel fairly confident this will get something that roughly works.

Perhaps I should use this as an opportunity to try github. I have some experience in C and C++, even though I opted for a different career path than one involving programming.

moeller0 · 2021-10-20T13:47:01.858Z

Interesting, but ROHC does not seem to guarantee a strict header size, but then according to your plot and the wikipedia article it might actually result in less size then the full (outer) IP packet... I just have no clue how to test whether it is actually in use... but assuming ROHC is used, then your 82+10 should be on the safe side....

Lynx:

I used to actually work on Intel/Samsung LTE patent applications, but every single application was on one very detailed aspect. I recall so many hacks to make each new innovation work with the (revised) 3GPP standard. Anyway that was a fair while ago now.

See, you are the resident LTE expert then (as demonstrated by the helpful chart above)

Lynx:

Thank you so much for taking the trouble to write out the algorithm above.

Well, that is the easy part, implementing it and addressing all the ignored corner-cases to make it robust is the real work.

dlakelan · 2021-10-20T13:47:41.976Z

moeller0:

unless we can differentiate 
		between ingress and egress congestion, we need to reduce both shapers:

I think the suggestion is to increase them separately but decrease together. That's A fairly reasonable approach. It may be problematic if there is a lot of asymmetry on the line. If we had a reasonably powerful language I might suggest to do something like a logistic regression on bufferbloat as a function of up and down bandwidth over the last 5 mins of data and set bandwidth to the value that results in say 1% chance.

But definitely not in shell script!!

On an RPi you could do all this in Julia quite nicely, you could run pings in a separate thread, read the bandwidth file every say 500msec and get a nice time series of bandwidth vs ping time. You could fit a logistic regression every minute and store that info permanently, from that you could Estimate a function of time of day, if there's A reasonable pattern. The time of day function could set a prior for a Bayesian estimate based on last minute of current actuals, then you could just immediately jump to the "optimal" BW...

Doing something like that in shell would require some serious pain meds

Lynx · 2021-10-20T13:54:24.149Z

Lynx:

echo $(ping -i 0.2 -c 10 $reflector | tail -1 | awk '{print $4}' | cut -d '/' -f 2) >> $RTTs&

Lynx:

avg_RTT=$(echo $(cat $RTTs) | awk '{ total += $2; count++ } END { print total/count }')

Lynx:

prev_avg_RTT=$(echo "scale=2;(1-$alpha)*$prev_avg_RTT+$alpha*$avg_RTT" | bc)

But aren't lines like the above just so much fun ! It's like brute force wins sometimes. With enough determination and grit.

dlakelan:

I think the suggestion is to increase them separately but decrease together.

Thank you for this suggestion. Makes sense to me. Only increase if there is bandwidth demand, and upon detection of bufferbloat we scale both down.

dlakelan:

If we had a reasonably powerful language I might suggest to do something like a logistic regression on bufferbloat as a function of up and down bandwidth over the last 5 mins of data and set bandwidth to the value that results in say 1% chance.

Seems intriguing, but I have always favoured simple hacks. I used to work in an organisation with two groups: 'Advanced Signal and Information Processing' and 'Pattern and Information Processing'. The former just hacked stuff together and got things to work. The latter spent ages working on these funky Bayesian models and stuff, but the processing was so difficult and hard to get to work in real time.

moeller0 · 2021-10-20T13:56:16.746Z

dlakelan:

I think the suggestion is to increase them separately but decrease together. That's A fairly reasonable approach.

Good point.

dlakelan:

But definitely not in shell script!!

+1; but for normal consumer routers, I believe only stuff like sh, awk, lua are realistic options, for raspberries however I agree, all of python, julia, R or even octave would be options... but even then I would probably first see how far one gets with a limited set of heuristics (like changing thresholds based on the current tie of day, day-of week or similar)

dlakelan:

Doing something like that in shell would require some serious pain meds

I fully agree. A much simpler design however seems possible, and maybe that could be good enough?

dlakelan · 2021-10-20T13:58:27.034Z

Lynx:

processing was so difficult and hard to get to work in real time.

Yes if a simple hack works go for it. However an Rpi4 has a ton of processor power. With 4 cores at 1400 MHz. Fitting a logistic regression to a hundred data points or so should take maybe 10 milliseconds.

moeller0 · 2021-10-20T13:58:36.470Z

Lynx:

The latter spent ages working on these funky Bayesian models and stuff, but the processing was so difficult and hard to get to work in real time.

I think for the shaper adjuster our real-time demands are in the "within a few seconds" range which might allow bayesian trickery (and I like about a Bayesian approach how we can simply feed the last posterior into the new posterior)

Lynx · 2021-10-20T13:59:26.354Z

moeller0:

but even then I would probably first see how far one gets with a limited set of heuristics (

I did suppose cron job that issues 'tc change' calls at different times of the day might work well enough. But feels like a cop out / just intellectually unsatisfactory. And in fairness congestion is variable. I haven't measured. Only observe that around 4pm onwards the available bandwidth tends to reduce until perhaps around 10pm or something. Presumably with LTE connection hinges upon a lot of different factors. Like how many individuals are within the cell tower and streaming Lady Gaga on Amazon Music during their commute.

moeller0:

+1; but for normal consumer routers, I believe only stuff like sh, awk, lua are realistic options, for raspberries

My RT3200 (only £80 on Amazon) seems to have lots of spare CPU cycles and RAM, at least since I only have max 80Mbit/s. I read in another thread with irqbalance it can even handle 1Gbit sqm.

And thank you @moeller0 and @dlakelan for your continued insights. Have been enjoying this tremendously.

dlakelan · 2021-10-20T14:12:36.515Z

Its possible with a detailed dataset, to develop an algorithm using something like Julia, and then code it into a compiled binary using maybe a C program. A shell script could collect data and every 20 seconds ask the C oracle what speed to set.

Lynx · 2021-10-20T14:14:00.415Z

Didn't think of that. Reminds me that I used to write mex code for Matlab. Those 'dll' files would get called for the intense operations. Hmm.

Fast

Julia was designed from the beginning for high performance.

Am I the only one immature enough to find the idea of giving a girl's name to a programming language rather curious. She has been designed for high performance and interactive use. Are some of the comments here:

julialang.org

The Julia Programming Language

The official website for the Julia Language. Julia is a language that is fast, dynamic, easy to use, and open source. Click here to learn more.

written with even a degree of humour?

The CAKE was only half baked, but then we put Julia into action!

dlakelan · 2021-10-20T14:26:25.536Z

The Julia developers claim its not named after anything. I always think of the fractals... The Julia con has an explicit code of conduct to not anthropomorphize it due to inclusive considerations...

Lynx · 2021-10-20T14:28:15.252Z

Oh man, that stuff even creeps into the domain of programming languages. There's no escape!

dlakelan · 2021-10-20T14:31:57.516Z

Anyway, I think collecting a days worth of data and take a look at it might be a worthwhile step. Your existing shell script if it logged time and BW to a file and ping time to a file... Could be enough

moeller0 · 2021-10-20T15:24:13.716Z

IMHO most of these codes of conduct boil down to: behave like a sensible human being and treat others with courtesy and respect. Personally I can get behind that message quite easily (after all that is what parents, school and society taught me to be desirable behavior in the first place)

slh · 2021-10-20T20:52:59.991Z

moeller0:

but for normal consumer routers, I believe only stuff like sh, awk, lua are realistic options

I wouldn't write new code in lua, luci is slowly migrating away from lua to client side javascript, once that covers the base luci package set, there's no reason to install lua on OpenWrt anymore. That won't happen over night, but it's progressing piece by piece, steadily.