LinuxLists.cc - [RFC/RFT] minstrel_ht: new rate control module for 802.11n

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On 2010-03-02 4:47 PM, Bj?rn Smedman wrote:
> 2010/3/2 Felix Fietkau <[email protected]>:
>> [snip] also the hardware
>> doesn't even provide enough information to do any kind of precise
>> calculation on airtime utilization by tx attempts. For instance, I don't
>> get any information on how many frames in an A-MPDU were successfully
>> transmitted on each retransmission attempt.
>
> You mean the hardware interprets the block-ack and keeps retrying the
> un-acked frames? I thought it stopped as soon as it got a block-ack to
> let software sort out the acked and un-acked frames and handle the
> "partial" A-MPDU retry.
Not sure, actually. I just looked at the ath9k tx path again, and it
seems that you're right. However it looks like it's not sending rate
control updates until it's done with the software retry, so that's
probably the reason why I wasn't able to make it more precise yet.

>> Software retries are being taken into account on some level, because a
>> software retry is simply going to be part of the next A-MPDU, which will
>> get accounted for in the rate control code.
>
> If my guess on block-ack implementation is correctly there is still
> have a major uncertainty: if the first frame in the A-MPDU is
> transferred correctly but every other frame in the AMPDU fails (and
> has to be retransmitted in other A-MPDUs) you run the risk of counting
> that as a success (and of course wise-versa)...
Yeah, I definitely need to deal with that.

>> This early version will probably not make a fully optimal tradeoff
>> between retransmission probability and raw throughput, but that can
>> probably be tweaked over time, simply by adjusting the internal
>> throughput metric calculation to something that gets close in practice
>> at least most of the time.
>
> I agree this new code is a big step forward and the aim here (with
> this patch) should of course not be a fully optimal solution. But
> shouldn't we try to at least set up a roadmap to remove as much as
> possible of these fundamental flaws / uncertainties?
Sure. I think the way to make this more precise is to ensure that the tx
path sends rate control updates even before it's done with the software
retry. The resulting feedback can then properly be accounted for by
comparing ampdu_len against ampdu_ack_len in the status info, thus
getting accurate statistics on subframe failures.
Still leaves open the question of how this is supposed to be handled for
other drivers, but I guess that can be dealt with later.

> The reason I'm so interested in this subject is I've tried to tweak
> the ath9k rate control to behave reasonably for me. This has taken a
> lot of time and the result is rather poor. Also, these tweaks are not
> general enough to even be contributed back as patches. My feeling is
> that the reason it is so difficult to get a rate control algorithm to
> work for all use-cases is that the underlying model is just plain
> wrong. Radio environments are very varied and complex. Add to that all
> the other variability, such as ANI dynamically adjusting radio chain
> parameters and it's very very difficult to know what is "incorrect but
> good enough".
Interesting.

- Felix

2010-03-01 23:02:27

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

Hi,

On Mon, 1 Mar 2010, Felix Fietkau wrote:

> On 2010-03-01 11:38 PM, Derek Smithies wrote:
>> Hi,
>> Great work on getting this far - it was a huge undertaking.
>>
>> Ok, before diving into the code, can we take a quick moment to think on
>> this. I wonder if you can answer the following questions:
>>
>> a)Minstrel worked hard at using information that is good and reliable: -
>> which is the record of what rates worked, and what rates failed.
>> Minstrel avoids using things like RSSI (which is not reliable)
> Yes, I still rely purely on tx status feedback, no RSSI voodoo.
>
>> b)You have stated in previous emails that with 802.11n there are too many
>> rates for minstrels random sampling technique.
>>
>> What is the approach taken in 802.11n & minstrel? I remember some comment
>> about dividing the 802.11n rate set up into groups, and then minstrel does
>> its thing within the rates of each group. - Do I have the idea here?
> The previous comments were based on faulty tx status feedback because of
> an ath9k issue that I resolved in a previous patch. The current
> implementation still does random sampling, with one exception: each
> sampling attempt goes to a different MCS group.
> Other than that, I split up the MCS rates into groups mainly because
> it's easier to deal with and allows me to calculate raw transmit
> durations at compile time.
>
> I did add some small special cases though. For instance if the code
> detects that the current transmit rate is failing really quickly on a
> multi-stream rate, it falls back to the max_tp_rate of a single-stream
> group, while leaving around enough feedback for EWMA.
> This reduces the strength of the throughput drop when I disconnect one
> antenna (which kills off pretty much all of the dual-stream rates
> immediately).
>
>> Where have you tested 802.11n & minstrel?
> Only at home. I just finished ironing out most of the important bugs
> today, so this hasn't seen any significant long-term testing yet.
>
>> Does 802.11n&minstrel pass the basic test
>> a) put two nodes on the desk - rate is high
>> b) move one of the nodes (or remove antenna) - rate should drop
>> c) move nodes back to the configuration of a)
>> -rate should go high again
> Yes, this was my primary test. I also did some tests with removing both
> antennas and moving the laptop away and back again.
>
> I also did quite a few tests switching back and forth between
> minstrel_ht and the ath9k rate control to compare them as accurately as
> possible. In HT40, rate adaptation with minstrel is usually a little
> slower (only a minor difference here, probably caused by the much larger
> search space), but it's able to deal with sources of interference (e.g.
> Bluetooth) a lot better.
> It also reacts much faster to problems with spatial multiplexing, and
> seems to get a better average throughput in HT20 in my tests.
>
>> Does 802.11n&minstrel work well with time?
>> In other words, is the throughput 10 hours later the same as at the start
>> of the test?
> If I force it to single-stream mode, then it seems to be just as
> reliable at sticking to a specific rate as the legacy implementation.
>
> With dual-stream rates it's hard to tell, because the reliability of
> rates varies quickly, even if the positions is fixed. I do not see any
> *significant* variations in throughput though.

Fantastic. This is encouraging, time to test further then.

Derek.

--
Derek Smithies Ph.D.
IndraNet Technologies Ltd.
ph +64 3 365 6485
Web: http://www.indranet-technologies.com/

"The only thing IE should be used for is to download Fire Fox"

"My favorite language is call STAR. It's extremely concise. It has
exactly one verb '*', which does exactly what I want at the moment."
--Larry Wall

2010-03-02 21:53:27

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On Tue, 2 Mar 2010, Bj?rn Smedman wrote:
(lots deleted)
>
> The reason I'm so interested in this subject is I've tried to tweak
> the ath9k rate control to behave reasonably for me. This has taken a
> lot of time and the result is rather poor. Also, these tweaks are not
> general enough to even be contributed back as patches. My feeling is
> that the reason it is so difficult to get a rate control algorithm to
> work for all use-cases is that the underlying model is just plain
> wrong. Radio environments are very varied and complex. Add to that all
> the other variability, such as ANI dynamically adjusting radio chain
> parameters and it's very very difficult to know what is "incorrect but
> good enough".

Some years ago, my colleagues and I set out to write a rate control
algorithm for madwifi. At that time, the existing rate control algorithms
were best described as "junk". Manual adjustment of the rates at either
end of a link would often double the throughput.
--After some thought - we realised that the rate control algorithm had to
use good data, and make the correct decision on the data.
And so an EWMA based approach was devised which only looked at the success
probability of packets to determine which rate to use in the future.
In other words, "select a rate that we know works, and have recently
tested and verified to work".

This approach worked. When the hardware/driver selected a bad ani setting,
manual adjustment of the rate, or using the ewma based approach -
the throughput was the same (as good as can be achieved).

Even when there were issues in the firmware (ramping, or transmission
delay) manual adjustment of the rate, or using the ewma based approach -
the throughput was the same (as good as can be achieved).

And the rate control algorithm that we wrote was called minstrel.
Felix has taken this on and done wonders to get it to mac80211 and
accepted as the default rate algorithm.
==================

if you look on linux wireless,
http://linuxwireless.org/en/developers/Documentation/mac80211#mac80211_rate_control_algorithms
and read up on rate control algorithms you will find docs for PID and
minstrel.

Where are the docs for the ath9k rate control algorithm?

PID got it wrong - implicit in PID is the assumption that the rates can be
ordered in terms of more successful / less successful - and the ordering
follows the speed (faster speed=less successful).

Since very slow rates are subject to interference loss (imagine there is a
60hz transmitter out there) packets that take a long time to transmit are
far more likely to be shot down, stepping down a rate is going to increase
the loss rate.

*Going on messages like:
http://osdir.com/ml/linux-wireless/2009-11/msg00952.html
*the absence of any docs,
*reliance on RSSI (which is a misleading figure)
I would say your efforts in working on the ath9k rate algorithm were
doomed to failure.

=================================================

> My feeling is that the reason it is so difficult to get a rate control
> algorithm to work for all use-cases is that the underlying model is just
> plain wrong.
yes. minstrel has a very very good model, and works very very well.
Minstrel's model needs to be used in ath9k - and so the work of Felix to
port Minstrel is valuable and appreciated.

> Radio environments are very varied and complex.
Yes, radio environments are varied and complex. If you have a good model
for the rate control algorithm, your rate control algorithm will work well.

> Add to that all the other variability, such as ANI dynamically adjusting
> radio chain parameters and it's very very difficult to know what is
> "incorrect but good enough".
The best measure of a rate control algorithm was hinted at above. I will
state it clearly here:
Take 2 nodes.
use your rate control algorithm on the 2 nodes.
a)measure the throughput between them.
Change to using manually adjust fixed rate.
b)Manually adjust the tx rate of either node until you achieve the best
throughput.
Compare the throughput from a) and b)

If ANI (or whatever else you can think of) is reducing throughput, the
above simple test should still give the same result. The throughput for a)
and b) should still be the same.

Derek.
--
Derek Smithies Ph.D.
IndraNet Technologies Ltd.
ph +64 3 365 6485
Web: http://www.indranet-technologies.com/

"The only thing IE should be used for is to download Fire Fox"

"My favorite language is call STAR. It's extremely concise. It has
exactly one verb '*', which does exactly what I want at the moment."
--Larry Wall

2010-03-04 14:14:13

by Bob Copeland

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On Wed, Mar 03, 2010 at 10:55:26AM +1300, Derek Smithies wrote:
> PID got it wrong - implicit in PID is the assumption that the rates can
> be ordered in terms of more successful / less successful - and the
> ordering follows the speed (faster speed=less successful).
>
> Since very slow rates are subject to interference loss (imagine there is
> a 60hz transmitter out there) packets that take a long time to transmit
> are far more likely to be shot down, stepping down a rate is going to
> increase the loss rate.

