GSOC2009Minstrel

Introduction

Minstrel is a well-known rate control algorithm in madwifi and linux kernel, based on Sample rate control algorithm. Our goal for this project is to port this control rate algorithm to NS-3. We will validate this port against the testbeds' experiements(with implementation of minstrel in the linux kernel). We hope our findings will contribute some further improvements to NS-3 simulator.

Approach

Main components of Minstrel

1. Measuring the throughput for each rate:
   • Calculate the probability of success(number successful packets packets/total attempts)
   • Calculate EWMA probabality using its formula.
   • Calculate throughput using EWMA probability and perfect transmission time(transmission time with zero retries).
     • Throughput = EWMA probability * 1,000,000 / perfect transmission time(micro secs)
2. Examine bit rates other than optimal, or "look around" about 10% of the frames.
   • Using a Sample Table,
   • Need to randomize lookaround frames by randomize the initialization of this table.
3. Statistics table.
   • Using EWMA to calculate probability and to process the success history of each rate. Find out which rate gives the best throughput, second best throughput and the highest probability of success.
   • Evaluated 10 times a second.
4. Retry chain to combat delaying of the next data packet(though has to do more with specific hardware)

EWMA

EWMA allows us to decide whether we would like to put more emphasis on the recent results or old results. EWMA calculation for each rate is done 10 times a second. Default value is 75%. The higher the value the more emphasis we put on old results

         Psucces_this_time_interval * (100 - ath_ewma_level) + (Pold * ath_ewma_level)
Pnew =  ------------------------------------------------------------------------------
                  100

                             number_packets_sent_successfully_this_rate_time_interval
Psuccess_this_time_interval=--------------------------------------------------------
                             number_packets_sent_this_rate_time_interval

if there is no packet transmission for a particular rate in a time interval, no need for calculation.

if the new time interval is the first time interval, set Pold to 0.

Retry Chain Table

Retry Chain table:

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

The algorithm of the Retry Chain is simply shown in the table. The table shows the order that we should select the rate according to normal rate and lookaound rate during the retries. Again, retry chain table has to do more with hardware.