mac80211: Exponential moving average estimate for rc80211_simple
PATCH v3 1/1 mac80211: Exponential moving average estimate for rc80211_simple
This changes rc80211_simple failed frame percentage estimation to use an exponential moving average method. Failed frames percentage is sampled over time and a smoothed average is computed. This average is examined periodically and the rate adjusted eventually.
Compared to the old method this new approach is much more responsive. The old method used plain tx success/failure counters. This made rate control very unresponsive after a short time of using the interface, since old data wouldn't age properly.
--- net/mac80211/ieee80211_rate.h | 3 - net/mac80211/rc80211_simple.c | 155 ++++++++++++++++++++++++++++++---------- 2 files changed, 116 insertions(+), 42 deletions(-)
net/mac80211/ieee80211_rate.h +0 -3
@@ -18,9 +18,6 @@#include "ieee80211_i.h" #include "sta_info.h" -#define RATE_CONTROL_NUM_DOWN 20 -#define RATE_CONTROL_NUM_UP 15 -struct rate_control_extra {/* values from rate_control_get_rate() to the caller: */
net/mac80211/rc80211_simple.c +116 -39
209 lines not on this page · raw message
Signature · 1 line
1.5.3.4
Johannes Berg
maintainerQuoted 9 lines · Mattias Nissler
This changes
rc80211_simplefailed frame percentage estimation to use an exponential moving average method. Failed frames percentage is sampled over time and a smoothed average is computed. This average is examined periodically and the rate adjusted eventually.Compared to the old method this new approach is much more responsive. The old method used plain tx success/failure counters. This made rate control very unresponsive after a short time of using the interface, since old data wouldn't age properly.
Sounds sane and better than before. If it works we can apply this I guess.
johannes
Quoted 6 lines · Johannes Berg
Quoted 5 lines · Mattias Nissler
This changes
rc80211_simplefailed frame percentage estimation to use an exponential moving average method. Failed frames percentage is sampled over time and a smoothed average is computed. This average is examined periodically and the rate adjusted eventually.
Quoted 7 lines
Quoted 4 lines
Compared to the old method this new approach is much more responsive. The old method used plain tx success/failure counters. This made rate control very unresponsive after a short time of using the interface, since old data wouldn't age properly.
Sounds sane and better than before. If it works we can apply this I guess.
I have not done any rigorous testing of this patch; however, it has not caused any harm on my system.
Larry
Quoted 12 lines · Larry Finger
Quoted 11 lines · Johannes Berg
Quoted 9 lines · Mattias Nissler
This changes
rc80211_simplefailed frame percentage estimation to use an exponential moving average method. Failed frames percentage is sampled over time and a smoothed average is computed. This average is examined periodically and the rate adjusted eventually.Compared to the old method this new approach is much more responsive. The old method used plain tx success/failure counters. This made rate control very unresponsive after a short time of using the interface, since old data wouldn't age properly.
Quoted 4 lines
Quoted 2 lines
Sounds sane and better than before. If it works we can apply this I guess.
I have not done any rigorous testing of this patch; however, it has not caused any harm on my system.
Good to hear. I've tested it with rt61pci and rt73usb. I guess you tested b43[legacy]. Any other test results, especially in low signal quality situations would be of great help.
Mattias
Quoted 4 lines · Mattias Nissler
Good to hear. I've tested it with rt61pci and rt73usb. I guess you tested b43[legacy]. Any other test results, especially in low signal quality situations would be of great help.
Sorry I wasn't clearer. I have tested V3 of the patch on a BCM4311/2 using b43. So far, it has only been tested with strong signal.
Larry
Quoted 6 lines · Johannes Berg
Quoted 5 lines · Mattias Nissler
This changes
rc80211_simplefailed frame percentage estimation to use an exponential moving average method. Failed frames percentage is sampled over time and a smoothed average is computed. This average is examined periodically and the rate adjusted eventually.
Quoted 7 lines
Quoted 4 lines
Compared to the old method this new approach is much more responsive. The old method used plain tx success/failure counters. This made rate control very unresponsive after a short time of using the interface, since old data wouldn't age properly.
Sounds sane and better than before. If it works we can apply this I guess.
Before this goes in, I have at least one issue to be discussed: As it is, the patch calculates the failed frames percentage exclusively from the retry_count. I'm not sure whether this is what we want, because some drivers cannot provide this parameter (or they only know there have been retries, but not how many). This is the case e.g. for the rt2x00 usb devices. I'm not sure what to do about this. My suggestion would be something like:
srctrl->tx_num_xmit++;
if (status->excessive_retries) {
srctrl->tx_num_failed += 2;
srctrl->tx_num_xmit++;
} else if (status->retry_count) {
srctrl->tx_num_failed++;
srctrl->tx_num_xmit++;
}This accounts correctly transmitted frames as one good, failed frames 2 bad and retry-succeeded frames 1 good + 1 bad point in the failed percentage calculation. Opinions?
Mattias
Quoted 4 lines · On Mon, 26 Nov 2007 22:30:05 +0100 Mattias Nissler <[email protected]>…
This changes
rc80211_simplefailed frame percentage estimation to use an exponential moving average method. Failed frames percentage is sampled over time and a smoothed average is computed. This average is examined periodically and the rate adjusted eventually.
This can be seen as a particular example of a PID controller [1]. It's actually a PI controller, with no derivative terms in it. It could be interesting to implement a regular PID controller.
This is clearly a MIMO model, with the setpoints being a reasonable value of TX failures and the highest achievable rate, the process input being the bitrate and the process output being TX failures and successes; and obviously, the big issue being the implementation without floating-point. Thus, with some tuning, you could probably get a very good rate control algorithm.
I just wanted to share this thought ATM, but I'll try to elaborate more if I happen to have some spare time.
[1] http://en.wikipedia.org/wiki/PID_controller
Signature · 2 lines
Ciao Stefano
Quoted 12 lines · Stefano Brivio
Quoted 4 lines · On Mon, 26 Nov 2007 22:30:05 +0100 Mattias Nissler <[email protected]>…
This changes
rc80211_simplefailed frame percentage estimation to use an exponential moving average method. Failed frames percentage is sampled over time and a smoothed average is computed. This average is examined periodically and the rate adjusted eventually.This can be seen as a particular example of a PID controller [1]. It's actually a PI controller, with no derivative terms in it. It could be interesting to implement a regular PID controller.
Quoted 6 lines
This is clearly a MIMO model, with the setpoints being a reasonable value of TX failures and the highest achievable rate, the process input being the bitrate and the process output being TX failures and successes; and obviously, the big issue being the implementation without floating-point. Thus, with some tuning, you could probably get a very good rate control algorithm.
Good point, I'm not too familiar with control theory, but I'll do some homework :-)
However, maybe you can answer some questions:
Is it sensible to preprocess (i.e. calculate a smoothed average) the input data for a PID controller? If so, should we compute a time average or just average over the last N frames?
Note that the rates (or actually modulations) are not a continuous entity, but we only have a limited set of choices. Normally, the PID would output a value from some continuous range. What are good ways to map the PID controller output to a rate?
Mattias
Quoted 3 lines · On Tue, 27 Nov 2007 22:38:04 +0100 Mattias Nissler <[email protected]>…
Is it sensible to preprocess (i.e. calculate a smoothed average) the input data for a PID controller? If so, should we compute a time average or just average over the last N frames?
By computing an average, you won't be able to implement differentiation, even if you could implement integration.
In fact, the integration here means considering error values occurred over some time (and I'd think of some 'windowing' approach, as explained below), and so if we make an average, that doesn't really matter because all the input numbers would weigh the same in the term to be integrated, as in an average.
But in order to differentiate, you need to have some array of values for the slope calculation (if you get a value only, you can't find the slope of the line which is passing by - or near to, if we consider more than two values - two points).
Maybe it doesn't even make sense to have more than two values, and it would be better to just compute a regular slope between two points, so that we would just need to keep an average value and two values. Plus, the differentiation here would just mean to make a difference between the latest two values and divide it by the time difference between the two frames, so we would get just two input values.
I would take this approach for computing the ID terms:
[number of bad frames]
[2][3][5][6][9][7]
| | | 0 S <-n-> E <-- S is where the sliding window starts, E where it
ends, n is the length of the window (here it's 4 as an example, that'll be subject to tuning).
- in order to integrate, we make the average of the bad frame values ranging from S to E; if that average is going to be over a reasonable threshold for bad frame values we preset, the I factor will be negative, positive otherwise;
- in order to differentiate, we'll just subtract the preset threshold from the values stored in E, E-1 from the preset threshold, then subtract the resulting E value from the resulting E-1 value and divide by the time which passed between the two bad frames computation; if this value is positive, the D factor will be negative, positive otherwise;
- after we did these computation, we wait for some time and make the sliding window shift right, and then repeat.
What we would avoid here - by properly tuning the n value - is the so-called integral wind-up [1], which could be really bad if the quality of the link varies rapidly, because we would take too much into account the past events, which could be meaningless to some degree if considering a not recent past.
Quoted 4 lines
Note that the rates (or actually modulations) are not a continuous entity, but we only have a limited set of choices. Normally, the PID would output a value from some continuous range. What are good ways to map the PID controller output to a rate?
The quick approach would be to round it to the nearest rate. A better one could be to keep a map of (1):[rate] <-> (2):[k1*rate + k2*recent errors at this rate], so that if we do have to decide whether to switch between two rates, we could actually evaluate the device performance - mainly sensitivity - at different rates(1), and accordingly think of the real difference between two rates(2). Then we round the output to the nearest rate(2) and choose the corresponding rate(1).
I understand this could look a bit obscure, if you are still interested however feel free to ask questions. :)
[1] http://en.wikipedia.org/wiki/Integral_windup
Signature · 2 lines
Ciao Stefano
Hi Stefano,
first of all, thanks for your input.
Quoted 42 lines · Stefano Brivio
By computing an average, you won't be able to implement differentiation, even if you could implement integration.
In fact, the integration here means considering error values occurred over some time (and I'd think of some 'windowing' approach, as explained below), and so if we make an average, that doesn't really matter because all the input numbers would weigh the same in the term to be integrated, as in an average.
But in order to differentiate, you need to have some array of values for the slope calculation (if you get a value only, you can't find the slope of the line which is passing by - or near to, if we consider more than two values - two points).
Maybe it doesn't even make sense to have more than two values, and it would be better to just compute a regular slope between two points, so that we would just need to keep an average value and two values. Plus, the differentiation here would just mean to make a difference between the latest two values and divide it by the time difference between the two frames, so we would get just two input values.
I would take this approach for computing the ID terms:
[number of bad frames]
[2][3][5][6][9][7]| | | 0 S <-n-> E <-- S is where the sliding window starts, E where itends, n is the length of the window (here it's 4 as an example, that'll be subject to tuning).
- in order to integrate, we make the average of the bad frame values ranging from S to E; if that average is going to be over a reasonable threshold for bad frame values we preset, the I factor will be negative, positive otherwise;
- in order to differentiate, we'll just subtract the preset thresholdQuoted 1 line
from the values stored in E, E-1 from the preset threshold, then subtract
the resulting E value from the resulting E-1 value and divide by the time which passed between the two bad frames computation; if this value is positive, the D factor will be negative, positive otherwise;
- after we did these computation, we wait for some time and make the sliding window shift right, and then repeat.
Quoted 5 lines
What we would avoid here - by properly tuning the n value - is the so-called integral wind-up [1], which could be really bad if the quality of the link varies rapidly, because we would take too much into account the past events, which could be meaningless to some degree if considering a not recent past.
That's all good, I completely agree.
I should have been a little clearer with my question, but when I wrote it, I probably still had some concepts mashed up in my brain. Anyway, let me try again: What about the problem of getting the failed frame number samples? The input data received by the rate scaling algorithm is basically if a frame failed to be transmitted or not, and if it was transmitted, how many retries were needed. What my original patch does (and what you also seem to assume in your explanations) is to count failed frames and total number of frames over fix-sized time intervals and compute a failed frames percentage sample value. The question is now whether this approach is a good one. There are situations where the device might only transmitted very few frames (as low as 1 frame every ten seconds). Clearly, there is not much information available to the rate scaling algorithm (not much need for rate scaling either, but nevertheless we have to consider the effect of such a situation for frames following an idle period). And then there are of course periods with many transmitted frames. So what I thought of is maybe using discrete time to calculate samples is perhaps not a good idea. Another option would be to calculate failed frames percentage samples from each M frames that were to be transmitted. What's your opinion on this?
Quoted 6 lines
Quoted 5 lines
Note that the rates (or actually modulations) are not a continuous entity, but we only have a limited set of choices. Normally, the PID would output a value from some continuous range. What are good ways to map the PID controller output to a rate?
Quoted 7 lines
The quick approach would be to round it to the nearest rate. A better one could be to keep a map of (1):[rate] <-> (2):[k1*rate + k2*recent errors at this rate], so that if we do have to decide whether to switch between two rates, we could actually evaluate the device performance - mainly sensitivity - at different rates(1), and accordingly think of the real difference between two rates(2). Then we round the output to the nearest rate(2) and choose the corresponding rate(1).
Ok, I understand. Question is whether it's worth the added overhead both in computation and storage.
Mattias
Quoted 9 lines · On Wed, 28 Nov 2007 17:34:21 +0100 Mattias Nissler <[email protected]>…
I should have been a little clearer with my question, but when I wrote it, I probably still had some concepts mashed up in my brain. Anyway, let me try again: What about the problem of getting the failed frame number samples? The input data received by the rate scaling algorithm is basically if a frame failed to be transmitted or not, and if it was transmitted, how many retries were needed. What my original patch does (and what you also seem to assume in your explanations) is to count failed frames and total number of frames over fix-sized time intervals and compute a failed frames percentage sample value.
Exactly.
Quoted 11 lines
The question is now whether this approach is a good one. There are situations where the device might only transmitted very few frames (as low as 1 frame every ten seconds). Clearly, there is not much information available to the rate scaling algorithm (not much need for rate scaling either, but nevertheless we have to consider the effect of such a situation for frames following an idle period). And then there are of course periods with many transmitted frames. So what I thought of is maybe using discrete time to calculate samples is perhaps not a good idea. Another option would be to calculate failed frames percentage samples from each M frames that were to be transmitted. What's your opinion on this?
The size of the time interval (not to be confused with the sliding window) could vary depending on number of frames we tried to sent. But I don't know if this is worth the effort. I'll list a few examples:
1) we are downloading a big file through our NFS server at home; we dance around with our laptop in our hands and suddenly we fall behind a short wall - SNR drops by 10dB and we need to suddenly react at this, the D term does this and we would need the time interval to be short enough so that we notice in time about the fast drop in SNR;
2) what if we consider 1), except that we are just on IRC, sending a few frames every some seconds? The time interval needs to be short anyway, because we would notice about the drop in SNR too late otherwise;
3) we are stealing connectivity from the neighborhood, rain falls and humidity slowly increases, thus producing a slow decrease in SNR; the I term should deal with this, by integrating the error over time and thus force a lower rate after, maybe, some minutes; both if we make a lot of traffic or just send few frames, the time interval here should be short enough - again - so that we can actually see a consistent decrease in SNR between different time intervals.
So I'd say that for maximum granularity and good precision, we should try to keep this time interval as short as possible (my rough guess is about 1s). We then need to solve the issue you mentioned, but I'd come up with another approach here. Instead of taking a long time interval, let's do interpolation. In other words, we can reasonably assume that, if at a given time t we don't transmit any frame so we miss data, the frame errors rate is similar to the one at t-1, and if we missed data from t-1 as well, we grab the value from the t-2 interval, and so on. This is rough, but still it seems to me a precise enough method for dealing with the issue.
Quoted 10 lines
Quoted 7 lines
The quick approach would be to round it to the nearest rate. A better one could be to keep a map of (1):[rate] <-> (2):[k1*rate + k2*recent errors at this rate], so that if we do have to decide whether to switch between two rates, we could actually evaluate the device performance - mainly sensitivity - at different rates(1), and accordingly think of the real difference between two rates(2). Then we round the output to the nearest rate(2) and choose the corresponding rate(1).
Ok, I understand. Question is whether it's worth the added overhead both in computation and storage.
Probably not, but so far I've seen very few examples of PID controllers for data rates by googling around, and my guess here is that you would need to try the simplest approach and then go further adding complexity until you are satisfied.
Signature · 2 lines
Ciao Stefano
Quoted 19 lines · Stefano Brivio
The size of the time interval (not to be confused with the sliding window) could vary depending on number of frames we tried to sent. But I don't know if this is worth the effort. I'll list a few examples:
1) we are downloading a big file through our NFS server at home; we dance around with our laptop in our hands and suddenly we fall behind a short wall - SNR drops by 10dB and we need to suddenly react at this, the D term does this and we would need the time interval to be short enough so that we notice in time about the fast drop in SNR;
2) what if we consider 1), except that we are just on IRC, sending a few frames every some seconds? The time interval needs to be short anyway, because we would notice about the drop in SNR too late otherwise;
3) we are stealing connectivity from the neighborhood, rain falls and humidity slowly increases, thus producing a slow decrease in SNR; the I term should deal with this, by integrating the error over time and thus force a lower rate after, maybe, some minutes; both if we make a lot of traffic or just send few frames, the time interval here should be short enough - again - so that we can actually see a consistent decrease in SNR between different time intervals.
Quoted 9 lines
So I'd say that for maximum granularity and good precision, we should try to keep this time interval as short as possible (my rough guess is about 1s). We then need to solve the issue you mentioned, but I'd come up with another approach here. Instead of taking a long time interval, let's do interpolation. In other words, we can reasonably assume that, if at a given time t we don't transmit any frame so we miss data, the frame errors rate is similar to the one at t-1, and if we missed data from t-1 as well, we grab the value from the t-2 interval, and so on. This is rough, but still it seems to me a precise enough method for dealing with the issue.
Ok, I your case study sounds reasonable :-) So I guess I'll stick with averaging over fix sized time intervals. The interpolation approach you suggest seems good enough. How I'd expect the rate control algorithm to behave in situations with not much input data is:
a) Stay at the current rate, just assume conditions didn't change.
b) Be optimistic: Slowly ramp up tx rate, so if more data to be transmitted is available, it'll get good rates from the beginning, if possible.
I think the approach you suggest is basically a) if we aren't adjusting rate heavily at the moment.
Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
The quick approach would be to round it to the nearest rate. A better one could be to keep a map of (1):[rate] <-> (2):[k1*rate + k2*recent errors at this rate], so that if we do have to decide whether to switch between two rates, we could actually evaluate the device performance - mainly sensitivity - at different rates(1), and accordingly think of the real difference between two rates(2). Then we round the output to the nearest rate(2) and choose the corresponding rate(1).
Quoted 7 lines
Quoted 2 lines
Ok, I understand. Question is whether it's worth the added overhead both in computation and storage.
Probably not, but so far I've seen very few examples of PID controllers for data rates by googling around, and my guess here is that you would need to try the simplest approach and then go further adding complexity until you are satisfied.
Ok, this whole thing sounds very promising to me. Now that we've discussed some important points, I'll go ahead and write some code, probably over the weekend.
Mattias
Quoted 5 lines · On Thu, 29 Nov 2007 02:59:43 +0100 Mattias Nissler <[email protected]>…
Ok, I your case study sounds reasonable :-) So I guess I'll stick with averaging over fix sized time intervals. The interpolation approach you suggest seems good enough. How I'd expect the rate control algorithm to behave in situations with not much input data is:
Quoted 7 lines
a) Stay at the current rate, just assume conditions didn't change.
b) Be optimistic: Slowly ramp up tx rate, so if more data to be transmitted is available, it'll get good rates from the beginning, if possible.I think the approach you suggest is basically a) if we aren't adjusting rate heavily at the moment.
Yes, because:
1) if the number of frame errors is over some threshold, by interpolating the way I suggested we will probably switch to a lower rate (mostly because of the I term - as the slope there would be 1); this should be just fine because anyway we didn't need the extra bitrate, and once we need it, we'll have enough data to switch to an higher rate, in case. A caveat here: what if we don't want an high throughput but we want low latency? We'll have to see if your b) approach is reasonable - i.e. if the increased latency provided by a lower bitrate is significant;
2) if the frame errors are below the threshold, no problem because we won't switch rate (if we are near to the threshold) or we'll switch to an higher one. We don't aim to 0 frame errors, but we aim to the threshold (and this threshold could be meant as a userspace parameter, maybe, and may be seen as a 'reliability over throughput' parameter).
Quoted 3 lines
Ok, this whole thing sounds very promising to me. Now that we've discussed some important points, I'll go ahead and write some code, probably over the weekend.
If I'm not too busy, I'm going to help you.
--
Ciao
Stefano