PID has more problems than just that -- it has lots of oscillation even
when the rate is relatively stable. See this chart which I
made using mac80211 hwsim and simulated loss (this was after I fixed
the problem in commit e850f68b8f):

http://bobcopeland.com/srcs/tcp_perf.pdf

My simulation involved no collisions and just reduced the SNR over
time. AARF in this case is an algorithm from academia, which is
susceptible to collision related-loss as you describe above.
In this example, it performed badly because of the latency inherent
between packet queuing and status reporting.

Minstrel definitely performs better in real life.

That said, I looked at the current minstrel code and have a few
puzzlements:

- As I understand it, minstrel is not supposed to delay packets more
than 24 ms to avoid TCP resends. However, if I understand the code,
this is done by limiting each MRR segment to 6 ms, which doesn't seem
right to me. The retries in the second MRR slot will have to wait
a backoff before being used, right?

- Often, two slots in the MRR array use the same rate (e.g. slots 1 and 3).
Maybe we should pick a 'next lower' rate for the lower slot in such a case?
If we are really in a place where the originally attempted rate isn't
workable, this might slightly boost throughput.

The large spikes at rate transition boundaries aren't quite so deep with
fewer retries.

--
Bob Copeland %% http://www.bobcopeland.com

2010-03-01 22:58:15

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On 2010-03-01 11:38 PM, Derek Smithies wrote:
> Hi,
> Great work on getting this far - it was a huge undertaking.
>
> Ok, before diving into the code, can we take a quick moment to think on
> this. I wonder if you can answer the following questions:
>
> a)Minstrel worked hard at using information that is good and reliable: -
> which is the record of what rates worked, and what rates failed.
> Minstrel avoids using things like RSSI (which is not reliable)
Yes, I still rely purely on tx status feedback, no RSSI voodoo.

> b)You have stated in previous emails that with 802.11n there are too many
> rates for minstrels random sampling technique.
>
> What is the approach taken in 802.11n & minstrel? I remember some comment
> about dividing the 802.11n rate set up into groups, and then minstrel does
> its thing within the rates of each group. - Do I have the idea here?
The previous comments were based on faulty tx status feedback because of
an ath9k issue that I resolved in a previous patch. The current
implementation still does random sampling, with one exception: each
sampling attempt goes to a different MCS group.
Other than that, I split up the MCS rates into groups mainly because
it's easier to deal with and allows me to calculate raw transmit
durations at compile time.

I did add some small special cases though. For instance if the code
detects that the current transmit rate is failing really quickly on a
multi-stream rate, it falls back to the max_tp_rate of a single-stream
group, while leaving around enough feedback for EWMA.
This reduces the strength of the throughput drop when I disconnect one
antenna (which kills off pretty much all of the dual-stream rates
immediately).

> Where have you tested 802.11n & minstrel?
Only at home. I just finished ironing out most of the important bugs
today, so this hasn't seen any significant long-term testing yet.

> Does 802.11n&minstrel pass the basic test
> a) put two nodes on the desk - rate is high
> b) move one of the nodes (or remove antenna) - rate should drop
> c) move nodes back to the configuration of a)
> -rate should go high again
Yes, this was my primary test. I also did some tests with removing both
antennas and moving the laptop away and back again.

I also did quite a few tests switching back and forth between
minstrel_ht and the ath9k rate control to compare them as accurately as
possible. In HT40, rate adaptation with minstrel is usually a little
slower (only a minor difference here, probably caused by the much larger
search space), but it's able to deal with sources of interference (e.g.
Bluetooth) a lot better.
It also reacts much faster to problems with spatial multiplexing, and
seems to get a better average throughput in HT20 in my tests.

> Does 802.11n&minstrel work well with time?
> In other words, is the throughput 10 hours later the same as at the start
> of the test?
If I force it to single-stream mode, then it seems to be just as
reliable at sticking to a specific rate as the legacy implementation.

With dual-stream rates it's hard to tell, because the reliability of
rates varies quickly, even if the positions is fixed. I do not see any
*significant* variations in throughput though.

- Felix

2010-03-02 15:47:51

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

2010/3/2 Felix Fietkau <[email protected]>:
> [snip] also the hardware
> doesn't even provide enough information to do any kind of precise
> calculation on airtime utilization by tx attempts. For instance, I don't
> get any information on how many frames in an A-MPDU were successfully
> transmitted on each retransmission attempt.

You mean the hardware interprets the block-ack and keeps retrying the
un-acked frames? I thought it stopped as soon as it got a block-ack to
let software sort out the acked and un-acked frames and handle the
"partial" A-MPDU retry.

> Software retries are being taken into account on some level, because a
> software retry is simply going to be part of the next A-MPDU, which will
> get accounted for in the rate control code.

If my guess on block-ack implementation is correctly there is still
have a major uncertainty: if the first frame in the A-MPDU is
transferred correctly but every other frame in the AMPDU fails (and
has to be retransmitted in other A-MPDUs) you run the risk of counting
that as a success (and of course wise-versa)...

> This early version will probably not make a fully optimal tradeoff
> between retransmission probability and raw throughput, but that can
> probably be tweaked over time, simply by adjusting the internal
> throughput metric calculation to something that gets close in practice
> at least most of the time.

I agree this new code is a big step forward and the aim here (with
this patch) should of course not be a fully optimal solution. But
shouldn't we try to at least set up a roadmap to remove as much as
possible of these fundamental flaws / uncertainties?

The reason I'm so interested in this subject is I've tried to tweak
the ath9k rate control to behave reasonably for me. This has taken a
lot of time and the result is rather poor. Also, these tweaks are not
general enough to even be contributed back as patches. My feeling is
that the reason it is so difficult to get a rate control algorithm to
work for all use-cases is that the underlying model is just plain
wrong. Radio environments are very varied and complex. Add to that all
the other variability, such as ANI dynamically adjusting radio chain
parameters and it's very very difficult to know what is "incorrect but
good enough".

/Bj?rn

2010-03-04 20:09:35

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

Hi,
On Thu, 4 Mar 2010, Bj?rn Smedman wrote:
> On Thu, Mar 4, 2010 at 3:12 PM, Bob Copeland <[email protected]> wrote:
>>
>> Minstrel definitely performs better in real life.
> Agree, minstrel works very well in real life.
yeah - we tested it hard and long outdoors. and indoors. and with driver
faults, and it still worked as well as could be expected.
>
>> That said, I looked at the current minstrel code and have a few
>> puzzlements:
>>
>> - As I understand it, minstrel is not supposed to delay packets more
>> ?than 24 ms to avoid TCP resends. ?However, if I understand the code,
>> ?this is done by limiting each MRR segment to 6 ms, which doesn't seem
>> ?right to me. ?The retries in the second MRR slot will have to wait
>> ?a backoff before being used, right?
>
> I took a look at the minstrel code back in madwifi and the comments
> there suggest this 24 ms thing is not very theoretically based. It
> sounds like a very reasonable explanation though so I'm not saying it
> is wrong. But I think there might be another very good reason to limit
> the number of attempts at a given rate: after a certain number of
> retries we have to conclude that our hypothesis about the packet
> error/success rate is probably incorrect, and there is no point in
> more retries at that rate.
Agreed. 24 ms was a value that was guessed at, and works well. However, If
there is no limit on the time taken for the entire chain, then performance
drops.
we observed the packets on the air for a tcp transfer (scp). There was
sometimes a 100ms gap after the successful transmission of one packet
before the next one was sent. Turns out that TCP's backoff/congestion
control mechanism was "upset" because of the long transmit time, and had
delayed the sending of the next. By limiting the time taken for an entire
retry chain to be used, we increased TCP throughput.

>
>> - Often, two slots in the MRR array use the same rate (e.g. slots 1 and 3).
>> ?Maybe we should pick a 'next lower' rate for the lower slot in such a case?
>> ?If we are really in a place where the originally attempted rate isn't
>> ?workable, this might slightly boost throughput.
>
> Agree. With the same reasoning as above this can be generalized to: if
> an MRR slot has failed and we have fallen through to the next one then
> that slot should be set up to be optimal under a new hypothesis
> (taking the failed MRR segment into account).
yes, This is an enhancement we have discussed.
It would more quickly fill the statistics tables that Minstrel uses, which
is a good thing.
Currently, the retry chain is something like
1.rate with the the highest throughput
2.rate with the the second highest throughput
3.rate with the highest probability
4.base rate of 1mbit.

You could change it to:
1.rate with the the highest throughput
2.rate with the the second highest throughput
3.rate with the highest probability,
such that this rate does not equal 1. or 2.
4.base rate of 1mbit.

Do not use the 'next lower' rate. This is effectively a variant on the
step up/step down philosophy, which does not apply to rate algorithms.

The philosophy that the success probability of a rate is proportional to
the bit rate is wrong. 100.00% wrong. Since things like PID have this
philosophy at their core, PID will always fail.

Derek.

--
Derek Smithies Ph.D.
IndraNet Technologies Ltd.
ph +64 3 365 6485
Web: http://www.indranet-technologies.com/

"The only thing IE should be used for is to download Fire Fox"

"My favorite language is call STAR. It's extremely concise. It has
exactly one verb '*', which does exactly what I want at the moment."
--Larry Wall

2010-03-02 14:51:13

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On 2010-03-02 1:19 PM, Bj?rn Smedman wrote:
> Hi Felix,
>
> First of all thanx for this new rate control algorithm!
>
> One question about AMPDUs (which is not really specific to your code
> but anyway): How do you handle "software retries"?
>
> At least ath9k seems to retry frames in serveral AMPDUs up to
> ATH_MAX_SW_RETRIES times within the driver (without notifying
> mac80211). First of all, is this your understanding as well?
Since the tx status information on A-MPDUs is imprecise either way, I
simply treat a full A-MPDU as a single frame at the moment. I did some
experiments with taking the exact number of frames into account, but it
didn't improve overall performance, so I removed the code for that again.

> If my understanding is correct then there are two problems as I see it:
>
> 1) The rate control algorithm will get incorrect information about the
> transmission attempts. This could be corrected to some extent by
> correctly setting the count and idx tx_status fields taking software
> retries into account, but that interface is actually too thin to carry
> all the information since the frame may have been retried at many
> bitrates (more than 4). Also, the duration the radio has been busy
> transmitting the frame is impossible to derive because you do not know
> how many separate AMPDUs it has been transmitted in which makes a
> difference in contention window and inter frame space, etc.
Correct. I use a rough approximation, because not only is the interface
too thin to carry all the relevant information, also the hardware
doesn't even provide enough information to do any kind of precise
calculation on airtime utilization by tx attempts. For instance, I don't
get any information on how many frames in an A-MPDU were successfully
transmitted on each retransmission attempt.
Additionally, I intend to use this rate control algorithm on non-Atheros
hardware - and tx status feedback will be even more limited there.

