GSOC2009Minstrel
Introduction
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.
Our current development is at http://code.nsnam.org/duy/ns-3-dev-minstrel/
Approach
Main components of Minstrel
- 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)
- 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.
- 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.
- 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 recent 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 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:
- look up duration of : slot, difs, sifs, ack, contention_window
- make sure PHY is matched depending on whether it's OFDM or DSSS.
- 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.
- 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.
- 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 Developments
please see our developments at http://code.nsnam.org/duy/ns-3-dev-minstrel/
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. 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.
Validation Plan
Set up scenarios(in simulations and testbeds)
- 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
- Two nodes in concurrent transmission, block the line of sight to cause the degrade in signal. Introduce moving obstacles between nodes
- 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.
- 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.
- 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.
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.
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
Scenario 3: Two nodes within transmission range 25 meters part. Set both nodes stationary. This is more like a sanity check. Throughput vs Time
Scenario 4: Two nodes in opposite direction about 230 meters apart. Moving into transmission range and out of transmission range
Scenario 5: Two nodes moving in and out of transmission range intermittently. Network interfaces are bring down every 5 seconds and back up within 1 second. Throughput is shown as the number of packets received vs Time.
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]
Current progress and priorities:
- Since the interference and error model requires a new wifi phy, our priority right now is to only create a set of test scripts and validating minstrel implementation. Then prepare for code review.
- After release code to ns-3-dev for review, work on the new wifi phy for a new error and interference model.
- ns-3 simulation and CMU emulation integration is taking longer than expected, so we don't expect to include this in our schedule.
NS3 Questions and Comments
- 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.
- We need to find out how to model interference in NS-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