I thought delta_delay is already baseline corrected, so what do we gain from subtracting baseline again? Basing the acceptable variance on the threshold (or adjusted_threshold?) seems like a decent idea, no intuition what proportionality factor to use here though, so starting with 0.9 is just as good as any other...
We can, but than we are restarting ping/fping/... at 1Hz which seems a bit off... if we pre-qualify our reflector candidates we might not need too fast a test rate, also to get better estimates of a reflectors statistics (EWMA(delta_delay)) we need to collect a number of samples per reflector with high interleaving we might only collect a sample per reflector and second...
I would only go to such extremes if we have data showing that is required, as is I see that our CDFs are either reasonably similar or prime candidates for recycling.
Let's not over do this unless we need to, ATM we do neither reject reflectors based on baseline of variance spread and we are doing pretty well, so let's introduce changes gently ;).
The thing is if we enforce too strict baseline or variance requirements we are likely to end up with reflectors pretty much sharing much of their path, which is not what we ideally want (ideally they should just share the bottleneck link we want to control). That is why I argue for working with rather looser requirements to bias against large baseline and variance but not to reduce either measure too harshly. We want as you say "low baselines and also low mids" but not too low
OK - I think I have enough to code something up when I get a chance now. Thanks for your patience!
By the way @moeller0 there may be a very legitimate reason for doing something like making delta threshold dependent on reflector behaviour because for some inexplicable reason my Vodafone 4G connection sometimes now sees unloaded pings like this:
Reply from 1.1.1.1: bytes=32 time=110ms TTL=58
Reply from 1.1.1.1: bytes=32 time=114ms TTL=58
Reply from 1.1.1.1: bytes=32 time=108ms TTL=58
Reply from 1.1.1.1: bytes=32 time=123ms TTL=58
Reply from 1.1.1.1: bytes=32 time=112ms TTL=58
Reply from 1.1.1.1: bytes=32 time=97ms TTL=58
Ping statistics for 1.1.1.1:
Packets: Sent = 774, Received = 770, Lost = 4 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 53ms, Maximum = 136ms, Average = 98ms
And of course cake-autorate pins it down to 5 Mbit/s because at this range the pingers/reflectors are continually triggering. And although the ping has rocketed up from the normal circa 35ms to circa 100ms, the available bandwidth without SQM is pretty hefty even now at circa 4pm UK time:
I'm not exactly sure what's going on here but perhaps the spread of my RTT even between modem and first ISP hop is non-static with time affecting everything?
I presume if the delta_thr were to be set based on minimum and delta that such temporal variation could be accounted for?
I think the above shows that the DL_ADJ_DELAY_THR (yellow line) is set too low because the DL_OWD_DELTA_US regularly traverses it (but this was not bufferbloat related). But I have been using this delta threshold for quite some time, so I think this shows how the DL_ADJ_DELAY_THR may need to dynamically adjust to reflect changes in the connection. I'm not sure how that dynamic adjustment could be implemented but assuming this is needed then I'd welcome ideas.
Here is some data (with SQM and where we see the pinning to 5Mbit/s):
I have acquired some resources in a datacenter. Holy cow, did I get some wildly varying results from their fabric, yesterday, no matter the underlying qdisc. Do a:
Goal is with these boxes to push the limits of what can be done with cake (see: https://libreqos.io), and a secondary goal might be to also add in active measurements like those on this thread to compensate... and a third goal is to get this little cluster to behave sanely on this fabric. That should be the first goal, I admit, but I imagine a lot of underlying SDN networks are actually behaving like this in the first place.
I'm also planning on trying to get openwrt running on one of the 32 core boxes to see what happens. Fun times in hardware land.... If anyone wants to play with us, you can find me @dtaht:matrix.org....
I think to 'tackle' this issue you would need to increase the baseline learning rate, that is increase the weight of the current sample in the baselene EWMA. This looks like a fluctuating baseline more than requiring a dynamic threshold.... dynamic threshold beyond the current adjustments is a bit tricky as it should not be necessary given what we try to model here.
Making the badeline estimate nimbler also has its own issues but seems less problematik to me.
# RTT baseline against which to measure delays
# the idea is that the baseline is allowed to increase slowly to allow for path changes
# and slowly enough such that bufferbloat will be corrected well before the baseline increases,
# but it will decrease very rapidly to ensure delays are measured against the shortest path
alpha_baseline_increase=0.001 # how rapidly baseline RTT is allowed to increase
alpha_baseline_decrease=0.9 # how rapidly baseline RTT is allowed to decrease
And SMA would look something like:
[Initial fill up of /tmp/SMA_fifo with Z values + determination of initial average]
[ .. and then for each ping result]
echo $rtt > /tmp/SMA_fifo
rtt_oldest = read 1st line from /tmp/SMA_fifo
rtt_baseline = rtt_baseline + (1/Z)*(rtt - rtt_oldest)
Not sure, making badeline less persistent or not resetting it fast on sampleRTT > baseline, will make our controller more prone to interpret longer duration bufferbloat/congestion as the 'new normal'. This will recover throughput but at the cost of increased latency. I would think we already have enough toggles to bias for higher throughput if desired, like increasing the threshold or adjusting the baseline faster. Making any of this automatic requires us to find a way of differentiating quickly and reliably between 'bad' and 'tolerable'.
Perhaps I need to repeat this exercise with actual bufferbloat since the above involved retention of bandwidth at 5 Mbit/s despite non-SQM bandwidth being in the region of 60 Mbit/s.
But the situation was clearly hopeless in the second graph - perpetual triggering!
That is not solving our problem You will get a similar result if you run an EWMA with lots of weight for the most recent value, both suffer from the fact that they will incorporate sustained delay due to true bufferbloat far too readily. The time constant of the EWMA or the window length of an SMA need to be selected such that our baseline does not increase too fast, once you do that however the "nice" tracking low/pass behaviour visible in your plots shifts to much lower frequencies.
That is quite something to behold... what are all the *mq variants?
All these "ramps" in the latency panels are puzzling, what do you think causes these?
Note how similar these can be depending on the selection of the EWMA alpha?
And here a plot showing examples of how much an EWMA diverges (filters) from the input data depending on alpha:
In short I do not think that SMA versus EWMA is going to help us much, plus the SMAs are centered on the mean of the delay data, while for baseline we really would like a moving minimum (which we get with the EWMAs by resetting quickly to encountered minima*)... Now if you calculate SMA you can just as easily calculate SMMinimum, but I think the real question is over what number of RTT samples to operate (which for EWMA is more or less equivalent with what alpha to select).
Side-note: with our default values we really do not use the EWMA to low pass filter the RTT in data in any meaningful way, we just use it as a means to sloooowly update our baseline estimates to eventually adapt to path changes that affect the baseline, as we operate in the principle that baseline represents that invariable component of the delay. In your case we could argue that either the network path fluctuates and hence the "invariable" term has some short term variability OR we could argue that there is an additional process in play that our current model "static" baseline + purely bufferbloat-driven deltaDelay does not capture well. In that interpretation a possible solution would lie in trying to first understand this additional delay-changing process first and then add it to our "model". I think my initial proposal to fudge the alpha is merely a work-around but no real solution. Your approach to adjust the threshold might have actually more merit in that it appears we have a process that affects the sample RTTs more than the baseline (as this component varies at timeframes incompatible with true changes of the network path). Intuitively I would (if I understood the root cause better) try to model this as an additional component to calculate the deltaDelay instead of changing the threshold but that is more a matter of taste and implementation than principle. So is there any rhyme or reason tho the fluctuations you see?
Just to throw something out, we could keep our existing conservative minimum corrected baseline and add another EWMA on top that tries to correct for intermediate time scale variations and then have the deltaDelay on top. Though that really just shifts the problem around as long as one of our three components will confuse true congestion with expected/acceptable delay increases our controller will loose sensitivity to congestion.
*) something like this could also be introduced to SMA style calculation e.g. by maintaining a common factor to multiply all values (and/or a common additive/subtractive term) before averaging with, but I am not sure whether that is going to be noticeably better than simple EWMAs which are pretty simple to maintain and use minimal state... to be explicit EWMA and SMA are not going to be exactly equal for any relationship between the SMA's N and the EWMA's alpha, but I argue that the fine-scale differences do not matter for our use-case.
Maybe try with EWMA alpha set to 2 / (20 + 1) = 0.095 which should have a similar center of mass to a 20 point SMA (since I forgot how we defined the EWMA factors you might need t specify (1 - (2 / (20 + 1) )) = 0.905. and maybe disable the reset to minimum logic.
Thanks. Very insightful as ever. Last night I coded up an SMA implementation (just a few lines and some trickery relating to setting up an array of arrays). Snippet here:
And from my testing so far including various plots in Excel I think it works. At least it works for a while, but something seems not quite right since after a night of running one of the baselines went negative(!) - so there is something I've missed that I will need to iron out. But once I have fixed that we can then easily test both side by side.
I can likely share data today from the SMA code since I'm running the revised code as a service to see how it feels, albeit serious testing to compare SMA and EWMA may need to wait until tomorrow.
Here are a couple of waveform tests:
I wonder if an issue is that increased variance hurts more when tracking the minimum than it does when tracking the middle? I have tried to illustrate what I have in my mind below.
Now of course this doesn't mean SMA is better than EWMA, just that the way we've implemented the EWMA so far may mean that variance hurts more than with my SMA tracking the middle.
In any case, I am thinking with a 20 point SMA and 0.5s between reflector responses (since playing with the reflector randomisation I have been using 10 reflectors to keep a 20 Hz response interval), this corresponds with a 10s SMA period and so surely that offers quite some resilience to the problem of baseline creep with bufferbloat? If the bufferbloat lasts long enough to make a big difference over this period then isn't there something rather wrong?
# Read in baselines if they exist, else just set them to 1s (rapidly converges downwards on new RTTs)
for (( reflector=0; reflector<$no_reflectors; reflector++ ))
do
if [[ -f /var/run/cake-autorate/reflector_${reflectors[$reflector]//./-}_baseline_us ]]; then
read rtt_baselines_us[${reflectors[$reflector]}] < /var/run/cake-autorate/reflector_${reflectors[$reflector]//./-}_baseline_us
else
rtt_baselines_us[${reflectors[$reflector]}]=50000
fi
done
# For each reflector initialize reflectory history for SMA
for ((reflector=0; reflector<$no_reflectors; reflector++))
do
declare -n reflector_rtts_us="reflector_${reflectors[$reflector]//./_}_rtts_us"
declare -n reflector_rtts_idx="reflector_${reflectors[$reflector]//./_}_rtts_idx"
reflector_rtts_idx=0
for ((i=0; i<$rtts_sma_period; i++)) do reflector_rtts_us[i]=50000; done
done
Perhaps I should rather instead initialize the array of past rtts to either 0 or if available the previously stored rtt_baselines_us upon a resume operation.
So the initialization then becomes:
# Read in baselines if they exist, else just conservatively set them to 0
for (( reflector=0; reflector<$no_reflectors; reflector++ ))
do
if [[ -f /var/run/cake-autorate/reflector_${reflectors[$reflector]//./-}_baseline_us ]]; then
read rtt_baselines_us[${reflectors[$reflector]}] < /var/run/cake-autorate/reflector_${reflectors[$reflector]//./-}_baseline_us
else
rtt_baselines_us[${reflectors[$reflector]}]=0
fi
done
# For each reflector initialize reflectory history for SMA
for ((reflector=0; reflector<$no_reflectors; reflector++))
do
declare -n reflector_rtts_us="reflector_${reflectors[$reflector]//./_}_rtts_us"
declare -n reflector_rtts_idx="reflector_${reflectors[$reflector]//./_}_rtts_idx"
reflector_rtts_idx=0
for ((i=0; i<$rtts_sma_period; i++)) do reflector_rtts_us[i]=${rtt_baselines_us[${reflectors[$reflector]}]}; done
done
Let me ask again, given that you can make our EWMA look almost identical to an SMA why the effort?
Tracking the baseline closely as you do will mis classify persistent congestion as simply part of the baseline, which IMHO counter acts the reason for autorate in the first place (keep latencies acceptably low, even if that requires to sacrifice some potential throughput).
Tracking the middle is not the right thing to do IMHO, as it will subsume part of the variable delay into the baseline estimate, which IMHO does not actually help...
Again, this has little to do with EWMA versus SMA and all with our goal for what the baseline is supposed to model. As I said it is easy to make the EWMA look close to your SMA, as it will be "easy" to make the SMA operate on minima (simply get the minimum sample in the widow first and subtract that value from all samples in the window prior to averaging), but my argument is that if we change the baseline too quickly we stop being able to detect sustained congestion.
I respectfully disagree changes in the order of ~10 seconds are unlikely to be changes in the underlaying path so they IMHO should not be modeled as changes of the baseline as that should describe the true path minimum. Think of it that way, congestion on a link can easily last for multiple minutes and with a 10 second window you will quickly in-sensitize the controller against bufferbloat.
Mind you, "bufferbloat" in a shared segment is not only caused by your link and your traffic, but also by other users (ISPs isolate user more or less from each other, but as far as I can tell more on the "less" side). As long as the user users in the cell keep hammering the basestation with requested packets the upstream congestion will continue...
Again I question the rationale behind this change and for initialization you might as well initialize with the first value or simply wait with calculating a baseline until you have a full window worth of samples collected for the SMA approach.
Which issue? Negative baseline values or the problem of accounting part of the variable delay to the supposedly static baseline ?
But the autorate cannot handle such long term congestion lasting as long, right? Isn't the point that we are looking for short term jumps associated with bufferbloat, and throttling of the cake rate to prevent that by operating under the link capacity? I have now seen on my own connection latency jump up from circa 35ms with tight spread to 80 or so with a bigger spread, and yet the available capacity seems to be in the order of 60 Mbit/s. I have no idea what causes that, but I am thinking this is not bufferbloat, and that again what we want to detect is short term latency increase, or not?
Getting the effect of the spread into the baseline seems to me like a good idea unless we actually take into account the spread when we work with only the minimum? Or put another way, it strikes me as problematic that the greater the spread the lower the baseline if we track the minimum baseline.
We could easily track both minimum (using existing EWMA code) and middle (using the new SMA) and work with that(!)?
But admittedly isn't the proof always in the pudding and the pudding is looking quite nice for me at the moment:
And I totally understand this may be more about tracking the middle rather than the minimum rather than EWMA vs SMA, but so far if we are not taking into account variance in using the minimum it seems to me like working with only the baseline middle is doing a pretty good job?
Admittedly I haven't tested in any thorough way at all here, but so far so good.
BTW @moeller0 as always I am totally open minded here, and also I need to consider your carefully thought through and insightful post above more carefully when I have more time. You understand the underlying theory a lot better than I do, and I place great store by these sorts of exchanges in helping converge on something that works well. I mean it has worked so far I think!
I think there is a way around that: periodically, for a few seconds, throttle it a bit more than necessary, so that any congestion has a chance to dissolve, and give a chance for the true baseline latency to be measured. Then unthrottle.
The commit switching from EWMA tracking minimum to SMA tracking middle is here:
I've put it in a new 'experimental' branch with revised config here:
And the 'main' branch still uses the previous technique (albeit admittedly I've tweaked some of the config parameters a little bit too, so you may want to ensure these match what you normally work with).
I'm sure the changes could be further polished a little, etc. - this is just so you can test if you like.
But so far so good from my quick and dirty testing:
Oh, it will do much better, just look at your plot how slowly the dark blue line inches up and is reset each time the current sample is smaller than the baseline, so I think we are tolerant to multiple minutes of ongoing congestion...
Well, there really only are two options, changes in the network path or lingering longer in some queue somewhere. Repetitive changes in network path are really unlikely to happen on a seconds timerange so I would say what you encounter is some form of bufferbloat, albeit one you might be willing to accept in exchange for higher throughput (sidenote, your speedtests are over the wireguard link, or could your ISP play games when recognizing speedtests?).
Well this is why we threshold the deltaDelay values and use a voting process this is designed to deal with the variable part of the delay. The baseline is modeling the hard lower limit of the network path as that is the delay we will have to accept if we want to use a reflector, no ifs not buts since the delay can not be lower. Now the variance of the deltaDelay differs between reflectors somewhat, but this variance is driven mostly by queueing/batching effects somewhere along the path. We can argue about recycling reflectors with very large deltaDelay variance, but we should not play tricks and simply hide part of that variance in the "baseline" estimate.
I get that you like your SMA implementation, but humor me and implement the EWMA with the factor i mentioned above. BUT tracking the mean and use that as baseline really just hides part of the variance into the baseline, which I do not think would be a helpful change.
Except tracking the middle is IMHO conceptually not the right split. Conceptually dissection the total delay into the unavoidable static and the variable makes more sense. And yes this has little to do with how you calculate your average estimate.
Nice idea, however the a bit more than necessary" part is the catch if we reliably would know that rate we could just set our shaper a tad below that and be done... BBR uses that approach but by the only known (to me) way to reliably probe capacity, by sending at an increased rate and measuring the effect on its flow-internal delay, but cake-autorate is opportunistic so we only have the load available that happens organically. So, I fail to see how to actually exploit this concept.
Fun times in hardware land.... If anyone wants to play with us, you can find me 