> 2) The rate selection is suboptimal if software retries are not taken
> into account. The reason you want to use a high probability bitrate on
> the last few transmission attempts is that you want to avoid packet
> loss at (almost) any price. But if you can retry the frame in software
> it may be better to transmit only at spectrum efficient bitrates and
> use the receivers reorder buffer to avoid packet loss. This is IMHO
> one of the main advantages of the 802.11n MAC and something we should
> really try to take advantage of.
Software retries are being taken into account on some level, because a
software retry is simply going to be part of the next A-MPDU, which will
get accounted for in the rate control code.

This early version will probably not make a fully optimal tradeoff
between retransmission probability and raw throughput, but that can
probably be tweaked over time, simply by adjusting the internal
throughput metric calculation to something that gets close in practice
at least most of the time.

- Felix

2010-03-04 16:46:59

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On Thu, Mar 4, 2010 at 3:12 PM, Bob Copeland <[email protected]> wrote:
>
> Minstrel definitely performs better in real life.

Agree, minstrel works very well in real life.

> That said, I looked at the current minstrel code and have a few
> puzzlements:
>
> - As I understand it, minstrel is not supposed to delay packets more
> ?than 24 ms to avoid TCP resends. ?However, if I understand the code,
> ?this is done by limiting each MRR segment to 6 ms, which doesn't seem
> ?right to me. ?The retries in the second MRR slot will have to wait
> ?a backoff before being used, right?

I took a look at the minstrel code back in madwifi and the comments
there suggest this 24 ms thing is not very theoretically based. It
sounds like a very reasonable explanation though so I'm not saying it
is wrong. But I think there might be another very good reason to limit
the number of attempts at a given rate: after a certain number of
retries we have to conclude that our hypothesis about the packet
error/success rate is probably incorrect, and there is no point in
more retries at that rate.

An example: Lets say my hypothesis is that the packet error rate at 24
Mbit/s is 10%. The probability that 3 attempts in a row will fail is
then 0.1^3 = 0.1% (given that my hypothesis is correct). A
statistician would say that we have tested my hypothesis and that it
can be rejected on the 99.9%-level. Continuing with a fourth attempt
is approaching what Einstein defined as insanity: doing the same thing
over and over again and expecting different results. :)

> - Often, two slots in the MRR array use the same rate (e.g. slots 1 and 3).
> ?Maybe we should pick a 'next lower' rate for the lower slot in such a case?
> ?If we are really in a place where the originally attempted rate isn't
> ?workable, this might slightly boost throughput.

Agree. With the same reasoning as above this can be generalized to: if
an MRR slot has failed and we have fallen through to the next one then
that slot should be set up to be optimal under a new hypothesis
(taking the failed MRR segment into account).

In any case Felix patch is a giant leap towards better rate control.
Looking forward to tweaking it and this time hopefully submitting
something.

/Bj?rn

2010-03-02 12:19:35

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

Hi Felix,

First of all thanx for this new rate control algorithm!

One question about AMPDUs (which is not really specific to your code
but anyway): How do you handle "software retries"?

At least ath9k seems to retry frames in serveral AMPDUs up to
ATH_MAX_SW_RETRIES times within the driver (without notifying
mac80211). First of all, is this your understanding as well?

If my understanding is correct then there are two problems as I see it:

1) The rate control algorithm will get incorrect information about the
transmission attempts. This could be corrected to some extent by
correctly setting the count and idx tx_status fields taking software
retries into account, but that interface is actually too thin to carry
all the information since the frame may have been retried at many
bitrates (more than 4). Also, the duration the radio has been busy
transmitting the frame is impossible to derive because you do not know
how many separate AMPDUs it has been transmitted in which makes a
difference in contention window and inter frame space, etc.

2) The rate selection is suboptimal if software retries are not taken
into account. The reason you want to use a high probability bitrate on
the last few transmission attempts is that you want to avoid packet
loss at (almost) any price. But if you can retry the frame in software
it may be better to transmit only at spectrum efficient bitrates and
use the receivers reorder buffer to avoid packet loss. This is IMHO
one of the main advantages of the 802.11n MAC and something we should
really try to take advantage of.

Best regards,

Bj?rn

On Mon, Mar 1, 2010 at 11:05 PM, Felix Fietkau <[email protected]> wrote:
>
> Hi all,
>
> this my initial implementation of minstrel for 802.11n. It works well
> for me with ath9k, haven't tested any other drivers yet. It handles
> guard interval setting, HT20/HT40 and multiple streams properly,
> STBC isn't implemented yet (I'll implement driver support in ath9k
> first). Legacy stations are handled by falling back to the old minstrel
> implementation.
>
> It requires the following other patches that I submitted:
> - ath9k: fix rate control tx status handling for A-MPDU
> - minstrel: simplify and fix debugfs code
> - minstrel: make the rate control ops reusable from another rc implementation
>
> There are still some things that need cleaning, for instance the
> internal flags that I use on tx_info->flags, or the sharing of
> the private struct with the old minstrel code.
[snip]

2010-03-01 22:36:51

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

Hi,
Great work on getting this far - it was a huge undertaking.

Ok, before diving into the code, can we take a quick moment to think on
this. I wonder if you can answer the following questions:

a)Minstrel worked hard at using information that is good and reliable: -
which is the record of what rates worked, and what rates failed.
Minstrel avoids using things like RSSI (which is not reliable)

b)You have stated in previous emails that with 802.11n there are too many
rates for minstrels random sampling technique.

What is the approach taken in 802.11n & minstrel? I remember some comment
about dividing the 802.11n rate set up into groups, and then minstrel does
its thing within the rates of each group. - Do I have the idea here?

Where have you tested 802.11n & minstrel?

Does 802.11n&minstrel pass the basic test
a) put two nodes on the desk - rate is high
b) move one of the nodes (or remove antenna) - rate should drop
c) move nodes back to the configuration of a)
-rate should go high again

Does 802.11n&minstrel work well with time?
In other words, is the throughput 10 hours later the same as at the start
of the test?

My view is that if 802.11n&minstrel has passed the above two tests (basic
and longevity) then it is a huge achievement.

Thanks,
Derek.

On Mon, 1 Mar 2010, Felix Fietkau wrote:

