From Nsnam
Jump to: navigation, search


This project has already been ported to ns-3.

Minstrel is a well-known rate control algorithm in madwifi and linux kernel, based on the Sample rate control algorithm. Our goal for this project is to port this control rate algorithm to the NS-3. We hope our findings will contribute some further improvements to the NS-3 simulator.


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 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 recent results

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


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 described in the table. The table shows the order that we should select the rate according to normal rate and lookaound rate during the retries. This retry chain table is needed at the higher layer as well, not just the hardware. We will use this algorithm to select a good rate when the lookaround rate target has not been reached. The goal is to prevent minstrel algorithm from getting "stuck" at a lower rate for some time.

Calculate the transmit duration of a frame

The purpose of this function is to estimate the perfect transmission time. We need to look for an equivalent function in NS-3.

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_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
	PBCC =0
	SIFS = 10 usec; APreamblelength =  144 or 72 with short preamble
	PLCPHeaderLenght = 48 or 24 with short preamble
	TXTIME = PreambleLength + PLCPHeaderTime +

Extra Minstrel Information

  • 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.

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

Rate   Col1   Col2  ...
5.5	RR	RR
6	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.

Validation Plan

Set up scenarios

Scenario 1: Two nodes within transmission range about 5 meters apart. Fix a node stationary, move the second node away from it. Throughput vs Time.

Image on center

Scenario 2: Two nodes out of transmission range about 230 meters apart. Fix a node stationary, move the second node into transmission range. Throughput vs Time

Image on center

Scenario 3: Two nodes within transmission range 25 meters part. Set both nodes stationary. This is more like a sanity check. Throughput vs Time

Image on center

Scenario 4: Two nodes in opposite direction about 230 meters apart. Moving into transmission range and out of transmission range

Image on center

Scenario 5: Two nodes moving in and out of transmission range intermittently. Network interfaces are bringing down every 10 seconds and back up within 1 second. The number of packets received vs Time.

Image on center

Schedule and Progress

Coding begins May 23 2009

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

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

Week 5: Implement retry chain. Finishing up major coding.[done]

Week 6-9: Start testing and validation phase.[done]

Week 10: Release code for review and merge with ns-3-dev[done]

NS3 Questions and Comments

  1. 802.11g does not seem to be implemented in NS-3. We would like to validate the algorithms in 802.11g 2.4ghz environment because it is more practical due to its overcrowded spectrum compared to the relatively unused 802.11a spectrum. Our objective is to test the multirate control algorithms in inteference-prone environment.
  2. We need to find out how to model interference in NS-3.
  3. We still need to figure out simulation scenarios that can easily be reproduced in testbeds.

tomh comment: the testing of this model is something that interests me. One direction to look at (which we've started using ourselves) is the CMU testbed. The interference timing and power can be controlled to fine granularity. Then, these types of controlled interference and path loss scenarios can hopefully be reproduced in the simulator. Contact me if you want help getting started with the CMU emulator. You can run ns-3 in emulation mode even, so that you can use ns-3 traffic generators and logging to move back and forth more easily between simulations and testbed.

It would also be interesting to me if you could come up with interference-dominated simulation testing script for ns-3. This would be similar in spirit to what people have tried to do to get representative background traffic flow through queues, to test congestion effects. For instance, a test script that allows you to define a primary sender/receiver with traffic generator (optionally running TCP or UDP, unicast or multicast) and packet logger, then define a number of background transmitters (unicast, multicast) where the user of the script can control things such as number of interferers, their power levels at the receiver, whether they send unicast or broadcast, whether they rts/cts, their data rates, etc.

duy comment: From my chat with Mathieu, the best way to create an error model and interference model is to create a new wifi phy. I am very interested in doing this, but our priority right now is to release the code for review