From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-yw0-x232.google.com (mail-yw0-x232.google.com [IPv6:2607:f8b0:4002:c05::232]) (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 A99383B260 for ; Wed, 11 May 2016 08:55:22 -0400 (EDT) Received: by mail-yw0-x232.google.com with SMTP id g133so41272418ywb.2 for ; Wed, 11 May 2016 05:55:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc; bh=3OESA+FoUC6PGUhMpG+tH6UjFVkuKXqdwwZ1LMofin0=; b=kmjz42bUBcGfssFlDYMJDnN3Sccz5poI6XA8PxsSWCUzwvc+MXVBhGXVCEV+8tIoJy yuW6WUeZujBseW84Y/5aL6Y3x3GNbwjQGtPVrywst/1du3eAxWn3XjpDZYnZey+q0wtj xkd+KQwmSD49jCSskjvoeDbFV2ncgDIoxcqTw/xv+u2B7Jx6q68vEhvVfw3Ki5+weT4+ lNQsEWdqYfb+grCGFMptLu/3EaUdK5D4iZST+++AHYlWQfW4ovDP0FqeUyJbDNOAfNlW NWxK2KpCvE09CpUMu/0OVDcsGJ0IBAnYJrWGT1Z4t2JlSPM4/DJtp318VMLF7algpSMW vlqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc; bh=3OESA+FoUC6PGUhMpG+tH6UjFVkuKXqdwwZ1LMofin0=; b=HkqaNPQBWwXIcs2vAYiWwE1pPFAIJl9hc/4y/K+zpwFsXjEa+cYkU4zBf17DzM2Std nbMYOHV+VbsHRnFOKfJyTZOgRfUNNO5GMwNHKyRf7T7HtS3MjPc7rXr7mc/oI6k+m65k DUkLPCO1XRpgpoQZWKfg1DfQFPMixeGDOit3FnH9QjgZPs2mOK+KXQMIStgSSxChdzWF jOHQrMmH8M2fgJlRStFShTTVnk4mfhhRIt4Ye6GWnFIkRQdYnmfZdusq7icaebyf19Rq CDIFNq5HDTX+8i5TKuMPCdnBNwH9seF/XXPtb9RePmyxPsdM/FnLOKxzaJrsHLD1gAuI AYSw== X-Gm-Message-State: AOPr4FXOS6XFIUJ2yyMIXWbk1trDQPv5GxK1GKXP5Fz9Ugn2Cya+xS/VUuMX0ER1qbfxQjv+qbTra4JbMkJE7w== MIME-Version: 1.0 X-Received: by 10.129.70.134 with SMTP id t128mr1398692ywa.208.1462971322118; Wed, 11 May 2016 05:55:22 -0700 (PDT) Received: by 10.37.74.134 with HTTP; Wed, 11 May 2016 05:55:22 -0700 (PDT) In-Reply-To: <871t58n5wk.fsf@toke.dk> References: <871t58n5wk.fsf@toke.dk> Date: Wed, 11 May 2016 14:55:22 +0200 Message-ID: From: Luca Muscariello To: =?UTF-8?B?VG9rZSBIw7hpbGFuZC1Kw7hyZ2Vuc2Vu?= Cc: make-wifi-fast@lists.bufferbloat.net Content-Type: multipart/alternative; boundary=001a114d71b8f8c71a0532908d90 Subject: Re: [Make-wifi-fast] Thoughts on tackling airtime fairness 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: Wed, 11 May 2016 12:55:22 -0000 --001a114d71b8f8c71a0532908d90 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Toke, I'd suggest to add this in you list of references: Godfrey Tan and John Guttag, Time-based fairness improves performance in multi-rate WLANs. In Proc of USENIX 2004 https://www.usenix.org/legacy/publications/library/proceedings/usenix04/tec= h/general/full_papers/tan/tan.pdf It's worth having a look to the APware project for freeBSD and Godfrey Tan PhD thesis at MIT. http://nms.csail.mit.edu/projects/apware/ this work predates 802.11n and aggregation. Ten years ago I played with SFQ and madwifi for 802.11g to get max-min time fairness (and so proportional rate fairness) with excellent results. The hacking I made was based on using time quanta instead of bytes. Which required me to get the current PHY rates (AP to all STAtions) and dynamically compute/update SFQ time quanta. It's surprising that 802.11 standard never considered time fairness in the EDCF. A reason might be the time fairness might be enforced using the PCF. IMO, It's a very good topic. Thanks for bringing this up. Luca On Wed, May 11, 2016 at 2:19 PM, Toke H=C3=B8iland-J=C3=B8rgensen wrote: > So one of the components of tackling WiFi performance in Linux is (I > believe) achieving airtime fairness (which turns out to be equivalent to > proportional throughput fairness [1]). This is my attempt to summarise > some thoughts on how to achieve this. I am by no means claiming these > thoughts are necessarily (all) original, a lot of it has been floating > around for a while; I'm simply trying to separate out airtime fairness > as a separate issue that can be tackled orthogonally from the other > parts of the stack (and that hopefully will be complementary). Feedback > welcome, obviously :) > > > In the literature, there are basically three approaches to achieving > airtime fairness: Varying the MAC protocol timing parameters (e.g. TXOP > duration or CWmin; see e.g. [2] for an over-engineered "optimal" way of > doing this), varying the size of the aggregate (see [3]) and scheduling > at the access point (see [4]). The two former approaches are distributed > in nature (i.e. each node adjusts its behaviour in a way that will > result in aggregate airtime fairness for the whole network) while the > latter is access point-centric. > > Improving the access point behaviour is definitely the straight-forward > way, and there are many obvious improvements that can result from that, > as we've already seen in e.g. Michal's patch set. So looking at airtime > fairness from the point of view of the access point makes sense. > > Basically, on a high level I think there are two things that we need to > achieve good airtime fairness: Building the right aggregates (like in > [3]), and scheduling (like in [4]) to compensate for when we get it > wrong or when we can't control the aggregation because the firmware > handles it. > > Now, of course the academic publications tend to be some way from > something that can be implemented in practice; I simply refer to them > here as concepts worth pursuing, and to shape thought. And, well, > because I happen to be in academia myself ;) > > > Getting closer to the practical level, what I plan to go poke at is: > > (1) The ath9k aggregation building logic, to try to achieve > constant-time aggregate size (for a suitable time quantum). Not sure > how much actually needs to change here; the standard already mandates > that an aggregate cannot be longer than 4ms, so the code already takes > time into account. And not sure how this interacts with rate > selection. > > (2) Adding a time-based scheduler to enforce airtime fairness. Building > this on FQ-CoDel seems like the sensible thing to do, to get the same > latency bonus for stations that only transmit occasionally. It would > be nice to be able to stick this in the mac80211 layer to make it > shared between drivers, but not sure the required timing information > is available at that layer. > > > A non-exhaustive list of issues that need to be resolved one way or > another: > > - What to account to each station's airtime? My thought would be > retransmissions, but not time spent waiting for other stations. > > - What about management, control and multicast frames? I'd say just > ignore it (at least for now). > > - How to measure the results? Can we dump the information from the > driver (and is it accurate)? Do we need to parse aircaps? Something > else? > > > Hope this all makes sense. Comments very welcome! :) > > -Toke > > > [1] Li Bin Jiang and Soung Chang Liew, "Proportional fairness in > wireless LANs and ad hoc networks" > > http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=3D&arnumber=3D1424745&isnum= ber=3D30730 > > [2] P. Lin, W. I. Chou and T. Lin, "Achieving airtime fairness of > delay-sensitive applications in multirate IEEE 802.11 wireless LANs," > > http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=3D&arnumber=3D6011749&isnum= ber=3D6011722 > > [3] Minho Kim, Eun-Chan Park, and Chong-Ho Choi, =E2=80=9CAdaptive Two-Le= vel > Frame Aggregation for Fairness and Efficiency in IEEE 802.11n Wireless > LANs,=E2=80=9D > http://www.hindawi.com/journals/misy/2015/548109/ > > [4] Li Bin Jiang and Soung Chang Liew, "Proportional fairness in > wireless LANs and ad hoc networks," > > http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=3D&arnumber=3D1424745&isnum= ber=3D30730 > _______________________________________________ > Make-wifi-fast mailing list > Make-wifi-fast@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/make-wifi-fast > --001a114d71b8f8c71a0532908d90 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Toke,

I'd suggest to add this in yo= u list of references:

Godfrey = Tan and John Guttag, Time-based fairness improves performance in multi-rate= WLANs. In Proc of=C2=A0USENIX 2004

It's worth = having a look to the APware project for freeBSD and Godfrey Tan PhD thesis = at MIT.


this work predates 802.11n and aggregation.
<= font color=3D"#000000" face=3D"Verdana, Arial, Helvetica, sans-serif">
Ten years ago I played with SFQ and madwifi for 802.11g
to get max-min time fairness (and so= proportional rate fairness) with excellent results.=C2=A0 The hacking I ma= de was based on
using ti= me quanta instead of bytes. Which required me to
get the current PHY rates (AP to all STAtions) and= dynamically compute/update=C2=A0SFQ time= quanta.

It's surprising that 802.11 standard = never considered time fairness in the EDCF. A reason might be the time fair= ness might be enforced using the PCF.

I= MO, It's a very good topic.
Thanks for bringing this up.

Luca


On Wed, May 11, 2016 at 2:19 PM, Toke H=C3=B8iland-J=C3=B8rgensen <toke@= toke.dk> wrote:
So one of t= he components of tackling WiFi performance in Linux is (I
believe) achieving airtime fairness (which turns out to be equivalent to proportional throughput fairness [1]). This is my attempt to summarise
some thoughts on how to achieve this. I am by no means claiming these
thoughts are necessarily (all) original, a lot of it has been floating
around for a while; I'm simply trying to separate out airtime fairness<= br> as a separate issue that can be tackled orthogonally from the other
parts of the stack (and that hopefully will be complementary). Feedback
welcome, obviously :)


