[ath9k-devel] Bayesian rate control

["Thomas Hühn" <thomas@inet.tu-berlin.de>]

> On 23 Oct 2016, at 15:57, Bj?rn Smedman <bjorn@openias.org> wrote:
> 
> Hi all,
> 
> I've been thinking about rate control a bit lately. I've written up
> some of my thoughts in a blog post
> (http://www.openias.org/bayesian-wifi-rate-control), but very briefly
> put I'd like to build a rate control algorithm based on Bayesian
> statistical inference, possibly by modeling the rate control problem
> as a "multi-armed bandit" problem and/or using Thompson sampling.
> 
> A couple of questions for the list:
> 
> 1. Is there anybody else out there thinking along similar lines?
> 
> I'd very much like to find collaborators interested in working on
> this. It could serve as a pretty nice masters thesis problem, for
> example.
> 
> 2. What would be the best hardware/software stack to base this work on?
> 
> I'm thinking the best driver for rate control experimentation would be
> ath9k, right? If so then a TP-Link TL-WA901ND router (apparently based
> on Qualcomm QCA956x SOC) with OpenWrt, and a TP-Link TL-WDN4800 PCIe
> card (apparently based on Atheros AR9380 with PCI ID 168c:0030) for my
> desktop sounds like a good combo, no? But would I have to run a custom
> kernel on my desktop then (or can I somehow get by with an Ubuntu
> standard kernel)?
> 
> Any other thoughts or pointers are also more than welcome.
> 
> Many thanks,
> 
> Bj?rn Smedman
> _______________________________________________
> ath9k-devel mailing list
> ath9k-devel at lists.ath9k.org
> https://lists.ath9k.org/mailman/listinfo/ath9k-devel
Hi Bjoern,

Nice to have someone remembering me on a one year idea I have roughly implemented but never got the paper ready :)
My comments are inline:

> On 23 Oct 2016, at 15:57, Bj?rn Smedman <bjorn@openias.org> wrote:
> 
> Hi all,
> 
> I've been thinking about rate control a bit lately. I've written up
> some of my thoughts in a blog post
> (http://www.openias.org/bayesian-wifi-rate-control), but very briefly
> put I'd like to build a rate control algorithm based on Bayesian
> statistical inference, possibly by modeling the rate control problem
> as a "multi-armed bandit? problem and/or using Thompson sampling.

While I have designed and implemented Minstrel-Blues in ath5k and mac80211 and digged into the rate control code, I observed several parts that I would like to do differently as is seems there is room for an improvement. Over time I started to look around for a proper mathematical view on rate control and found the multi-armed-bandit problem a very promising way to solve such a WiFi resource allocation problem.
The two major publications that I used as motivation/guideline and my proof of concept implementation:

https://people.kth.se/~alepro/pdf/infocom2014.pdf

jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf

Thompson Sampling is straight forward to understand/implement and to apply to the rate problem as dynamic exploration vs. exploitation.
I have not played with the optimal solution by Gittins Index or the UBC alternatives.
So I started detouring from power control and changed Minstrel? Sampling to follow the Thompsons approach.
Each rate is a bandit with a changing value of expected reward and a variance. And in each round the algo draws a random number from each bandits beta distribution and play the one with the highest reward.
I had to solve certain computational issues. The major I just remember while typing this email was that Thompson uses the Beta distribution. And 
in order to calculate the rate (rate bandit) with the most reward I had to find a fast way of calculation a reverse Beta CDF that runs in kernel space, so on intergers no floats? that was not an easy one.
The first tests were promising in terms of performance, but I focussed on finishing tpc first and than come back to my rate control ideas ? so maybe it is the right time now :)

I have to look up my patch set of Thompson based Minstrel rate control?by the end of the week I find the time.
? all my current rate control changes and WiFi work I do have on my github repo: www.github.com/thuehn <http://www.github.com/thuehn>

> 
> A couple of questions for the list:
> 
> 1. Is there anybody else out there thinking along similar lines?
> 
> I'd very much like to find collaborators interested in working on
> this. It could serve as a pretty nice masters thesis problem, for
> example.

As I am a postdoc at TU Berlin, I would like to collaborate with you.
So I would prefer to write a joint publication as paper .. in an open fashion on github o share latex .. what do you think? 
Are you working in academia or what kind of collaboration do you have in mind ?

> 
> 2. What would be the best hardware/software stack to base this work on?
> 
> I'm thinking the best driver for rate control experimentation would be
> ath9k, right?

As this is currently the most open and advanced driver to use with mac80211 rate control, yes I would go for it.

> If so then a TP-Link TL-WA901ND router (apparently based
> on Qualcomm QCA956x SOC) with OpenWrt, and a TP-Link TL-WDN4800 PCIe
> card (apparently based on Atheros AR9380 with PCI ID 168c:0030) for my
> desktop sounds like a good combo, no? But would I have to run a custom
> kernel on my desktop then (or can I somehow get by with an Ubuntu
> standard kernel)?
> 

My students and me do our daily linux wifi development under Linux Lede trunk, PCengines APU with ath9k Atheros radios.


> Any other thoughts or pointers are also more than welcome.
> 

Greetings from Berlin
Thomas


> Many thanks,
> 
> Bj?rn Smedman
> _______________________________________________
> ath9k-devel mailing list
> ath9k-devel at lists.ath9k.org <mailto:ath9k-devel@lists.ath9k.org>
> https://lists.ath9k.org/mailman/listinfo/ath9k-devel <https://lists.ath9k.org/mailman/listinfo/ath9k-devel>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ath9k.org/pipermail/ath9k-devel/attachments/20161025/c7581a10/attachment-0001.htm