> Hi all,
>
> this my initial implementation of minstrel for 802.11n. It works well
> for me with ath9k, haven't tested any other drivers yet. It handles
> guard interval setting, HT20/HT40 and multiple streams properly,
> STBC isn't implemented yet (I'll implement driver support in ath9k
> first). Legacy stations are handled by falling back to the old minstrel
> implementation.
>
> It requires the following other patches that I submitted:
> - ath9k: fix rate control tx status handling for A-MPDU
> - minstrel: simplify and fix debugfs code
> - minstrel: make the rate control ops reusable from another rc implementation
>
> There are still some things that need cleaning, for instance the
> internal flags that I use on tx_info->flags, or the sharing of
> the private struct with the old minstrel code.
>
> --- a/net/mac80211/Makefile
> +++ b/net/mac80211/Makefile
> @@ -47,8 +47,8 @@ CFLAGS_driver-trace.o := -I$(src)
> rc80211_pid-y := rc80211_pid_algo.o
> rc80211_pid-$(CONFIG_MAC80211_DEBUGFS) += rc80211_pid_debugfs.o
>
> -rc80211_minstrel-y := rc80211_minstrel.o
> -rc80211_minstrel-$(CONFIG_MAC80211_DEBUGFS) += rc80211_minstrel_debugfs.o
> +rc80211_minstrel-y := rc80211_minstrel.o rc80211_minstrel_ht.o
> +rc80211_minstrel-$(CONFIG_MAC80211_DEBUGFS) += rc80211_minstrel_debugfs.o rc80211_minstrel_ht_debugfs.o
>
> mac80211-$(CONFIG_MAC80211_RC_PID) += $(rc80211_pid-y)
> mac80211-$(CONFIG_MAC80211_RC_MINSTREL) += $(rc80211_minstrel-y)
> --- a/net/mac80211/main.c
> +++ b/net/mac80211/main.c
> @@ -710,6 +710,10 @@ static int __init ieee80211_init(void)
> if (ret)
> return ret;
>
> + ret = rc80211_minstrel_ht_init();
> + if (ret)
> + goto err_minstrel;
> +
> ret = rc80211_pid_init();
> if (ret)
> goto err_pid;
> @@ -722,6 +726,8 @@ static int __init ieee80211_init(void)
> err_netdev:
> rc80211_pid_exit();
> err_pid:
> + rc80211_minstrel_ht_exit();
> + err_minstrel:
> rc80211_minstrel_exit();
>
> return ret;
> @@ -730,6 +736,7 @@ static int __init ieee80211_init(void)
> static void __exit ieee80211_exit(void)
> {
> rc80211_pid_exit();
> + rc80211_minstrel_ht_exit();
> rc80211_minstrel_exit();
>
> /*
> --- a/net/mac80211/rate.h
> +++ b/net/mac80211/rate.h
> @@ -136,6 +136,8 @@ static inline void rc80211_pid_exit(void
> #ifdef CONFIG_MAC80211_RC_MINSTREL
> extern int rc80211_minstrel_init(void);
> extern void rc80211_minstrel_exit(void);
> +extern int rc80211_minstrel_ht_init(void);
> +extern void rc80211_minstrel_ht_exit(void);
> #else
> static inline int rc80211_minstrel_init(void)
> {
> @@ -144,6 +146,13 @@ static inline int rc80211_minstrel_init(
> static inline void rc80211_minstrel_exit(void)
> {
> }
> +static inline int rc80211_minstrel_ht_init(void)
> +{
> + return 0;
> +}
> +static inline void rc80211_minstrel_ht_exit(void)
> +{
> +}
> #endif
>
>
> --- /dev/null
> +++ b/net/mac80211/rc80211_minstrel_ht.c
> @@ -0,0 +1,803 @@
> +/*
> + * Copyright (C) 2010 Felix Fietkau <[email protected]>
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License version 2 as
> + * published by the Free Software Foundation.
> + */
> +#include <linux/netdevice.h>
> +#include <linux/types.h>
> +#include <linux/skbuff.h>
> +#include <linux/debugfs.h>
> +#include <linux/random.h>
> +#include <linux/ieee80211.h>
> +#include <net/mac80211.h>
> +#include "rate.h"
> +#include "rc80211_minstrel.h"
> +#include "rc80211_minstrel_ht.h"
> +
> +#define AVG_PKT_SIZE 1200
> +#define SAMPLE_COLUMNS 10
> +#define EWMA_LEVEL 75
> +
> +/* Number of bits for an average sized packet */
> +#define MCS_NBITS (AVG_PKT_SIZE << 3)
> +
> +/* Number of symbols for a packet with (bps) bits per symbol */
> +#define MCS_NSYMS(bps) ((MCS_NBITS + (bps) - 1) / (bps))
> +
> +/* Transmission time for a packet containing (syms) symbols */
> +#define MCS_SYMBOL_TIME(sgi, syms) \
> + (sgi ? \
> + ((syms) * 18 + 4) / 5 : /* syms * 3.6 us */ \
> + (syms) << 2 /* syms * 4 us */ \
> + )
> +
> +/* Transmit duration for the raw data part of an average sized packet */
> +#define MCS_DURATION(streams, sgi, bps) MCS_SYMBOL_TIME(sgi, MCS_NSYMS((streams) * (bps)))
> +
> +/* MCS rate information for an MCS group */
> +#define MCS_GROUP(_streams, _sgi, _ht40) { \
> + .streams = _streams, \
> + .flags = \
> + (_sgi ? IEEE80211_TX_RC_SHORT_GI : 0) | \
> + (_ht40 ? IEEE80211_TX_RC_40_MHZ_WIDTH : 0), \
> + .duration = { \
> + MCS_DURATION(_streams, _sgi, _ht40 ? 54 : 26), \
> + MCS_DURATION(_streams, _sgi, _ht40 ? 108 : 52), \
> + MCS_DURATION(_streams, _sgi, _ht40 ? 162 : 78), \
> + MCS_DURATION(_streams, _sgi, _ht40 ? 216 : 104), \
> + MCS_DURATION(_streams, _sgi, _ht40 ? 324 : 156), \
> + MCS_DURATION(_streams, _sgi, _ht40 ? 432 : 208), \
> + MCS_DURATION(_streams, _sgi, _ht40 ? 486 : 234), \
> + MCS_DURATION(_streams, _sgi, _ht40 ? 540 : 260) \
> + } \
> +}
> +
> +#define MINSTREL_INTFL_SAMPLE_SLOT0 BIT(30)
> +#define MINSTREL_INTFL_SAMPLE_SLOT1 BIT(31)
> +
> +/*
> + * To enable sufficiently targeted rate sampling, MCS rates are divided into
> + * groups, based on the number of streams and flags (HT40, SGI) that they
> + * use.
> + */
> +const struct mcs_group minstrel_mcs_groups[] = {
> + MCS_GROUP(1, 0, 0),
> + MCS_GROUP(2, 0, 0),
> +#if MINSTREL_MAX_STREAMS >= 3
> + MCS_GROUP(3, 0, 0),
> +#endif
> +
> + MCS_GROUP(1, 1, 0),
> + MCS_GROUP(2, 1, 0),
> +#if MINSTREL_MAX_STREAMS >= 3
> + MCS_GROUP(3, 1, 0),
> +#endif
> +
> + MCS_GROUP(1, 0, 1),
> + MCS_GROUP(2, 0, 1),
> +#if MINSTREL_MAX_STREAMS >= 3
> + MCS_GROUP(3, 0, 1),
> +#endif
> +
> + MCS_GROUP(1, 1, 1),
> + MCS_GROUP(2, 1, 1),
> +#if MINSTREL_MAX_STREAMS >= 3
> + MCS_GROUP(3, 1, 1),
> +#endif
> +};
> +
> +static u8 sample_table[SAMPLE_COLUMNS][MCS_GROUP_RATES];
> +
> +/*
> + * Perform EWMA (Exponentially Weighted Moving Average) calculation
> + */
> +static int
> +minstrel_ewma(int old, int new, int weight)
> +{
> + return (new * (100 - weight) + old * weight) / 100;
> +}
> +
> +/*
> + * Look up an MCS group index based on mac80211 rate information
> + */
> +static int
> +minstrel_ht_get_group_idx(struct ieee80211_tx_rate *rate)
> +{
> + int streams = (rate->idx / MCS_GROUP_RATES) + 1;
> + u32 flags = IEEE80211_TX_RC_SHORT_GI | IEEE80211_TX_RC_40_MHZ_WIDTH;
> + int i;
> +
> + for (i = 0; i < ARRAY_SIZE(minstrel_mcs_groups); i++) {
> + if (minstrel_mcs_groups[i].streams != streams)
> + continue;
> + if (minstrel_mcs_groups[i].flags != (rate->flags & flags))
> + continue;
> +
> + return i;
> + }
> +
> + WARN_ON(1);
> + return 0;
> +}
> +
> +static inline struct minstrel_rate_stats *
> +minstrel_get_ratestats(struct minstrel_ht_sta *mi, int index)
> +{
> + return &mi->groups[index / MCS_GROUP_RATES].rates[index % MCS_GROUP_RATES];
> +}
> +
> +
> +/*
> + * Recalculate success probabilities and counters for a rate using EWMA
> + */
> +static void
> +minstrel_calc_rate_ewma(struct minstrel_priv *mp, struct minstrel_rate_stats *mr)
> +{
> + if (mr->attempts) {
> + mr->cur_prob = MINSTREL_FRAC(mr->success, mr->attempts);
> + if (!mr->att_hist)
> + mr->probability = mr->cur_prob;
> + else
> + mr->probability = minstrel_ewma(mr->probability,
> + mr->cur_prob, EWMA_LEVEL);
> + mr->att_hist += mr->attempts;
> + mr->succ_hist += mr->success;
> + }
> + mr->last_success = mr->success;
> + mr->last_attempts = mr->attempts;
> + mr->success = 0;
> + mr->attempts = 0;
> +}
> +
> +/*
> + * Calculate throughput based on the average A-MPDU length, taking into account
> + * the expected number of retransmissions and their expected length
> + */
> +static void
> +minstrel_ht_calc_tp(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,
> + int group, int rate)
> +{
> + struct minstrel_rate_stats *mr;
> + unsigned int usecs;
> +
> + mr = &mi->groups[group].rates[rate];
> +
> + if (mr->probability < MINSTREL_FRAC(1, 10)) {
> + mr->cur_tp = 0;
> + return;
> + }
> +
> + usecs = mi->overhead / MINSTREL_TRUNC(mi->avg_ampdu_len);
> + usecs += minstrel_mcs_groups[group].duration[rate];
> + mr->cur_tp = MINSTREL_TRUNC((1000000 / usecs) * mr->probability);
> +}
> +
> +/*
> + * Update rate statistics and select new primary rates
> + *
> + * Rules for rate selection:
> + * - max_prob_rate must use only one stream, as a tradeoff between delivery
> + * probability and throughput during strong fluctuations
> + * - as long as the max prob rate has a probability of more than 3/4, pick
> + * higher throughput rates, even if the probablity is a bit lower
> + */
> +static void
> +minstrel_ht_update_stats(struct minstrel_priv *mp, struct minstrel_ht_sta *mi)
> +{
> + struct minstrel_mcs_group_data *mg;
> + struct minstrel_rate_stats *mr;
> + int cur_prob, cur_prob_tp, cur_tp, cur_tp2;
> + int group, i, index;
> +
> + mi->max_tp_rate = 0;
> + mi->max_tp_rate2 = 0;
> + mi->max_prob_rate = 0;
> +
> + for (group = 0; group < ARRAY_SIZE(minstrel_mcs_groups); group++) {
> + cur_prob = 0;
> + cur_prob_tp = 0;
> + cur_tp = 0;
> + cur_tp2 = 0;
> +
> + mg = &mi->groups[group];
> + if (!mg->supported)
> + continue;
> +
> + mg->max_tp_rate = 0;
> + mg->max_tp_rate2 = 0;
> + mg->max_prob_rate = 0;
> +
> + for (i = 0; i < MCS_GROUP_RATES; i++) {
> + if (!(mg->supported & BIT(i)))
> + continue;
> +
> + mr = &mg->rates[i];
> + mr->retry_updated = false;
> + index = MCS_GROUP_RATES * group + i;
> + minstrel_calc_rate_ewma(mp, mr);
> + minstrel_ht_calc_tp(mp, mi, group, i);
> +
> + if (!mr->cur_tp)
> + continue;
> +
> + /* ignore the lowest rate of each single-stream group */
> + if (!i && minstrel_mcs_groups[group].streams == 1)
> + continue;
> +
> + if ((mr->cur_tp > cur_prob_tp && mr->probability >
> + MINSTREL_FRAC(3, 4)) || mr->probability > cur_prob) {
> + mg->max_prob_rate = index;
> + cur_prob = mr->probability;
> + }
> +
> + if (mr->cur_tp > cur_tp) {
> + swap(index, mg->max_tp_rate);
> + cur_tp = mr->cur_tp;
> + mr = minstrel_get_ratestats(mi, index);
> + }
> +
> + if (index == mg->max_tp_rate)
> + continue;
> +
> + if (mr->cur_tp > cur_tp2) {
> + mg->max_tp_rate2 = index;
> + cur_tp2 = mr->cur_tp;
> + }
> + }
> + }
> +
> + cur_prob = 0;
> + cur_prob_tp = 0;
> + cur_tp = 0;
> + cur_tp2 = 0;
> + for (group = 0; group < ARRAY_SIZE(minstrel_mcs_groups); group++) {
> + mg = &mi->groups[group];
> + if (!mg->supported)
> + continue;
> +
> + mr = minstrel_get_ratestats(mi, mg->max_prob_rate);
> + if (cur_prob_tp < mr->cur_tp &&
> + minstrel_mcs_groups[group].streams == 1) {
> + mi->max_prob_rate = mg->max_prob_rate;
> + cur_prob = mr->cur_prob;
> + }
> +
> + mr = minstrel_get_ratestats(mi, mg->max_tp_rate);
> + if (cur_tp < mr->cur_tp) {
> + mi->max_tp_rate = mg->max_tp_rate;
> + cur_tp = mr->cur_tp;
> + }
> +
> + mr = minstrel_get_ratestats(mi, mg->max_tp_rate2);
> + if (cur_tp2 < mr->cur_tp) {
> + mi->max_tp_rate2 = mg->max_tp_rate2;
> + cur_tp2 = mr->cur_tp;
> + }
> + }
> +
> + mi->stats_update = jiffies;
> +}
> +
> +static bool
> +minstrel_ht_txstat_valid(struct ieee80211_tx_rate *rate)
> +{
> + if (!rate->count)
> + return false;
> +
> + if (rate->idx < 0)
> + return false;
> +
> + return !!(rate->flags & IEEE80211_TX_RC_MCS);
> +}
> +
> +static void
> +minstrel_next_sample_idx(struct minstrel_ht_sta *mi)
> +{
> + struct minstrel_mcs_group_data *mg;
> +
> + for (;;) {
> + mi->sample_group++;
> + mi->sample_group %= ARRAY_SIZE(minstrel_mcs_groups);
> + mg = &mi->groups[mi->sample_group];
> +
> + if (!mg->supported)
> + continue;
> +
> + if (++mg->index > MCS_GROUP_RATES) {
> + mg->index = 0;
> + if (++mg->column > ARRAY_SIZE(sample_table))
> + mg->column = 0;
> + }
> + break;
> + }
> +}
> +
> +static void
> +minstrel_downgrade_rate(struct minstrel_ht_sta *mi, int *idx, int type)
> +{
> + int group, orig_group;
> +
> + orig_group = group = *idx / MCS_GROUP_RATES;
> + while (group > 0) {
> + group--;
> +
> + if (!mi->groups[group].supported)
> + continue;
> +
> + if (minstrel_mcs_groups[group].streams >=
> + minstrel_mcs_groups[orig_group].streams)
> + continue;
> +
> + switch(type) {
> + case 0:
> + *idx = mi->groups[group].max_tp_rate;
> + break;
> + case 1:
> + *idx = mi->groups[group].max_tp_rate2;
> + break;
> + }
> + break;
> + }
> +}
> +
> +
> +static void
> +minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband,
> + struct ieee80211_sta *sta, void *priv_sta,
> + struct sk_buff *skb)
> +{
> + struct minstrel_ht_sta_priv *msp = priv_sta;
> + struct minstrel_ht_sta *mi = &msp->ht;
> + struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
> + struct ieee80211_tx_rate *ar = info->status.rates;
> + struct minstrel_rate_stats *rate, *rate2;
> + struct minstrel_priv *mp = priv;
> + bool last = false;
> + int group;
> + int i = 0;
> +
> + if (!msp->is_ht)
> + return mac80211_minstrel.tx_status(priv, sband, sta, &msp->legacy, skb);
> +
> + /* This packet was aggregated but doesn't carry status info */
> + if ((info->flags & IEEE80211_TX_CTL_AMPDU) &&
> + !(info->flags & IEEE80211_TX_STAT_AMPDU))
> + return;
> +
> + if (!info->status.ampdu_len) {
> + info->status.ampdu_ack_len = 1;
> + info->status.ampdu_len = 1;
> + }
> +
> + mi->avg_ampdu_len = minstrel_ewma(mi->avg_ampdu_len,
> + MINSTREL_FRAC(info->status.ampdu_len, 1), 90);
> +
> + for (i = 0; !last; i++) {
> + last = (i == IEEE80211_TX_MAX_RATES - 1) ||
> + !minstrel_ht_txstat_valid(&ar[i + 1]);
> +
> + if (!minstrel_ht_txstat_valid(&ar[i]))
> + break;
> +
> + if ((i == 0 && (info->flags & MINSTREL_INTFL_SAMPLE_SLOT0)) ||
> + (i == 1 && (info->flags & MINSTREL_INTFL_SAMPLE_SLOT1))) {
> + if (mi->sample_pending > 0)
> + mi->sample_pending--;
> + mi->sample_packets++;
> + minstrel_next_sample_idx(mi);
> + }
> +
> + group = minstrel_ht_get_group_idx(&ar[i]);
> + rate = &mi->groups[group].rates[ar[i].idx % 8];
> +
> + if (last && (info->flags & IEEE80211_TX_STAT_ACK) &&
> + info->status.ampdu_len == info->status.ampdu_ack_len)
> + rate->success++;
> +
> + rate->attempts += ar[i].count;
> + }
> +
> +
> + /*
> + * check for sudden death of spatial multiplexing,
> + * downgrade to a lower number of streams if necessary.
> + */
> + rate = minstrel_get_ratestats(mi, mi->max_tp_rate);
> + if (MINSTREL_FRAC(rate->success, rate->attempts) <
> + MINSTREL_FRAC(20, 100) && rate->attempts > 15)
> + minstrel_downgrade_rate(mi, &mi->max_tp_rate, 0);
> +
> + rate2 = minstrel_get_ratestats(mi, mi->max_tp_rate2);
> + if (MINSTREL_FRAC(rate->success, rate->attempts) <
> + MINSTREL_FRAC(20, 100) && rate->attempts > 15)
> + minstrel_downgrade_rate(mi, &mi->max_tp_rate2, 1);
> +
> + if (time_after(jiffies, mi->stats_update + (mp->update_interval / 2 * HZ) / 1000))
> + minstrel_ht_update_stats(mp, mi);
> +}
> +
> +static void
> +minstrel_calc_retransmit(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,
> + int index)
> +{
> + struct minstrel_rate_stats *mr;
> + const struct mcs_group *group;
> + unsigned int tx_time, tx_time_rtscts, tx_time_data;
> + unsigned int cw = mp->cw_min;
> + unsigned int t_slot = 9; /* FIXME */
> + unsigned int ampdu_len = MINSTREL_TRUNC(mi->avg_ampdu_len);
> +
> + mr = minstrel_get_ratestats(mi, index);
> + if (mr->probability < MINSTREL_FRAC(1, 10)) {
> + mr->retry_count = 1;
> + mr->retry_count_rtscts = 1;
> + return;
> + }
> +
> + mr->retry_count = 2;
> + mr->retry_count_rtscts = 2;
> + mr->retry_updated = true;
> +
> + group = &minstrel_mcs_groups[index / MCS_GROUP_RATES];
> + tx_time_data = group->duration[index % MCS_GROUP_RATES] * ampdu_len;
> + tx_time = 2 * (t_slot + mi->overhead + tx_time_data);
> + tx_time_rtscts = 2 * (t_slot + mi->overhead_rtscts + tx_time_data);
> + do {
> + cw = (cw << 1) | 1;
> + cw = min(cw, mp->cw_max);
> + tx_time += cw + t_slot + mi->overhead;
> + tx_time_rtscts += cw + t_slot + mi->overhead_rtscts;
> + if (tx_time_rtscts < mp->segment_size)
> + mr->retry_count_rtscts++;
> + } while ((tx_time < mp->segment_size) &&
> + (++mr->retry_count < mp->max_retry));
> +}
> +
> +
> +static void
> +minstrel_ht_set_rate(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,
> + struct ieee80211_tx_rate *rate, int index,
> + struct ieee80211_tx_rate_control *txrc,
> + bool sample, bool rtscts)
> +{
> + const struct mcs_group *group = &minstrel_mcs_groups[index / MCS_GROUP_RATES];
> + struct minstrel_rate_stats *mr;
> +
> + mr = minstrel_get_ratestats(mi, index);
> + if (!mr->retry_updated)
> + minstrel_calc_retransmit(mp, mi, index);
> +
> + if (rtscts)
> + rate->count = mr->retry_count_rtscts;
> + else
> + rate->count = mr->retry_count;
> +
> + rate->flags = IEEE80211_TX_RC_MCS | group->flags;
> + if (txrc->short_preamble)
> + rate->flags |= IEEE80211_TX_RC_USE_SHORT_PREAMBLE;
> + if (txrc->rts || rtscts)
> + rate->flags |= IEEE80211_TX_RC_USE_RTS_CTS;
> + rate->idx = index % MCS_GROUP_RATES + (group->streams - 1) * MCS_GROUP_RATES;
> +}
> +
> +static inline int
> +minstrel_get_duration(int index)
> +{
> + const struct mcs_group *group = &minstrel_mcs_groups[index / MCS_GROUP_RATES];
> + return group->duration[index % MCS_GROUP_RATES];
> +}
> +
> +static int
> +minstrel_get_sample_rate(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,
> + bool *defer)
> +{
> + struct minstrel_rate_stats *mr;
> + struct minstrel_mcs_group_data *mg;
> + int sample_idx = 0;
> + int sample_rate;
> + int delta;
> +
> + if (mp->has_mrr)
> + sample_rate = mp->lookaround_rate_mrr;
> + else
> + sample_rate = mp->lookaround_rate;
> +
> + delta = (mi->total_packets * sample_rate) / 100 - mi->sample_packets;
> + delta -= mi->sample_pending / 2;
> +
> + if (delta <= 0)
> + return -1;
> +
> + delta -= 16;
> + if (delta > 1) {
> + /* With multi-rate retry, not every planned sample
> + * attempt actually gets used, due to the way the retry
> + * chain is set up - [max_tp,sample,prob,lowest] for
> + * sample_rate < max_tp.
> + *
> + * If there's too much sampling backlog and the link
> + * starts getting worse, minstrel would start bursting
> + * out lots of sampling frames, which would result
> + * in a large throughput loss.
> + */
> + mi->sample_packets += delta - 1;
> + }
> +
> + mg = &mi->groups[mi->sample_group];
> + sample_idx = sample_table[mg->column][mg->index];
> + mr = &mg->rates[sample_idx];
> + sample_idx += mi->sample_group * MCS_GROUP_RATES;
> +
> + /*
> + * When not using MRR, do not sample if the probability is already
> + * higher than 95% to avoid wasting airtime
> + */
> + if (!mp->has_mrr && (mr->probability > MINSTREL_FRAC(95, 100)))
> + return -1;
> +
> + if (minstrel_get_duration(sample_idx) >
> + minstrel_get_duration(mi->max_tp_rate)) {
> + /*
> + * Make sure that lower rates get sampled occasionally, even
> + * if the link is working perfectly. Some drivers such as ath9k
> + * severely limit aggregation size if the MRR chain contains low
> + * rates
> + *
> + * If the lower rate has already been tried a few times, there's
> + * no point in forcing it to be sampled again, so skip to the
> + * next sampling index after applying this one in the tx control
> + */
> + if (mr->att_hist > 15) {
> + *defer = true;
> + minstrel_next_sample_idx(mi);
> + }
> + }
> +
> + return sample_idx;
> +}
> +
> +static void
> +minstrel_aggr_check(struct minstrel_priv *mp, struct ieee80211_sta *pubsta, struct sk_buff *skb)
> +{
> + struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
> + struct sta_info *sta = container_of(pubsta, struct sta_info, sta);
> + u16 tid;
> +
> + if (unlikely(!ieee80211_is_data_qos(hdr->frame_control)))
> + return;
> +
> + if (unlikely(skb->protocol == cpu_to_be16(ETH_P_PAE)))
> + return;
> +
> + tid = *ieee80211_get_qos_ctl(hdr) & IEEE80211_QOS_CTL_TID_MASK;
> + if (likely(sta->ampdu_mlme.tid_state_tx[tid] != HT_AGG_STATE_IDLE))
> + return;
> +
> + ieee80211_start_tx_ba_session(pubsta, tid);
> +}
> +
> +static void
> +minstrel_ht_get_rate(void *priv, struct ieee80211_sta *sta, void *priv_sta,
> + struct ieee80211_tx_rate_control *txrc)
> +{
> + struct ieee80211_tx_info *info = IEEE80211_SKB_CB(txrc->skb);
> + struct ieee80211_tx_rate *ar = info->status.rates;
> + struct minstrel_ht_sta_priv *msp = priv_sta;
> + struct minstrel_ht_sta *mi = &msp->ht;
> + struct minstrel_priv *mp = priv;
> + bool sample_defer = false;
> + int sample_idx;
> +
> + if (rate_control_send_low(sta, priv_sta, txrc))
> + return;
> +
> + if (!msp->is_ht)
> + return mac80211_minstrel.get_rate(priv, sta, &msp->legacy, txrc);
> +
> + minstrel_aggr_check(mp, sta, txrc->skb);
> +
> + sample_idx = minstrel_get_sample_rate(mp, mi, &sample_defer);
> + if (sample_idx >= 0) {
> + if (sample_defer) {
> + minstrel_ht_set_rate(mp, mi, &ar[0], mi->max_tp_rate,
> + txrc, false, false);
> + minstrel_ht_set_rate(mp, mi, &ar[1], sample_idx,
> + txrc, true, true);
> + info->flags |= MINSTREL_INTFL_SAMPLE_SLOT1;
> + } else {
> + minstrel_ht_set_rate(mp, mi, &ar[0], sample_idx,
> + txrc, true, false);
> + minstrel_ht_set_rate(mp, mi, &ar[1], mi->max_tp_rate,
> + txrc, false, true);
> + info->flags |= MINSTREL_INTFL_SAMPLE_SLOT0;
> + }
> + mi->sample_pending++;
> + } else {
> + minstrel_ht_set_rate(mp, mi, &ar[0], mi->max_tp_rate,
> + txrc, false, false);
> + minstrel_ht_set_rate(mp, mi, &ar[1], mi->max_tp_rate2,
> + txrc, false, true);
> + }
> + minstrel_ht_set_rate(mp, mi, &ar[2], mi->max_prob_rate, txrc, false, true);
> +
> + ar[3].count = 0;
> + ar[3].idx = -1;
> +
> + mi->total_packets++;
> +
> + /* wraparound */
> + if (mi->total_packets >= 100000) {
> + mi->total_packets = 0;
> + mi->sample_packets = 0;
> + mi->sample_pending = 0;
> + }
> +}
> +
> +
> +static void
> +minstrel_ht_rate_init(void *priv, struct ieee80211_supported_band *sband,
> + struct ieee80211_sta *sta, void *priv_sta)
> +{
> + struct minstrel_priv *mp = priv;
> + struct minstrel_ht_sta_priv *msp = priv_sta;
> + struct minstrel_ht_sta *mi = &msp->ht;
> + struct ieee80211_mcs_info *mcs = &sta->ht_cap.mcs;
> + struct ieee80211_local *local = hw_to_local(mp->hw);
> + int tx_streams;
> + int ack_dur;
> + int i;
> +
> + /* fall back to the old minstrel for legacy stations */
> + if (sta && !sta->ht_cap.ht_supported) {
> + msp->is_ht = false;
> + memset(&msp->legacy, 0, sizeof(msp->legacy));
> + msp->legacy.r = msp->ratelist;
> + msp->legacy.sample_table = msp->sample_table;
> + return mac80211_minstrel.rate_init(priv, sband, sta, &msp->legacy);
> + }
> +
> + BUILD_BUG_ON(ARRAY_SIZE(minstrel_mcs_groups) !=
> + MINSTREL_MAX_STREAMS * MINSTREL_STREAM_GROUPS);
> +
> + msp->is_ht = true;
> + memset(mi, 0, sizeof(*mi));
> + mi->stats_update = jiffies;
> +
> + ack_dur = ieee80211_frame_duration(local, 10, 60, 1, 1);
> + mi->overhead = ieee80211_frame_duration(local, 0, 60, 1, 1) + ack_dur;
> + mi->overhead_rtscts = mi->overhead + 2 * ack_dur;
> +
> + mi->avg_ampdu_len = MINSTREL_FRAC(1, 1);
> + tx_streams = ((mcs->tx_params & IEEE80211_HT_MCS_TX_MAX_STREAMS_MASK) >>
> + IEEE80211_HT_MCS_TX_MAX_STREAMS_SHIFT) + 1;
> +
> + for (i = 0; i < ARRAY_SIZE(mi->groups); i++) {
> + u16 req = 0;
> +
> + if (minstrel_mcs_groups[i].flags & IEEE80211_TX_RC_SHORT_GI) {
> + if (minstrel_mcs_groups[i].flags & IEEE80211_TX_RC_40_MHZ_WIDTH)
> + req |= IEEE80211_HT_CAP_SGI_40;
> + else
> + req |= IEEE80211_HT_CAP_SGI_20;
> + }
> +
> + if (minstrel_mcs_groups[i].flags & IEEE80211_TX_RC_40_MHZ_WIDTH)
> + req |= IEEE80211_HT_CAP_SUP_WIDTH_20_40;
> +
> + if ((sta->ht_cap.cap & req) != req)
> + continue;
> +
> + mi->groups[i].supported =
> + mcs->rx_mask[minstrel_mcs_groups[i].streams - 1];
> + }
> +}
> +
> +static void *
> +minstrel_ht_alloc_sta(void *priv, struct ieee80211_sta *sta, gfp_t gfp)
> +{
> + struct ieee80211_supported_band *sband;
> + struct minstrel_ht_sta_priv *msp;
> + struct minstrel_priv *mp = priv;
> + struct ieee80211_hw *hw = mp->hw;
> + int max_rates = 0;
> + int i;
> +
> + for (i = 0; i < IEEE80211_NUM_BANDS; i++) {
> + sband = hw->wiphy->bands[i];
> + if (sband && sband->n_bitrates > max_rates)
> + max_rates = sband->n_bitrates;
> + }
> +
> + msp = kzalloc(sizeof(struct minstrel_ht_sta), gfp);
> + if (!msp)
> + return NULL;
> +
> + msp->ratelist = kzalloc(sizeof(struct minstrel_rate) * max_rates, gfp);
> + if (!msp->ratelist)
> + goto error;
> +
> + msp->sample_table = kmalloc(SAMPLE_COLUMNS * max_rates, gfp);
> + if (!msp->sample_table)
> + goto error1;
> +
> + return msp;
> +
> +error1:
> + kfree(msp->sample_table);
> +error:
> + kfree(msp);
> + return NULL;
> +}
> +
> +static void
> +minstrel_ht_free_sta(void *priv, struct ieee80211_sta *sta, void *priv_sta)
> +{
> + struct minstrel_ht_sta_priv *msp = priv_sta;
> +
> + kfree(msp->sample_table);
> + kfree(msp->ratelist);
> + kfree(msp);
> +}
> +
> +static void *
> +minstrel_ht_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir)
> +{
> + return mac80211_minstrel.alloc(hw, debugfsdir);
> +}
> +
> +static void
> +minstrel_ht_free(void *priv)
> +{
> + mac80211_minstrel.free(priv);
> +}
> +
> +static struct rate_control_ops mac80211_minstrel_ht = {
> + .name = "minstrel_ht",
> + .tx_status = minstrel_ht_tx_status,
> + .get_rate = minstrel_ht_get_rate,
> + .rate_init = minstrel_ht_rate_init,
> + .alloc_sta = minstrel_ht_alloc_sta,
> + .free_sta = minstrel_ht_free_sta,
> + .alloc = minstrel_ht_alloc,
> + .free = minstrel_ht_free,
> +#ifdef CONFIG_MAC80211_DEBUGFS
> + .add_sta_debugfs = minstrel_ht_add_sta_debugfs,
> + .remove_sta_debugfs = minstrel_ht_remove_sta_debugfs,
> +#endif
> +};
> +
> +
> +static void
> +init_sample_table(void)
> +{
> + int col, i, new_idx;
> + u8 rnd[MCS_GROUP_RATES];
> +
> + memset(sample_table, 0xff, sizeof(sample_table));
> + for (col = 0; col < SAMPLE_COLUMNS; col++) {
> + for (i = 0; i < MCS_GROUP_RATES; i++) {
> + get_random_bytes(rnd, sizeof(rnd));
> + new_idx = (i + rnd[i]) % MCS_GROUP_RATES;
> +
> + while (sample_table[col][new_idx] != 0xff)
> + new_idx = (new_idx + 1) % MCS_GROUP_RATES;
> +
> + sample_table[col][new_idx] = i;
> + }
> + }
> +}
> +
> +int __init
> +rc80211_minstrel_ht_init(void)
> +{
> + init_sample_table();
> + return ieee80211_rate_control_register(&mac80211_minstrel_ht);
> +}
> +
> +void
> +rc80211_minstrel_ht_exit(void)
> +{
> + ieee80211_rate_control_unregister(&mac80211_minstrel_ht);
> +}
> --- /dev/null
> +++ b/net/mac80211/rc80211_minstrel_ht.h
> @@ -0,0 +1,115 @@
> +/*
> + * Copyright (C) 2010 Felix Fietkau <[email protected]>
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License version 2 as
> + * published by the Free Software Foundation.
> + */
> +
> +#ifndef __RC_MINSTREL_HT_H
> +#define __RC_MINSTREL_HT_H
> +
> +/*
> + * maximum number of spatial streams to make use of
> + * set this value to 3 once we have drivers that support it
> + */
> +#define MINSTREL_MAX_STREAMS 2
> +#define MINSTREL_STREAM_GROUPS 4
> +
> +/* scaled fraction values */
> +#define MINSTREL_SCALE 16
> +#define MINSTREL_FRAC(val, div) (((val) << MINSTREL_SCALE) / div)
> +#define MINSTREL_TRUNC(val) ((val) >> MINSTREL_SCALE)
> +
> +#define MCS_GROUP_RATES 8
> +
> +struct mcs_group {
> + u32 flags;
> + unsigned int streams;
> + unsigned int duration[MCS_GROUP_RATES];
> +};
> +
> +struct minstrel_rate_stats {
> + /* current / last sampling period attempts/success counters */
> + unsigned int attempts, last_attempts;
> + unsigned int success, last_success;
> +
> + /* total attempts/success counters */
> + u64 att_hist, succ_hist;
> +
> + /* current throughput */
> + unsigned int cur_tp;
> +
> + /* packet delivery probabilities */
> + unsigned int cur_prob, probability;
> +
> + /* maximum retry counts */
> + bool retry_updated;
> + unsigned int retry_count;
> + unsigned int retry_count_rtscts;
> +};
> +
> +struct minstrel_mcs_group_data {
> + u8 index;
> + u8 column;
> +
> + /* bitfield of supported MCS rates of this group */
> + u8 supported;
> +
> + /* selected primary rates */
> + unsigned int max_tp_rate;
> + unsigned int max_tp_rate2;
> + unsigned int max_prob_rate;
> +
> + /* MCS rate statistics */
> + struct minstrel_rate_stats rates[MCS_GROUP_RATES];
> +};
> +
> +struct minstrel_ht_sta {
> + /* ampdu length average (EWMA) */
> + unsigned int avg_ampdu_len;
> +
> + /* best throughput rate */
> + unsigned int max_tp_rate;
> +
> + /* second best throughput rate */
> + unsigned int max_tp_rate2;
> +
> + /* best probability rate */
> + unsigned int max_prob_rate;
> +
> + /* time of last status update */
> + unsigned long stats_update;
> +
> + /* overhead time in usec for each frame */
> + unsigned int overhead;
> + unsigned int overhead_rtscts;
> +
> + unsigned int total_packets;
> + unsigned int sample_packets;
> + unsigned int sample_pending;
> +
> + /* current MCS group to be sampled */
> + unsigned int sample_group;
> +
> + /* MCS rate group info and statistics */
> + struct minstrel_mcs_group_data groups[MINSTREL_MAX_STREAMS * MINSTREL_STREAM_GROUPS];
> +};
> +
> +struct minstrel_ht_sta_priv {
> + union {
> + struct minstrel_ht_sta ht;
> + struct minstrel_sta_info legacy;
> + };
> +#ifdef CONFIG_MAC80211_DEBUGFS
> + struct dentry *dbg_stats;
> +#endif
> + void *ratelist;
> + void *sample_table;
> + bool is_ht;
> +};
> +
> +void minstrel_ht_add_sta_debugfs(void *priv, void *priv_sta, struct dentry *dir);
> +void minstrel_ht_remove_sta_debugfs(void *priv, void *priv_sta);
> +
> +#endif
> --- /dev/null
> +++ b/net/mac80211/rc80211_minstrel_ht_debugfs.c
> @@ -0,0 +1,120 @@
> +/*
> + * Copyright (C) 2010 Felix Fietkau <[email protected]>
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License version 2 as
> + * published by the Free Software Foundation.
> + */
> +#include <linux/netdevice.h>
> +#include <linux/types.h>
> +#include <linux/skbuff.h>
> +#include <linux/debugfs.h>
> +#include <linux/ieee80211.h>
> +#include <net/mac80211.h>
> +#include "rc80211_minstrel.h"
> +#include "rc80211_minstrel_ht.h"
> +
> +extern const struct mcs_group minstrel_mcs_groups[];
> +
> +static int
> +minstrel_ht_stats_open(struct inode *inode, struct file *file)
> +{
> + struct minstrel_ht_sta_priv *msp = inode->i_private;
> + struct minstrel_ht_sta *mi = &msp->ht;
> + struct minstrel_debugfs_info *ms;
> + unsigned int i, j, tp, prob, eprob;
> + char *p;
> + int ret;
> +
> + if (!msp->is_ht) {
> + inode->i_private = &msp->legacy;
> + ret = minstrel_stats_open(inode, file);
> + inode->i_private = msp;
> + return ret;
> + }
> +
> + ms = kmalloc(sizeof(*ms) + 8192, GFP_KERNEL);
> + if (!ms)
> + return -ENOMEM;
> +
> + file->private_data = ms;
> + p = ms->buf;
> + p += sprintf(p, "type rate throughput ewma prob this prob "
> + "this succ/attempt success attempts\n");
> + for (i = 0; i < MINSTREL_MAX_STREAMS * MINSTREL_STREAM_GROUPS; i++) {
> + char htmode = '2';
> + char gimode = 'L';
> +
> + if (!mi->groups[i].supported)
> + continue;
> +
> + if (minstrel_mcs_groups[i].flags & IEEE80211_TX_RC_40_MHZ_WIDTH)
> + htmode = '4';
> + if (minstrel_mcs_groups[i].flags & IEEE80211_TX_RC_SHORT_GI)
> + gimode = 'S';
> +
> + for (j = 0; j < MCS_GROUP_RATES; j++) {
> + struct minstrel_rate_stats *mr = &mi->groups[i].rates[j];
> + int idx = i * MCS_GROUP_RATES + j;
> +
> + if (!mi->groups[i].supported & BIT(j))
> + continue;
> +
> + p += sprintf(p, "HT%c0/%cGI ", htmode, gimode);
> +
> + *(p++) = (idx == mi->max_tp_rate) ? 'T' : ' ';
> + *(p++) = (idx == mi->max_tp_rate2) ? 't' : ' ';
> + *(p++) = (idx == mi->max_prob_rate) ? 'P' : ' ';
> + p += sprintf(p, "MCS%-2u", (minstrel_mcs_groups[i].streams - 1) *
> + MCS_GROUP_RATES + j);
> +
> + tp = mr->cur_tp / 10;
> + prob = MINSTREL_TRUNC(mr->cur_prob * 1000);
> + eprob = MINSTREL_TRUNC(mr->probability * 1000);
> +
> + p += sprintf(p, " %6u.%1u %6u.%1u %6u.%1u "
> + "%3u(%3u) %8llu %8llu\n",
> + tp / 10, tp % 10,
> + eprob / 10, eprob % 10,
> + prob / 10, prob % 10,
> + mr->last_success,
> + mr->last_attempts,
> + (unsigned long long)mr->succ_hist,
> + (unsigned long long)mr->att_hist);
> + }
> + }
> + p += sprintf(p, "\nTotal packet count:: ideal %d "
> + "lookaround %d\n",
> + max(0, (int) mi->total_packets - (int) mi->sample_packets),
> + mi->sample_packets);
> + p += sprintf(p, "Average A-MPDU length: %d.%d\n",
> + MINSTREL_TRUNC(mi->avg_ampdu_len),
> + MINSTREL_TRUNC(mi->avg_ampdu_len * 10) % 10);
> + ms->len = p - ms->buf;
> +
> + return 0;
> +}
> +
> +static const struct file_operations minstrel_ht_stat_fops = {
> + .owner = THIS_MODULE,
> + .open = minstrel_ht_stats_open,
> + .read = minstrel_stats_read,
> + .release = minstrel_stats_release,
> +};
> +
> +void
> +minstrel_ht_add_sta_debugfs(void *priv, void *priv_sta, struct dentry *dir)
> +{
> + struct minstrel_ht_sta_priv *msp = priv_sta;
> +
> + msp->dbg_stats = debugfs_create_file("rc_stats", S_IRUGO, dir, msp,
> + &minstrel_ht_stat_fops);
> +}
> +
> +void
> +minstrel_ht_remove_sta_debugfs(void *priv, void *priv_sta)
> +{
> + struct minstrel_ht_sta_priv *msp = priv_sta;
> +
> + debugfs_remove(msp->dbg_stats);
> +}
>
>

