[PATCH v3 0/7] mac80211: improve and consolidate minstrel rate control

[PATCH v3 0/7] mac80211: improve and consolidate minstrel rate control

[Thomas Huehn]

This patch series merges functions, macros and sampling improvements from
minstrel_ht into minstrel. It adds several improvements to the rate control.

Thomas

v2: remove debugging output (thx to Bob Copeland)
v3: fix array initialization in init_sample_table (thx to Johannes Berg)

[PATCH v3 1/7] mac80211: merge EWMA calculation of minstrel_ht and minstrel

[Thomas Huehn]

Both rate control algorithms (minstrel and minstrel_ht) calculate
averages based on EWMA. Shift function minstrel_ewma() into
rc80211_minstrel.h and make use of it in both minstrel version.
Also shift the default EWMA level (75%) definition to the header file
and clean up variable usage.

Signed-off-by: Thomas Huehn <thomas@net.t-labs.tu-berlin.de>
---
 net/mac80211/rc80211_minstrel.c    | 15 +++++----------
 net/mac80211/rc80211_minstrel.h    | 13 ++++++++++++-
 net/mac80211/rc80211_minstrel_ht.c | 10 ----------
 3 files changed, 17 insertions(+), 21 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index eea45a2..d78f629 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -76,7 +76,6 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 	u32 max_tp = 0, index_max_tp = 0, index_max_tp2 = 0;
 	u32 max_prob = 0, index_max_prob = 0;
 	u32 usecs;
-	u32 p;
 	int i;
 
 	mi->stats_update = jiffies;
@@ -90,14 +89,13 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 		/* To avoid rounding issues, probabilities scale from 0 (0%)
 		 * to 18000 (100%) */
 		if (mr->attempts) {
-			p = (mr->success * 18000) / mr->attempts;
+			mr->cur_prob = (mr->success * 18000) / mr->attempts;
 			mr->succ_hist += mr->success;
 			mr->att_hist += mr->attempts;
-			mr->cur_prob = p;
-			p = ((p * (100 - mp->ewma_level)) + (mr->probability *
-				mp->ewma_level)) / 100;
-			mr->probability = p;
-			mr->cur_tp = p * (1000000 / usecs);
+			mr->probability = minstrel_ewma(mr->probability,
+							mr->cur_prob,
+							EWMA_LEVEL);
+			mr->cur_tp = mr->probability * (1000000 / usecs);
 		}
 
 		mr->last_success = mr->success;
@@ -542,9 +540,6 @@ minstrel_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir)
 	mp->lookaround_rate = 5;
 	mp->lookaround_rate_mrr = 10;
 
-	/* moving average weight for EWMA */
-	mp->ewma_level = 75;
-
 	/* maximum time that the hw is allowed to stay in one MRR segment */
 	mp->segment_size = 6000;
 
diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index 5ecf757..98db93f 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -9,6 +9,18 @@
 #ifndef __RC_MINSTREL_H
 #define __RC_MINSTREL_H
 
