Difference between revisions of "GSOC2009Minstrel"

From Nsnam
Jump to: navigation, search
(Schedule and Progress)
(NS-3 Developments)
 
(33 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Introduction ==
 
== Introduction ==
  
[http://linuxwireless.org/en/developers/Documentation/mac80211/RateControl/minstrel Minstrel] is a well-known rate control algorithm in [http://madwifi-project.org/ 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 will validate this port against the testbeds's experiements(with implementation of minstrel algorithm in both linux kernel and madwifi drivers).  We hope our findings will contribute some further improvements to the NS-3 simulator.
+
This project has already been ported to ns-3.
  
Our current development is at http://code.nsnam.org/duy/ns-3-dev-minstrel/
+
[http://linuxwireless.org/en/developers/Documentation/mac80211/RateControl/minstrel Minstrel] is a well-known rate control algorithm in [http://madwifi-project.org/ 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.
  
 
== Approach ==
 
== Approach ==
Line 24: Line 24:
 
on the recent results or old results.  EWMA calculation for each rate
 
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
 
is done 10 times a second.  Default value is 75%.  The higher the
value the more emphasis we put on old results
+
value the more emphasis we put on recent results
  
 
<pre>
 
<pre>
Line 97: Line 97:
 
</pre>
 
</pre>
  
==== NS-3 Developments ====
 
  
please see our developments at http://code.nsnam.org/duy/ns-3-dev-minstrel/
 
  
 
=== Extra Minstrel Information ===
 
=== Extra Minstrel Information ===
Line 148: Line 146:
  
 
==== Validation Plan ====
 
==== Validation Plan ====
Set up scenarios(in simulations and testbeds)
+
Set up scenarios
  
#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.
 +
[[Image:minstrel1.jpg|center|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:minstrel2.jpg|center|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:minstrel3.jpg|center|Image on center]]
 +
Scenario 4: Two nodes in opposite direction about 230 meters apart.
 +
Moving into transmission range and out of transmission range
 +
[[Image:minstrel4.jpg|750px|center|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:minstrel5two.jpg|750px|center|Image on center]]
  
 
==== Schedule and Progress ====
 
==== Schedule and Progress ====
Line 173: Line 177:
 
Week 5:  Implement retry chain.  Finishing up major coding.[done]
 
Week 5:  Implement retry chain.  Finishing up major coding.[done]
  
Week 6-7: Start testing and validation phase.[current]
+
Week 6-9: Start testing and validation phase.[done]
  
Week 8-9Testing and validation continues (comparing results with testbeds)
+
Week 10Release code for review and merge with ns-3-dev[done]
 
+
Week 10:  Completely port to NS-3 and merge to NS-3 main source code.
+
 
+
 
+
Current Progress and priority:
+
#Continue testing and validating Minstrel implementation
+
#Work on the errormodel for creating interesting scenarios(http://www.nsnam.org/bugzilla/show_bug.cgi?id=414)
+
#Working on the interference model
+
  
 
==== NS3 Questions and Comments ====
 
==== NS3 Questions and Comments ====
Line 194: Line 190:
  
 
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.
 
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

Latest revision as of 17:57, 29 October 2009

Introduction

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.

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 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:

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


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



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