Author: Prashiddha

Hi everyone! With the GSoC 2022 session almost coming to an end, this is my final blog post to share all of the accomplishments, conclusions, and outlook for the Minstrel TX Rate Control in user space.

Goals of the Project

• Adding a proper output to the existing user space Minstrel HT to aid in rate control analysis.
• Extending user space Minstrel HT with missing functions present in its kernel counterpart.
• Addition of new estimators/filters for research purposes.
• Proper documentation, demo, and guide on working with the Minstrel HT package.

All of the mentioned goals have been completed. Furthermore, there have been additional changes/improvements to the user space Minstrel HT that isn’t listed above. With this, the next sections will cover all of my contributions to the project followed by future work and limitations.

(1) New Output

Before GSoC ’22, the user space Minstrel HT didn’t have a proper output which wasn’t even easily interpretable. Furthermore, it wasn’t possible to run a script to analyze the performance of the user space Minstrel HT. Hence, I’ve replaced the old output which was simply a printout of the rate statistics dictionary with its own dedicated file and folder for each access point. For each access point and the physical WiFi chip, it creates two files: rc_stats and rc_stats_csv. The rc_stats is a human-readable output of the RateTable object for user convenience whereas the rc_stats_csv is a file that stores all the RateTable data throughout the execution of user space Minstrel HT for offline analysis.

The output has been previously discussed in the previous blog post with the screenshot of the outputs which can be found here.

(2) Addition of new functions from kernel Minstrel HT

The user space Minstrel HT has been extended with additional functionalities from the kernel Minstrel HT which was missing prior to GSoC ’22. Consequently, the user space Minstrel HT now, in terms of functionality, is closer to its kernel counterpart than before.

get_avg_ampdu_len: Calculates and returns the average AMPDU length for a station connected to the access point.

calc_retransmit: Previously, the retry count in the multi-rate retry chain was static and set to a specific value (10) for all the rates. With this new function, the user space Minstrel HT now dynamically computes the retry count for each rate in the rate setting.

check_sudden_death: Checks if the two best throughput rates have sudden packet loss and, if the packet count is greater than 30 with 75% loss, then the affected rate is downgraded.

prob_rate_reduce_streams: Tries to find a more robust rate index that uses fewer streams than the current maximum probability rate.

downgrade_rate: Reduces either the best or the second best throughput rate to the maximum group throughput rate from a lower group that uses fewer streams.

For the addition of these functionalities, the RateMan package had to be extended to parse additional station information such as AMPDU length, AMPDU packet, and overhead for MCS and legacy rates.

(3) New Estimators

The user space Minstrel HT has been added with two new filters: Butterworth Filter and Exponentially Discounted Averaging and Variance. The kernel Minstrel HT no longer uses the Exponentially Weighted Moving Average (EWMA) and has switched to the Butterworth filter, however, prior to GSoC ’22, the user space Minstrel HT only had a simple implementation of the EWMA. The details on the Butterworth and the Discounted filter have been already discussed in my previous blog post which also includes the implemented mathematical formulas.

Regarding the EWMA, the previous implementation of the filter in user space Minstrel HT was also not identical to the kernel variant. Since the EWMA is used to calculate the average AMPDU length for a station, I’ve updated the implementation of the EWMA in the user space Minstrel HT and now consists of both EWMA level and division.

(4) Restructure

During the GSoC ’22 coding period, the RateMan package was restructured twice and, as the user space Minstrel HT is dependent on RateMan to perform kernel rate control functionalities, it was also modified to make the rate control algorithm compatible with the changes. Additionally, the user space Minstrel HT was also refactored to split the minstrel module into two modules: minstrel and sample module. Consequently, this enables each station to have an independent Sample object for probing which can be scaled and customized as needed in the future. Furthermore, the previous structure of user space Minstrel HT consisted of several independent loops which could have been avoided or merged to save computation time. Therefore, I’ve reduced the number of iterations in the minstrel module which has significantly reduced the computation time.

Previously, to obtain the best throughput rate and also the maximum probability rate, the user space Minstrel HT ran all the computations of finding the rates every time and was not stored to be accessed later. However, I’ve changed it such that, for an update interval, the best throughput rate and maximum probability rate are calculated only once and are available as an attribute of the RateTable object for direct access. Furthermore, I’ve also added a new attribute called “max_group_prob_rates” which stores the maximum probability for each group.

(5) Configuration

The user space Minstrel HT has been added with a configuration module to tweak filter parameters and rate control properties such as sample interval and update interval. The configuration file also allows the user to select the filter to be used for rate control. Currently, the user can choose from the following filters: Exponentially Weighted Moving Average (EWMA), Butterworth filter, and Exponentially Discounted Averaging and Variance.

The configuration parameters have been discussed in the previous blog post if this is in the interest of the reader. I have not included it here as this blog post is meant to only serve as an overview of all the changes and reiterating it here would only make the post longer.