+#define EWMA_LEVEL 75	/* ewma weighting factor [%] */
+
+/*
+ * Perform EWMA (Exponentially Weighted Moving Average) calculation
+  */
+static inline int
+minstrel_ewma(int old, int new, int weight)
+{
+	return (new * (100 - weight) + old * weight) / 100;
+}
+
+
 struct minstrel_rate {
 	int bitrate;
 	int rix;
@@ -73,7 +85,6 @@ struct minstrel_priv {
 	unsigned int cw_min;
 	unsigned int cw_max;
 	unsigned int max_retry;
-	unsigned int ewma_level;
 	unsigned int segment_size;
 	unsigned int update_interval;
 	unsigned int lookaround_rate;
diff --git a/net/mac80211/rc80211_minstrel_ht.c b/net/mac80211/rc80211_minstrel_ht.c
index 3af141c..a3081e5 100644
--- a/net/mac80211/rc80211_minstrel_ht.c
+++ b/net/mac80211/rc80211_minstrel_ht.c
@@ -18,7 +18,6 @@
 
 #define AVG_PKT_SIZE	1200
 #define SAMPLE_COLUMNS	10
-#define EWMA_LEVEL		75
 
 /* Number of bits for an average sized packet */
 #define MCS_NBITS (AVG_PKT_SIZE << 3)
@@ -129,15 +128,6 @@ const struct mcs_group minstrel_mcs_groups[] = {
 static u8 sample_table[SAMPLE_COLUMNS][MCS_GROUP_RATES];
 
 /*
- * Perform EWMA (Exponentially Weighted Moving Average) calculation
- */
-static int
-minstrel_ewma(int old, int new, int weight)
-{
-	return (new * (100 - weight) + old * weight) / 100;
-}
-
-/*
  * Look up an MCS group index based on mac80211 rate information
  */
 static int
-- 
1.8.1.1

[PATCH v3 2/7] mac80211: merge value scaling macros of minstrel_ht and minstrel

[Thomas Huehn]

Both minstrel versions use individual ways to scale up integer values
to perform calculations. Merge minstrel_ht's scaling macros into
minstrels header file and use them in both minstrel versions.

Signed-off-by: Thomas Huehn <thomas@net.t-labs.tu-berlin.de>
---
 net/mac80211/rc80211_minstrel.c         | 9 ++++-----
 net/mac80211/rc80211_minstrel.h         | 5 +++++
 net/mac80211/rc80211_minstrel_debugfs.c | 6 +++---
 net/mac80211/rc80211_minstrel_ht.h      | 5 -----
 4 files changed, 12 insertions(+), 13 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index d78f629..c9b9902 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -86,10 +86,8 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 		if (!usecs)
 			usecs = 1000000;
 
-		/* To avoid rounding issues, probabilities scale from 0 (0%)
-		 * to 18000 (100%) */
 		if (mr->attempts) {
-			mr->cur_prob = (mr->success * 18000) / mr->attempts;
+			mr->cur_prob = MINSTREL_FRAC(mr->success, mr->attempts);
 			mr->succ_hist += mr->success;
 			mr->att_hist += mr->attempts;
 			mr->probability = minstrel_ewma(mr->probability,
@@ -105,7 +103,8 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 
 		/* Sample less often below the 10% chance of success.
 		 * Sample less often above the 95% chance of success. */
-		if ((mr->probability > 17100) || (mr->probability < 1800)) {
+		if (mr->probability > MINSTREL_FRAC(95, 100) ||
+		    mr->probability < MINSTREL_FRAC(10, 100)) {
 			mr->adjusted_retry_count = mr->retry_count >> 1;
 			if (mr->adjusted_retry_count > 2)
 				mr->adjusted_retry_count = 2;
@@ -300,7 +299,7 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
 	/* If we're not using MRR and the sampling rate already
 	 * has a probability of >95%, we shouldn't be attempting
 	 * to use it, as this only wastes precious airtime */
-	if (!mrr && sample && (mi->r[ndx].probability > 17100))
+	if (!mrr && sample && (mi->r[ndx].probability > MINSTREL_FRAC(95, 100)))
 		ndx = mi->max_tp_rate;
 
 	ar[0].idx = mi->r[ndx].rix;
diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index 98db93f..fda4a61 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -11,6 +11,11 @@
 
 #define EWMA_LEVEL 75	/* ewma weighting factor [%] */
 
+/* scaled fraction values */
+#define MINSTREL_SCALE  16
+#define MINSTREL_FRAC(val, div) (((val) << MINSTREL_SCALE) / div)
+#define MINSTREL_TRUNC(val) ((val) >> MINSTREL_SCALE)
+
 /*
  * Perform EWMA (Exponentially Weighted Moving Average) calculation
   */
diff --git a/net/mac80211/rc80211_minstrel_debugfs.c b/net/mac80211/rc80211_minstrel_debugfs.c
index d5a5622..c0ebfac 100644
--- a/net/mac80211/rc80211_minstrel_debugfs.c
+++ b/net/mac80211/rc80211_minstrel_debugfs.c
@@ -79,9 +79,9 @@ minstrel_stats_open(struct inode *inode, struct file *file)
 		p += sprintf(p, "%3u%s", mr->bitrate / 2,
 				(mr->bitrate & 1 ? ".5" : "  "));
 
-		tp = mr->cur_tp / ((18000 << 10) / 96);
-		prob = mr->cur_prob / 18;
-		eprob = mr->probability / 18;
+		tp = MINSTREL_TRUNC(mr->cur_tp / 10);
+		prob = MINSTREL_TRUNC(mr->cur_prob * 1000);
+		eprob = MINSTREL_TRUNC(mr->probability * 1000);
 
 		p += sprintf(p, "  %6u.%1u   %6u.%1u   %6u.%1u        "
 				"%3u(%3u)   %8llu    %8llu\n",
diff --git a/net/mac80211/rc80211_minstrel_ht.h b/net/mac80211/rc80211_minstrel_ht.h
index 302dbd5..4ee5999 100644
--- a/net/mac80211/rc80211_minstrel_ht.h
+++ b/net/mac80211/rc80211_minstrel_ht.h
@@ -16,11 +16,6 @@
 #define MINSTREL_MAX_STREAMS	3
 #define MINSTREL_STREAM_GROUPS	4
 
-/* scaled fraction values */
-#define MINSTREL_SCALE	16
-#define MINSTREL_FRAC(val, div) (((val) << MINSTREL_SCALE) / div)
-#define MINSTREL_TRUNC(val) ((val) >> MINSTREL_SCALE)
-
 #define MCS_GROUP_RATES	8
 
 struct mcs_group {
-- 
1.8.1.1

[PATCH v3 3/7] mac80211: add documentation and verbose variable names in

[Thomas Huehn]

Add documentation and more verbose variable names to minstrel's
multi-rate-retry setup within function minstrel_get_rate() to
increase the readability of the algorithm.

Signed-off-by: Thomas Huehn <thomas@net.t-labs.tu-berlin.de>
---
 net/mac80211/rc80211_minstrel.c | 81 +++++++++++++++++++++++++----------------
 net/mac80211/rc80211_minstrel.h |  2 +-
 2 files changed, 50 insertions(+), 33 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index c9b9902..152bb0e 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -78,7 +78,6 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 	u32 usecs;
 	int i;
 
-	mi->stats_update = jiffies;
 	for (i = 0; i < mi->n_rates; i++) {
 		struct minstrel_rate *mr = &mi->r[i];
 
@@ -144,6 +143,9 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 	mi->max_tp_rate = index_max_tp;
 	mi->max_tp_rate2 = index_max_tp2;
 	mi->max_prob_rate = index_max_prob;
+
+	/* Reset update timer */
+	mi->stats_update = jiffies;
 }
 
 static void
@@ -204,10 +206,10 @@ static int
 minstrel_get_next_sample(struct minstrel_sta_info *mi)
 {
 	unsigned int sample_ndx;
-	sample_ndx = SAMPLE_TBL(mi, mi->sample_idx, mi->sample_column);
-	mi->sample_idx++;
-	if ((int) mi->sample_idx > (mi->n_rates - 2)) {
-		mi->sample_idx = 0;
+	sample_ndx = SAMPLE_TBL(mi, mi->sample_row, mi->sample_column);
+	mi->sample_row++;
+	if ((int) mi->sample_row > (mi->n_rates - 2)) {
+		mi->sample_row = 0;
 		mi->sample_column++;
 		if (mi->sample_column >= SAMPLE_COLUMNS)
 			mi->sample_column = 0;
@@ -225,31 +227,37 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
 	struct minstrel_priv *mp = priv;
 	struct ieee80211_tx_rate *ar = info->control.rates;
 	unsigned int ndx, sample_ndx = 0;
-	bool mrr;
-	bool sample_slower = false;
-	bool sample = false;
+	bool mrr_capable;
+	bool indirect_rate_sampling = false;
+	bool rate_sampling = false;
 	int i, delta;
 	int mrr_ndx[3];
-	int sample_rate;
+	int sampling_ratio;
 
+	/* management/no-ack frames do not use rate control */
 	if (rate_control_send_low(sta, priv_sta, txrc))
 		return;
 
-	mrr = mp->has_mrr && !txrc->rts && !txrc->bss_conf->use_cts_prot;
+	/* check multi-rate-retry capabilities & adjust lookaround_rate */
+	mrr_capable = mp->has_mrr &&
+		      !txrc->rts &&
+		      !txrc->bss_conf->use_cts_prot;
+	if (mrr_capable)
+		sampling_ratio = mp->lookaround_rate_mrr;
+	else
+		sampling_ratio = mp->lookaround_rate;
 
+	/* init rateindex [ndx] with max throughput rate */
 	ndx = mi->max_tp_rate;
 
-	if (mrr)
-		sample_rate = mp->lookaround_rate_mrr;
-	else
-		sample_rate = mp->lookaround_rate;
-
+	/* increase sum packet counter */
 	mi->packet_count++;
-	delta = (mi->packet_count * sample_rate / 100) -
+
+	delta = (mi->packet_count * sampling_ratio / 100) -
 			(mi->sample_count + mi->sample_deferred / 2);
 
 	/* delta > 0: sampling required */
-	if ((delta > 0) && (mrr || !mi->prev_sample)) {
+	if ((delta > 0) && (mrr_capable || !mi->prev_sample)) {
 		struct minstrel_rate *msr;
 		if (mi->packet_count >= 10000) {
 			mi->sample_deferred = 0;
@@ -268,21 +276,25 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
 			mi->sample_count += (delta - mi->n_rates * 2);
 		}
 
+		/* get next random rate sample */
 		sample_ndx = minstrel_get_next_sample(mi);
 		msr = &mi->r[sample_ndx];
-		sample = true;
-		sample_slower = mrr && (msr->perfect_tx_time >
-			mi->r[ndx].perfect_tx_time);
+		rate_sampling = true;
 
-		if (!sample_slower) {
+		/* Decide if direct ( 1st mrr stage) or indirect (2nd mrr stage)
+		 * rate sampling method should be used */
+		if (mrr_capable &&
+		    msr->perfect_tx_time > mi->r[ndx].perfect_tx_time)
+				indirect_rate_sampling = true;
+
+		if (!indirect_rate_sampling) {
 			if (msr->sample_limit != 0) {
 				ndx = sample_ndx;
 				mi->sample_count++;
 				if (msr->sample_limit > 0)
 					msr->sample_limit--;
-			} else {
-				sample = false;
-			}
+			} else
+				rate_sampling = false;
 		} else {
 			/* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark
 			 * packets that have the sampling rate deferred to the
@@ -294,34 +306,39 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
 			mi->sample_deferred++;
 		}
 	}
-	mi->prev_sample = sample;
+	mi->prev_sample = rate_sampling;
 
 	/* If we're not using MRR and the sampling rate already
 	 * has a probability of >95%, we shouldn't be attempting
 	 * to use it, as this only wastes precious airtime */
-	if (!mrr && sample && (mi->r[ndx].probability > MINSTREL_FRAC(95, 100)))
+	if (!mrr_capable && rate_sampling &&
+	   (mi->r[ndx].probability > MINSTREL_FRAC(95, 100)))
 		ndx = mi->max_tp_rate;
 
+	/* mrr setup for 1st stage */
 	ar[0].idx = mi->r[ndx].rix;
 	ar[0].count = minstrel_get_retry_count(&mi->r[ndx], info);
 
-	if (!mrr) {
-		if (!sample)
+	/* non mrr setup for 2nd stage */
+	if (!mrr_capable) {
+		if (!rate_sampling)
 			ar[0].count = mp->max_retry;
 		ar[1].idx = mi->lowest_rix;
 		ar[1].count = mp->max_retry;
 		return;
 	}
 
-	/* MRR setup */
-	if (sample) {
-		if (sample_slower)
+	/* mrr setup for 2nd stage */
+	if (rate_sampling) {
+		if (indirect_rate_sampling)
 			mrr_ndx[0] = sample_ndx;
 		else
 			mrr_ndx[0] = mi->max_tp_rate;
 	} else {
 		mrr_ndx[0] = mi->max_tp_rate2;
 	}
+
+	/* mrr setup for 3rd & 4th stage */
 	mrr_ndx[1] = mi->max_prob_rate;
 	mrr_ndx[2] = 0;
 	for (i = 1; i < 4; i++) {
@@ -352,7 +369,7 @@ init_sample_table(struct minstrel_sta_info *mi)
 	u8 rnd[8];
 
 	mi->sample_column = 0;
-	mi->sample_idx = 0;
+	mi->sample_row = 0;
 	memset(mi->sample_table, 0, SAMPLE_COLUMNS * mi->n_rates);
 
 	for (col = 0; col < SAMPLE_COLUMNS; col++) {
diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index fda4a61..5fb5cb8 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -69,7 +69,7 @@ struct minstrel_sta_info {
 	unsigned int sample_count;
 	int sample_deferred;
 
-	unsigned int sample_idx;
+	unsigned int sample_row;
 	unsigned int sample_column;
 
 	int n_rates;
-- 
1.8.1.1

[PATCH v3 4/7] mac80211: extend minstrel's rate sampling to avoid unsampled rates

[Thomas Huehn]

Minstrel's decision which rate should be directly sampled within the
1st mrr stage is limited to such rates faster than the current max
throughput rate. All rates below the current max. throughput rate
are indirectly sampled via the 2nd mrr stage.
This approach leads to deprecated per rate statistics and therfore
a deprecated mrr chain setup.

This patch uses the sampling approach from minstrel_ht. A counter is
added to sum all indirect sample attempts per rate. After 20 indirect
sampling attempts the rate is directly sampled within the 1st mrr stage.
Therefore more up-to-date statistics for all rates are maintained and
used to setup the mrr chain.

Signed-off-by: Thomas Huehn <thomas@net.t-labs.tu-berlin.de>
---
 net/mac80211/rc80211_minstrel.c | 13 +++++++++----
 net/mac80211/rc80211_minstrel.h |  1 +
 2 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index 152bb0e..aa59f29 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -85,7 +85,8 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 		if (!usecs)
 			usecs = 1000000;
 
-		if (mr->attempts) {
+		if (unlikely(mr->attempts > 0)) {
+			mr->sample_skipped = 0;
 			mr->cur_prob = MINSTREL_FRAC(mr->success, mr->attempts);
 			mr->succ_hist += mr->success;
 			mr->att_hist += mr->attempts;
@@ -93,7 +94,8 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 							mr->cur_prob,
 							EWMA_LEVEL);
 			mr->cur_tp = mr->probability * (1000000 / usecs);
-		}
+		} else
+			mr->sample_skipped++;
 
 		mr->last_success = mr->success;
 		mr->last_attempts = mr->attempts;
@@ -282,9 +284,12 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
 		rate_sampling = true;
 
 		/* Decide if direct ( 1st mrr stage) or indirect (2nd mrr stage)
-		 * rate sampling method should be used */
+		 * rate sampling method should be used.
+		 * Respect such rates that are not sampled for 20 interations.
+		 */
 		if (mrr_capable &&
-		    msr->perfect_tx_time > mi->r[ndx].perfect_tx_time)
+		    msr->perfect_tx_time > mi->r[ndx].perfect_tx_time &&
+		    msr->sample_skipped < 20)
 				indirect_rate_sampling = true;
 
 		if (!indirect_rate_sampling) {
diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index 5fb5cb8..200b7e3 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -43,6 +43,7 @@ struct minstrel_rate {
 	u32 attempts;
 	u32 last_attempts;
 	u32 last_success;
+	u8 sample_skipped;
 
 	/* parts per thousand */
 	u32 cur_prob;
-- 
1.8.1.1

[PATCH v3 5/7] mac80211: add lowest rate into minstrel's randmon rate sampling table

[Thomas Huehn]

While minstrel bootstraps and fills the success probabilities of each
rate the lowest rate has typically a very high success probability
(often 100% in our tests).
Its statistics are never updated but considered to setup the mrr chain.
In our tests we see that especially the 3rd mrr stage (which is that
rate providing highest success probability) is filled with the lowest rate
because its initial high sucess probability is never updated. By design
the 4th mrr stage is filled with the lowest rate so often 3rd and 4th
mrr stage are equal.

This patch follows minstrels general approach of assuming as little
as possible about rate dependencies. Consequently we include the
lowest rate into the random sampling table to get balanced up-to-date
statistics of all rates and therefore balanced decisions.

Signed-off-by: Thomas Huehn <thomas@net.t-labs.tu-berlin.de>
---
 net/mac80211/rc80211_minstrel.c    | 20 +++++++-------------
 net/mac80211/rc80211_minstrel.h    |  4 +++-
 net/mac80211/rc80211_minstrel_ht.c |  1 -
 3 files changed, 10 insertions(+), 15 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index aa59f29..aa1e81a 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -55,7 +55,6 @@
 #include "rate.h"
 #include "rc80211_minstrel.h"
 
-#define SAMPLE_COLUMNS	10
 #define SAMPLE_TBL(_mi, _idx, _col) \
 		_mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col]
 
@@ -210,7 +209,7 @@ minstrel_get_next_sample(struct minstrel_sta_info *mi)
 	unsigned int sample_ndx;
 	sample_ndx = SAMPLE_TBL(mi, mi->sample_row, mi->sample_column);
 	mi->sample_row++;
-	if ((int) mi->sample_row > (mi->n_rates - 2)) {
+	if ((int) mi->sample_row >= mi->n_rates) {
 		mi->sample_row = 0;
 		mi->sample_column++;
 		if (mi->sample_column >= SAMPLE_COLUMNS)
@@ -370,26 +369,21 @@ static void
 init_sample_table(struct minstrel_sta_info *mi)
 {
 	unsigned int i, col, new_idx;
-	unsigned int n_srates = mi->n_rates - 1;
 	u8 rnd[8];
 
 	mi->sample_column = 0;
 	mi->sample_row = 0;
-	memset(mi->sample_table, 0, SAMPLE_COLUMNS * mi->n_rates);
+	memset(mi->sample_table, 0xff, SAMPLE_COLUMNS * mi->n_rates);
 
 	for (col = 0; col < SAMPLE_COLUMNS; col++) {
-		for (i = 0; i < n_srates; i++) {
+		for (i = 0; i < mi->n_rates; i++) {
 			get_random_bytes(rnd, sizeof(rnd));
-			new_idx = (i + rnd[i & 7]) % n_srates;
+			new_idx = (i + rnd[i]) % mi->n_rates;
 
-			while (SAMPLE_TBL(mi, new_idx, col) != 0)
-				new_idx = (new_idx + 1) % n_srates;
+			while (SAMPLE_TBL(mi, new_idx, col) != 0xff)
+				new_idx = (new_idx + 1) % mi->n_rates;
 
-			/* Don't sample the slowest rate (i.e. slowest base
-			 * rate). We must presume that the slowest rate works
-			 * fine, or else other management frames will also be
-			 * failing and the link will break */
-			SAMPLE_TBL(mi, new_idx, col) = i + 1;
+			SAMPLE_TBL(mi, new_idx, col) = i;
 		}
 	}
 }
diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index 200b7e3..a0ccc57 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -9,7 +9,9 @@
 #ifndef __RC_MINSTREL_H
 #define __RC_MINSTREL_H
 
-#define EWMA_LEVEL 75	/* ewma weighting factor [%] */
+#define EWMA_LEVEL	75	/* ewma weighting factor [%] */
+#define SAMPLE_COLUMNS	10	/* number of columns in sample table */
+
 
 /* scaled fraction values */
 #define MINSTREL_SCALE  16
diff --git a/net/mac80211/rc80211_minstrel_ht.c b/net/mac80211/rc80211_minstrel_ht.c
index a3081e5..8f88108 100644
--- a/net/mac80211/rc80211_minstrel_ht.c
+++ b/net/mac80211/rc80211_minstrel_ht.c
@@ -17,7 +17,6 @@
 #include "rc80211_minstrel_ht.h"
 
 #define AVG_PKT_SIZE	1200
-#define SAMPLE_COLUMNS	10
 
 /* Number of bits for an average sized packet */
 #define MCS_NBITS (AVG_PKT_SIZE << 3)
-- 
1.8.1.1

Re: [PATCH v3 5/7] mac80211: add lowest rate into minstrel's randmon rate sampling table

[Felix Fietkau]

On 2013-03-04 7:48 PM, Thomas Huehn wrote:
> While minstrel bootstraps and fills the success probabilities of each
> rate the lowest rate has typically a very high success probability
> (often 100% in our tests).
> Its statistics are never updated but considered to setup the mrr chain.
> In our tests we see that especially the 3rd mrr stage (which is that
> rate providing highest success probability) is filled with the lowest rate
> because its initial high sucess probability is never updated. By design
> the 4th mrr stage is filled with the lowest rate so often 3rd and 4th
> mrr stage are equal.
> 
> This patch follows minstrels general approach of assuming as little
> as possible about rate dependencies. Consequently we include the
> lowest rate into the random sampling table to get balanced up-to-date
> statistics of all rates and therefore balanced decisions.
> 
> Signed-off-by: Thomas Huehn <thomas@net.t-labs.tu-berlin.de>
> ---
>  net/mac80211/rc80211_minstrel.c    | 20 +++++++-------------
>  net/mac80211/rc80211_minstrel.h    |  4 +++-
>  net/mac80211/rc80211_minstrel_ht.c |  1 -
>  3 files changed, 10 insertions(+), 15 deletions(-)
> 
> diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
> index aa59f29..aa1e81a 100644
> --- a/net/mac80211/rc80211_minstrel.c
> +++ b/net/mac80211/rc80211_minstrel.c
> @@ -370,26 +369,21 @@ static void
>  init_sample_table(struct minstrel_sta_info *mi)
>  {
>  	unsigned int i, col, new_idx;
> -	unsigned int n_srates = mi->n_rates - 1;
>  	u8 rnd[8];
>  
>  	mi->sample_column = 0;
>  	mi->sample_row = 0;
> -	memset(mi->sample_table, 0, SAMPLE_COLUMNS * mi->n_rates);
> +	memset(mi->sample_table, 0xff, SAMPLE_COLUMNS * mi->n_rates);
>  
>  	for (col = 0; col < SAMPLE_COLUMNS; col++) {
> -		for (i = 0; i < n_srates; i++) {
> +		for (i = 0; i < mi->n_rates; i++) {
>  			get_random_bytes(rnd, sizeof(rnd));
> -			new_idx = (i + rnd[i & 7]) % n_srates;
> +			new_idx = (i + rnd[i]) % mi->n_rates;
Don't remove the '& 7' part, otherwise the rnd array will overflow.
There's no need for it to be as big as the number of rates though.
Also, there's a typo in the subject line: 'randmon'.

- Felix

[PATCH v3 6/7] mac80211: treat minstrel success probabilities below 10% as implausible

[Thomas Huehn]

Based on minstrel_ht this patch treats success probabilities below 10% as
implausible values for throughput calculation in minstrel's statistics.
Current throughput per rate with such a low success probability is reset
to 0 MBit/s.

Signed-off-by: Thomas Huehn <thomas@net.t-labs.tu-berlin.de>
---
 net/mac80211/rc80211_minstrel.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index aa1e81a..de88ae7 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -92,7 +92,6 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 			mr->probability = minstrel_ewma(mr->probability,
 							mr->cur_prob,
 							EWMA_LEVEL);
-			mr->cur_tp = mr->probability * (1000000 / usecs);
 		} else
 			mr->sample_skipped++;
 
@@ -101,6 +100,12 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 		mr->success = 0;
 		mr->attempts = 0;
 
+		/* Update throughput per rate, reset thr. below 10% success */
+		if (mr->probability < MINSTREL_FRAC(10, 100))
+			mr->cur_tp = 0;
+		else
+			mr->cur_tp = mr->probability * (1000000 / usecs);
+
 		/* Sample less often below the 10% chance of success.
 		 * Sample less often above the 95% chance of success. */
 		if (mr->probability > MINSTREL_FRAC(95, 100) ||
-- 
1.8.1.1

[PATCH v3 7/7] mac80211: improve minstrels rate sorting by means of throughput & probability

[Thomas Huehn]

This patch improves the way minstrel sorts rates according to throughput
and success probability. 3 FOR-loops across the entire rate set in function
minstrel_update_stats() which where used to determine the fastest, second
fastest and most robust rate are reduced to 1 FOR-loop.

The sorted list of rates according throughput is extended to the best four
rates as we need them in upcoming joint rate and power control. The sorting
is done via the new function minstrel_sort_best_tp_rates().

The most robust rate selection is aligned with minstrel_ht's approach.
Once any success probability is above 95% the one with the highest
throughput is chosen as most robust rate. If success probabilities of all
rates are below 95%, the rate with the highest succ. prob. is elected as
most robust one

Signed-off-by: Thomas Huehn <thomas@net.t-labs.tu-berlin.de>
---
 net/mac80211/rc80211_minstrel.c         | 71 +++++++++++++++++++--------------
 net/mac80211/rc80211_minstrel.h         |  8 ++--
 net/mac80211/rc80211_minstrel_debugfs.c |  6 ++-
 3 files changed, 49 insertions(+), 36 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index de88ae7..66e6ae4 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -69,14 +69,31 @@ rix_to_ndx(struct minstrel_sta_info *mi, int rix)
 	return i;
 }
 
+/* find & sort topmost throughput rates */
+static inline void
+minstrel_sort_best_tp_rates(struct minstrel_sta_info *mi, int i, u8 *tp_list)
+{
+	int j = MAX_THR_RATES;
+
+	while (j > 0 && mi->r[i].cur_tp > mi->r[tp_list[j - 1]].cur_tp)
+		j--;
+	if (j < MAX_THR_RATES - 1)
+		memmove(&tp_list[j + 1], &tp_list[j], MAX_THR_RATES - (j + 1));
+	if (j < MAX_THR_RATES)
+		tp_list[j] = i;
+}
+
 static void
 minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 {
-	u32 max_tp = 0, index_max_tp = 0, index_max_tp2 = 0;
-	u32 max_prob = 0, index_max_prob = 0;
+	u8 tmp_tp_rate[MAX_THR_RATES];
+	u8 tmp_prob_rate = 0;
 	u32 usecs;
 	int i;
 
+	for (i=0; i < MAX_THR_RATES; i++)
+	    tmp_tp_rate[i] = 0;
+
 	for (i = 0; i < mi->n_rates; i++) {
 		struct minstrel_rate *mr = &mi->r[i];
 
@@ -120,35 +137,27 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 		}
 		if (!mr->adjusted_retry_count)
 			mr->adjusted_retry_count = 2;
-	}
 
-	for (i = 0; i < mi->n_rates; i++) {
-		struct minstrel_rate *mr = &mi->r[i];
-		if (max_tp < mr->cur_tp) {
-			index_max_tp = i;
-			max_tp = mr->cur_tp;
-		}
-		if (max_prob < mr->probability) {
-			index_max_prob = i;
-			max_prob = mr->probability;
+		minstrel_sort_best_tp_rates(mi, i, tmp_tp_rate);
+
+		/* To determine the most robust rate (max_prob_rate) used at
+		 * 3rd mmr stage we distinct between two cases:
+		 * (1) if any success probabilitiy >= 95%, out of those rates
+		 * choose the maximum throughput rate as max_prob_rate
+		 * (2) if all success probabilities < 95%, the rate with
+		 * highest success probability is choosen as max_prob_rate */
+		if (mr->probability >= MINSTREL_FRAC(95,100)) {
+			if (mr->cur_tp >= mi->r[tmp_prob_rate].cur_tp)
+				tmp_prob_rate = i;
+		} else {
+			if (mr->probability >= mi->r[tmp_prob_rate].probability)
+				tmp_prob_rate = i;
 		}
 	}
 
-	max_tp = 0;
-	for (i = 0; i < mi->n_rates; i++) {
-		struct minstrel_rate *mr = &mi->r[i];
-
-		if (i == index_max_tp)
-			continue;
-
-		if (max_tp < mr->cur_tp) {
-			index_max_tp2 = i;
-			max_tp = mr->cur_tp;
-		}
-	}
-	mi->max_tp_rate = index_max_tp;
-	mi->max_tp_rate2 = index_max_tp2;
-	mi->max_prob_rate = index_max_prob;
+	/* Assign the new rate set */
+	memcpy(mi->max_tp_rate, tmp_tp_rate, sizeof(mi->max_tp_rate));
+	mi->max_prob_rate = tmp_prob_rate;
 
 	/* Reset update timer */
 	mi->stats_update = jiffies;
@@ -254,7 +263,7 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
 		sampling_ratio = mp->lookaround_rate;
 
 	/* init rateindex [ndx] with max throughput rate */
-	ndx = mi->max_tp_rate;
+	ndx = mi->max_tp_rate[0];
 
 	/* increase sum packet counter */
 	mi->packet_count++;
@@ -322,7 +331,7 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
 	 * to use it, as this only wastes precious airtime */
 	if (!mrr_capable && rate_sampling &&
 	   (mi->r[ndx].probability > MINSTREL_FRAC(95, 100)))
-		ndx = mi->max_tp_rate;
+		ndx = mi->max_tp_rate[0];
 
 	/* mrr setup for 1st stage */
 	ar[0].idx = mi->r[ndx].rix;
@@ -342,9 +351,9 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
 		if (indirect_rate_sampling)
 			mrr_ndx[0] = sample_ndx;
 		else
-			mrr_ndx[0] = mi->max_tp_rate;
+			mrr_ndx[0] = mi->max_tp_rate[0];
 	} else {
-		mrr_ndx[0] = mi->max_tp_rate2;
+		mrr_ndx[0] = mi->max_tp_rate[1];
 	}
 
 	/* mrr setup for 3rd & 4th stage */
diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index a0ccc57..85ebf42 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -18,6 +18,9 @@
 #define MINSTREL_FRAC(val, div) (((val) << MINSTREL_SCALE) / div)
 #define MINSTREL_TRUNC(val) ((val) >> MINSTREL_SCALE)
 
+/* number of highest throughput rates to consider*/
+#define MAX_THR_RATES 4
+
 /*
  * Perform EWMA (Exponentially Weighted Moving Average) calculation
   */
@@ -65,9 +68,8 @@ struct minstrel_sta_info {
 
 	unsigned int lowest_rix;
 
-	unsigned int max_tp_rate;
-	unsigned int max_tp_rate2;
-	unsigned int max_prob_rate;
+	u8 max_tp_rate[MAX_THR_RATES];
+	u8 max_prob_rate;
 	unsigned int packet_count;
 	unsigned int sample_count;
 	int sample_deferred;
diff --git a/net/mac80211/rc80211_minstrel_debugfs.c b/net/mac80211/rc80211_minstrel_debugfs.c
index c0ebfac..d104834 100644
--- a/net/mac80211/rc80211_minstrel_debugfs.c
+++ b/net/mac80211/rc80211_minstrel_debugfs.c
@@ -73,8 +73,10 @@ minstrel_stats_open(struct inode *inode, struct file *file)
 	for (i = 0; i < mi->n_rates; i++) {
 		struct minstrel_rate *mr = &mi->r[i];
 
-		*(p++) = (i == mi->max_tp_rate) ? 'T' : ' ';
-		*(p++) = (i == mi->max_tp_rate2) ? 't' : ' ';
+		*(p++) = (i == mi->max_tp_rate[0]) ? 'A' : ' ';
+		*(p++) = (i == mi->max_tp_rate[1]) ? 'B' : ' ';
+		*(p++) = (i == mi->max_tp_rate[2]) ? 'C' : ' ';
+		*(p++) = (i == mi->max_tp_rate[3]) ? 'D' : ' ';
 		*(p++) = (i == mi->max_prob_rate) ? 'P' : ' ';
 		p += sprintf(p, "%3u%s", mr->bitrate / 2,
 				(mr->bitrate & 1 ? ".5" : "  "));
-- 
1.8.1.1