Also general question. Concerning Netflix and Prime sending periodic spikes. Is there a situation in which I would want to increase download to offer more bandwidth for those spikes but the load will be less than half my minimum over the sample duration? Or if Netflix/Prime need more bandwidth do they just increase the width and/or frequency of those spikes such that it will still over my sample duration eat up the load needed to trigger an increase? Obviously so long as I am satisfying the Netflix/Prime 4K demand there is no need to increase.
I guess I am trying to work out if just working with cumulative bandwidth over the sample duration is sufficient or I should also be reacting to things hitting the ceiling in a periodic way. Hmm.
I think for solid file downloads / OneDrive uploads etc the load increases will trigger as they should.
Will test properly later with the actual tc qdisc calls.
So I would move the sleep into the main loop, just after the call to tc to update the rates.
Traditionally in networking, data volume has been measured in true si-units, so K being 1000, not 2^10=1024, but in the end that is your choice; as long as you convert and use the units consciously both should work. (Personally, having 10 fingers and not just 2, I like base10 better than base2, so would stick to KBps instead of KiBps, heck, I probably would convert to kilo-bit-per-second so that the values are in the same unit as SQM's rate settings, which are in Kbps).
You need to measure that, but you can always fine-tune your xx_load_thresh values and or the time you run the loop (BTW, as you probably know, making the period smaller than the expected ping train duration for all targets makes the sleep call superflous)
I do not know, but I would expect that if they can not refill their buffers X milliseconds before that buffer runs out, they are going to request a lower sending rate/lower quality, how that relates to your parameters I do not know.
Yes, but the devil is in the details, so you would need to know the buffer low water-marks Netflix uses to decide when to scale quality up or down... (which with variable rate codecs might not even be invariant over time).
I would guess that this is equivalent to just lowering your load_thresholds, at least as first approximation, no?
Hey @moeller0, so far so good with the tc qdisc calls. Looking extremely promising to me. Nice for me to see how high my LTE bandwidth can go.
Here is the latest code:
#!/bin/sh
max_ul_rate=35000
min_ul_rate=25000
max_dl_rate=60000
min_dl_rate=20000
read -d '' reflectors << EOF
1.1.1.1
8.8.8.8
EOF
alpha=0.1
ratio_adjust_down=0.25
ratio_adjust_up=0.125
max_delta_RTT=20
rx_bytes_path="/sys/class/net/wan/statistics/rx_bytes"
tx_bytes_path="/sys/class/net/wan/statistics/tx_bytes"
no_reflectors=$(echo "$reflectors" | wc -l)
rx_load_thresh=$(echo "scale=4; $min_dl_rate/2"|bc)
tx_load_thresh=$(echo "scale=4; $min_ul_rate/2"|bc)
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
}
function update_rates {
get_avg_RTT
delta_RTT=$(echo "scale=4; $avg_RTT - $prev_avg_RTT" | bc)
prev_avg_RTT=$(echo "scale=4; (1-$alpha)*$prev_avg_RTT+$alpha*$avg_RTT" | bc)
if [ $(echo "$delta_RTT > $max_delta_RTT" | bc -l) -eq 1 ]; then
cur_dl_rate=$(echo "scale=4; $cur_dl_rate-$ratio_adjust_down*($max_dl_rate-$min_dl_rate)" | bc)
cur_ul_rate=$(echo "scale=4; $cur_ul_rate-($max_ul_rate-$min_ul_rate)/4" | bc)
fi
cur_rx_bytes=$(cat $rx_bytes_path)
cur_tx_bytes=$(cat $tx_bytes_path)
t_cur_bytes=$(date +%s)
rx_load=$(echo "scale=4; (8/1000)*(($cur_rx_bytes-$prev_rx_bytes)/($t_cur_bytes-$t_prev_bytes))"|bc)
tx_load=$(echo "scale=4; (8/1000)*(($cur_tx_bytes-$prev_tx_bytes)/($t_cur_bytes-$t_prev_bytes))"|bc)
t_prev_bytes=$t_cur_bytes
prev_rx_bytes=$cur_rx_bytes
prev_tx_bytes=$cur_tx_bytes
if [ $(echo "$delta_RTT < $max_delta_RTT && $rx_load > $rx_load_thresh" |bc) -eq 1 ]; then
cur_dl_rate=$(echo "scale=4; $cur_dl_rate + $ratio_adjust_up*($max_dl_rate-$min_dl_rate)"|bc)
fi
if [ $(echo "$delta_RTT < $max_delta_RTT && $tx_load > $tx_load_thresh" |bc) -eq 1 ]; then
cur_ul_rate=$(echo "scale=4; $cur_ul_rate + $ratio_adjust_up*($max_ul_rate-$min_ul_rate)"|bc)
fi
if [ $(echo "$delta_RTT < $max_delta_RTT && $rx_load < $rx_load_thresh" |bc) -eq 1 ]; then
cur_dl_rate=$(echo "scale=4; $cur_dl_rate - $ratio_adjust_down*($max_dl_rate-$min_dl_rate)"|bc)
fi
if [ $(echo "$delta_RTT < $max_delta_RTT && $tx_load < $tx_load_thresh" |bc) -eq 1 ]; then
cur_ul_rate=$(echo "scale=4; $cur_ul_rate - $ratio_adjust_down*($max_ul_rate-$min_ul_rate)"|bc)
fi
if [ $(echo "$cur_dl_rate<$min_dl_rate" | bc) -eq 1 ]; then
cur_dl_rate=$min_dl_rate;
fi
if [ $(echo "$cur_ul_rate<$min_ul_rate" | bc) -eq 1 ]; then
cur_ul_rate=$min_ul_rate;
fi
echo -e "rx_load= $rx_load;\ttx_load=$tx_load;\tdelta_RTT= $delta_RTT;\tcur_dl_rate= $cur_dl_rate;\tcur_dl_rate= $cur_ul_rate"
}
get_avg_RTT
prev_avg_RTT=$avg_RTT;
cur_dl_rate=$min_dl_rate
cur_ul_rate=$min_ul_rate
t_prev_bytes=$(date +%s)
prev_rx_bytes=$(cat $rx_bytes_path)
prev_tx_bytes=$(cat $tx_bytes_path)
while true
do
t_start=$(date +%s)
update_rates
tc qdisc change root dev wan cake bandwidth "$cur_ul_rate"Kbit
tc qdisc change root dev veth-lan cake bandwidth "$cur_dl_rate"Kbit
t_end=$(date +%s)
sleep $(echo "5-($t_start-$t_end)"|bc)
done
Check out these results with active download/upload. The rates correctly increase until my connection gets saturated and bufferbloat is detected. And with no load the rates decay back down.
Do you suppose the ul and dl change thresholds should be based on the present bandwidth? So only increase if greater than 50% current bandwidth? And vice versa.
yeah, I assumed that was the whole plan. 50 percent of some theoretical max isn't very relevant when interference is making the actual max say 20% of that theoretical max for example.
@moeller0, @dlakelan - I suppose the below indicates alpha needs to be reduced? Because the prev_avg_RTT seems to creep up too much. My typical RTT is around 50ms. Sorry the formatting is horrible.
Yes, I would make the 50% a parameter that can be easily changed/set, but I would always base it on the current capacity, because that will keep the meaning of the "load" in percentage easy to understand without additional knowledge
Probably, but then it will also stay elevated for longer if you encounter sustained overload, without much thinking maybe alpha could be transiently elevated just after a rate decrease to capture the new RTT quicker (under the theory that decreasing the rate should also decrease the measured RTT). But maybe it is better to keep it simpler and simply let the increased RTTs age out...
Here is with alpha set to 0.05. With a constant download the prev_avg_RTT still just explodes. Is this solvable by playing around with different alpha values or does the routine need some alteration I wonder? I am trying to keep everything as simple as possible. And avoid hacks where possible!
Originally I had wondered about only updating prev_avg_RTT when load is less than half the minimum set (i.e. more or less unloaded). But that would be a significant departure from the routine you proposed.
Generally speaking I think the routine seems very promising.
How about using two different alphas depending whether the current RTT value would in- or decrease the long-term average? That should allow faster down than upscaling, to keep the bufferbloat detection snappy?
The rationale for slow increase is simply, that bufferbloat increases the RTT in relative short timescales, while persistent RTT changes (e.g. due to routing changes) will be relative rare and far between. And the "cost" of underestimating the real path RTT will just result in a bit sacrificied throughput, which at least will not increase bufferbloat.
The rationale for fast decrease is that ideally the average RTT should be close to the minimal RTT over a given path, as we try to control the most likely cause for large RTTs, and erring on setting the avgRTT too low has acceptable bufferbloat consequences.
So maybe that is not that hackish after all
P.S.: Could your present the rx/tx load as ratios of the currently set shaper rate, currentkly I am at a loss what these numbers mean...
I like it! Please can you suggest initial values for me to try?
They are just the present rx and tx load in Kbit/s, which matches the units of the current download and upload rates and those that I set in tc qdisc change. Does that make sense? I can still change if you think I should. So that would mean making the loads a fraction of the presently set download rate / upload rate? And then rather than compare load in Kbit/s with load_thresh*cur_dl/ul_rate I would instead just compare rx_load with load_thresh. What do you think is best?
By the way do the throughput values on the left even just very roughly correspond with the CAKE bandwidths set on the right? They certainly scale together, but there is a big loss. I have set the overhead to 92 based on the above. Perhaps that accounts for the big difference.
Ah okay, typically I am a friend of raw values like these, but I think that a percentage threshold will scale better to human psychology (where we minimal noticeable change tends to depend on the current level), it certainly will be easier to read
Oh, this is your baby now, you make the decisions; I am just sitting in the peanut gallery
That, I believe will be easier to think about.
Well if you increase the shaper rate once the load hits 50%, you can only expect 100% load once you reached the maximum, no? I would not expect these to be precisely matched as they might differ in how much overhead they include (but that is not your issue here, on the wan interface wireguard overhead is part of the payload). Maybe you could extract the load counters also directly from cake (but that might be costly)?
No idea, mybe it is time to actually test this in the real world and then change the alphas and see whether it feels better or worse? (Not the most scientific approach, but after all your subjective assessment is the final arbiter anyway)
OK will do. From initial testing it seems like a challenge is to stop the average _RTT getting too large (e.g. > 100ms) following each ascent in the sawtooth to the capacity limit and eventual overshoot (before the bandwidth is corrected back down).
Any clue at what average_RTT you would start to see glitches in zoom / teams calls? I think it is higher than I previously thought. The waveform bufferbloat website allows an increase of average latency of up to 30ms before downgrading from A to B I think:
Less than 5 ms latency increase - A+
Less than 30 ms latency increase - A
Less than 60 ms latency increase - B
Less than 200 ms latency increase - C
Less than 400 ms latency increase - D
400 ms or greater latency increase - F
It is tempting to set an upper limit 'capacity estimate' upon a downward inflection (once bufferbloat detected) + timeout for that capacity estimate(?), but this adds more complexity and I am trying to avoid arbitrary hacks, favouring a simple algorithm.
Will see what I can manage with tweaking the parameters. I am thinking small tick duration (like 2 seconds or smaller) and small bandwidth increases will help.
In the meantime, quick question: do I need to be concerned about seeing rx_load > 1.0? It is calculated based on the cur_dl_rate from the previous tick. Since I thought 'tc qdisc change' gives an instant bandwidth change I am slightly bemused why it sometimes goes above 1.0.
Any thoughts about the '0.2'? Could that be safely decreased further? I am trying to see how fast I can make the ticks. Could it be '0' in fact? How many simultaneous instantaneous pings can a connection manage I wonder.
I guess that statistics keeping is generally considered to be okay if not fully temporally precise... I would probably try to get the transfer estimates from tc -s qdisc instead of getting the wan stats, by I have no idea how temporally precise these are in comparison.
I think traditionally you need to be root to do so, not an issue under OpenWrt, but then on slow links that might already cause a noticeable load in itself.... I would, probably naively, try to see wether I can get away with a cycle time of 10-30 seconds and then getting by with the normal ping interval should work.
Nah, you do not want to have your ICMP probes cause congestion themselves
Mmmh, wouldn't we need to scale the size of the rate change to the amount of measured deltaRTT then? I am not firm on control theory (I work on wet ware for a living)... but I guess this is great advice to look into the literature instead of cobbling something together on the fly.
Then again, only talking for myself, so @Lynx and @dlakelan might disagree, this learning by doing trial and error approach is fun (especially since I only play the role of the armchair designer, having borrowed the inspiration from @dlakelan 's earlier solution, and letting @Lynx deal with implementation and testing).
I still think Bayesian inference for the current BW ceiling would be ideal to converge quickly on the right value rather than oscillating or overly restricting your BW.
Suppose you observe BW1 at time 1 and no significant bufferbloat, and at time 2 you observe BW2 and bloat. You have a prior over the maximum rate of change the available bandwidth can undergo, you have a cost per second of bufferbloat, and a cost per second of lost bandwidth opportunity. You place a distribution over the likely rates based on maximum rate of change, you truncate it to the current set point if you see bufferbloat (since it must be below the current value in that case) then you choose a set point based on optimizing the expected cost. You might get away with a truncated gaussian as the distribution and a relatively simple optimization. Don't try this in shell script though!
@moeller0 is that wetware as in an anorak or wetware as in biological processing I wonder? I totally don't mind trying out different ideas. Very much enjoying it! Without wanting to sound too creepy, in trying to better understand elements of CAKE I have read your posts on this forum on SQM for months and you appear to have a handle on this that very few people do. I originally tried CAKE on Asus Merlin and your posts on this forum and the SQM implementation code promoted me to try OpenWrt in the first place with my RT3200. Really glad I did. In any case, for me it's an honour that you take the time to reply to my messages on this.
And to both @moeller0 and @dlakelan I really appreciate and welcome the suggestions. I have not had time yet to try to optimise the bash script I have, but yes I also have the nagging feeling that the approach might be improved on a theoretical level.
In my experience with solving problems like this and coding in general it can be helpful to write a bit then try then write a bit more then try further. So iterative approach and back to drawing board sometimes is familiar territory for me.
Perhaps the oscillation doesn't make so much sense because although the bandwidth changes it doesn't change that frequently I don't think. So perhaps it doesn't need to keep testing the ceiling. I think we may need some form of slow moving capacity estimation. Right at the begining of this thread I referenced the approach scripted by @Bndwdthseekr and @richb-hanover-priv here:
There is something neat about coming into action every now and then to estimate capacity and then going to sleep. But I don't like saturating the line to do that because it means causing bufferbloat every time it comes into action. So I think this approach is broken for that reason.
I think we need some way of tracking capacity.
@dlakelan could you elaborate how your idea would avoid oscillation?
On the other hand I think the basic gist of the script works. It could well be that tweaking it I'd get something that's acceptable. But I think it's worth exploring how it might be improved on theoretical level. That said, I still strongly favour simplicity and @moeller0's present approach has that in its favour.
In essence I think you're right, and in some sense the "slow moving" would be built in to a Bayesian model. Suppose you saturate your line for a while, and you somehow converge to set the bandwidth right below the real available amount. Now your speed test ends... In the 1 second after that speed test, how much do you believe the available bandwidth could move? Not much right? So the Bayesian posterior is tightly concentrated around the last known good value. But as time goes on, the bandwidth could change... your knowledge of what it is as represented by a probability distribution spreads out... After a long time, your probability distribution would be something like a uniform(0,maxcontracted) distribution.
If it's over-night for example, and no-one is using your connection at all, then there's no information we have about what it is. But every time some transfer occurs and no bloat occurs... we suddenly can put a lower bound on what the available values are at that time. And when we have a pulse of packets that induces bufferbloat we can put an upper bound on the available amount. Since the pulse of packets rarely is just all in one shot, you'll have recent bandwidth values to set a lower bound once you start to get bufferbloat, so you'll have some kind of good estimate of an interval in which your available bandwidth lies.
By using that information and then doing a kind of "optimization" we'll be able to pick a bandwidth value that doesn't waste too much bandwidth, but doesn't allow bufferbloat either. Once we've got that estimate, then as time goes on, the credible values will start spreading out again. The idea I think is that you're always tracking an interval in which the real bandwidth probably lies, and when you get bloat, you could somehow immediately calculate the "best" value to reduce your bandwidth to. And, when your current usage gets near to the lower bound... you'd have a "best value" to increase to as well.
.