[ath9k-devel] Bayesian rate control

[ath9k-devel] Bayesian rate control

[Björn Smedman]

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] Bayesian rate control

[Johannes Berg]

> 1. Is there anybody else out there thinking along similar lines?

I'm not aware, but that may not mean much :)

> 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? 

Seems reasonable, yes. You wouldn't have VHT, but HT has enough search
space to keep you busy ;-)

> But would I have to run a custom kernel on my desktop then (or can I
> somehow get by with an Ubuntu standard kernel)?

You could use a backported driver. https://backports.wiki.kernel.org/

johannes

[ath9k-devel] Bayesian rate control

[Björn Smedman]

Hi Johannes,

Thanks for the pointers.

On Mon, Oct 24, 2016 at 7:28 AM, Johannes Berg
<johannes@sipsolutions.net> wrote:
>> 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?
>
> Seems reasonable, yes. You wouldn't have VHT, but HT has enough search
> space to keep you busy ;-)

Are there any cards out there that support VHT and use s/w rate
control (Minstrel)? Just in case I run out of search space. :P

BR Bj?rn

[ath9k-devel] Bayesian rate control

[Johannes Berg]

On Mon, 2016-10-24 at 22:17 +0200, Bj?rn Smedman wrote:
>?
> Are there any cards out there that support VHT and use s/w rate
> control (Minstrel)? Just in case I run out of search space. :P

Maybe something that's usable with brcmsmac? Not sure I'd recommend
buying Broadcom NICs though at this point, with them having been bought
out and all (and their upstream support is somewhat spotty, so you
might have a hard time finding the right NIC)

johannes

[ath9k-devel] Bayesian rate control

[Adrian Chadd]

hiya,

there's a tplink RTL81xx 11ac NIC that's growing linux and freebsd
support. I believe it's software rate controllable.

The intel 7260 and later parts also allow user controllable rate
control and provide transmit completion feedback, but I don't know
whether it's enough for your needs.

Unfortunately the ath10k firmware .. doesn't :( Not by default, anyway.


-adrian

[ath9k-devel] Bayesian rate control

[Johannes Berg]

> The intel 7260 and later parts also allow user controllable rate
> control and provide transmit completion feedback, but I don't know
> whether it's enough for your needs.

Perhaps. However, existing rate control is *very* tightly coupled to
the driver, and it'd be fairly pointless to disentangle just for the
sake of playing with a rate control algorithm.

Also, the device doesn't support per-frame control nor any kind of
sampling-with-table-fallback, only the rate table that you give to the
device and update.

Btw, mac80211_hwsim with wmediumd doing some medium simulation might
also be something to look at for just extending to VHT.

And come to think of it, there's this new driver Felix et al have been
working on,?mt7601u, which also should support proper rate control
APIs.

johannes

[ath9k-devel] Bayesian rate control

[Adrian Chadd]

Hi,

On 25 October 2016 at 22:56, Johannes Berg <johannes@sipsolutions.net> wrote:
>
>> The intel 7260 and later parts also allow user controllable rate
>> control and provide transmit completion feedback, but I don't know
>> whether it's enough for your needs.
>
> Perhaps. However, existing rate control is *very* tightly coupled to
> the driver, and it'd be fairly pointless to disentangle just for the
> sake of playing with a rate control algorithm.
>
> Also, the device doesn't support per-frame control nor any kind of
> sampling-with-table-fallback, only the rate table that you give to the
> device and update.

Hi,

But there is a per-descriptor TX rate table entry in the driver.
FreeBSD uses it to implement its rate control for the intel drivers.

What am I missing? :)

>
> Btw, mac80211_hwsim with wmediumd doing some medium simulation might
> also be something to look at for just extending to VHT.
>
> And come to think of it, there's this new driver Felix et al have been
> working on, mt7601u, which also should support proper rate control
> APIs.



-adrian

[ath9k-devel] Bayesian rate control

[Johannes Berg]

> But there is a per-descriptor TX rate table entry in the driver.
> FreeBSD uses it to implement its rate control for the intel drivers.
> 
> What am I missing? :)

Not sure. But there isn't a per-descriptor table in the driver. There's
a per-station table, that *can* be used in similar ways, but at least
in Linux none of the APIs are hooked up to the general implementation,
it's all driver/device-specific code, so it'd be very painful to try to
experiment with.

johannes

[ath9k-devel] Bayesian rate control

[Adrian Chadd]

On 15 November 2016 at 01:34, Johannes Berg <johannes@sipsolutions.net> wrote:
>
>> But there is a per-descriptor TX rate table entry in the driver.
>> FreeBSD uses it to implement its rate control for the intel drivers.
>>
>> What am I missing? :)
>
> Not sure. But there isn't a per-descriptor table in the driver. There's
> a per-station table, that *can* be used in similar ways, but at least
> in Linux none of the APIs are hooked up to the general implementation,
> it's all driver/device-specific code, so it'd be very painful to try to
> experiment with.

Ok. well, we do that. :)

I'll let you know how well it works when I'm doing 11ac with the 7260 driver.



-adrian

[ath9k-devel] Bayesian rate control

[Dave Taht]

On Sun, Oct 23, 2016 at 6:57 AM, 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

It is nice to see some newer thinking here.

> 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.

The paper on minstrel's design was never widely published. I linked to it here:

http://blog.cerowrt.org/post/minstrel/

Looking harder at rate control has long been on my todo list, but at
the top of my list to finish first has been the fair queuing
(fq_codel) and airtime fairness work.

https://blog.tohojo.dk/2016/06/fixing-the-wifi-performance-anomaly-on-ath9k.html#results

http://blog.cerowrt.org/post/real_results

Once you are statistically hitting more stations, more often, on a
more regular basis, with smaller txops, I felt that many things that
were perceived as rate control problems would go away, and other
things become easier.

A basic "fix" to minstrel is to opportunistically sample (which so far
as I know, minstrel-blues does), rather than at a fixed rate.

btw: I called my early (unpublished) attempt at a "minstrel-2", "bard". :)

The now-enormous search space is a big problem in present-day
minstrel, followed by excessive retries/latency when sampling, and
hidden stations are becoming more and more of a problem as densities
go up. (long list of minstrel issues on that first link I posted
above).

> A couple of questions for the list:
>
> 1. Is there anybody else out there thinking along similar lines?

Yes and no. At the moment I am thinking about the insights from the
TCP "BBR" work google just published: (paywalled but at:
http://queue.acm.org/app/ ) where they also point to max-plus algebra
as being helpful for solving the problems it had.

> I'd very much like to find collaborators interested in working on
> this. It coruld serve as a pretty nice masters thesis problem, for
> example.

Please join us over on the make-wifi-fast list. There are more than a
few good papers to be had out of it.

>
> 2. What would be the best hardware/software stack to base this work on?

Presently ath9k is the only game in town, and developing/debugging on
x86 is the easiest.

> 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)?

These days I am using a pcengines apu2 as my primary x86 testbed, with
ath9k and ath10k cards in it (and one day mt72). The new turris omnia
looks like a good platform also. I've been trying to use stuff newer
than AR92xx there.

Another box I really like is the ubnt uap-lite.

Prior to all those, it was the wndr3800, archer c7v2, and nanostation
m5s for outdoor work.

>
> Any other thoughts or pointers are also more than welcome.
>
> Many thanks,
>
> Bj?rn Smedman



-- 
Dave T?ht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

[ath9k-devel] Bayesian rate control

[Thomas Hühn]

> 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