[Make-wifi-fast] Thoughts on tackling airtime fairness

[Toke Høiland-Jørgensen]

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=&arnumber=1424745&isnumber=30730

[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=&arnumber=6011749&isnumber=6011722

[3] Minho Kim, Eun-Chan Park, and Chong-Ho Choi, “Adaptive Two-Level
Frame Aggregation for Fairness and Efficiency in IEEE 802.11n Wireless LANs,”
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=&arnumber=1424745&isnumber=30730