From: "Thomas Hühn" <thomas@inet.tu-berlin.de>
To: ath9k-devel@lists.ath9k.org
Subject: [ath9k-devel] Bayesian rate control
Date: Tue, 25 Oct 2016 19:41:16 -0000 [thread overview]
Message-ID: <A9EF20BC-E559-4537-89F8-5A490C52FD9A@inet.tu-berlin.de> (raw)
In-Reply-To: <CAGp19xcg1qCP3+JNbuiB7Hx=UjLN7KP55wVJT0sKV-iE12501A@mail.gmail.com>
> 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
prev parent reply other threads:[~2016-10-25 19:41 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-10-23 13:57 [ath9k-devel] Bayesian rate control Björn Smedman
2016-10-24 5:28 ` Johannes Berg
2016-10-24 20:23 ` Björn Smedman
2016-10-25 7:14 ` Johannes Berg
2016-10-26 3:25 ` Adrian Chadd
2016-10-26 5:56 ` Johannes Berg
2016-11-05 5:09 ` Adrian Chadd
2016-11-15 9:34 ` Johannes Berg
2016-11-16 4:45 ` Adrian Chadd
2016-10-24 15:09 ` Dave Taht
2016-10-25 19:41 ` Thomas Hühn [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=A9EF20BC-E559-4537-89F8-5A490C52FD9A@inet.tu-berlin.de \
--to=thomas@inet.tu-berlin.de \
--cc=ath9k-devel@lists.ath9k.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).