From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk0-x242.google.com (mail-qk0-x242.google.com [IPv6:2607:f8b0:400d:c09::242]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 9D4DB3BA8D for ; Sun, 8 Jan 2017 12:09:49 -0500 (EST) Received: by mail-qk0-x242.google.com with SMTP id a20so16238559qkc.3 for ; Sun, 08 Jan 2017 09:09:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-transfer-encoding; bh=qzajSd7A6L+mb30QDidUIguF+SKnvSwfZV7sLtPWQBQ=; b=HN0DQqTfeosUnkIpHiBK2V5hp7RyxXHdxojjvt3FxmmTZPB2q9QWz+I/U5uGMup4i+ IXug+FVAUyQR4uQ5/2IFCSolIgwZwOXXQsEEy0r4oEJ4qdB/SG8TxZM0lV9g5iIYkj16 GkqrVZcSyLuASLIYvAaKf/lAQhyXKug1L3v1KkdP4gcGKCB0I1cghEjyeff/pSTGUi8w IM5lbud/KWr8EUHwD0a6RxN+K1bOqOnCAbx3Z0zoctTaJD3OP1OWTDkkWEoef3//VR2Z h7sStwaoa9SpG2JUp2LKyE1LxhqcaE60sS68VjYqSsXEaSW+sy5t8nLcw5v4OtWWCkY3 eWoA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:content-transfer-encoding; bh=qzajSd7A6L+mb30QDidUIguF+SKnvSwfZV7sLtPWQBQ=; b=ckHbhICHt837NnsTa5gZNmunrtVHmp6tf1DWe+nrQnq4XRSfxqN8nsCgWvOK9AA11r hTgNq5wdqvXx9AHZR9vIj+Tjhoal05QHOm5YjkmcehZQAj3UqkqjWaqk8wBXqLWyq1DJ rrrFd8ANiO9z89DbXiYMaFBsM6sjciDkfkB3bKtBn0ER/Koyn9+EDQ+9yDkOZ3RES1Vm mhjwRmcgFoxkQ3gNmu4Ea9tDKdXzD6pgTvWBcpdc+1GEzq+4Wxa3wytcXcsLfizMF3/C FEb4agH6z5fa+U2A4LSVg47vTNqrrpRZ5VeyYKDa7aBBNWv/+mzTKfBSrBICclyuY7RP jsJw== X-Gm-Message-State: AIkVDXIYv1zVHYg24l90Hn+jz8Gmhh7ZvTNuqSVZe4eBqxRmDhtk8OWtb9XljwVT3kcL10CrgbEmsDaBUG2/qw== X-Received: by 10.55.9.15 with SMTP id 15mr83274956qkj.118.1483895389081; Sun, 08 Jan 2017 09:09:49 -0800 (PST) MIME-Version: 1.0 Received: by 10.12.152.197 with HTTP; Sun, 8 Jan 2017 09:09:47 -0800 (PST) In-Reply-To: References: From: Dave Taht Date: Sun, 8 Jan 2017 09:09:47 -0800 Message-ID: To: make-wifi-fast@lists.bufferbloat.net Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: [Make-wifi-fast] Fwd: [ath9k-devel] Bayesian rate control X-BeenThere: make-wifi-fast@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 08 Jan 2017 17:09:49 -0000 ---------- Forwarded message ---------- From: Thomas H=C3=BChn Date: Tue, Oct 25, 2016 at 12:31 PM Subject: Re: [ath9k-devel] Bayesian rate control To: Bj=C3=B6rn Smedman Cc: ath9k-devel@lists.ath9k.org, linux-wireless ??? On 23 Oct 2016, at 15:57, Bj=C3=B6rn 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=C3=B6rn Smedman _______________________________________________ ath9k-devel mailing list ath9k-devel@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=C3=B6rn 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=E2=80=9D 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=E2=80=99 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=E2=80=A6 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 =E2=80= =A6 so maybe it is the right time now :) I have to look up my patch set of Thompson based Minstrel rate control=E2=80=A6by the end of the week I find the time. =E2=80=A6 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 mi= nd ? 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=C3=B6rn Smedman _______________________________________________ ath9k-devel mailing list ath9k-devel@lists.ath9k.org https://lists.ath9k.org/mailman/listinfo/ath9k-devel _______________________________________________ ath9k-devel mailing list ath9k-devel@lists.ath9k.org https://lists.ath9k.org/mailman/listinfo/ath9k-devel --=20 Dave T=C3=A4ht Let's go make home routers and wifi faster! With better software! http://blog.cerowrt.org