--
Derek Smithies Ph.D.
IndraNet Technologies Ltd.
ph +64 3 365 6485
Web: http://www.indranet-technologies.com/

"The only thing IE should be used for is to download Fire Fox"

"My favorite language is call STAR. It's extremely concise. It has
exactly one verb '*', which does exactly what I want at the moment."
--Larry Wall

2010-06-23 23:56:01

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

2010/6/23 Felix Fietkau <[email protected]>:
> On 2010-06-23 8:47 PM, Bj?rn Smedman wrote:
[snip]
>> But on the other hand doesn't that also mean that MRR rates and counts
>> in the tx status will be incorrect? I.e. one set of rates/counts used
>> to transmit the aggregate (first subframe) and (possibly) another set
>> reported back in tx status (first acked/expired subframe)?
> No, MRR info is just fine. The retry stats are reported for the whole
> A-MPDU, not for indvididual subframes. It's always present in the last
> descriptor of the whole batch. Also, since my code cleanup a while ago,
> the converted rx/tx status info is not longer part of the allocated
> descriptor space, but instead kept on stack in the function that
> processes the tx status. This on stack tx status is then passed to the
> rc update function, which sends the data to mac80211 along with the
> AMPDU tx status report.

That part looks reasonable to me. The part I don't understand is how
ath_tx_rc_update() builds the 'status' field of the
'ieee80211_tx_info' struct. The way I read the code we rely on the
compiler laying out the 'status' field on top of the 'control' field
(both members of an anonymous union) so that rates and counts align.
Since the 'control' field was (presumably) used to set up the tx we
already have a 'status' field that is almost correct. We only have to
remove the retries that where not actually needed from the counts. But
the presumption seems incorrect in the aggregation case. We may be
adjusting an MRR series that has never been used to control tx, right?

