Hi everyone! As the first evaluation of GSoC ’22 is almost here, I’m writing this blog post to provide a detailed update on the progress of the user space Minstrel HT.
1) Addition of new estimators
Previously, the user space Minstrel HT consisted of only the Exponentially Weighted Moving Average (EWMA) filter. However, the current kernel Minstrel HT algorithm has replaced EWMA with a new estimator based on the SuperSmoother (Butterworth) filter developed by John F. Ehlers. As such, the Butterworth filter has now been added to the user space Minstrel HT with the period set to 16.
The image above shows the formula of the Butterworth filter used to calculate the average success probability of a data rate in Minstrel HT. The curr_prob denotes the success probability of a data rate in the current update interval (50 milliseconds) and, for the first success probability data, the new_avg is set to the first success probability as no previous average probability exists.
Exponentially Discounted Averaging and Variance
In addition to the Butterworth filter, an exponentially discounted filter has also been implemented in user space Minstrel HT for research purposes. Consider two data rates with the given statistics, during the last ‘t’ timesteps, as packet counts: rate1 with 4 attempts and 5 successes, and rate2 with 280 attempts and 350 successes. The success probability of both these rates is 80%, however, rate2 seems to be more reliable as it has more observations.
This new filter can discount with respect to the number of observations and also with respect to the time of these observations, using two different discounting parameters: α, β ∈ [0,1]. The formula of the Exp. Discounted filter shown below is for incremental calculation and, at time t0, the following values are initialised to 0: μ0 = s0 = W0 = t0 = 0.
By choosing α and β we can trade-off between emphasizing the number of observations and how recent these observations are. Extreme cases are ignoring the number of observations (α = 1) and ignoring time (β = 1). Currently, the value of β is set to 1 in the user space Minstrel HT and the value of α is dynamic. The value of alpha depends on the number of observations in the current update interval.
2) Changes to the output
Prior to GSoC ’22, the output of the user space Minstrel HT was a simple printout of the rate statistics dictionary during every update interval which wasn’t easy to read or interpret. The output has now been changed to match the kernel Minstrel HT debug output.
Human Readable Statistics (rc_stats)
The human-readable rate statistics table shows the average success probability and average throughput for each data rate using the three filters implemented in user space Minstrel HT, namely Exponentially Weighted Moving Average (EWMA), Exponentially Discounted filter, and the Butterworth filter.
Statistics as CSV file (rc_stats_csv)
Along with the human-readable statistics, at the end of every update interval, the user space Minstrel HT also stores the rate table in a CSV format to the ‘rc_stats_csv’ file. The CSV file can then be used to analyze the performance of different filters and also compare the user space Minstrel HT with its kernel counterpart.
The rate table is separated by the delimiter ‘*’ between each update interval. Furthermore, along with the rate table, the CSV format also consists of a timestamp, at the top, to indicate when the rate table was printed to the CSV file.
File Structure for the output
By default, the output of Minstrel HT in user space is saved to a “data” folder inside the same directory which contains the RateMan driver script. Running RateMan and Minstrel HT on two access points, for example, would result in the following output structure inside the “data” folder:
3) Compatibility with the new RateMan
As described in the first blog post, the user space Minstrel HT relies on RateMan, short for Rate Manager, to perform rate control functionalities in the user space. At the end of June, the RateMan package was restructured resulting in Minstrel HT being incompatible with the new Rateman. As such, the user space Minstrel HT has been reprogrammed in order to make it compatible with the new Rateman.
4) Configuration File
The user space Minstrel HT package now consists of a configuration script named ‘config.py’ which can be used to modify the settings of the rate control such as disabling output, changing the property of Minstrel HT, and also the parameters of the different averaging filters.
Additionally, the configuration script lets the user select the filter to use for rate control. The table below describes some of the configuration parameters:
|rate_stats_csv_output||Denotes whether to save rc stats as CSV|
|rate_stats_output||Denotes whether to save rc stats as human-readable table format|
|EWMA_stats||Denotes whether to show EWMA stats in rate table output|
|Butterworth_stats||Denotes whether to show Butterworth Filter stats in rate table output|
|Exp_Disc_stats||Denotes whether to show Exponentially Discounted Averaging and Variance stats in rate table output|
|Filter_EWMA||Denotes whether to use EWMA for rate control|
|Filter_Butterworth||Denotes whether to use Butterworth filter for rate control|
|Filter_Exp_Disc||Denotes whether to use Exponentially Discounted Averaging and Variance for rate control|
Note: Only one of Filter_EWMA, Filter_Butterworth, and Filter_Exp_Disc can be True at once and the user space Minstrel HT will not execute if this constraint is not fulfilled. In the case of this constraint not being fulfilled, user space Minstrel HT will give control to the kernel Minstrel HT.
5) First analysis of the estimators
After the implementation of the two additional filters described in (2), an experiment was conducted for 10 minutes and the rate stats output collected in the CSV file was analyzed using the ‘seaborn’ visualization tool in Python. The goal of the experiment was to compare the estimated throughput of the three filters: Exponentially Weighted Moving Average, Exponentially Discounted, and the Butterworth filter.
Description of the Experiment
The experiment was conducted on a custom Banana Pi router, Mediathek 7622 WiFi chip to be exact. The user space Minstrel HT was run from Macbook Pro 13’ 2020 (base model) using the wireless link. Furthermore, an iperf3 connection was also set up between the Macbook Pro and the custom Banana Pi router for the entirety of the experiment. The experiment yielded rate statistics for a total of 24 data rates.
For conciseness, this sub-section only consists of a few handpicked results from the experiment. The average throughput achieved by each data rate was plotted against time in a line graph, box plot, and scatter plot.
The first phase of GSoC ’22 has been mostly about making the user space Minstrel HT compatible with the new RateMan, implementing new filters/estimators, and also making the output more readable and convenient for analysis. Furthermore, the user space Minstrel HT has been added with a configurable script allowing users to customize the rate control to the desired settings. The first phase ended with the first analysis of the estimated throughput using the three different filters: Exponentially Weighted Moving Average (EWMA), Exponentially Discounted, and Butterworth filter.
The second phase of GSoC ’22 will mostly entail research and analysis of the user space Minstrel HT. Along with that, the user space Minstrel HT will be further extended with functionalities from the kernel variant such as calculating the number of retransmission, random sample tables, and reducing the number of spatial streams.
Thanks for reading!