(6) Rate-setting Experiment

Towards the end of GSoC ’22, I was also involved in conducting several experiments to validate the rate setting functionality in user space. For this, I created a separate GitHub repository with scripts to configure and run rate-setting experiments. The experiment script, for all supported rates, sets the rate between the client and access point, and after a rate-setting delay collects packet statistics for a specified time duration. The rate-setting delay and the time duration for rate statistics collection are completely configurable by the user. The output is stored in a file that shows, for each rate setting, the rates used, and their statistics.

For example, a WiFi connection with three supported rates could have the following experiment output:

Setting Rate Index 00

{’00’: {‘attempts’: 275927, ‘success’: 236525, ‘timestamp’: ’16d54c2156813120′}}

Setting Rate Index 01

{’01’: {‘attempts’: 366064, ‘success’: 318634, ‘timestamp’: ’16d54c3dfcf4af70′}, ’00’: {‘attempts’: 1199, ‘success’: 584, ‘timestamp’: ’16d54c3cb7d445a0′}}

Setting Rate Index 40

{’40’: {‘attempts’: 270312, ‘success’: 255716, ‘timestamp’: ’16d54deb84d2b0a0′}}

The middle result would denote that after setting the rate between the connection to index ’01’, we still see that rate ’00’ was used where we would generally only expect to see ’01’.

(7) Sample Rate

The last thing that I worked on during GSoC ’22 was another prominent but older rate control algorithm, called Sample Rate, in user space. The Sample Rate algorithm was developed by John C. Bicket in 2005. Unlike Minstrel HT, Sample Rate is not time interval based but real-time packet-based rate control. In the beginning, the Sample Rate algorithm sets the rate index to the highest bit rate. If a rate index fails, then it switches to the next highest bit rate until it finds a rate that works. Every 10th packet, the algorithm samples a random bit rate that does not have four successive packet failures, and the lossless transmission time is less than the average transmission time of the current best rate.

The algorithm uses only the latest results that are not older than 10 seconds to determine the average transmission time for each bitrate. The best rate is the data rate with the lowest average transmission time per packet. The transmission time is calculated as follows:

tx_time(rate) = airtime(rate) + backoff_time(failed_packetes)

The average backoff time, in microseconds, for up to 8 attempts of a unicast packet is:

Where to find my work?

• Introduction blog post
• Mid-term blog post
• Final blog post

GitHub Repositories

• scnx-py-minstrel
• scnx-snippets/rate_setting_validation
• scnx-sample-rate

The repositories have not been public yet, but they will soon be released as open-source.

Future Work and Limitations

The user space Minstrel HT is running and fully functional but it has been only run on decent hardware i.e. laptop and not on embedded systems. It could be that the user space Minstrel HT requires heavy computation and may not be able to perform timely update intervals when running on an OpenWRT router itself. The output file, rc_stats_csv, file stores all the historical RateTable data which causes it to grow quite quickly and infeasible for experiment durations longer than several hours. Hence, a good addition to the user space Minstrel HT could be an in-built compression for the CSV file.

Furthermore, there are still some minor functionalities remaining to be implemented in the user space Minstrel HT. The kernel Minstrel HT uses a random sampling table to select probe rates which could be also implemented in the user space Minstrel HT as well instead of filtering from a list of potential probe rates. Additionally, now that the average AMPDU length can be calculated in user space Minstrel HT, the AMPDU length can be used to find the estimated throughput in an exact way as in the kernel variant.

The user space rate control API (minstrel-rcd) doesn’t have a way to set the retry count for RTS/CTS frames. Once this is implemented in the API, the calc_retransmit function in the user space Minstrel HT can be extended to compute and set the retry count for RTS/CTS frames as well. Similarly, the minstrel_ht_get_max_amsdu_len from the kernel Minstrel should also be implemented in the user space, in case it can be explicitly used which isn’t the case as of now.

Concluding Thoughts

The GSoC ’22 session has been a great opportunity to research and develop user space rate control algorithms. Even though, this is only the start of user space rate control algorithms, within the short time frame, a lot of work has been completed which has met and exceeded the initial goals. The Minstrel HT user space algorithm is now almost complete with all the functionalities from its kernel variant. Aditionally, another user space algorithm, Sample Rate, has also been implemented as a python package using RateMan.

I would like to thank my mentor, Prof. Thomas Hühn for his time and guidance throughout the project. This was a fruitful experience and would love to see the future of rate control in user space.

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.

Introduction

Hi everyone! I’m Prashiddha. I have recently graduated from Jacobs University Bremen with a BSc. Computer Science and minors in Robotics and, Global Economics and Management. For the past year, I have been involved in the research and development of open-source software at SupraCoNeX, primarily focusing on facilitating rate control in user space, which will soon be public.