> - Felix
>

/Bj?rn

2010-06-28 00:01:05

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

2010/6/23 Felix Fietkau <[email protected]>:
> On 2010-06-23 6:36 PM, Bj?rn Smedman wrote:
>> [snip] As
>> far as I can tell, whenever the first subframe of an aggregate fails
>> and is software retried, the rate control feedback for that aggregate
>> is lost (ath_tx_rc_status() is never called with update_rc = true in
>> xmit.c).
> I think you misread that part. The loop iterates over all subframes in
> the aggregate, and the first successful or swretry-expired frame will
> trigger an AMPDU status report, which will update the RC. The first
> subframe of the A-MPDU is not getting any special treatment here.

You're (still) right I misread that part. But I think there is another
problem when the first subframe of an A-MPDU is not acked: if it has
not expired yet it is (as I understand it) prepended to the tid queue
for software retry and will therefore be the first subframe of the
next aggregate as well, which will then be transmitted with the same
"old" rates and counts as the previous aggregate. So the feedback from
xmit to rc works, but the control information flow from rc to xmit is
delayed.

I guess the real solution is your rewrite... But in the mean time
perhaps we can memcpy the tx_info control from the last subframe to
the first before calling ath_buf_set_rate() in ath_tx_sched_aggr()?
Could that have any side effects? It could make the aggregate size go
over the 4 ms limit I guess... How bad is that?

