Update on Minstrel TX Rate Control in User space – GSoC ’22

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 Minstrel HT WiFi rate control in user space. If you are unfamiliar with WiFi rate control, then you can have a look at my first blog post.

1) Addition of new estimators

WiFi rate controls usually comprise of averaging filter/estimators to update the packet transmission statistics with respect to the newer packet counts in real-time. As such, the Minstrel HT rate control also has an estimator which is currently a variant of the Butterworth Filter.

Butterworth Filter

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: rate₁ with 4 attempts and 5 successes, and rate₂ with 280 attempts and 350 successes. The success probability of both these rates is 80%, however, rate₂ 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 t₀, the following values are initialised to 0: μ₀ = s₀ = W₀ = t₀ = 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 also ignoring the time steps (β = 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:

Config Parameter	Description
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.

Results

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.