minstrel.txt.svn-base

最新之atheros芯片driver source code, 基于linux操作系统,內含atheros芯片HAL全部代码

minstrel

Introduction
==============================================================================

This code is called minstrel, because we have taken a wandering minstrel
approach. Wander around the different rates, singing wherever you can. And
then, look at the performance, and make a choice. Note that the wandering
minstrel will always wander in directions where he/she feels he/she will get
paid the best for his/her work.

The minstrel autorate selection algorithm is an EWMA based algorithm and is
derived from

 1) An initial rate module we released in 2005,
  http://sourceforge.net/mailarchive/forum.php?forum_id=33966&max_rows=25&style=flat&viewmonth=200501&viewday=5

 2) the "sample" module in the madwifi-ng source tree.

The code released in 2005 had some algorithmic and implementation flaws (one
of which was that it was based on the old madwifi codebase) and was shown to
be unstable. Performance of the sample module is poor
(http://www.madwifi.org/ticket/989), and we have observed similar issues.

We noted:

 1) The rate chosen by sample did not alter to match changes in the radio
    environment.

 2) Higher throughput (between two nodes) could often be achieved by fixing
    the bitrate of both nodes to some value.

 3) After a long period of operation, "sample" appeared to be stuck in a low
    data rate, and would not move to a higher data rate.

We examined the code in sample, and decided the best approach was a rewrite
based on sample and the module we released in January 2005.

Theory of operation
==============================================================================

We defined the measure of successfulness (of packet transmission) as

                                  Mega bits transmitted
    Prob_success_transmission *  -----------------------
	     		              elapsed time

This measure of successfulness will therefore adjust the transmission speed to
get the maximum number of data bits through the radio interface. Further, it
means that the 1 Mbps rate (which has a very high probability of successful
transmission) will not be used in preference to the 11 Mbps rate.

We decided that the module should record the successfulness of all packets
that are transmitted. From this data, the module has sufficient information to
decide which packets are more successful than others. However, a variability
element was required. We had to force the module to examine bit rates other
than optimal. Consequently, some percent of the packets have to be sent at
rates regarded as non optimal.

10 times a second (this frequency is alterable by changing the driver code) a
timer fires, which evaluates the statistics table. EWMA calculations
(described below) are used to process the success history of each rate. On
completion of the calculation, a decision is made as to the rate which has the
best throughput, second best throughput, and highest probability of success.
This data is used for populating the retry chain during the next 100 ms.

As stated above, the minstrel algorithm collects statistics from all packet
attempts. Minstrel spends a particular percentage of frames, doing "look
around" i.e. randomly trying other rates, to gather statistics. The percentage
of "look around" frames, is set at boot time via the module parameter
"ath_lookaround_rate" and defaults to 10%. The distribution of lookaround
frames is also randomised somewhat to avoid any potential "strobing" of
lookaround between similar nodes.

TCP theory tells us that each packet sent must be delivered in under 26
ms. Any longer duration, and the TCP network layers will start to back off. A
delay of 26 ms implies that there is congestion in the network, and that fewer
packets should be injected to the device. Our conclusion was to adjust the
retry chain of each packet so the retry chain was guaranteed to be finished in
under 26 ms.

Retry Chain
==============================================================================

The HAL provides a multirate retry chain - which consists of four
segments. Each segment is an advisement to the HAL to try to send the current
packet at some rate, with a fixed number of retry attempts. Once the packet is
successfully transmitted, the remainder of the retry chain is
ignored. Selection of the number of retry attempts was based on the desire to
get the packet out in under 26 ms, or fail. We provided a module parameter,
ath_segment_size, which has units of microseconds, and specifies the maximum
duration one segment in the retry chain can last. This module parameter has a
default of 6000. Our view is that a segment size of between 4000 and 6000
seems to fit most situations.

There is some room for movement here - if the traffic is UDP then the limit of
26 ms for the retry chain length is "meaningless". However, one may argue that
if the packet was not transmitted after some time period, it should
fail. Further, one does expect UDP packets to fail in transmission. We leave
it as an area for future improvement.


The (re)try segment chain is calculated in two possible manners. If this
packet is a normal tranmission packet (90% of packets are this) then the retry
count is best throughput, next best throughput, best probability, lowest
baserate. If it is a sample packet (10% of packets are this), then the retry
chain is random lookaround, best throughput, best probability, lowest base
rate. In tabular format:

        Try | Lookaround rate    | Normal rate         
        ------------------------------------------------
         1  | Random lookaround  | Best throughput     
         2  | Best throughput    | Next best throughput
         3  | Best probability   | Best probability    
         4  | Lowest Baserate    | Lowest Baserate     

The retry count is adjusted so that the transmission time for that section of
the retry chain is less than 26 ms.

After some discussion, we have adjusted the code so that the lowest rate is
never used for the lookaround packet. Our view is that since this rate is used
for management packets, this rate must be working. Alternatively, the link is
set up with management packets, data packets are acknowledged with management
packets. Should the lowest rate stop working, the link is going to die
reasonably soon.

Analysis of information in the /proc/net/madwifi/athX/rate_info file showed
that the system was sampling too hard at some rates. For those rates that
never work (54mb, 500m range) there is no point in sending 10 sample packets
(< 6 ms time). Consequently, for the very very low probability rates, we
sample at most twice.

The retry chain above does "work", but performance is suboptimal. The key
problem being that when the link is good, too much time is spent sampling the
slower rates. Thus, for two nodes adjacent to each other, the throughput
between them was several Mbps below using a fixed rate. The view was that
minstrel should not sample at the slower rates if the link is doing
well. However, if the link deteriorates, minstrel should immediately sample at
the lower rates.

Some time later, we realised that the only way to code this reliably was to
use the retry chain as the method of determining if the slower rates are
sampled. The retry chain was modified as:

Try |         Lookaround rate              | Normal rate         
    | random < best    | random > best     |
--------------------------------------------------------------
 1  | Best throughput  | Random rate       | Best throughput     
 2  | Random rate      | Best throughput   | Next best throughput
 3  | Best probability | Best probability  | Best probability    
 4  | Lowest Baserate  | Lowest baserate   | Lowest baserate     

With this retry chain, if the randomly selected rate is slower than the
current best throughput, the randomly selected rate is placed second in the
chain. If the link is not good, then there will be data collected at the
randomly selected rate.  Thus, if the best throughput rate is currently 54
Mbps, the only time slower rates are sampled is when a packet fails in
transmission. Consequently, if the link is ideal, all packets will be sent at
the full rate of 54 Mbps. Which is good.

EWMA
==============================================================================

The EWMA calculation is carried out 10 times a second, and is run for each
rate. This calculation has a smoothing effect, so that new results have a
reasonable (but not large) influence on the selected rate. However, with time,
a series of new results in some particular direction will predominate. Given
this smoothing, we can use words like inertia to describe the EWMA.

By "new results", we mean the results collected in the just completed 100 ms
interval. Old results are the EWMA scaling values from before the just
completed 100 ms interval.

EWMA scaling is set by the module parameter ath_ewma_level, and defaults to
75%. A value of 0% means use only the new results, ignore the old results.  A
value of 99% means use the old results, with a tiny influence from the new