> - Felix

/Bj?rn

2010-06-23 17:07:49

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On 2010-06-23 6:36 PM, Bj?rn Smedman wrote:
> 2010/3/2 Felix Fietkau <[email protected]>:
>> On 2010-03-02 4:47 PM, Bj?rn Smedman wrote:
>>> 2010/3/2 Felix Fietkau <[email protected]>:
> [snip]
>>> You mean the hardware interprets the block-ack and keeps retrying the
>>> un-acked frames? I thought it stopped as soon as it got a block-ack to
>>> let software sort out the acked and un-acked frames and handle the
>>> "partial" A-MPDU retry.
>> Not sure, actually. I just looked at the ath9k tx path again, and it
>> seems that you're right. However it looks like it's not sending rate
>> control updates until it's done with the software retry, so that's
>> probably the reason why I wasn't able to make it more precise yet.
>
> I had another look at the code now and if I read it correctly this
> delay in the rate control feedback is really scary. In the extreme
> case where all the rates in the MRR stop working you have to make 10
> (ATH_MAX_SW_RETRIES) aggregate software retries (of about 20 frames
> each) with approx 10 hardware retries each before you give the rate
> control algorithm any feedback whatsoever. That is a worst case of
> several thousand (pointless) subframe retransmissions before the rate
> control algorithm has a chance to adjust...
Yes, the extreme case is currently not handled properly. However the
extreme case is also extremely unlikely to trigger. With minstrel_ht,
the max_prob_rate is always in the MRR series. If the conditions jump
from all rates working down to even max_prob_rate failing, then
something must be so wrong with the radio, that there's probably no
possibility of a graceful fallback at all. I do agree that this should
be fixed, though.

