From mboxrd@z Thu Jan 1 00:00:00 1970 From: =?utf-8?Q?Thomas_H=C3=BChn?= Date: Tue, 25 Oct 2016 19:41:16 -0000 Subject: [ath9k-devel] Bayesian rate control In-Reply-To: References: Message-ID: List-Id: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: ath9k-devel@lists.ath9k.org > On 23 Oct 2016, at 15:57, Bj?rn Smedman 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 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 > > 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 > 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