On Fri, Aug 26, 2011 at 4:27 PM, Luis R. Rodriguez [off-list ref] wrote:
I've just read this thread:
http://marc.info/?t=131277868500001&r=1&w=2
Since its not linux-wireless I'll chime in here. It seems that you are
trying to write an algorithm that will work for all networking and
802.11 devices. For networking is seems tough given driver
architecture and structure and the hope that all drivers will report
things in a fairly similar way. For 802.11 it was pointed out how we
have varying bandwidths and depending on the technology used for
connection (AP, 802.11s, IBSS) a different number of possible peers
need to be considered. 802.11 faced similar algorithmic complexities
with rate control and the way Andrew and Derek resolved this was to
not assume you could solve this problem and simply test out the water
by trial and error, that gave birth to the minstrel rate control
algorithm which Felix later rewrote for mac80211 with 802.11n support
[1]. Can the BQL algorithm make use of the same trial and error
mechanism and simply try different values and and use EWMA [2] to pick
the best size for the queue ?
[1] http://wireless.kernel.org/en/developers/Documentation/mac80211/RateControl/minstrel
[2] http://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average
Let me elaborate on 802.11 and bufferbloat as so far I see only crap
documentation on this and also random crap adhoc patches. Given that I
see effort on netdev to try to help with latency issues its important
for netdev developers to be aware of what issues we do face today and
what stuff is being mucked with.
As far as I see it I break down the issues into two categories:
* 1. High latencies on ping
* 2. Constant small drops in throughput
1. High latencies on ping
===================
It seems the bufferbloat folks are blaming the high latencies on our
obsession on modern hardware to create huge queues and also with
software retries. They assert that reducing the queue length
(ATH_MAX_QDEPTH on ath9k) and software retries (ATH_MAX_SW_RETRIES on
ath9k) helps with latencies. They have at least empirically tested
this with ath9k with
a simple patch:
https://www.bufferbloat.net/attachments/43/580-ath9k_lowlatency.patch
The obvious issue with this approach is it assumes STA mode of
operation, with an AP you do not want to reduce the queue size like
that. In fact because of the dynamic nature of 802.11 and the
different modes of operation it is a hard question to solve on what
queue size you should have. The BQL effort seems to try to unify a
solution but obviously did not consider 802.11's complexities. 802.11
makes this very complicated given the PtP and PtMP support we have and
random number of possible peers.
Then -- we have Aggregation. At least AMPDU Aggregation seems to
empirically deteriorate latency and bufferbloat guys seem to hate it.
Of course their statements are baseless and they are ignoring a lot of
effort that went into this. Their current efforts have been to reduce
segment size of a aggregates and this seems to help but the same
problem looms over this resolution -- the optimal aggregation segment
size should be dynamic and my instincts tell me we likely need to also
rely on a minstrel-like based algorithm for finding the optimal length.
2. Constant small drops in throughput
=============================
How to explain this? I have no clue. Two current theories:
a. Dynamic Power save
b. Offchannel operations on bgscans
c. Bufferbloat: large hw queue size and sw retries
One can rule out (a) and (b) by disabling Dynamic Power Save (iw dev
wlan0 power_save off) and also bg scans. If its (c) then we can work
our way up to proving a solution with the same fixes for the first
latency issue. But there are more subtle issues here. Bufferbloat
folks talk about "ants" and "elephants". They call "Elephants" as
frames that are just data, but "ants" are small frames that build make
the networks work -- so consider 802.11 management frames, and TCP
ACKs, and so forth. They argue we should prioritize these more and
ensure we use whatever techniques we can to ensure we reduce latency
for them. At least on ath9k we only aggregate data frames, but that
doesn't mean we are not aggregating other "ant" frames. We at least
now have in place code to not aggregate Voice Traffic -- that's good
but we can do more. For example we can use AMSDU TX support for small
frame. This means we'd need to prioritize AMSDU TX support, which we
do not have support for in mac80211. I think this will help here, but
consider queue size too -- we can likely get even better results here
by ensuring we reduce latency further for them.
Hope this helps sum up the issue for 802.11 and what we are faced with.
Luis
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
I have a few other things to correct and comment on from the earlier
postings on this topic, but I'll start here, and work backwards.
On Mon, Aug 29, 2011 at 2:10 PM, Luis R. Rodriguez [off-list ref] wrote:
On Mon, Aug 29, 2011 at 2:02 PM, Luis R. Rodriguez [off-list ref] wrote:
quoted
Hope this helps sum up the issue for 802.11 and what we are faced with.
I should elaborate a bit more here on ensuring people understand that
the "bufferbloat" issue assumes simply not retrying frames is a good
thing. This is incorrect.
No, we don't assume that "simply not retrying frames is a good thing".
The particular patch to which you are referring is part of a series of
patches still under development and test and is already obsolete.
In particular, the bug we were stomping in that thread involved
excessive retries in the packet aggregation queue on the ath9k driver,
where a ping at distance, was taking 1.6 seconds to get there.
http://www.bufferbloat.net/issues/216 - I note there was a lot of
confusing activity around this bug as this was the final piece of a
solution to why my mesh network in Nica went to h*ll in rain, and I
was trapped in a hotel at the time.
Far worse ping times have been observed in the field - 20+ seconds, or
more - and as most internet protocols were designed with a little over
a lunar diameter in mind at most (~2 seconds of latency) - induced
latency of over a certain point is a very bad thing as it introduces
major problems/timeouts in what we now call the 'ANT' protocols -
DHCP, DNS, ARP, ND, etc - as well as begin to serious muck with the
servo mechanisms within TCP itself.
Please note that ping is merely a diagnostic - all sorts of packets
are exhibiting unbounded latency across most wireless standards.
Retrying wireless frames with bounded latency is a good thing.
Dropping packets to signal congestion is a good thing, also. Knowing
when to drop a packet is a very good thing. Preserving all packets, no
matter the cost, leads to RFC970.
TCP's congestion algorithm is designed to
help with the network conditions, not the dynamic PHY conditions.
Agreed, although things like TCP westwood and the earlier vegas,
attempt to also measure latencies more dynamically.
Also, I have always been an advocate of using "split tcp" when making
the jump to from wired to wireless.
The
dyanmic PHY conditions are handled through a slew of different means:
* Rate control
* Adaptive Noise Immunity effort
Rate control is addressed either in firmware or by the driver.
Typically rate control algorithms use some sort of metrics to do best
guess at what rate a frame should be transmitted at. Minstrel was the
first to say -- ahhh the hell with it, I give up and simply do trial
and error and keep using the most reliable one but keep testing
different rates as you go on. You fixate on the best one by using
EWMA.
Which I like, very much.
I note that the gargoyle traffic shaper attempts to use the number of
packets in a conntracked connection as a measure of the TCP
mice/elephant transition to determine what traffic class the stream
should be in.
It cannot, however, detect a elephant/mouse transition, and perhaps
if there was also EWMA in conntrack, it may help the shaping problem
somewhat.
The concepts of "TCP mice and elephants" are well established in the
literature (see google), however the concept of an 'Ant' is not, it's
a new usage we have tried to establish to raise the importance of
lower latency needed, system critical packets on local wireless lans.
What I was arguing early was that perhaps the same approach can be
taken for the latency issues under the assumption the resolution is
queue size and software retries. In fact this same principle might be
able to be applicable to the aggregation segment size as well.
EWMA time and feedback to higher layers, of how long it takes packets
to make a given next-hop destination
Also somehow passing up the stack that 'this (wireless-n) destination
can handle an aggregate of 32 packets or XX bytes', and this
destination (g or b), can't, would make
applying higher level traffic shaping and fairness algorithms such as
SFB, RED, SFQ, HSFC, actually somewhat useful.
There is also the huge weight of wireless multicast packets on
wireless-n, which can be well over 300x1 vs normal packets at present,
to somehow account for throughout the stack. It only takes a little
multicast to mess up your whole day.
Now, ANI is specific to hardware and does adjustments on hardware
based on some known metrics. Today we have fixed thresholds for these
but I wouldn't be surprised if taking minstrel-like guesses and doing
trial and error and EWMA based fixation would help here as well.
In this 80 minute discussion of the interaction of wireless stack
between myself and felix feitkau, we attempt to summarize all the work
re bufferbloat and wireless specific to the ath9k done to date, and in
the last 10 minutes or so, speculate as to further solutions,based on
and expanding on andrew's input from the previous week.
http://huchra.bufferbloat.net/~d/talks/felix/
There will be a transcript available soon.
Felix has (as of this morning) already implemented pieces of what we discussed.
There is an earlier discussion with Andrew McGregor, as well as
transcript, here:
http://huchra.bufferbloat.net/~d/talks/andrew/
The transcriptionist struggles mightily with the acronyms and I
haven't got around to trying to fix it yet. I'd like very much to
capture andrew's descriptions of how minstrel actually works and one
day fold all this stuff together, along with how power management
actually works on wireless, etc, so more people internalize how
wireless really works.
--
Dave Täht
http://www.bufferbloat.net
On Mon, Aug 29, 2011 at 2:02 PM, Luis R. Rodriguez [off-list ref] wrote:
On Fri, Aug 26, 2011 at 4:27 PM, Luis R. Rodriguez [off-list ref] wrote:
Let me elaborate on 802.11 and bufferbloat as so far I see only crap
documentation on this and also random crap adhoc patches.
I agree that the research into bufferbloat has been an evolving topic, and
the existing documentation and solutions throughout the web is inaccurate
or just plan wrong in many respects. While I've been accumulating better
and more interesting results as research continues, we're not there yet...
Given that I
see effort on netdev to try to help with latency issues its important
for netdev developers to be aware of what issues we do face today and
what stuff is being mucked with.
Hear, Hear!
As far as I see it I break down the issues into two categories:
* 1. High latencies on ping
* 2. Constant small drops in throughput
I'll take on 2, in a separate email.
1. High latencies on ping
===================
For starters, no, "high - and wildly varying - latencies on all sorts
of packets".
Ping is merely a diagnostic tool in this case.
If you would like several gb of packet captures of all sorts of streams
from various places and circumstances, ask. JG published a long
series about 7 months back, more are coming.
Regrettably most of the most recent traces come from irreproducible
circumstances, a flaw we are trying to fix after 'CeroWrt' is finished.
It seems the bufferbloat folks are blaming the high latencies on our
obsession on modern hardware to create huge queues and also with
software retries. They assert that reducing the queue length
(ATH_MAX_QDEPTH on ath9k) and software retries (ATH_MAX_SW_RETRIES on
ath9k) helps with latencies. They have at least empirically tested
this with ath9k with
a simple patch:
https://www.bufferbloat.net/attachments/43/580-ath9k_lowlatency.patch
The obvious issue with this approach is it assumes STA mode of
operation, with an AP you do not want to reduce the queue size like
that. In fact because of the dynamic nature of 802.11 and the
If there is any one assumption about the bufferbloat issue that people
keep assuming we have, it's this one.
In article after article, in blog post after blog post, people keep
'fixing' bufferbloat by setting their queues to very low values,
and almost miraculously start seeing their QoS start working
(which it does), and then they gleefully publish their results
as recommendations, and then someone from the bufferbloat
effort has to go and comment on that piece, whenever we
notice, to straighten them out.
In no presentation, no documentation, anywhere I know of,
have we expressed that queuing as it works today
is the right thing.
More recently, JG got fed up and wrote these...
http://gettys.wordpress.com/2011/07/06/rant-warning-there-is-no-single-right-answer-for-buffering-ever/
http://gettys.wordpress.com/2011/07/09/rant-warning-there-is-no-single-right-answer-for-buffering-ever-part-2/
There has been no time, since the inception of the bufferbloat
concept, have we had a fixed buffer size in any layer of the
stack as even a potential solution.
And you just did applied that preconception to us again.
My take on matters is that *unmanaged* buffer sizes > 1 is a
problem. Others set the number higher.
Of late, given what tools we have, we HAVE been trying to establish
what *good baseline* queue sizes (txqueues, driver queues, etc)
actually are for wireless under ANY circumstance that was
duplicate-able.
For the drivers JG was using last year, that answer was: 0.
Actually, less than 0 would have been good, but that
would have involved having tachyon emitters in the
architecture.
For the work that felix and andrew recently performed on the ath9k,
it looks to be about 37 for STA mode, but further testing is required
and is taking place... as well as instrumentation of the tcp stack, changes
to the system clock interrupt, and a horde of other things.
As for AP performance... don't know. Am testing, capturing streams,
testing contention, building up labs, and creating a distro to deploy
to the field to test everything with.
different modes of operation it is a hard question to solve on what
queue size you should have. The BQL effort seems to try to unify a
solution but obviously did not consider 802.11's complexities.
I only noticed the presentation and thread a few days ago. I do happen
to like byte, rather than packet limits, as a start towards sanity, but
framing overhead is still a problem, and an effective API and
set of servos more so.
802.11
makes this very complicated given the PtP and PtMP support we have and
random number of possible peers.
Then -- we have Aggregation. At least AMPDU Aggregation seems to
empirically deteriorate latency and bufferbloat guys seem to hate it.
I think aggregation is awesome, actually. I've said so on multiple occasions.
After reading the early work done on it, back in the early 2000s, I thought it
could not be made to work, at all. I was wrong.
The problems I have with aggregation as seemingly commenly
implemented today are:
0) Attempts to make the media look 100% perfect
1) Head of line blocking
2) Assumption that all packets are equal.
3) Co-existence with previous forms of 802.11 is difficult
4) Horrible behavior with every AQM algorithm, particularly with fair queuing
Of course their statements are baseless and they are ignoring a lot of
effort that went into this. Their current efforts have been to reduce
segment size of a aggregates and this seems to help but the same
I note that some of the ongoing suggestions actually will make it statistically
more likely that stuff emerging from higher levels of the stack will be even
more aggregate-able than it is currently.
Also, it would be good to have some statistics as to how good aggregation
is currently, actually working under normal multiuser workloads.
A suggestion of felix's was to make that available via netlink broadcast.
problem looms over this resolution -- the optimal aggregation segment
size should be dynamic and my instincts tell me we likely need to also
rely on a minstrel-like based algorithm for finding the optimal length.
We agree very much it should be dynamic.
--
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://the-edge.blogspot.com