[Madwifi-cvs] revision 3361 committed
Status: Beta
Brought to you by:
otaku
From: Benoit P. <svn...@ma...> - 2008-02-21 22:04:44
|
Project : madwifi Revision : 3361 Author : benoit (Benoit Papillault) Date : 2008-02-21 23:04:34 +0100 (Thu, 21 Feb 2008) Log Message : Reformatting. Fixed a bug where the percentage of look around packets was not correct Affected Files: * madwifi/branches/madwifi-dfs/ath_rate/minstrel/minstrel.c updated * madwifi/branches/madwifi-dfs/ath_rate/minstrel/minstrel.txt updated Modified: madwifi/branches/madwifi-dfs/ath_rate/minstrel/minstrel.c =================================================================== --- madwifi/branches/madwifi-dfs/ath_rate/minstrel/minstrel.c 2008-02-21 01:47:52 UTC (rev 3360) +++ madwifi/branches/madwifi-dfs/ath_rate/minstrel/minstrel.c 2008-02-21 22:04:34 UTC (rev 3361) @@ -124,7 +124,7 @@ }; #define DPRINTF(sc, _fmt, ...) do { \ if (sc->sc_debug & ATH_DEBUG_RATE) \ - printk(_fmt, __VA_ARGS__); \ + printk("%s: " _fmt, SC_DEV_NAME(sc), __VA_ARGS__); \ } while (0) #else #define DPRINTF(sc, _fmt, ...) @@ -140,12 +140,14 @@ #define STALE_FAILURE_TIMEOUT_MS 10000 #define ENABLE_MRR 1 -static int ath_timer_interval = (1000 / 10); /* every 1/10 second, timer runs */ -static void ath_timer_function(unsigned long data); +/* interval (in ms) between successive rate statistics, default to 100 ms */ -/* 10% of the time, send a packet at something other than the optimal rate, which fills - * the statistics tables nicely. This percentage is applied to the first packet of the - * multi rate retry chain. */ +static int ath_timer_interval = 100; + +/* 10% of the time, send a packet at something other than the optimal rate, + * which fills the statistics tables nicely. This percentage is applied to the + * first packet of the multi rate retry chain. */ + static int ath_lookaround_rate = 10; static int ath_ewma_level = 75; static int ath_segment_size = 6000; @@ -334,7 +336,8 @@ sn->packet_count++; sn->random_n = (sn->a * sn->random_n) + sn->b; offset = sn->random_n & 0xf; - if ((((100 * sn->sample_count) / (sn->sample_count + sn->packet_count)) < ath_lookaround_rate) && (offset < 2)) { + + if (((100 * sn->sample_count)/sn->packet_count < ath_lookaround_rate) && (offset < 2)) { sn->sample_count++; sn->is_sampling = 1; if (sn->packet_count >= 10000) { @@ -543,185 +546,181 @@ } static void -ath_fill_sample_table(struct minstrel_node *sn) +ath_fill_sample_table(struct ath_softc *sc, struct minstrel_node *sn) { - unsigned int num_sample_rates = (sn->num_rates - 1); - /* newIndex varies as 0 .. (num_rates - 2) - * The highest index rate is the slowest and is ignored */ - unsigned int i, column_index, newIndex; - u_int8_t random_bytes[8]; + unsigned int num_sample_rates = (sn->num_rates - 1); + /* newIndex varies as 0 .. (num_rates - 2) + * The highest index rate is the slowest and is ignored */ + unsigned int i, column_index, newIndex; + u_int8_t random_bytes[8]; - /* This should be unnecessary if we are assuming storage is provided - * as zeroed */ - memset(sn->rs_sampleTable, 0, sizeof(sn->rs_sampleTable)); + /* This should be unnecessary if we are assuming storage is provided + * as zeroed */ + memset(sn->rs_sampleTable, 0, sizeof(sn->rs_sampleTable)); - sn->rs_sampleColumn = 0; - sn->rs_sampleIndex = 0; + sn->rs_sampleColumn = 0; + sn->rs_sampleIndex = 0; - /* Seed value to random number generator, which determines when we - * send a sample packet at some non-optimal rate - * FIXME: randomise? */ - sn->random_n = 1; - sn->a = 1664525; - sn->b = 1013904223; + /* Seed value to random number generator, which determines when we + * send a sample packet at some non-optimal rate + * FIXME: randomise? */ + sn->random_n = 1; + sn->a = 1664525; + sn->b = 1013904223; - if (sn->num_rates > 1) { - for (column_index = 0; column_index < MINSTREL_COLUMNS; column_index++) { - for (i = 0; i < num_sample_rates; i++) { - get_random_bytes(random_bytes, 8); - newIndex = (i + random_bytes[i & 7]) % num_sample_rates; + if (sn->num_rates > 1) { + for (column_index = 0; column_index < MINSTREL_COLUMNS; column_index++) { + for (i = 0; i < num_sample_rates; i++) { + get_random_bytes(random_bytes, 8); + newIndex = (i + random_bytes[i & 7]) % num_sample_rates; - while (sn->rs_sampleTable[newIndex][column_index] != 0) - newIndex = (newIndex + 1) % num_sample_rates; + while (sn->rs_sampleTable[newIndex][column_index] != 0) + newIndex = (newIndex + 1) % num_sample_rates; - sn->rs_sampleTable[newIndex][column_index] = i + 1; - } + sn->rs_sampleTable[newIndex][column_index] = i + 1; } } - -#if 0 - char rates[200]; - char *p; - for (column_index = 0; column_index < MINSTREL_COLUMNS; column_index++) { - p = rates + sprintf(rates, "rates :: %d ", column_index); - for (i = 0; i < num_sample_rates; i++) - p += sprintf(p, "%2u ", sn->rs_sampleTable[i][column_index]); - DPRINTF(sc, "%s\n", rates); - }; -#endif + } + + for (column_index = 0; column_index < MINSTREL_COLUMNS; column_index++) { + for (i = 0; i < num_sample_rates && i < IEEE80211_RATE_MAXSIZE; i++) { + DPRINTF(sc, "rs_sampleTable[%2u][%2u] = %2u\n", + i, column_index, sn->rs_sampleTable[i][column_index]); + } + } } /* Initialize the tables for a node. */ static void ath_rate_ctl_reset(struct ath_softc *sc, struct ieee80211_node *ni) { - struct ath_node *an = ATH_NODE(ni); - struct minstrel_node *sn = ATH_NODE_MINSTREL(an); - struct ieee80211vap *vap = ni->ni_vap; - const HAL_RATE_TABLE *rt = sc->sc_currates; - unsigned int x; - int retry_index, tx_time; - int srate; - int ndx = 0; + struct ath_node *an = ATH_NODE(ni); + struct minstrel_node *sn = ATH_NODE_MINSTREL(an); + struct ieee80211vap *vap = ni->ni_vap; + const HAL_RATE_TABLE *rt = sc->sc_currates; + unsigned int x; + int retry_index, tx_time; + int srate; + int ndx = 0; - sn->num_rates = 0; - sn->max_tp_rate = 0; - sn->max_tp_rate2 = 0; - sn->max_prob_rate = 0; - sn->packet_count = 0; - sn->sample_count = 0; - sn->is_sampling = 0; + sn->num_rates = 0; + sn->max_tp_rate = 0; + sn->max_tp_rate2 = 0; + sn->max_prob_rate = 0; + sn->packet_count = 0; + sn->sample_count = 0; + sn->is_sampling = 0; - if (rt == NULL) { - DPRINTF(sc, "no rates yet! mode %u\n", sc->sc_curmode); - return; - } - sn->static_rate_ndx = -1; + if (rt == NULL) { + DPRINTF(sc, "no rates yet! mode %u\n", sc->sc_curmode); + return; + } + sn->static_rate_ndx = -1; - sn->num_rates = ni->ni_rates.rs_nrates; - for (x = 0; x < ni->ni_rates.rs_nrates; x++) { - sn->rs_rateattempts [x] = 0; - sn->rs_thisprob [x] = 0; - sn->rs_ratesuccess [x] = 0; - sn->rs_lastrateattempts [x] = 0; - sn->rs_lastratesuccess [x] = 0; - sn->rs_probability [x] = 0; - sn->rs_succ_hist [x] = 0; - sn->rs_att_hist [x] = 0; - sn->rs_this_tp [x] = 0; + sn->num_rates = ni->ni_rates.rs_nrates; + for (x = 0; x < ni->ni_rates.rs_nrates; x++) { + sn->rs_rateattempts [x] = 0; + sn->rs_thisprob [x] = 0; + sn->rs_ratesuccess [x] = 0; + sn->rs_lastrateattempts [x] = 0; + sn->rs_lastratesuccess [x] = 0; + sn->rs_probability [x] = 0; + sn->rs_succ_hist [x] = 0; + sn->rs_att_hist [x] = 0; + sn->rs_this_tp [x] = 0; - sn->rates[x].rate = ni->ni_rates.rs_rates[x] & IEEE80211_RATE_VAL; - sn->rates[x].rix = sc->sc_rixmap[sn->rates[x].rate]; - if (sn->rates[x].rix == 0xff) { - DPRINTF(sc, "%s: %s ignore bogus rix at %d\n", - dev_info, __func__, x); - continue; - } - sn->rates[x].rateCode = rt->info[sn->rates[x].rix].rateCode; - sn->rates[x].shortPreambleRateCode = - rt->info[sn->rates[x].rix].rateCode | - rt->info[sn->rates[x].rix].shortPreamble; + sn->rates[x].rate = ni->ni_rates.rs_rates[x] & IEEE80211_RATE_VAL; + sn->rates[x].rix = sc->sc_rixmap[sn->rates[x].rate]; + if (sn->rates[x].rix == 0xff) { + DPRINTF(sc, "%s: %s ignore bogus rix at %d\n", + dev_info, __func__, x); + continue; } + sn->rates[x].rateCode = rt->info[sn->rates[x].rix].rateCode; + sn->rates[x].shortPreambleRateCode = + rt->info[sn->rates[x].rix].rateCode | + rt->info[sn->rates[x].rix].shortPreamble; + } + + ath_fill_sample_table(sc, sn); + + ni->ni_txrate = 0; - ath_fill_sample_table(sn); + if (sn->num_rates <= 0) { + DPRINTF(sc, "%s: %s " MAC_FMT " no rates (fixed %d) \n", + dev_info, __func__, MAC_ADDR(ni->ni_macaddr), + vap->iv_fixed_rate); + /* There are no rates yet; we're done */ + return; + } - ni->ni_txrate = 0; + if (vap->iv_fixed_rate != IEEE80211_FIXED_RATE_NONE) { + srate = sn->num_rates - 1; - if (sn->num_rates <= 0) { - DPRINTF(sc, "%s: %s " MAC_FMT " no rates (fixed %d) \n", - dev_info, __func__, MAC_ADDR(ni->ni_macaddr), - vap->iv_fixed_rate); - /* There are no rates yet; we're done */ - return; - } + /* A fixed rate is to be used; ic_fixed_rate is an + * index into the supported rate set. Convert this + * to the index into the negotiated rate set for + * the node. We know the rate is there because the + * rate set is checked when the station associates. */ + /* NB: the rate set is assumed sorted */ + for (; (srate >= 0) && (ni->ni_rates.rs_rates[srate] & IEEE80211_RATE_VAL) != vap->iv_fixed_rate; srate--); - if (vap->iv_fixed_rate != IEEE80211_FIXED_RATE_NONE) { - srate = sn->num_rates - 1; + KASSERT(srate >= 0, + ("fixed rate %d not in rate set", vap->iv_fixed_rate)); - /* A fixed rate is to be used; ic_fixed_rate is an - * index into the supported rate set. Convert this - * to the index into the negotiated rate set for - * the node. We know the rate is there because the - * rate set is checked when the station associates. */ - /* NB: the rate set is assumed sorted */ - for (; (srate >= 0) && (ni->ni_rates.rs_rates[srate] & IEEE80211_RATE_VAL) != vap->iv_fixed_rate; srate--); + sn->static_rate_ndx = srate; + ni->ni_txrate = srate; + DPRINTF(sc, "%s: %s " MAC_FMT " fixed rate %d%sMbps\n", + dev_info, __func__, MAC_ADDR(ni->ni_macaddr), + sn->rates[srate].rate / 2, + (sn->rates[srate].rate % 2) ? ".5 " : " "); + return; + } - KASSERT(srate >= 0, - ("fixed rate %d not in rate set", vap->iv_fixed_rate)); - - sn->static_rate_ndx = srate; - ni->ni_txrate = srate; - DPRINTF(sc, "%s: %s " MAC_FMT " fixed rate %d%sMbps\n", - dev_info, __func__, MAC_ADDR(ni->ni_macaddr), - sn->rates[srate].rate / 2, - (sn->rates[srate].rate % 2) ? ".5 " : " "); - return; + for (x = 0; x < ni->ni_rates.rs_nrates; x++) { + if (sn->rates[x].rix == 0xff) { + DPRINTF(sc, "%s: %s ignore bogus rix at %d\n", + dev_info, __func__, x); + continue; } - for (x = 0; x < ni->ni_rates.rs_nrates; x++) { - if (sn->rates[x].rix == 0xff) { - DPRINTF(sc, "%s: %s ignore bogus rix at %d\n", - dev_info, __func__, x); - continue; - } + sn->rs_rateattempts [x] = 0; + sn->rs_thisprob [x] = 0; + sn->rs_ratesuccess [x] = 0; + sn->rs_probability [x] = 0; + sn->rs_lastrateattempts [x] = 0; + sn->rs_lastratesuccess [x] = 0; + sn->rs_succ_hist [x] = 0; + sn->rs_att_hist [x] = 0; + sn->perfect_tx_time [x] = + calc_usecs_unicast_packet(sc, 1200, + sn->rates[x].rix, + 0, 0); + sn->retry_count [x] = 1; + sn->retry_adjusted_count[x] = 1; - sn->rs_rateattempts [x] = 0; - sn->rs_thisprob [x] = 0; - sn->rs_ratesuccess [x] = 0; - sn->rs_probability [x] = 0; - sn->rs_lastrateattempts [x] = 0; - sn->rs_lastratesuccess [x] = 0; - sn->rs_succ_hist [x] = 0; - sn->rs_att_hist [x] = 0; - sn->perfect_tx_time [x] = - calc_usecs_unicast_packet(sc, 1200, - sn->rates[x].rix, - 0, 0); - sn->retry_count [x] = 1; - sn->retry_adjusted_count[x] = 1; - - for (retry_index = 2; retry_index < ATH_TXMAXTRY; retry_index++) { - tx_time = calc_usecs_unicast_packet(sc, 1200, sn->rates[x].rix, 0, retry_index); - if (tx_time > ath_segment_size) - break; - sn->retry_count[x] = retry_index; - sn->retry_adjusted_count[x] = retry_index; - } + for (retry_index = 2; retry_index < ATH_TXMAXTRY; retry_index++) { + tx_time = calc_usecs_unicast_packet(sc, 1200, sn->rates[x].rix, 0, retry_index); + if (tx_time > ath_segment_size) + break; + sn->retry_count[x] = retry_index; + sn->retry_adjusted_count[x] = retry_index; } + } #if 0 - DPRINTF(sc, "%s: Retry table for this node\n", __func__); - for (x = 0; x < ni->ni_rates.rs_nrates; x++) - DPRINTF(sc, "%2d %2d %6d \n", x, sn->retry_count[x], sn->perfect_tx_time[x]); + DPRINTF(sc, "%s: Retry table for this node\n", __func__); + for (x = 0; x < ni->ni_rates.rs_nrates; x++) + DPRINTF(sc, "%2d %2d %6d \n", x, sn->retry_count[x], sn->perfect_tx_time[x]); #endif - /* Set the initial rate */ - for (ndx = sn->num_rates - 1; ndx > 0; ndx--) - if (sn->rates[ndx].rate <= 72) - break; - sn->current_rate = ndx; + /* Set the initial rate */ + for (ndx = sn->num_rates - 1; ndx > 0; ndx--) + if (sn->rates[ndx].rate <= 72) + break; + sn->current_rate = ndx; - ni->ni_txrate = sn->current_rate; + ni->ni_txrate = sn->current_rate; } static void @@ -748,160 +747,160 @@ static void ath_timer_function(unsigned long data) { - struct minstrel_softc *ssc = (struct minstrel_softc *) data; - struct ath_softc *sc = ssc->sc; - struct ieee80211com *ic; - struct net_device *dev = ssc->sc_dev; - struct timer_list *timer; - unsigned int interval = ath_timer_interval; + struct minstrel_softc *ssc = (struct minstrel_softc *) data; + struct ath_softc *sc = ssc->sc; + struct ieee80211com *ic; + struct net_device *dev = ssc->sc_dev; + struct timer_list *timer; + unsigned int interval = ath_timer_interval; - if (dev == NULL) - DPRINTF(sc, "%s: 'dev' is null in this timer \n", __func__); + if (dev == NULL) + DPRINTF(sc, "%s: 'dev' is null in this timer \n", __func__); - if (sc == NULL) - DPRINTF(sc, "%s: 'sc' is null in this timer\n", __func__); + if (sc == NULL) + DPRINTF(sc, "%s: 'sc' is null in this timer\n", __func__); - ic = &sc->sc_ic; + ic = &sc->sc_ic; - if (ssc->close_timer_now) - return; + if (ssc->close_timer_now) + return; - if (dev->flags & IFF_RUNNING) { - sc->sc_stats.ast_rate_calls++; + if (dev->flags & IFF_RUNNING) { + sc->sc_stats.ast_rate_calls++; - if (ic->ic_opmode == IEEE80211_M_STA) { - struct ieee80211vap *tmpvap; - TAILQ_FOREACH(tmpvap, &ic->ic_vaps, iv_next) { - ath_rate_statistics(sc, tmpvap->iv_bss);/* NB: no reference */ - } - } else - ieee80211_iterate_nodes(&ic->ic_sta, ath_rate_statistics, sc); - } + if (ic->ic_opmode == IEEE80211_M_STA) { + struct ieee80211vap *tmpvap; + TAILQ_FOREACH(tmpvap, &ic->ic_vaps, iv_next) { + ath_rate_statistics(sc, tmpvap->iv_bss);/* NB: no reference */ + } + } else + ieee80211_iterate_nodes(&ic->ic_sta, ath_rate_statistics, sc); + } - if (ic->ic_opmode == IEEE80211_M_STA) - interval = ath_timer_interval >> 1; + if (ic->ic_opmode == IEEE80211_M_STA) + interval = ath_timer_interval >> 1; - timer = &(ssc->timer); - if (timer == NULL) - DPRINTF(sc, "%s: timer is null - leave it\n", __func__); + timer = &(ssc->timer); + if (timer == NULL) + DPRINTF(sc, "%s: timer is null - leave it\n", __func__); - timer->expires = jiffies + ((HZ * interval) / 1000); - add_timer(timer); + timer->expires = jiffies + ((HZ * interval) / 1000); + add_timer(timer); } static void ath_rate_statistics(void *arg, struct ieee80211_node *ni) { - struct ath_node *an = (struct ath_node *) ni; - struct ieee80211_rateset *rs = &ni->ni_rates; - struct minstrel_node *rn = ATH_NODE_MINSTREL(an); - unsigned int i; - u_int32_t p; - u_int32_t micro_secs; - u_int32_t max_prob, index_max_prob; - u_int32_t max_tp, index_max_tp, index_max_tp2; + struct ath_node *an = (struct ath_node *) ni; + struct ieee80211_rateset *rs = &ni->ni_rates; + struct minstrel_node *rn = ATH_NODE_MINSTREL(an); + unsigned int i; + u_int32_t p; + u_int32_t micro_secs; + u_int32_t max_prob, index_max_prob; + u_int32_t max_tp, index_max_tp, index_max_tp2; - /* Calculate statistics for each date rate in the table */ - /* 'micro_secs' is the time to transmit 1200 bytes, or 9600 bits. */ - for (i = 0; i < rs->rs_nrates; i++) { - micro_secs = rn->perfect_tx_time[i]; - if (micro_secs == 0) - micro_secs = ONE_SECOND; + /* Calculate statistics for each date rate in the table */ + /* 'micro_secs' is the time to transmit 1200 bytes, or 9600 bits. */ + for (i = 0; i < rs->rs_nrates; i++) { + micro_secs = rn->perfect_tx_time[i]; + if (micro_secs == 0) + micro_secs = ONE_SECOND; - if (rn->rs_rateattempts[i] != 0) { - p = (rn->rs_ratesuccess[i] * 18000) / rn->rs_rateattempts[i]; - rn->rs_succ_hist[i] += rn->rs_ratesuccess[i]; - rn->rs_att_hist[i] += rn->rs_rateattempts[i]; - rn->rs_thisprob[i] = p; - p = ((p * (100 - ath_ewma_level)) + (rn->rs_probability[i] * ath_ewma_level)) / 100; - rn->rs_probability[i] = p; - rn->rs_this_tp[i] = p * (ONE_SECOND / micro_secs); - rn->rs_lastratesuccess[i] = rn->rs_ratesuccess[i]; - rn->rs_lastrateattempts[i] = rn->rs_rateattempts[i]; - rn->rs_ratesuccess[i] = 0; - rn->rs_rateattempts[i] = 0; - } else { - rn->rs_lastratesuccess[i] = 0; - rn->rs_lastrateattempts[i] = 0; - } - - /* Sample less often below the 10% chance of success. - * Sample less often above the 95% chance of success. - * 'rn->rs_probability' has a scale of 0 (0%) to 18000 (100%), which avoids rounding issues.*/ - if ((rn->rs_probability[i] > 17100) || (rn->rs_probability[i] < 1800)) { - rn->retry_adjusted_count[i] = rn->retry_count[i] >> 1; - if (rn->retry_adjusted_count[i] > 2) - rn->retry_adjusted_count[i] = 2; - } else - rn->retry_adjusted_count[i] = rn->retry_count[i]; - if (rn->retry_adjusted_count[i] == 0) - rn->retry_adjusted_count[i] = 1; + if (rn->rs_rateattempts[i] != 0) { + p = (rn->rs_ratesuccess[i] * 18000) / rn->rs_rateattempts[i]; + rn->rs_succ_hist[i] += rn->rs_ratesuccess[i]; + rn->rs_att_hist[i] += rn->rs_rateattempts[i]; + rn->rs_thisprob[i] = p; + p = ((p * (100 - ath_ewma_level)) + (rn->rs_probability[i] * ath_ewma_level)) / 100; + rn->rs_probability[i] = p; + rn->rs_this_tp[i] = p * (ONE_SECOND / micro_secs); + rn->rs_lastratesuccess[i] = rn->rs_ratesuccess[i]; + rn->rs_lastrateattempts[i] = rn->rs_rateattempts[i]; + rn->rs_ratesuccess[i] = 0; + rn->rs_rateattempts[i] = 0; + } else { + rn->rs_lastratesuccess[i] = 0; + rn->rs_lastrateattempts[i] = 0; } - /* The High speed rates (e.g 54Mbps) is checked last. If - * throughput is the same for two rates, we prefer the - * lower rate, as this has a better chance of success. */ - max_prob = 0; - index_max_prob = 0; - max_tp = 0; - index_max_tp = 0; - index_max_tp2 = 0; + /* Sample less often below the 10% chance of success. + * Sample less often above the 95% chance of success. + * 'rn->rs_probability' has a scale of 0 (0%) to 18000 (100%), which avoids rounding issues.*/ + if ((rn->rs_probability[i] > 17100) || (rn->rs_probability[i] < 1800)) { + rn->retry_adjusted_count[i] = rn->retry_count[i] >> 1; + if (rn->retry_adjusted_count[i] > 2) + rn->retry_adjusted_count[i] = 2; + } else + rn->retry_adjusted_count[i] = rn->retry_count[i]; + if (rn->retry_adjusted_count[i] == 0) + rn->retry_adjusted_count[i] = 1; + } - /* This code could have been moved up into the previous - * loop. More readable to have it here */ - for (i = 0; i < rs->rs_nrates; i++) { - if (max_tp < rn->rs_this_tp[i]) { - index_max_tp = i; - max_tp = rn->rs_this_tp[i]; - } + /* The High speed rates (e.g 54Mbps) is checked last. If + * throughput is the same for two rates, we prefer the + * lower rate, as this has a better chance of success. */ + max_prob = 0; + index_max_prob = 0; + max_tp = 0; + index_max_tp = 0; + index_max_tp2 = 0; - if (max_prob < rn->rs_probability[i]) { - index_max_prob = i; - max_prob = rn->rs_probability[i]; - } + /* This code could have been moved up into the previous + * loop. More readable to have it here */ + for (i = 0; i < rs->rs_nrates; i++) { + if (max_tp < rn->rs_this_tp[i]) { + index_max_tp = i; + max_tp = rn->rs_this_tp[i]; } - max_tp = 0; - for (i = 0; i < rs->rs_nrates; i++) { - if ((i != index_max_tp) && (max_tp < rn->rs_this_tp[i])) { - index_max_tp2 = i; - max_tp = rn->rs_this_tp[i]; - } + if (max_prob < rn->rs_probability[i]) { + index_max_prob = i; + max_prob = rn->rs_probability[i]; } + } - rn->max_tp_rate = index_max_tp; - rn->max_tp_rate2 = index_max_tp2; - rn->max_prob_rate = index_max_prob; - rn->current_rate = index_max_tp; + max_tp = 0; + for (i = 0; i < rs->rs_nrates; i++) { + if ((i != index_max_tp) && (max_tp < rn->rs_this_tp[i])) { + index_max_tp2 = i; + max_tp = rn->rs_this_tp[i]; + } + } + + rn->max_tp_rate = index_max_tp; + rn->max_tp_rate2 = index_max_tp2; + rn->max_prob_rate = index_max_prob; + rn->current_rate = index_max_tp; } static struct ath_ratectrl * ath_rate_attach(struct ath_softc *sc) { - struct minstrel_softc *osc; - DPRINTF(sc, "%s: %s\n", dev_info, __func__); + struct minstrel_softc *osc; + DPRINTF(sc, "%s: %s\n", dev_info, __func__); - _MOD_INC_USE(THIS_MODULE, return NULL); - osc = kmalloc(sizeof(struct minstrel_softc), GFP_ATOMIC); - if (osc == NULL) { - _MOD_DEC_USE(THIS_MODULE); - return NULL; - } + _MOD_INC_USE(THIS_MODULE, return NULL); + osc = kmalloc(sizeof(struct minstrel_softc), GFP_ATOMIC); + if (osc == NULL) { + _MOD_DEC_USE(THIS_MODULE); + return NULL; + } - osc->arc.arc_space = sizeof(struct minstrel_node); - osc->arc.arc_vap_space = 0; + osc->arc.arc_space = sizeof(struct minstrel_node); + osc->arc.arc_vap_space = 0; - osc->close_timer_now = 0; - init_timer(&osc->timer); + osc->close_timer_now = 0; + init_timer(&osc->timer); osc->sc = sc; - osc->sc_dev = sc->sc_dev; - osc->timer.function = ath_timer_function; - osc->timer.data = (unsigned long)osc; + osc->sc_dev = sc->sc_dev; + osc->timer.function = ath_timer_function; + osc->timer.data = (unsigned long)osc; - osc->timer.expires = jiffies + HZ; - add_timer(&osc->timer); + osc->timer.expires = jiffies + HZ; + add_timer(&osc->timer); - return &osc->arc; + return &osc->arc; } static void @@ -918,134 +917,134 @@ static int ath_proc_read_nodes(struct ieee80211vap *vap, char *buf, int space) { - char *p = buf; - struct ieee80211_node *ni; - struct ath_node *an; - struct minstrel_node *odst; - struct ieee80211_node_table *nt = - (struct ieee80211_node_table *) &vap->iv_ic->ic_sta; - unsigned int x = 0; - unsigned int this_tp, this_prob, this_eprob; - struct ath_softc *sc = vap->iv_ic->ic_dev->priv;; + char *p = buf; + struct ieee80211_node *ni; + struct ath_node *an; + struct minstrel_node *odst; + struct ieee80211_node_table *nt = + (struct ieee80211_node_table *) &vap->iv_ic->ic_sta; + unsigned int x = 0; + unsigned int this_tp, this_prob, this_eprob; + struct ath_softc *sc = vap->iv_ic->ic_dev->priv;; - IEEE80211_NODE_TABLE_LOCK_IRQ(nt); - TAILQ_FOREACH(ni, &nt->nt_node, ni_list) { - /* Assume each node needs 1500 bytes */ - if ((buf + space) < (p + 1500)) { - if ((buf + space) > (p + 100)) { - p += sprintf(p, "out of room for node " MAC_FMT "\n\n", MAC_ADDR(ni->ni_macaddr)); - break; - } - DPRINTF(sc, "%s: out of memeory to write tall of the nodes\n", __func__); - break; + IEEE80211_NODE_TABLE_LOCK_IRQ(nt); + TAILQ_FOREACH(ni, &nt->nt_node, ni_list) { + /* Assume each node needs 1500 bytes */ + if ((buf + space) < (p + 1500)) { + if ((buf + space) > (p + 100)) { + p += sprintf(p, "out of room for node " MAC_FMT "\n\n", MAC_ADDR(ni->ni_macaddr)); + break; } - an = ATH_NODE(ni); - odst = ATH_NODE_MINSTREL(an); - /* Skip ourself */ - if (IEEE80211_ADDR_EQ(vap->iv_myaddr, ni->ni_macaddr)) - continue; + DPRINTF(sc, "%s: out of memeory to write tall of the nodes\n", __func__); + break; + } + an = ATH_NODE(ni); + odst = ATH_NODE_MINSTREL(an); + /* Skip ourself */ + if (IEEE80211_ADDR_EQ(vap->iv_myaddr, ni->ni_macaddr)) + continue; - p += sprintf(p, "rate data for node: " MAC_FMT "\n", MAC_ADDR(ni->ni_macaddr)); - p += sprintf(p, "rate throughput ewma prob this prob this succ/attempt success attempts\n"); - for (x = 0; x < odst->num_rates; x++) { - p += sprintf(p, "%s", - (x == odst->current_rate) ? "T" : " "); + p += sprintf(p, "rate data for node: " MAC_FMT "\n", MAC_ADDR(ni->ni_macaddr)); + p += sprintf(p, " rate throughput ewma prob this prob this succ/attempt success attempts\n"); + for (x = 0; x < odst->num_rates; x++) { + p += sprintf(p, "%c", + (x == odst->current_rate) ? 'T' : ' '); - p += sprintf(p, "%s", - (x == odst->max_tp_rate2) ? "t" : " "); + p += sprintf(p, "%c", + (x == odst->max_tp_rate2) ? 't' : ' '); - p += sprintf(p, "%s", - (x == odst->max_prob_rate) ? "P" : " "); + p += sprintf(p, "%c", + (x == odst->max_prob_rate) ? 'P' : ' '); - p += sprintf(p, "%3u%s", - odst->rates[x].rate / 2, - (odst->rates[x].rate & 0x1) != 0 ? ".5" : " "); + p += sprintf(p, " %2u%s", + odst->rates[x].rate / 2, + (odst->rates[x].rate & 0x1) != 0 ? ".5" : " "); - this_tp = ((odst->rs_this_tp[x] / 18000) * 96) >> 10; - this_prob = odst->rs_thisprob[x] / 18; - this_eprob = odst->rs_probability[x] / 18; - p += sprintf(p, " %6u.%1u %6u.%1u %6u.%1u %3u(%3u) %8llu %8llu\n", - this_tp / 10, this_tp % 10, - this_eprob / 10, this_eprob % 10, - this_prob / 10, this_prob % 10, - odst->rs_lastratesuccess[x], - odst->rs_lastrateattempts[x], - (unsigned long long)odst->rs_succ_hist[x], - (unsigned long long)odst->rs_att_hist[x]); - } - p += sprintf(p, "\n"); - - p += sprintf(p, "Total packet count:: ideal %d lookaround %d\n\n", odst->packet_count, odst->sample_count); + this_tp = ((odst->rs_this_tp[x] / 18000) * 96) >> 10; + this_prob = odst->rs_thisprob[x] / 18; + this_eprob = odst->rs_probability[x] / 18; + p += sprintf(p, " %2u.%1u %2u.%1u %6u.%1u %3u(%3u) %8llu %8llu\n", + this_tp / 10, this_tp % 10, + this_eprob / 10, this_eprob % 10, + this_prob / 10, this_prob % 10, + odst->rs_lastratesuccess[x], + odst->rs_lastrateattempts[x], + (unsigned long long)odst->rs_succ_hist[x], + (unsigned long long)odst->rs_att_hist[x]); } - IEEE80211_NODE_TABLE_UNLOCK_IRQ(nt); + p += sprintf(p, "\n"); - return (p - buf); + p += sprintf(p, "Total packet count:: ideal %d lookaround %d\n\n", odst->packet_count, odst->sample_count); + } + IEEE80211_NODE_TABLE_UNLOCK_IRQ(nt); + + return (p - buf); } static int ath_proc_ratesample_open(struct inode *inode, struct file *file) { - struct proc_ieee80211_priv *pv = NULL; - struct proc_dir_entry *dp = PDE(inode); - struct ieee80211vap *vap = dp->data; + struct proc_ieee80211_priv *pv = NULL; + struct proc_dir_entry *dp = PDE(inode); + struct ieee80211vap *vap = dp->data; - if (!(file->private_data = kmalloc(sizeof(struct proc_ieee80211_priv), - GFP_KERNEL))) - return -ENOMEM; + if (!(file->private_data = kmalloc(sizeof(struct proc_ieee80211_priv), + GFP_KERNEL))) + return -ENOMEM; - /* Initially allocate both read and write buffers */ - pv = (struct proc_ieee80211_priv *) file->private_data; - memset(pv, 0, sizeof(struct proc_ieee80211_priv)); - pv->rbuf = vmalloc(MAX_PROC_IEEE80211_SIZE); - if (!pv->rbuf) { - kfree(pv); - return -ENOMEM; - } - pv->wbuf = vmalloc(MAX_PROC_IEEE80211_SIZE); - if (!pv->wbuf) { - vfree(pv->rbuf); - kfree(pv); - return -ENOMEM; - } + /* Initially allocate both read and write buffers */ + pv = (struct proc_ieee80211_priv *) file->private_data; + memset(pv, 0, sizeof(struct proc_ieee80211_priv)); + pv->rbuf = vmalloc(MAX_PROC_IEEE80211_SIZE); + if (!pv->rbuf) { + kfree(pv); + return -ENOMEM; + } + pv->wbuf = vmalloc(MAX_PROC_IEEE80211_SIZE); + if (!pv->wbuf) { + vfree(pv->rbuf); + kfree(pv); + return -ENOMEM; + } - memset(pv->wbuf, 0, MAX_PROC_IEEE80211_SIZE); - memset(pv->rbuf, 0, MAX_PROC_IEEE80211_SIZE); - pv->max_wlen = MAX_PROC_IEEE80211_SIZE; - pv->max_rlen = MAX_PROC_IEEE80211_SIZE; + memset(pv->wbuf, 0, MAX_PROC_IEEE80211_SIZE); + memset(pv->rbuf, 0, MAX_PROC_IEEE80211_SIZE); + pv->max_wlen = MAX_PROC_IEEE80211_SIZE; + pv->max_rlen = MAX_PROC_IEEE80211_SIZE; - /* Now read the data into the buffer */ - pv->rlen = ath_proc_read_nodes(vap, pv->rbuf, MAX_PROC_IEEE80211_SIZE); - return 0; + /* Now read the data into the buffer */ + pv->rlen = ath_proc_read_nodes(vap, pv->rbuf, MAX_PROC_IEEE80211_SIZE); + return 0; } static struct file_operations ath_proc_ratesample_ops = { - .read = NULL, - .write = NULL, - .open = ath_proc_ratesample_open, - .release = NULL, + .read = NULL, + .write = NULL, + .open = ath_proc_ratesample_open, + .release = NULL, }; static void ath_rate_dynamic_proc_register(struct ieee80211vap *vap) { - /* Create proc entries for the rate control algorithm */ - ieee80211_proc_vcreate(vap, &ath_proc_ratesample_ops, "rate_info"); + /* Create proc entries for the rate control algorithm */ + ieee80211_proc_vcreate(vap, &ath_proc_ratesample_ops, "rate_info"); } #endif /* CONFIG_SYSCTL */ static struct ieee80211_rate_ops ath_rate_ops = { - .ratectl_id = IEEE80211_RATE_MINSTREL, - .node_init = ath_rate_node_init, - .node_cleanup = ath_rate_node_cleanup, - .findrate = ath_rate_findrate, - .get_mrr = ath_rate_get_mrr, - .tx_complete = ath_rate_tx_complete, - .newassoc = ath_rate_newassoc, - .newstate = ath_rate_newstate, - .attach = ath_rate_attach, - .detach = ath_rate_detach, - .dynamic_proc_register = ath_rate_dynamic_proc_register, + .ratectl_id = IEEE80211_RATE_MINSTREL, + .node_init = ath_rate_node_init, + .node_cleanup = ath_rate_node_cleanup, + .findrate = ath_rate_findrate, + .get_mrr = ath_rate_get_mrr, + .tx_complete = ath_rate_tx_complete, + .newassoc = ath_rate_newassoc, + .newstate = ath_rate_newstate, + .attach = ath_rate_attach, + .detach = ath_rate_detach, + .dynamic_proc_register = ath_rate_dynamic_proc_register, }; MODULE_AUTHOR("John Bicket/Derek Smithies"); @@ -1059,22 +1058,22 @@ static int __init ath_rate_minstrel_init(void) { - printk(KERN_INFO "%s: Minstrel automatic rate control " - "algorithm %s\n", dev_info, version); - printk(KERN_INFO "%s: look around rate set to %d%%\n", - dev_info, ath_lookaround_rate); - printk(KERN_INFO "%s: EWMA rolloff level set to %d%%\n", - dev_info, ath_ewma_level); - printk(KERN_INFO "%s: max segment size in the mrr set " - "to %d us\n", dev_info, ath_segment_size); - return ieee80211_rate_register(&ath_rate_ops); + printk(KERN_INFO "%s: Minstrel automatic rate control " + "algorithm %s\n", dev_info, version); + printk(KERN_INFO "%s: look around rate set to %d%%\n", + dev_info, ath_lookaround_rate); + printk(KERN_INFO "%s: EWMA rolloff level set to %d%%\n", + dev_info, ath_ewma_level); + printk(KERN_INFO "%s: max segment size in the mrr set " + "to %d us\n", dev_info, ath_segment_size); + return ieee80211_rate_register(&ath_rate_ops); } module_init(ath_rate_minstrel_init); static void __exit ath_rate_minstrel_exit(void) { - ieee80211_rate_unregister(&ath_rate_ops); - printk(KERN_INFO "%s: unloaded\n", dev_info); + ieee80211_rate_unregister(&ath_rate_ops); + printk(KERN_INFO "%s: unloaded\n", dev_info); } module_exit(ath_rate_minstrel_exit); Modified: madwifi/branches/madwifi-dfs/ath_rate/minstrel/minstrel.txt =================================================================== --- madwifi/branches/madwifi-dfs/ath_rate/minstrel/minstrel.txt 2008-02-21 01:47:52 UTC (rev 3360) +++ madwifi/branches/madwifi-dfs/ath_rate/minstrel/minstrel.txt 2008-02-21 22:04:34 UTC (rev 3361) @@ -1,51 +1,54 @@ +minstrel -Minstrel - Introduction -================================================================== +============================================================================== + This code is called minstrel, because we have taken a wandering minstrel -approach. Wander around the different rates, singing wherever you -can. And then, look at the performance, and make a choice. Note that the -wandering minstrel will always wander in directions where he/she feels he/she -will get paid the best for his/her work. +approach. Wander around the different rates, singing wherever you can. And +then, look at the performance, and make a choice. Note that the wandering +minstrel will always wander in directions where he/she feels he/she will get +paid the best for his/her work. -The Minstrel autorate selection algorithm is an EWMA based algorithm and is -derived from - 1)An initial rate module we released in 2005, +The minstrel autorate selection algorithm is an EWMA based algorithm and is +derived from + + 1) An initial rate module we released in 2005, http://sourceforge.net/mailarchive/forum.php?forum_id=33966&max_rows=25&style=flat&viewmonth=200501&viewday=5 - 2)the "sample" module in the madwifi-ng source tree. + 2) the "sample" module in the madwifi-ng source tree. -The code released in 2005 had some algorithmic and implementation -flaws (one of which was that it was based on the old madwifi codebase) -and was shown to be unstable. Performance of the sample module is poor -(http://www.madwifi.org/ticket/989), and we have observed similar -issues. +The code released in 2005 had some algorithmic and implementation flaws (one +of which was that it was based on the old madwifi codebase) and was shown to +be unstable. Performance of the sample module is poor +(http://www.madwifi.org/ticket/989), and we have observed similar issues. We noted: - 1)The rate chosen by sample did not alter to match changes in the radio + + 1) The rate chosen by sample did not alter to match changes in the radio environment. - 2)Higher throughput (between two nodes) could often be achieved by fixing the - bitrate of both nodes to some value. - 3)After a long period of operation, "sample" appeared to be stuck in a low + + 2) Higher throughput (between two nodes) could often be achieved by fixing + the bitrate of both nodes to some value. + + 3) After a long period of operation, "sample" appeared to be stuck in a low data rate, and would not move to a higher data rate. -We examined the code in sample, and decided the best approach was a -rewrite based on sample and the module we released in January 2005. +We examined the code in sample, and decided the best approach was a rewrite +based on sample and the module we released in January 2005. Theory of operation -================================================================== +============================================================================== -We defined the measure of successfulness (of packet transmission) as +We defined the measure of successfulness (of packet transmission) as - mega-bits-transmitted - Prob_success_transmission * ---------------------- - elapsed time + Mega bits transmitted + Prob_success_transmission * ----------------------- + elapsed time -This measure of successfulness will therefore adjust the transmission speed to +This measure of successfulness will therefore adjust the transmission speed to get the maximum number of data bits through the radio interface. Further, it -means that the 1mb/sec rate (which has a very high probability of successful -transmission) will not be used in preference to the 11mb/sec rate. +means that the 1 Mbits rate (which has a very high probability of successful +transmission) will not be used in preference to the 11 Mbits rate. We decided that the module should record the successfulness of all packets that are transmitted. From this data, the module has sufficient information to @@ -54,43 +57,44 @@ than optimal. Consequently, some percent of the packets have to be sent at rates regarded as non optimal. -10 times a second (this frequency is alterable by changing the driver code) -a timer fires, which evaluates the statistics table. EWMA calculations +10 times a second (this frequency is alterable by changing the driver code) a +timer fires, which evaluates the statistics table. EWMA calculations (described below) are used to process the success history of each rate. On completion of the calculation, a decision is made as to the rate which has the -best throughput, second best throughput, and highest probability of success. +best throughput, second best throughput, and highest probability of success. This data is used for populating the retry chain during the next 100 ms. As stated above, the minstrel algorithm collects statistics from all packet -attempts. Minstrel spends a particular percentage of frames, doing "look -around" i.e. randomly trying other rates, to gather statistics. The -percentage of "look around" frames, is set at boot time via the module -parameter "ath_lookaround_rate" and defaults to 10%. The distribution of -lookaround frames is also randomised somewhat to avoid any potential -"strobing" of lookaround between similar nodes. +attempts. Minstrel spends a particular percentage of frames, doing "look +around" i.e. randomly trying other rates, to gather statistics. The percentage +of "look around" frames, is set at boot time via the module parameter +"ath_lookaround_rate" and defaults to 10%. The distribution of lookaround +frames is also randomised somewhat to avoid any potential "strobing" of +lookaround between similar nodes. -TCP theory tells us that each packet sent must be delivered in under 26ms. Any -longer duration, and the TCP network layers will start to back off. A delay of -26ms implies that there is congestion in the network, and that fewer packets -should be injected to the device. Our conclusion was to adjust the retry chain -of each packet so the retry chain was guaranteed to be finished in under 26ms. +TCP theory tells us that each packet sent must be delivered in under 26 +ms. Any longer duration, and the TCP network layers will start to back off. A +delay of 26 ms implies that there is congestion in the network, and that fewer +packets should be injected to the device. Our conclusion was to adjust the +retry chain of each packet so the retry chain was guaranteed to be finished in +under 26 ms. - Retry Chain -================================================================== +============================================================================== + The HAL provides a multirate retry chain - which consists of four segments. Each segment is an advisement to the HAL to try to send the current packet at some rate, with a fixed number of retry attempts. Once the packet is successfully transmitted, the remainder of the retry chain is ignored. Selection of the number of retry attempts was based on the desire to -get the packet out in under 26ms, or fail. We provided a module parameter, +get the packet out in under 26 ms, or fail. We provided a module parameter, ath_segment_size, which has units of microseconds, and specifies the maximum duration one segment in the retry chain can last. This module parameter has a default of 6000. Our view is that a segment size of between 4000 and 6000 seems to fit most situations. There is some room for movement here - if the traffic is UDP then the limit of -26ms for the retry chain length is "meaningless". However, one may argue that +26 ms for the retry chain length is "meaningless". However, one may argue that if the packet was not transmitted after some time period, it should fail. Further, one does expect UDP packets to fail in transmission. We leave it as an area for future improvement. @@ -115,28 +119,28 @@ After some discussion, we have adjusted the code so that the lowest rate is never used for the lookaround packet. Our view is that since this rate is used -for management packets, this rate must be working. - Alternatively, the link -is set up with management packets, data packets are acknowledged with -management packets. Should the lowest rate stop working, the link is going to -die reasonably soon. +for management packets, this rate must be working. Alternatively, the link is +set up with management packets, data packets are acknowledged with management +packets. Should the lowest rate stop working, the link is going to die +reasonably soon. -Analysis of information in the /proc/net/madwifi/athX/rate_info file -showed that the system was sampling too hard at some rates. For those -rates that never work (54mb, 500m range) there is no point in sending -10 sample packets (<6ms time). Consequently, for the very very low -probability rates, we sample at most twice. +Analysis of information in the /proc/net/madwifi/athX/rate_info file showed +that the system was sampling too hard at some rates. For those rates that +never work (54mb, 500m range) there is no point in sending 10 sample packets +(< 6 ms time). Consequently, for the very very low probability rates, we +sample at most twice. -The retry chain above does "work", but performance is suboptimal. The -key problem being that when the link is good, too much time is spent -sampling the slower rates. Thus, for two nodes adjacent to each other, -the throughput between them was several megabits/sec below using a -fixed rate. The view was that minstrel should not sample at the slower -rates if the link is doing well. However, if the link deteriorates, -minstrel should immediately sample at the lower rates. +The retry chain above does "work", but performance is suboptimal. The key +problem being that when the link is good, too much time is spent sampling the +slower rates. Thus, for two nodes adjacent to each other, the throughput +between them was several Mbits below using a fixed rate. The view was that +minstrel should not sample at the slower rates if the link is doing +well. However, if the link deteriorates, minstrel should immediately sample at +the lower rates. -Some time later, we realised that the only way to code this reliably -was to use the retry chain as the method of determining if the slower -rates are sampled. The retry chain was modified as: +Some time later, we realised that the only way to code this reliably was to +use the retry chain as the method of determining if the slower rates are +sampled. The retry chain was modified as: Try | Lookaround rate | Normal rate | random < best | random > best | @@ -149,33 +153,31 @@ With this retry chain, if the randomly selected rate is slower than the current best throughput, the randomly selected rate is placed second in the chain. If the link is not good, then there will be data collected at the -randomly selected rate. Thus, if the best throughput rate is currently 54mbs, -the only time slower rates are sampled is when a packet fails in +randomly selected rate. Thus, if the best throughput rate is currently 54 +Mbits, the only time slower rates are sampled is when a packet fails in transmission. Consequently, if the link is ideal, all packets will be sent at -the full rate of 54mbs. Which is good. +the full rate of 54 Mbits. Which is good. EWMA -================================================================== +============================================================================== The EWMA calculation is carried out 10 times a second, and is run for each -rate. This calculation has a smoothing effect, so that new results have -a reasonable (but not large) influence on the selected rate. However, with -time, a series of new results in some particular direction will predominate. -Given this smoothing, we can use words like inertia to describe the EWMA. +rate. This calculation has a smoothing effect, so that new results have a +reasonable (but not large) influence on the selected rate. However, with time, +a series of new results in some particular direction will predominate. Given +this smoothing, we can use words like inertia to describe the EWMA. -By "new results", we mean the results collected in the just completed 100ms +By "new results", we mean the results collected in the just completed 100 ms interval. Old results are the EWMA scaling values from before the just -completed 100ms interval. +completed 100 ms interval. EWMA scaling is set by the module parameter ath_ewma_level, and defaults to -75%. A value of 0% means use only the new results, ignore the old results. -A value of 99% means use the old results, with a tiny influence from the new -results. +75%. A value of 0% means use only the new results, ignore the old results. A +value of 99% means use the old results, with a tiny influence from the new +results. - - The calculation (performed for each rate, at each timer interrupt) of the - probability of success is: +probability of success is: Psucces_this_time_interval * (100 - ath_ewma_level) + (Pold * ath_ewma_level) Pnew = ------------------------------------------------------------------------------ @@ -192,16 +194,19 @@ If the new time interval is the first time interval (the module has just been inserted), then Pnew is calculated from above with Pold set to 0. -The appropriate update interval was selected on the basis of choosing a compromise -between - *collecting enough success/failure information to be meaningful - *minimising the amount of cpu time spent do the updates - *providing a means to recover quickly enough from a bad rate selection. -The first two points are self explanatory. When there is a sudden change in the radio -environment, an update interval of 100ms will mean that the rates marked as optimal are -very quickly marked as poor. Consequently, the sudden change in radio environment will -mean that minstrel will very quickly switch to a better rate. +The appropriate update interval was selected on the basis of choosing a +compromise between + * collecting enough success/failure information to be meaningful + * minimising the amount of cpu time spent do the updates + * providing a means to recover quickly enough from a bad rate selection. + +The first two points are self explanatory. When there is a sudden change in +the radio environment, an update interval of 100 ms will mean that the rates +marked as optimal are very quickly marked as poor. Consequently, the sudden +change in radio environment will mean that minstrel will very quickly switch +to a better rate. + A sudden change in the transmission probabilities will happen when the node has not transmitted any data for a while, and during that time the environment has changed. On starting to transmit, the probability @@ -209,10 +214,8 @@ as quickly as possible, so as to not upset the higher TCP network layers. - - Module Parameters -==================================================== +============================================================================== The module has three parameters: name default value purpose @@ -225,8 +228,9 @@ Test Network -==================================================== -We used three computers in our test network. The first two, equipped with +============================================================================== + +We used three computers in our test network. The first two, equipped with atheros cards running in adhoc mode. We used a program that sends a fixed number of TCP packets between computers, and reports on the data rate. The application reports on the data rate - at an application layer level, which is @@ -238,50 +242,49 @@ without introducing any additional load on the first two computers. It was from monitoring the results on the third computer that we started to -get some confidence in the correctness of the code. We observed TCP -backoffs (described above) on this box. There was much celebration when the -throughput increased simply because the retry chain was finished in under 26 -ms. +get some confidence in the correctness of the code. We observed TCP backoffs +(described above) on this box. There was much celebration when the throughput +increased simply because the retry chain was finished in under 26 ms. -Our view was that throughput between the two computers should be as -close as possible (or better than) what can be achieved by setting -both ends to fixed rates. Thus, if setting the both ends to fixed -rates significantly increases the throughput, a reasonable conclusion -is that a fault exists in the adaptive rate rate. +Our view was that throughput between the two computers should be as close as +possible (or better than) what can be achieved by setting both ends to fixed +rates. Thus, if setting the both ends to fixed rates significantly increases +the throughput, a reasonable conclusion is that a fault exists in the adaptive +rate rate. We recorded throughputs (with minstrel) that are within 10% of what is -achieved with the experimentally determined optimum fixed rate. +achieved with the experimentally determined optimum fixed rate. Notes on Timing -==================================================== +============================================================================== -As noted above, Minstrel calculates the throughput for each rate. This -calculation (using a packet of size 1200 bytes) determines the -transmission time on the radio medium. In these calculations, we assume a -contention window min and max value of 4 and 10 microseconds respectively. +As noted above, minstrel calculates the throughput for each rate. This +calculation (using a packet of size 1200 bytes) determines the transmission +time on the radio medium. In these calculations, we assume a contention window +min and max value of 4 and 10 microseconds respectively. Further, calculation of the transmission time is required so that we can -guarantee a packet is transmitted (or dropped) in a minimum time period. -The transmission time is used in determining how many times a packet -is transmitted in each segment of the retry chain. +guarantee a packet is transmitted (or dropped) in a minimum time period. The +transmission time is used in determining how many times a packet is +transmitted in each segment of the retry chain. Indeed, the card will supply the cwmin/cwmax values directly iwpriv if_name get_cwmin <0|1|2|3> <0|1> -We have not made direct calls to determine cwmin/cwmax - this is an area -for future work. Indeed, the cwmin/cwmax determination code could check to -see if the user has altered these values with the appropriate iwpriv. +We have not made direct calls to determine cwmin/cwmax - this is an area for +future work. Indeed, the cwmin/cwmax determination code could check to see if +the user has altered these values with the appropriate iwpriv. -The contention window size does vary with traffic class. For example, -video and voice have a contention window min of 3 and 2 microseconds +The contention window size does vary with traffic class. For example, video +and voice have a contention window min of 3 and 2 microseconds respectively. Currently, minstrel does not check traffic class. -Calculating the throughputs based on traffic class and bit rate and -variable packet size will significantly complicate the code and require -many more sample packets. More sample packets will lower the throughput -achieved. Thus, our view is that for this release, we should take a simple -(but reasonable) approach that works stably and gives good throughputs. +Calculating the throughputs based on traffic class and bit rate and variable +packet size will significantly complicate the code and require many more +sample packets. More sample packets will lower the throughput achieved. Thus, +our view is that for this release, we should take a simple (but reasonable) +approach that works stably and gives good throughputs. Values of cwin/cwmax of 4 and 10 microseconds are from @@ -291,7 +294,8 @@ Internal variable reporting -==================================================== +============================================================================== + The minstrel algorithm reports to the proc file system its internal statistics, which can be viewed as text. A sample output is below: @@ -325,7 +329,7 @@ second maximum throughput and maximum probability are indicated by the letters T, t, and P respectively. -The statistics gathered in the last 100ms time period are displayed in the +The statistics gathered in the last 100 ms time period are displayed in the "this prob" and "this succ/attempt" columns. Finally, the number of packets transmitted at each rate, since module loading @@ -334,23 +338,14 @@ sent from this node to the remote node. The driver determines success by analysing reports from the hal. The word "attempt" or "attempts" means the count of packets that we transmitted. Thus, the number in the success column -will always be lower than the number in the attempts column. +will always be lower than the number in the attempts column. +When the two nodes are brought closer together, the statistics starts +changing, and you see more successful attempts at the higher rates. The ewma +prob at the higher rates increases and then most packets are conveyed at the +higher rates. -When the two nodes are brought closer together, the statistics start changing, -and you see more successful attempts at the higher rates. The ewma prob at the -higher rates increases and then most packets are conveyed at the higher rates. - -When the rate is not on auto, but fixed, this table is still -available, and will report the throughput etc for the current bit -rate. Changing the rate from auto to fixed to auto will completely -reset this table, and the operation of the minstrel module. - - - - - - - - - +When the rate is not on auto, but fixed, this table is still available, and +will report the throughput etc for the current bit rate. Changing the rate +from auto to fixed to auto will completely reset this table, and the operation +of the minstrel module. |