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.

http://code.nsnam.org/duy/ns-3-dev-minstrel/

We are really appreciate readers for any comments.

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, make sure that retry chain never exceeds 26ms(madwifi hardward only). The hardware offers four segments retry chain to combat delay. For the purpose of simulation in NS-3, we might safely ignore this for now.

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.

rmz: I always find that stuff a bit misleading given the fact that 802.11 itself tries to retransmit a packet several time. It is still not clear to me what is the interaction between the two.

duy: I think this is has to do more with hardware. basically when the first rate fails, the hardware should find another rate to try right away. Again, give you a definite answer soon.

Calculate the transmit duration of a frame

Given a rate and n len bytes

Things to consider:

1. look up duration of : slot, difs, sifs, ack, contention_window
2. make sure PHY is matched depending on whether it's OFDM or DSSS.
3. check for protection mode in 802.11: Protection mode is for backward compatibility with b. For example, 802.11g uses OFDM PHY and 802.11b clients cannot recognize OFDM modulated frames. Often, when 802.11g is in protection modes, headers are modulated using DSSS PHY and frame bodies using OFDM. Two protectio modes: CTS-toself(announce NAV in order to reserve the medium) and RTS-CTS.
4. short and long retry frames: Short retries is used to keep track of the number of retransmitted control frames smaller than rts threshold. On the other hand, long retries is used for packets longer than rts threshold.
5. short or long preamble: Preamble is used to let the receiver aware of the incoming data. By processing preamble, the receiver then is able to synchronize with the transmitter. The remaining portion of the preamble is a header, which contains modulation scheme, transmission rate, transmission time of entire data frame. Long preamble gives the receiver more time to decode information, more resiliant in lossy links but incurs additional overhead. DSSS PHY supports only long preamble. HR/DSSS PHY(802.11b) introduces optional short preamble support. ERP PHY 802.11g requires both long and short preamble support. It seems like Minstrel in linux kernel only considers short preamble.

In linux kernel(/net/mac80211/util.c): frame duration caculation is as follow

if(IEEE80211_BAND_5GHZ || erp) 
{
  N_DBPS = DATARATE x 4
  N_SYM = Ceiling((16+8xLENGTH+6) / N_DBPS)
        (16 = SIGNAL time, 6 = tail bits)
  TSYM = 4 usec;Signal Ext = 6 usec;T_PREAMBLE = 16 usec;T_SIGNAL = 4usecs
  TXTIME = T_PREAMBLE + T_SIGNAL + T_SYM x N_SYM + Signal Ext
}  
else
{
	PBCC =0
	SIFS = 10 usec; APreamblelength =  144 or 72 with short preamble
	PLCPHeaderLenght = 48 or 24 with short preamble
 	
	TXTIME = PreambleLength + PLCPHeaderTime +
                  Ceiling(((LENGTH+PBCC)x8)/DATARATE)
}

NS-3 Components

• Data structure: An array of structs of a struct and two dimensional array

struct minstrel_rate_info {
	//rate, rate_index, rateCode, shortPreambleRatecode, retry_count, number of attemps, probability…etc
}


struct minstrel_node_info {

        //may need to include Wifi-Mode helper class to
        //include some characteristics associated with the this node.

	//for table of rates:
	
	//Option#1: allocate space as needed
	struct minstrel_rate_info * rates;        

	//Option#2: fixed array
	struct minstrel_rate_info rates[MAX_NUM_RATES];



	//for table of sample rates:

        //Option#1 Sample Table pointer to pointer
        //used in the linux kernel
        int ** sample_table;


        //Option#2 a vector of vectors
        //length 1 initialized to 0
        std::vector<std::vector<int>> table_elements(1,0);

	rmz: this is the option I would go for. Basically, the more
	C++ we can use, the better in my opinion.


        //Option#3, just create a bunch of arrays
        //used in mad-wifi 0.9.4
	//the more sample columns, the more samples we can choose from.
	//SAMPLE_COL= 10 in madwifi
	int sample_table[MAX_NUM_RATES][SAMPLE_COL]


	//book-keeping variables
	
	//to keep track of our current location in the sample table
	int sample_idx;
	int sample-col;


	//keep track of current max, second best, highest prob of success
	int max_tp_rate;
	int maxt_tp_rate2;
	int max_prob_rate;



}


/*Allocation of data structures */
struct minstrel_node_info * mi;

mi->rates = new minstrel_node_info[GetNSupportedModes()];