For GSoC’22, I’ll be working on implementing and testing Minstrel HT, the default WiFi rate control for Linux-based OpenWRT OS, in user space. This first blog post intends to cover details on the necessary background to understand the project and its implementation.

What is WiFi Rate Control?

A typical WiFi network consists of at least a sender and a receiver that communicate through the propagation of radio frequencies within the license-free ISM band. The radio waves carry information in binary as an encoding, and the sender devices can choose from several modulation and transmission parameters such as coding rate, bandwidth, and guard interval. The choice of a transmission scheme between the WiFi devices determines the theoretical network throughput or data rate. A metric called the Modulation Coding Scheme (MCS) Index has been defined to help better understand the WiFi data rates and the RF environment of the network. The MCS index is based on the parameters of the transmission schemes mentioned above.

With newer IEEE 802.11 standards such as IEEE 802.11ax, there are hundreds of available MCS rates for transmission. At first glance, it may seem like maximum data transmission could be easily attained using only those rates which yield the highest theoretical throughput. However, the modulations which achieve high data rates only work best when the link between the WiFi devices is robust. Furthermore, compared to wired-based communication, the wireless communication channel demonstrates higher dynamics and is prone to interference, especially if multiple wireless devices share the medium uncoordinated. As such, the performance of WiFi networks is far from optimal, and there have been significant efforts to develop WiFi rate control algorithms that dynamically adapt transmission data rates in response to the varying wireless channel conditions.

Motivation

In Linux-based OpenWRT WiFi devices, the mac80211 subsystem in the kernel space is responsible for rate control. This includes the implementation of rate control algorithms like the Minstrel HT in the kernel space. The kernel space provides full access to the device’s hardware and memory. Development of modules is hence subject to the risk of complete system failure due to bugs or failure in particular modules and submodules. Additionally, development in kernel space is restricted to the use of integer value operations. Due to the instability and risk involved in accessing the floating-point unit, floating-point operations are avoided in kernel space. Lastly, capabilities for prototyping and debugging required research and development are highly restricted in this space.

Given the limitations and lack of ease of development in kernel space, the need for a user space rate control algorithm is apparent. With this, my GSoC’22 project will focus on implementing a user space variant of Minstrel HT with experiments designed to compare the performance with its kernel space counterpart.

Deliverables of the project

The end goals of my GSoC ’22 projects are as follows:

• Software Architecture of the user space Minstrel HT implementation in Python.
• Proper Documentation and Guide on working with the Minstrel HT package.
• Ready to run demo script to showcase the potential of user space Minstrel HT.
• Detailed analysis of WiFi rate control experiments for performance comparison between kernel and user space Minstrel HT.

What’s been already done?

Prior to GSoC ’22, I had already been heavily involved in the implementation of Rateman, short for Rate Manager, which acts as an intermediary to provide necessary information and functionalities for WiFi rate control in user space. The Rateman package is still under development and will soon be released as an open-source OpenWRT package. Furthermore, as a part of my bachelor thesis, I’ve already implemented a working version of the user space Minstrel HT in Python using Rateman.

Since the rate control algorithm in user space needs to be designed such that it can work on multiple access points simultaneously, initially, multiple experiments were conducted to evaluate various methods of parallelizing rate control from the Rateman, namely async task, thread pool, and process pool. The results have indicated async task to be the best scheme for parallelizing rate control from Rateman.

With this, the user space Minstrel HT in Python has been developed to be executed as an async task and the first results seem to indicate towards a comparable performance with its kernel counterpart. However, the first experiments were far from foolproof and require better-designed experiments to yield a concrete result.

What’s next?

The user space Minstrel HT is not complete and still requires implementation of additional features in order to be identical to the kernel Minstrel HT in terms of functionality.

• Changing the output of user space Minstrel HT to a live printout of the rate statistics table.
• Adding option to store the output in a CSV file to aid in comparison with the kernel Minstrel HT.
• Extending user space Minstrel HT with functionalities from the kernel variant such as calculating the number of retransmission, random sample table, and reducing the number of spatial streams.
• Adding a new estimator called Butterworth Filter which is currently used by the kernel Minstrel HT.
• Modifying user space Minstrel HT to accommodate for various WiFi rate control experiments if needed.

Concluding Thoughts

With the start of GSoC ’22 coding period, I’ll begin with modifying the output of user space Minstrel HT to the printout of live rate statistics along with the option to save it in a CSV file, identical to the kernel Minstrel HT. This will be followed by extending the user space Minstrel HT with the remaining functionalities from the kernel variant. In the end, the project will mainly focus on experimentations for performance analysis of Minstrel HT in user space.

With this, I’d like to conclude the first blog on the user space Minstrel HT GSoC ’22 project with freifunk. Please feel free to reach out and connect with me. 🙂

Thanks for reading!