Difference between revisions of "GSOC2009Minstrel"

Revision as of 19:08, 13 May 2009

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.

   rmz: I would try to make the code modular enough so that other function of the acquired statistics can be used

   duy: sounds good

4. Retry chain to combat delaying of the next data packet, make sure that retry chain never exceed 26ms.

   rmz: why 26 ms? I still have not found an answer

   duy: this has to do more with specific hardware, we might not need to deal with it, let me take a deeper look

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)
}

On to NS-3

to be added

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.