//Option#1 Sample Table pointer to pointer
mi->sample_table = new int*[GetNSupportedModes()]
for (int i=0; i < GetNSupportedModes(); i++)

        mi->sample_table[i] = new int[1];


//Option#2 A vector of vectors
std::vector<std::vector<int>> sampe_table(GetNSupportedModes(), table_elements);

rmz: same comment than before

• Output of index and rate from madwifi drivers:

index 11  rate 108   //54 Mbps
index 10  rate 96    //48 Mbps
index  9  rate 72    //36 Mbps
index  8  rate 48    //24 Mbps
index  7  rate 36    //18 Mbps
index  6  rate 24    //12 Mbps
index  5  rate 22    //11 Mbps
index  4  rate 18    //9  Mbps
index  3  rate 12    //6  Mbps
index  2  rate 11
index  1  rate  4

• Sample Table

Sample Tables: The sample table is mainly used for "look around" rate,
these constitute about 10% of transmitted frames. The every single
column contain rates that are randomized in no particular order.  By
defaults there are 10 such columns.

Example:
RR stands for a random rate chosen from 1 to max_num_rates for each single Col


Rate   Col1   Col2  ...
1	RR	RR
2	RR	RR
5.5	RR	RR
6	RR	RR	
9	RR	RR
11	RR	RR
12	RR	RR
...

We need to find a way to randomize the rates in sample table in NS-3.

rmz: how do they do it in Linux? (or am I missing something)
duy: they get call a random number generator, i guess we can do the same thing.

• Initializing Minstrel

/* to initialize minstrel variables*/



.AddAttribute

        /* contention windows */
        minCw, maxCW,


        /* number of pkts to use for sampling other rates
         * may be percentage or  the number of pkts
         * 5% */
        lookaround_rate,


        /* for mrr we can set it higer cuz it's less overhead than non-mmr */
	//10% 
        lookaround_rate_mrr,


        /* moving average weight
         * to decide how much emphasis we put on history*/
	// 75%
        ewma_level,


        /* for updating stuff */
	//100ms
        update_interval


        /*maximum rate tries */
	//7
        max_rate_tries


        /*max time that hw is allowed to stay in MRR segment */
	//6000
        segment_size
       
        /*enable multirate retry */
        //true
        mmr

• Lowest rate for sending control packets:

//Get the lowest rate for control packets call this function
// m_modes[0] or 6mbs for RTS packets
GetSupportedMode (0)

Validation Plan

Set up scenarios(in simulations and testbeds)

1. Two nodes in concurrent transmission move away from one another until they are out of range. Then, they move back again.

   rmz: by concurrent transmissions, you mean that one is transmitting packets to the other one, right?

   duy:yes

2. Two nodes in concurrent transmission, block the line of sight to cause the degrade in signal. Introduce moving obstacles between nodes
3. Two nodes in concurrent transmission, suddenly bring the receiver down and up again. Can be accomplished by bringing the network interface down and up.

   rmz: what is the point of this scenario? To find out how the algorithm behave in case of failures?

   duy: this scenario is somewhat similar to scenario (1), what I am trying to do is to test the algorithm behavior when none of the rates works, and how the algorithm behaves when the links become good all of a sudden.

4. Two nodes in concurrent transmission, bring up two other pairs of nodes into transmission, make sure all nodes are within one another's range for maximum interference experience.
5. Repeat step but suffle the other other two pairs of nodes around in order to cause maximum inteference and degradadtion in throughput

Other types of interference can be introduced by conducting the experiements in an environment which has many nearby Access Points(APs) These experiments will be carried out in the 2.4Ghz frequency of 802.11g and 5Ghz frequency of 802.11a. For each events 1-5 from above, use randomness in time in order to introduce these events into the nodes in concurrent transmission. Study how protocol behaves in both simulation and testbeds. The goal is to mirror simulation of ns-3 with the kernel implementation of minstrel. We may also study the minstrel implementation in madwifi to compare its behavior with linux kernel and ns-3 simulation.

Schedule

Coding begins May 23 2009

Week 1-2: Implement the skeleton of the class and core data structures for minstrel.

Week 3-4: Implement EMWA to calculate probability and to process the success history of each rate.

Week 5: Implement retry chain. Finishing up coding.

Week 6-7: Start testing and validation phase.

Week 8-9: Testing and validation continues (comparing results with testbeds)

Week 10: Completely port to NS-3 and merge to NS-3 main source code.

NS3 Questions

to be added