> If I'm not wrong above then the rate control feedback must also be
> incorrect: a disaster of that magnitude simply cannot be conveyed to
> the rate control algorithm through the thin tx status interface. As
> far as I can tell, whenever the first subframe of an aggregate fails
> and is software retried, the rate control feedback for that aggregate
> is lost (ath_tx_rc_status() is never called with update_rc = true in
> xmit.c).
I think you misread that part. The loop iterates over all subframes in
the aggregate, and the first successful or swretry-expired frame will
trigger an AMPDU status report, which will update the RC. The first
subframe of the A-MPDU is not getting any special treatment here.

> Any ideas on how to fix this? To me the aggregation and rate control
> code seems to need a major overhaul, something which would require
> changes to the interface between mac80211 and drivers, e.g. ath9k.
> That's out of my league unfortunately...
I've already made a lot of progress rewriting the entire aggregation
logic (it'll be in mac80211 instead of ath9k).
As soon as I'm done fixing the current batch of bugs that I'm debugging
at the moment, I will post my changes as RFC on the linux-wireless list.

- Felix

2010-06-23 18:47:01

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

2010/6/23 Felix Fietkau <[email protected]>:
> On 2010-06-23 6:36 PM, Bj?rn Smedman wrote:
[snip]
>> If I'm not wrong above then the rate control feedback must also be
>> incorrect: a disaster of that magnitude simply cannot be conveyed to
>> the rate control algorithm through the thin tx status interface. As
>> far as I can tell, whenever the first subframe of an aggregate fails
>> and is software retried, the rate control feedback for that aggregate
>> is lost (ath_tx_rc_status() is never called with update_rc = true in
>> xmit.c).
> I think you misread that part. The loop iterates over all subframes in
> the aggregate, and the first successful or swretry-expired frame will
> trigger an AMPDU status report, which will update the RC. The first
> subframe of the A-MPDU is not getting any special treatment here.

You're right, I missed that part. And I guess that's also why the
worst case is so rare.

But on the other hand doesn't that also mean that MRR rates and counts
in the tx status will be incorrect? I.e. one set of rates/counts used
to transmit the aggregate (first subframe) and (possibly) another set
reported back in tx status (first acked/expired subframe)?

Also, bf->bf_retries is used in ath_tx_rc_status() but the logic makes
no sense if bf_retries holds the number of software retries...

>> Any ideas on how to fix this? To me the aggregation and rate control
>> code seems to need a major overhaul, something which would require
>> changes to the interface between mac80211 and drivers, e.g. ath9k.
>> That's out of my league unfortunately...
> I've already made a lot of progress rewriting the entire aggregation
> logic (it'll be in mac80211 instead of ath9k).
> As soon as I'm done fixing the current batch of bugs that I'm debugging
> at the moment, I will post my changes as RFC on the linux-wireless list.

Very nice to hear a rewrite is in progress. :) Looking forward to those patches.

> - Felix
>

/Bj?rn

2010-06-23 16:36:29

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

2010/3/2 Felix Fietkau <[email protected]>:
> On 2010-03-02 4:47 PM, Bj?rn Smedman wrote:
>> 2010/3/2 Felix Fietkau <[email protected]>:
[snip]
>> You mean the hardware interprets the block-ack and keeps retrying the
>> un-acked frames? I thought it stopped as soon as it got a block-ack to
>> let software sort out the acked and un-acked frames and handle the
>> "partial" A-MPDU retry.
> Not sure, actually. I just looked at the ath9k tx path again, and it
> seems that you're right. However it looks like it's not sending rate
> control updates until it's done with the software retry, so that's
> probably the reason why I wasn't able to make it more precise yet.

I had another look at the code now and if I read it correctly this
delay in the rate control feedback is really scary. In the extreme
case where all the rates in the MRR stop working you have to make 10
(ATH_MAX_SW_RETRIES) aggregate software retries (of about 20 frames
each) with approx 10 hardware retries each before you give the rate
control algorithm any feedback whatsoever. That is a worst case of
several thousand (pointless) subframe retransmissions before the rate
control algorithm has a chance to adjust...

If I'm not wrong above then the rate control feedback must also be
incorrect: a disaster of that magnitude simply cannot be conveyed to
the rate control algorithm through the thin tx status interface. As
far as I can tell, whenever the first subframe of an aggregate fails
and is software retried, the rate control feedback for that aggregate
is lost (ath_tx_rc_status() is never called with update_rc = true in
xmit.c).

Any ideas on how to fix this? To me the aggregation and rate control
code seems to need a major overhaul, something which would require
changes to the interface between mac80211 and drivers, e.g. ath9k.
That's out of my league unfortunately...

2010-06-28 10:20:34

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

2010/6/28 Felix Fietkau <[email protected]>:
> On 2010-06-28 2:01 AM, Bj?rn Smedman wrote:
[snip]
>> I guess the real solution is your rewrite... But in the mean time
>> perhaps we can memcpy the tx_info control from the last subframe to
>> the first before calling ath_buf_set_rate() in ath_tx_sched_aggr()?
>> Could that have any side effects? It could make the aggregate size go
>> over the 4 ms limit I guess... How bad is that?
> There's an easy solution which would take into account the 4ms frame
> limit properly, and which could work without any memcpy() hacks:
>
> I could just grab a pointer to the last buffer in the tid queue in the
> ath_tx_sched_aggr() function, then pass it to ath_lookup_rate() via
> ath_tx_form_aggr(), and also to ath_buf_set_rate(). Then I make those
> functions use this last buffer as reference for the rate lookup.

Sounds better to use the rate control from the last buffer in the tid
queue. But be careful if you don't memcpy it to the first frame of the
aggregate then the feedback calculated in ath_tx_rc_status() after tx
will be incorrect again, no?

> - Felix

/Bj?rn

2010-06-28 00:12:29

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On 2010-06-28 2:01 AM, Bj?rn Smedman wrote:
> 2010/6/23 Felix Fietkau <[email protected]>:
>> On 2010-06-23 6:36 PM, Bj?rn Smedman wrote:
>>> [snip] As
>>> far as I can tell, whenever the first subframe of an aggregate fails
>>> and is software retried, the rate control feedback for that aggregate
>>> is lost (ath_tx_rc_status() is never called with update_rc = true in
>>> xmit.c).
>> I think you misread that part. The loop iterates over all subframes in
>> the aggregate, and the first successful or swretry-expired frame will
>> trigger an AMPDU status report, which will update the RC. The first
>> subframe of the A-MPDU is not getting any special treatment here.
>
> You're (still) right I misread that part. But I think there is another
> problem when the first subframe of an A-MPDU is not acked: if it has
> not expired yet it is (as I understand it) prepended to the tid queue
> for software retry and will therefore be the first subframe of the
> next aggregate as well, which will then be transmitted with the same
> "old" rates and counts as the previous aggregate. So the feedback from
> xmit to rc works, but the control information flow from rc to xmit is
> delayed.
>
> I guess the real solution is your rewrite... But in the mean time
> perhaps we can memcpy the tx_info control from the last subframe to
> the first before calling ath_buf_set_rate() in ath_tx_sched_aggr()?
> Could that have any side effects? It could make the aggregate size go
> over the 4 ms limit I guess... How bad is that?
There's an easy solution which would take into account the 4ms frame
limit properly, and which could work without any memcpy() hacks:

I could just grab a pointer to the last buffer in the tid queue in the
ath_tx_sched_aggr() function, then pass it to ath_lookup_rate() via
ath_tx_form_aggr(), and also to ath_buf_set_rate(). Then I make those
functions use this last buffer as reference for the rate lookup.

- Felix

2010-06-28 10:27:47

[permalink] [raw]

Subject: Re: [RFC/RFT] minstrel_ht: new rate control module for 802.11n

On 2010-06-28 12:20 PM, Bj?rn Smedman wrote:
> 2010/6/28 Felix Fietkau <[email protected]>:
>> On 2010-06-28 2:01 AM, Bj?rn Smedman wrote:
> [snip]
>>> I guess the real solution is your rewrite... But in the mean time
>>> perhaps we can memcpy the tx_info control from the last subframe to
>>> the first before calling ath_buf_set_rate() in ath_tx_sched_aggr()?
>>> Could that have any side effects? It could make the aggregate size go
>>> over the 4 ms limit I guess... How bad is that?
>> There's an easy solution which would take into account the 4ms frame
>> limit properly, and which could work without any memcpy() hacks:
>>
>> I could just grab a pointer to the last buffer in the tid queue in the
>> ath_tx_sched_aggr() function, then pass it to ath_lookup_rate() via
>> ath_tx_form_aggr(), and also to ath_buf_set_rate(). Then I make those
>> functions use this last buffer as reference for the rate lookup.
>
> Sounds better to use the rate control from the last buffer in the tid
> queue. But be careful if you don't memcpy it to the first frame of the
> aggregate then the feedback calculated in ath_tx_rc_status() after tx
> will be incorrect again, no?
Right. I intend to let ath_buf_set_rate() set the rates array of the
first subframe accordingly.

- Felix

2010-06-23 19:27:40