[PATCH 0/6] Improvement to initial mesh metric

[PATCH 0/6] Improvement to initial mesh metric

[Jason Abele]

I am submitting this patch set on behalf of the cozybit team after
testing them with the wireless-testing tag master-2012-06-06

The first patch was previously submitted by Timo Lindhorst and adds
important features to hwsim.

The remaining patches add a feature to initialize the link rate metric
with a guess based off of RSSI when insufficient traffic has passed to
allow actual calculation of the link rate.

Thanks
Jason


Javier Cardona (4):
  mac80211: Remove unused variable
  mac80211: Keep tx rate averages for mesh peers for better metric
    calculation.
  mac80211: Rename stainfo variable for the more common sta
  mac80211: Change rssi_get_rate to interpolated data rates.

Thomas Pedersen (1):
  mac80211: Use signal strength as a proxy for expected datarate.

Timo Lindhorst (1):
  mac80211_hwsim: Report rate info in tx status

 drivers/net/wireless/mac80211_hwsim.c |   21 +++++++
 net/mac80211/mesh_hwmp.c              |   99 +++++++++++++++++++++++++++------
 net/mac80211/sta_info.c               |    1 +
 net/mac80211/sta_info.h               |    1 +
 4 files changed, 106 insertions(+), 16 deletions(-)

-- 
1.7.9.5

[PATCH 1/6] mac80211_hwsim: Report rate info in tx status

[Jason Abele]

From: Timo Lindhorst <tlnd@online.de>

Assuming an ideal channel, always the first transmission is considered
successful if an ACK is received. If no ACK is received, the
rates/attempts are reported as set by the rate control.

Signed-off-by: Timo Lindhorst <tlnd@online.de>
---
 drivers/net/wireless/mac80211_hwsim.c |   21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/drivers/net/wireless/mac80211_hwsim.c b/drivers/net/wireless/mac80211_hwsim.c
index 4c9336c..52ba3e6 100644
--- a/drivers/net/wireless/mac80211_hwsim.c
+++ b/drivers/net/wireless/mac80211_hwsim.c
@@ -715,6 +715,14 @@ static void mac80211_hwsim_tx(struct ieee80211_hw *hw, struct sk_buff *skb)
 	bool ack;
 	struct ieee80211_tx_info *txi;
 	u32 _pid;
+	u8 tx_count[IEEE80211_TX_MAX_RATES];
+	int i;
+	struct ieee80211_mgmt *mgmt = (struct ieee80211_mgmt *) skb->data;
+	struct mac80211_hwsim_data *data = hw->priv;
+
+	if (ieee80211_is_beacon(mgmt->frame_control) ||
+	    ieee80211_is_probe_resp(mgmt->frame_control))
+		mgmt->u.beacon.timestamp = __mac80211_hwsim_get_tsf(data);
 
 	mac80211_hwsim_monitor_rx(hw, skb);
 
@@ -745,6 +753,10 @@ static void mac80211_hwsim_tx(struct ieee80211_hw *hw, struct sk_buff *skb)
 	if (txi->control.sta)
 		hwsim_check_sta_magic(txi->control.sta);
 
+	if (!ack)
+		for (i = 0; i < IEEE80211_TX_MAX_RATES; i++)
+			tx_count[i] = txi->control.rates[i].count;
+
 	ieee80211_tx_info_clear_status(txi);
 
 	/* frame was transmitted at most favorable rate at first attempt */
@@ -753,6 +765,15 @@ static void mac80211_hwsim_tx(struct ieee80211_hw *hw, struct sk_buff *skb)
 
 	if (!(txi->flags & IEEE80211_TX_CTL_NO_ACK) && ack)
 		txi->flags |= IEEE80211_TX_STAT_ACK;
+
+	if (ack) {
+		txi->status.rates[0].count = 1;
+		txi->status.rates[1].idx = -1;
+	} else {
+		for (i = 0; i < IEEE80211_TX_MAX_RATES; i++)
+			txi->control.rates[i].count = tx_count[i];
+	}
+
 	ieee80211_tx_status_irqsafe(hw, skb);
 }
 
-- 
1.7.9.5

[PATCH 2/6] mac80211: Remove unused variable

[Jason Abele]

From: Javier Cardona <javier@cozybit.com>

Signed-off-by: Javier Cardona <javier@cozybit.com>
---
 net/mac80211/mesh_hwmp.c |    3 ---
 1 file changed, 3 deletions(-)

diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
index fa7c580..acbd1ad 100644
--- a/net/mac80211/mesh_hwmp.c
+++ b/net/mac80211/mesh_hwmp.c
@@ -323,7 +323,6 @@ void ieee80211s_update_metric(struct ieee80211_local *local,
 static u32 airtime_link_metric_get(struct ieee80211_local *local,
 				   struct sta_info *sta)
 {
-	struct ieee80211_supported_band *sband;
 	struct rate_info rinfo;
 	/* This should be adjusted for each device */
 	int device_constant = 1 << ARITH_SHIFT;
@@ -333,8 +332,6 @@ static u32 airtime_link_metric_get(struct ieee80211_local *local,
 	u32 tx_time, estimated_retx;
 	u64 result;
 
-	sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
-
 	if (sta->fail_avg >= 100)
 		return MAX_METRIC;
 
-- 
1.7.9.5

[PATCH 3/6] mac80211: Keep tx rate averages for mesh peers for better metric calculation.

[Jason Abele]

From: Javier Cardona <javier@cozybit.com>

The mesh metric is computed every time it was requested by the path
selection framework.  At that time only the last_tx_rate was taken into
account when computing the metric.  This last frame may not reflect the
average data rate that was possible ver that peer link (it could be a
management frame, a rate control probe, or other outlier).

This patch maintains an average tx rate for each peer link which is used
in metric calculation.

Signed-off-by: Javier Cardona <javier@cozybit.com>
---
 net/mac80211/mesh_hwmp.c |   24 +++++++++++++++---------
 net/mac80211/sta_info.c  |    1 +
 net/mac80211/sta_info.h  |    1 +
 3 files changed, 17 insertions(+), 9 deletions(-)

diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
index acbd1ad..8fb3e59 100644
--- a/net/mac80211/mesh_hwmp.c
+++ b/net/mac80211/mesh_hwmp.c
@@ -307,7 +307,9 @@ void ieee80211s_update_metric(struct ieee80211_local *local,
 {
 	struct ieee80211_tx_info *txinfo = IEEE80211_SKB_CB(skb);
 	struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
+	struct rate_info rinfo;
 	int failed;
+	int rate;
 
 	if (!ieee80211_is_data(hdr->frame_control))
 		return;
@@ -318,36 +320,40 @@ void ieee80211s_update_metric(struct ieee80211_local *local,
 	stainfo->fail_avg = ((80 * stainfo->fail_avg + 5) / 100 + 20 * failed);
 	if (stainfo->fail_avg > 95)
 		mesh_plink_broken(stainfo);
+
+	sta_set_rate_info_tx(stainfo, &stainfo->last_tx_rate, &rinfo);
+	rate = cfg80211_calculate_bitrate(&rinfo);
+	if (WARN_ON(!rate))
+		return;
+
+	ewma_add(&stainfo->avg_rate, rate);
+	return;
 }
 
 static u32 airtime_link_metric_get(struct ieee80211_local *local,
 				   struct sta_info *sta)
 {
-	struct rate_info rinfo;
 	/* This should be adjusted for each device */
 	int device_constant = 1 << ARITH_SHIFT;
 	int test_frame_len = TEST_FRAME_LEN << ARITH_SHIFT;
 	int s_unit = 1 << ARITH_SHIFT;
-	int rate, err;
 	u32 tx_time, estimated_retx;
 	u64 result;
+	int rate;
+	int err = (sta->fail_avg << ARITH_SHIFT) / 100;
 
 	if (sta->fail_avg >= 100)
 		return MAX_METRIC;
 
-	sta_set_rate_info_tx(sta, &sta->last_tx_rate, &rinfo);
-	rate = cfg80211_calculate_bitrate(&rinfo);
-	if (WARN_ON(!rate))
-		return MAX_METRIC;
-
-	err = (sta->fail_avg << ARITH_SHIFT) / 100;
+	/* If not enough values accumulated in rate average, assume 1 Mbps */
+	rate = max(ewma_read(&sta->avg_rate), 10UL);
 
 	/* bitrate is in units of 100 Kbps, while we need rate in units of
 	 * 1Mbps. This will be corrected on tx_time computation.
 	 */
 	tx_time = (device_constant + 10 * test_frame_len / rate);
 	estimated_retx = ((1 << (2 * ARITH_SHIFT)) / (s_unit - err));
-	result = (tx_time * estimated_retx) >> (2 * ARITH_SHIFT) ;
+	result = (tx_time * estimated_retx) >> (2 * ARITH_SHIFT);
 	return (u32)result;
 }
 
diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
index 77dcf2f..ddbec7b 100644
--- a/net/mac80211/sta_info.c
+++ b/net/mac80211/sta_info.c
@@ -256,6 +256,7 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
 	do_posix_clock_monotonic_gettime(&uptime);
 	sta->last_connected = uptime.tv_sec;
 	ewma_init(&sta->avg_signal, 1024, 8);
+	ewma_init(&sta->avg_rate, 1, 32);
 
 	if (sta_prepare_rate_control(local, sta, gfp)) {
 		kfree(sta);
diff --git a/net/mac80211/sta_info.h b/net/mac80211/sta_info.h
index 3bb24a1..0bf888e 100644
--- a/net/mac80211/sta_info.h
+++ b/net/mac80211/sta_info.h
@@ -330,6 +330,7 @@ struct sta_info {
 	unsigned long tx_retry_failed, tx_retry_count;
 	/* moving percentage of failed MSDUs */
 	unsigned int fail_avg;
+	struct ewma avg_rate;
 
 	/* Updated from TX path only, no locking requirements */
 	unsigned long tx_packets;
-- 
1.7.9.5

[PATCH 4/6] mac80211: Rename stainfo variable for the more common sta

[Jason Abele]

From: Javier Cardona <javier@cozybit.com>

Signed-off-by: Javier Cardona <javier@cozybit.com>
---
 net/mac80211/mesh_hwmp.c |   12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
index 8fb3e59..22b327a 100644
--- a/net/mac80211/mesh_hwmp.c
+++ b/net/mac80211/mesh_hwmp.c
@@ -303,7 +303,7 @@ int mesh_path_error_tx(u8 ttl, u8 *target, __le32 target_sn,
 }
 
 void ieee80211s_update_metric(struct ieee80211_local *local,
-		struct sta_info *stainfo, struct sk_buff *skb)
+		struct sta_info *sta, struct sk_buff *skb)
 {
 	struct ieee80211_tx_info *txinfo = IEEE80211_SKB_CB(skb);
 	struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
@@ -317,16 +317,16 @@ void ieee80211s_update_metric(struct ieee80211_local *local,
 	failed = !(txinfo->flags & IEEE80211_TX_STAT_ACK);
 
 	/* moving average, scaled to 100 */
-	stainfo->fail_avg = ((80 * stainfo->fail_avg + 5) / 100 + 20 * failed);
-	if (stainfo->fail_avg > 95)
-		mesh_plink_broken(stainfo);
+	sta->fail_avg = ((80 * sta->fail_avg + 5) / 100 + 20 * failed);
+	if (sta->fail_avg > 95)
+		mesh_plink_broken(sta);
 
-	sta_set_rate_info_tx(stainfo, &stainfo->last_tx_rate, &rinfo);
+	sta_set_rate_info_tx(sta, &sta->last_tx_rate, &rinfo);
 	rate = cfg80211_calculate_bitrate(&rinfo);
 	if (WARN_ON(!rate))
 		return;
 
-	ewma_add(&stainfo->avg_rate, rate);
+	ewma_add(&sta->avg_rate, rate);
 	return;
 }
 
-- 
1.7.9.5

[PATCH 5/6] mac80211: Use signal strength as a proxy for expected datarate.

[Jason Abele]

From: Thomas Pedersen <thomas@cozybit.com>

When establishing mesh paths with new stations, there is no historic
datarate information to compute the airtime link metric.  Up until now
we were just using a poor initial metric.  A better approach is to
use the signal strength as an indicator of how good the new link will
be.  Once traffic is exchanged with the station, the average datarate is
computed and the signal strength is not used anymore.

Signed-off-by: Javier Cardona <javier@cozybit.com>
Signed-off-by: Thomas Pedersen <thomas@cozybit.com>
Reviewed-by: Jason Abele <jason@cozybit.com>
---
 net/mac80211/mesh_hwmp.c |   72 ++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 70 insertions(+), 2 deletions(-)

diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
index 22b327a..bb32203 100644
--- a/net/mac80211/mesh_hwmp.c
+++ b/net/mac80211/mesh_hwmp.c
@@ -330,6 +330,71 @@ void ieee80211s_update_metric(struct ieee80211_local *local,
 	return;
 }
 
+/* estimate link rate as a function of last rssi for sta */
+static unsigned int rssi_get_rate(struct sta_info *sta)
+{
+	struct ieee80211_sub_if_data *sdata = sta->sdata;
+	/* XXX: oper_channel is moving to sdata upstream */
+	enum ieee80211_band band = sta->local->oper_channel->band;
+	struct ieee80211_sta_ht_cap *ht_cap = &sta->sta.ht_cap;
+	struct rate_info rinfo;
+	int i, ridx, ci = 0;
+	int rssi, rate;
+	u32 cidx[IEEE80211_MAX_SUPP_RATES];
+
+	if (sta->last_signal >= 0)
+		return 0;
+
+	memset(&rinfo, sizeof(rinfo), 0);
+
+	/* make rates contiguous */
+	for (i = 0; i < IEEE80211_MAX_SUPP_RATES; i++) {
+		if (ht_cap->ht_supported &&
+		    !(ht_cap->mcs.rx_mask[i / 8] & (i % 8)))
+			continue;
+
+		if (!(sta->sta.supp_rates[band] & BIT(i)))
+			continue;
+
+		cidx[ci++] = i;
+	}
+
+	/* map rssi in range 20 - 70 to rates 32 - 0 */
+#define RSSI_OFF 20
+#define RSSI_MAX 50
+	rssi = abs(sta->last_signal) - RSSI_OFF;
+	rssi = max(rssi, 0);
+	rssi = min(rssi, RSSI_MAX);
+	/* invert rssi against ci and get the supported nth rate */
+	/* TODO: make this non-linear */
+	ridx = cidx[min((int)(ci * (1 - ((float) rssi / RSSI_MAX))), ci)];
+
+	if (ht_cap->ht_supported) {
+		rinfo.flags |= RATE_INFO_FLAGS_MCS;
+		rinfo.flags |= (sta->sta.ht_cap.cap &
+				IEEE80211_HT_CAP_SUP_WIDTH_20_40) ?
+					RATE_INFO_FLAGS_40_MHZ_WIDTH :
+					0;
+		rinfo.flags |= (sta->sta.ht_cap.cap &
+				(IEEE80211_HT_CAP_SGI_20 |
+				 IEEE80211_HT_CAP_SGI_40)) ?
+						RATE_INFO_FLAGS_SHORT_GI :
+						0;
+		rinfo.mcs = ridx;
+	} else {
+		struct ieee80211_supported_band *sband;
+		sband = sta->local->hw.wiphy->bands[band];
+		rinfo.legacy = sband->bitrates[ridx].bitrate;
+	}
+
+	rate = cfg80211_calculate_bitrate(&rinfo);
+	if (WARN_ON(!rate))
+		rate = 10;
+	mhwmp_dbg("est. %d Mbps for %pM with rssi %d\n",
+		  rate/10, sta->sta.addr, sta->last_signal);
+	return rate;
+}
+
 static u32 airtime_link_metric_get(struct ieee80211_local *local,
 				   struct sta_info *sta)
 {
@@ -345,8 +410,11 @@ static u32 airtime_link_metric_get(struct ieee80211_local *local,
 	if (sta->fail_avg >= 100)
 		return MAX_METRIC;
 
-	/* If not enough values accumulated in rate average, assume 1 Mbps */
-	rate = max(ewma_read(&sta->avg_rate), 10UL);
+	if (sta->tx_packets > 100)
+		rate = max(ewma_read(&sta->avg_rate), 10UL);
+	else
+		/* Not enough traffic sent, use rx signal strengh as proxy */
+		rate = rssi_get_rate(sta);
 
 	/* bitrate is in units of 100 Kbps, while we need rate in units of
 	 * 1Mbps. This will be corrected on tx_time computation.
-- 
1.7.9.5

[PATCH 6/6] mac80211: Change rssi_get_rate to interpolated data rates.

[Jason Abele]

From: Javier Cardona <javier@cozybit.com>

Signed-off-by: Javier Cardona <javier@cozybit.com>
Reviewed-by: Jason Abele <jason@cozybit.com>
---
 net/mac80211/mesh_hwmp.c |   58 +++++++++++++++++++++-------------------------
 1 file changed, 27 insertions(+), 31 deletions(-)

diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
index bb32203..86fc9e5 100644
--- a/net/mac80211/mesh_hwmp.c
+++ b/net/mac80211/mesh_hwmp.c
@@ -338,38 +338,20 @@ static unsigned int rssi_get_rate(struct sta_info *sta)
 	enum ieee80211_band band = sta->local->oper_channel->band;
 	struct ieee80211_sta_ht_cap *ht_cap = &sta->sta.ht_cap;
 	struct rate_info rinfo;
-	int i, ridx, ci = 0;
-	int rssi, rate;
-	u32 cidx[IEEE80211_MAX_SUPP_RATES];
+	int i, rssi, rate, rate_max, rate_min = 10, maxidx = 0;
+	const int rssi_min = -100;
+	const int rssi_max = -20;
 
 	if (sta->last_signal >= 0)
-		return 0;
+		return rate_min;
 
 	memset(&rinfo, sizeof(rinfo), 0);
 
-	/* make rates contiguous */
-	for (i = 0; i < IEEE80211_MAX_SUPP_RATES; i++) {
-		if (ht_cap->ht_supported &&
-		    !(ht_cap->mcs.rx_mask[i / 8] & (i % 8)))
-			continue;
-
-		if (!(sta->sta.supp_rates[band] & BIT(i)))
-			continue;
-
-		cidx[ci++] = i;
-	}
-
-	/* map rssi in range 20 - 70 to rates 32 - 0 */
-#define RSSI_OFF 20
-#define RSSI_MAX 50
-	rssi = abs(sta->last_signal) - RSSI_OFF;
-	rssi = max(rssi, 0);
-	rssi = min(rssi, RSSI_MAX);
-	/* invert rssi against ci and get the supported nth rate */
-	/* TODO: make this non-linear */
-	ridx = cidx[min((int)(ci * (1 - ((float) rssi / RSSI_MAX))), ci)];
-
 	if (ht_cap->ht_supported) {
+		for (i = 0; i < IEEE80211_HT_MCS_MASK_LEN; i++) {
+			if (ht_cap->mcs.rx_mask[i])
+				maxidx = i*8 + fls(ht_cap->mcs.rx_mask[i]) - 1;
+		}
 		rinfo.flags |= RATE_INFO_FLAGS_MCS;
 		rinfo.flags |= (sta->sta.ht_cap.cap &
 				IEEE80211_HT_CAP_SUP_WIDTH_20_40) ?
@@ -380,18 +362,32 @@ static unsigned int rssi_get_rate(struct sta_info *sta)
 				 IEEE80211_HT_CAP_SGI_40)) ?
 						RATE_INFO_FLAGS_SHORT_GI :
 						0;
-		rinfo.mcs = ridx;
+		rinfo.mcs = maxidx;
 	} else {
 		struct ieee80211_supported_band *sband;
+
+		maxidx = fls(sta->sta.supp_rates[band]) - 1;
+		if (WARN_ON(maxidx < 0))
+			return rate_min;
 		sband = sta->local->hw.wiphy->bands[band];
-		rinfo.legacy = sband->bitrates[ridx].bitrate;
+		rinfo.legacy = sband->bitrates[maxidx].bitrate;
 	}
 
-	rate = cfg80211_calculate_bitrate(&rinfo);
+	rate_max = cfg80211_calculate_bitrate(&rinfo);
+
+	rssi = max(rssi_min, sta->last_signal);
+	rssi = min(rssi_max, rssi);
+
+	rate = ((rssi - rssi_min) * rate_max +
+		(rssi_max - rssi) * rate_min) /
+		(rssi_max - rssi_min);
+
 	if (WARN_ON(!rate))
-		rate = 10;
-	mhwmp_dbg("est. %d Mbps for %pM with rssi %d\n",
+		rate = rate_min;
+
+	mhwmp_dbg("\nest. %d Mbps for %pM with rssi %d\n",
 		  rate/10, sta->sta.addr, sta->last_signal);
+
 	return rate;
 }
 
-- 
1.7.9.5

Re: [PATCH 0/6] Improvement to initial mesh metric

[Jason Abele]

On Wed, Jun 06, 2012 at 03:48:46PM -0700, Jason Abele wrote:
> I am submitting this patch set on behalf of the cozybit team after
> testing them with the wireless-testing tag master-2012-06-06
> 
> The first patch was previously submitted by Timo Lindhorst and adds
> important features to hwsim.
> 
> The remaining patches add a feature to initialize the link rate metric
> with a guess based off of RSSI when insufficient traffic has passed to
> allow actual calculation of the link rate.

Actually, let me squash 5 and 6 real quick, my apologies for sending
this a bit too quick

v2 patch set coming soon

Jason

> 
> 
> Javier Cardona (4):
>   mac80211: Remove unused variable
>   mac80211: Keep tx rate averages for mesh peers for better metric
>     calculation.
>   mac80211: Rename stainfo variable for the more common sta
>   mac80211: Change rssi_get_rate to interpolated data rates.
> 
> Thomas Pedersen (1):
>   mac80211: Use signal strength as a proxy for expected datarate.
> 
> Timo Lindhorst (1):
>   mac80211_hwsim: Report rate info in tx status
> 
>  drivers/net/wireless/mac80211_hwsim.c |   21 +++++++
>  net/mac80211/mesh_hwmp.c              |   99 +++++++++++++++++++++++++++------
>  net/mac80211/sta_info.c               |    1 +
>  net/mac80211/sta_info.h               |    1 +
>  4 files changed, 106 insertions(+), 16 deletions(-)
> 
> -- 
> 1.7.9.5
>