In the literature, there are basically three approaches to achieving
airtime fairness: Varying the MAC protocol timing parameters (e.g. TXOP
duration or CWmin; see e.g. [2] for an over-engineered "optimal" = way of
doing this), varying the size of the aggregate (see [3]) and scheduling
at the access point (see [4]). The two former approaches are distributed in nature (i.e. each node adjusts its behaviour in a way that will
result in aggregate airtime fairness for the whole network) while the
latter is access point-centric.

Improving the access point behaviour is definitely the straight-forward
way, and there are many obvious improvements that can result from that,
as we've already seen in e.g. Michal's patch set. So looking at air= time
fairness from the point of view of the access point makes sense.

Basically, on a high level I think there are two things that we need to
achieve good airtime fairness: Building the right aggregates (like in
[3]), and scheduling (like in [4]) to compensate for when we get it
wrong or when we can't control the aggregation because the firmware
handles it.

Now, of course the academic publications tend to be some way from
something that can be implemented in practice; I simply refer to them
here as concepts worth pursuing, and to shape thought. And, well,
because I happen to be in academia myself ;)


Getting closer to the practical level, what I plan to go poke at is:

(1) The ath9k aggregation building logic, to try to achieve
=C2=A0 constant-time aggregate size (for a suitable time quantum). Not sure=
=C2=A0 how much actually needs to change here; the standard already mandate= s
=C2=A0 that an aggregate cannot be longer than 4ms, so the code already tak= es
=C2=A0 time into account. And not sure how this interacts with rate
=C2=A0 selection.

(2) Adding a time-based scheduler to enforce airtime fairness. Building
=C2=A0 this on FQ-CoDel seems like the sensible thing to do, to get the sam= e
=C2=A0 latency bonus for stations that only transmit occasionally. It would=
=C2=A0 be nice to be able to stick this in the mac80211 layer to make it =C2=A0 shared between drivers, but not sure the required timing information=
=C2=A0 is available at that layer.


A non-exhaustive list of issues that need to be resolved one way or
another:

- What to account to each station's airtime? My thought would be
=C2=A0 retransmissions, but not time spent waiting for other stations.

- What about management, control and multicast frames? I'd say just
=C2=A0 ignore it (at least for now).

- How to measure the results? Can we dump the information from the
=C2=A0 driver (and is it accurate)? Do we need to parse aircaps? Something<= br> =C2=A0 else?


Hope this all makes sense. Comments very welcome! :)

-Toke


[1] Li Bin Jiang and Soung Chang Liew, "Proportional fairness in
wireless LANs and ad hoc networks"
http://i= eeexplore.ieee.org/stamp/stamp.jsp?tp=3D&arnumber=3D1424745&isnumbe= r=3D30730

[2] P. Lin, W. I. Chou and T. Lin, "Achieving airtime fairness of
delay-sensitive applications in multirate IEEE 802.11 wireless LANs,"<= br> http:/= /ieeexplore.ieee.org/stamp/stamp.jsp?tp=3D&arnumber=3D6011749&isnum= ber=3D6011722

[3] Minho Kim, Eun-Chan Park, and Chong-Ho Choi, =E2=80=9CAdaptive Two-Leve= l
Frame Aggregation for Fairness and Efficiency in IEEE 802.11n Wireless LANs= ,=E2=80=9D
http://www.hindawi.com/journals/misy/2015/548109/

[4] Li Bin Jiang and Soung Chang Liew, "Proportional fairness in
wireless LANs and ad hoc networks,"
http://i= eeexplore.ieee.org/stamp/stamp.jsp?tp=3D&arnumber=3D1424745&isnumbe= r=3D30730
_______________________________________________
Make-wifi-fast mailing list
Make-wifi-fast@list= s.bufferbloat.net
https://lists.bufferbloat.net/listinfo/make-wif= i-fast

--001a114d71b8f8c71a0532908d90--