Implement support for dynamic RTS threshold in MiRA.

Improves throughput and latency on 11n networks.
Tested by myself, jmc@, jcs@, phessler@, benno@

5 files changed, 145 insertions, 13 deletions

diff --git a/sys/dev/ic/ar5008.c b/sys/dev/ic/ar5008.c
index 7cf96bf074b..1890ab7d389 100644
--- a/sys/dev/ic/ar5008.c
+++ b/sys/dev/ic/ar5008.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ar5008.c,v 1.48 2019/02/19 10:17:09 stsp Exp $	*/
+/*	$OpenBSD: ar5008.c,v 1.49 2019/02/27 04:10:35 stsp Exp $	*/
 
 /*-
  * Copyright (c) 2009 Damien Bergamini <damien.bergamini@free.fr>
@@ -1514,11 +1514,16 @@ ar5008_tx(struct athn_softc *sc, struct mbuf *m, struct ieee80211_node *ni,
 	if (!IEEE80211_IS_MULTICAST(wh->i_addr1) &&
 	    (wh->i_fc[0] & IEEE80211_FC0_TYPE_MASK) ==
 	    IEEE80211_FC0_TYPE_DATA) {
+		int rtsthres = ic->ic_rtsthreshold;
 		enum ieee80211_htprot htprot;
-		
+
+		if (ni->ni_flags & IEEE80211_NODE_HT)
+			rtsthres = ieee80211_mira_get_rts_threshold(&an->mn,
+			    ic, ni, totlen);
 		htprot = (ic->ic_bss->ni_htop1 & IEEE80211_HTOP1_PROT_MASK);
+
 		/* NB: Group frames are sent using CCK in 802.11b/g. */
-		if (totlen > ic->ic_rtsthreshold) {
+		if (totlen > rtsthres) {
 			ds->ds_ctl0 |= AR_TXC0_RTS_ENABLE;
 		} else if (((ic->ic_flags & IEEE80211_F_USEPROT) &&
 		    athn_rates[ridx[0]].phy == IEEE80211_T_OFDM) ||
diff --git a/sys/dev/pci/if_iwm.c b/sys/dev/pci/if_iwm.c
index 7d7f0697a2b..bfa9a7bf47a 100644
--- a/sys/dev/pci/if_iwm.c
+++ b/sys/dev/pci/if_iwm.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_iwm.c,v 1.235 2019/02/24 09:37:18 stsp Exp $	*/
+/*	$OpenBSD: if_iwm.c,v 1.236 2019/02/27 04:10:38 stsp Exp $	*/
 
 /*
  * Copyright (c) 2014, 2016 genua gmbh <info@genua.de>
@@ -4216,7 +4216,7 @@ iwm_tx(struct iwm_softc *sc, struct mbuf *m, struct ieee80211_node *ni, int ac)
 	bus_dma_segment_t *seg;
 	uint8_t tid, type;
 	int i, totlen, err, pad;
-	int hdrlen2;
+	int hdrlen2, rtsthres = ic->ic_rtsthreshold;
 
 	wh = mtod(m, struct ieee80211_frame *);
 	hdrlen = ieee80211_get_hdrlen(wh);
@@ -4292,9 +4292,13 @@ iwm_tx(struct iwm_softc *sc, struct mbuf *m, struct ieee80211_node *ni, int ac)
 		flags |= IWM_TX_CMD_FLG_ACK;
 	}
 
+	if (ni->ni_flags & IEEE80211_NODE_HT)
+		rtsthres = ieee80211_mira_get_rts_threshold(&in->in_mn, ic, ni,
+		    totlen + IEEE80211_CRC_LEN);
+
 	if (type == IEEE80211_FC0_TYPE_DATA &&
 	    !IEEE80211_IS_MULTICAST(wh->i_addr1) &&
-	    (totlen + IEEE80211_CRC_LEN > ic->ic_rtsthreshold ||
+	    (totlen + IEEE80211_CRC_LEN > rtsthres ||
 	    (ic->ic_flags & IEEE80211_F_USEPROT)))
 		flags |= IWM_TX_CMD_FLG_PROT_REQUIRE;
 
diff --git a/sys/dev/pci/if_iwn.c b/sys/dev/pci/if_iwn.c
index 4574f5a5261..c7bc1ddd8dc 100644
--- a/sys/dev/pci/if_iwn.c
+++ b/sys/dev/pci/if_iwn.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_iwn.c,v 1.208 2019/02/27 01:09:06 stsp Exp $	*/
+/*	$OpenBSD: if_iwn.c,v 1.209 2019/02/27 04:10:38 stsp Exp $	*/
 
 /*-
  * Copyright (c) 2007-2010 Damien Bergamini <damien.bergamini@free.fr>
@@ -3068,8 +3068,13 @@ iwn_tx(struct iwn_softc *sc, struct mbuf *m, struct ieee80211_node *ni)
 
 	/* Check if frame must be protected using RTS/CTS or CTS-to-self. */
 	if (!IEEE80211_IS_MULTICAST(wh->i_addr1)) {
+		int rtsthres = ic->ic_rtsthreshold;
+		if (ni->ni_flags & IEEE80211_NODE_HT)
+			rtsthres = ieee80211_mira_get_rts_threshold(&wn->mn,
+			    ic, ni, totlen + IEEE80211_CRC_LEN);
+
 		/* NB: Group frames are sent using CCK in 802.11b/g/n (2GHz). */
-		if (totlen + IEEE80211_CRC_LEN > ic->ic_rtsthreshold) {
+		if (totlen + IEEE80211_CRC_LEN > rtsthres) {
 			flags |= IWN_TX_NEED_RTS;
 		} else if ((ic->ic_flags & IEEE80211_F_USEPROT) &&
 		    ridx >= IWN_RIDX_OFDM6) {
diff --git a/sys/net80211/ieee80211_mira.c b/sys/net80211/ieee80211_mira.c
index 4edd26a5fde..0d14daff4d1 100644
--- a/sys/net80211/ieee80211_mira.c
+++ b/sys/net80211/ieee80211_mira.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ieee80211_mira.c,v 1.13 2019/01/23 10:08:49 stsp Exp $	*/
+/*	$OpenBSD: ieee80211_mira.c,v 1.14 2019/02/27 04:10:40 stsp Exp $	*/
 
 /*
  * Copyright (c) 2016 Stefan Sperling <stsp@openbsd.org>
@@ -85,6 +85,9 @@ int	ieee80211_mira_valid_tx_mcs(struct ieee80211com *, int);
 uint32_t ieee80211_mira_valid_rates(struct ieee80211com *,
 	    struct ieee80211_node *);
 uint32_t ieee80211_mira_mcs_below(struct ieee80211_mira_node *, int, int);
+void	ieee80211_mira_set_rts_threshold(struct ieee80211_mira_node *,
+	    struct ieee80211com *, struct ieee80211_node *);
+void	ieee80211_mira_reset_collision_stats(struct ieee80211_mira_node *);
 
 /* We use fixed point arithmetic with 64 bit integers. */
 #define MIRA_FP_SHIFT	21
@@ -309,7 +312,7 @@ ieee80211_mira_ack_rate(struct ieee80211_node *ni)
 {
 	/* 
 	 * Assume the ACK was sent at a mandatory ERP OFDM rate.
-	 * In the worst case, the firmware has retried at non-HT rates,
+	 * In the worst case, the driver has retried at non-HT rates,
 	 * so for MCS 0 assume we didn't actually send an OFDM frame
 	 * and ACKs arrived at a basic rate.
 	 */
@@ -347,11 +350,12 @@ ieee80211_mira_toverhead(struct ieee80211_mira_node *mn,
 		(ic->ic_htcaps & IEEE80211_HTCAP_CBW20_40))
 		rts = 1;
 	else
-		rts = (mn->ampdu_size > ic->ic_rtsthreshold);
+		rts = (mn->ampdu_size > ieee80211_mira_get_rts_threshold(mn,
+		    ic, ni, mn->ampdu_size));
 
 	if (rts) {
 		/* Assume RTS/CTS were sent at a basic rate. */
-		rate = ieee80211_mira_best_basic_rate(ni);
+		rate = ieee80211_min_basic_rate(ic);
 		overhead += ieee80211_mira_legacy_txtime(MIRA_RTSLEN, rate, ic);
 		overhead += ieee80211_mira_legacy_txtime(MIRA_CTSLEN, rate, ic);
 	}
@@ -723,6 +727,7 @@ ieee80211_mira_probe_done(struct ieee80211_mira_node *mn)
 {
 	ieee80211_mira_cancel_timeouts(mn);
 	ieee80211_mira_reset_driver_stats(mn);
+	ieee80211_mira_reset_collision_stats(mn);
 	mn->probing = IEEE80211_MIRA_NOT_PROBING;
 	mn->probed_rates = 0;
 	mn->candidate_rates = 0;
@@ -1021,6 +1026,103 @@ ieee80211_mira_mcs_below(struct ieee80211_mira_node *mn, int mcs, int sgi)
 	return mcs_mask;
 }
 
+/*
+ * Constants involved in detecting suspected frame collisions.
+ * See section 5.2 of MiRA paper
+ */
+#define MIRA_COLLISION_LOSS_PERCENTAGE	10	/* from MiRA paper */
+#define MIRA_COLLISION_DETECTED		3	/* from MiRA paper */
+
+/*
+ * XXX The paper's algorithm assumes aggregated frames. This is particularly
+ * important for the detection of consecutive frame collisions which indicate
+ * high competition for air time. Because we do not yet support Tx aggregation,
+ * we run the algorithm over the result of several frames instead.
+ * We also aggregate retries across all frames and act upon a percentage of
+ * retried frames, rather than acting on retries seen for one aggregated frame.
+ *
+ * The collision window size (number of frames sent) needs to be short to
+ * ensure our detection of consecutive collisions remains somewhat accurate.
+ * We really have no idea how much time passes between frames in the window!
+ * The good news is that users will only care about collision detection during
+ * a transmit burst anyway, and we have this case more or less covered.
+ */
+#define MIRA_COLLISION_MIN_FRAMES	6	/* XXX magic number */
+#define MIRA_COLLISION_RETRY_PERCENTAGE	60	/* XXX magic number */
+
+/* Set RTS threshold based on suspected collision from other STAs. */
+void
+ieee80211_mira_set_rts_threshold(struct ieee80211_mira_node *mn,
+    struct ieee80211com *ic, struct ieee80211_node *ni)
+{
+	uint16_t rtsthreshold = mn->rts_threshold;
+	uint32_t loss, retry;
+
+	/* Update collision window stats. */
+	mn->ifwnd_frames += mn->frames;
+	mn->ifwnd_retries += mn->retries;
+	mn->ifwnd_txfail += mn->txfail;
+	if (mn->ifwnd_frames < MIRA_COLLISION_MIN_FRAMES)
+		return; /* not enough frames yet */
+
+	/* Check whether the loss pattern indicates frame collisions. */
+	loss = (mn->ifwnd_txfail * 100) / mn->ifwnd_frames;
+	retry = (mn->ifwnd_retries * 100) / mn->ifwnd_frames;
+	if (retry > MIRA_COLLISION_RETRY_PERCENTAGE &&
+	    loss < MIRA_COLLISION_LOSS_PERCENTAGE) {
+		if (mn->ifwnd == 0) {
+			/* First frame collision confirmed. */
+			mn->ifwnd = MIRA_COLLISION_DETECTED;
+		} else if (mn->ifwnd == MIRA_COLLISION_DETECTED) {
+			/* Successive frame collision confirmed. Use RTS. */
+			rtsthreshold = IEEE80211_RTS_DEFAULT;
+		}
+	} else {
+		if (mn->ifwnd > 0)
+			mn->ifwnd--;
+		if (mn->ifwnd == 0)
+			rtsthreshold = IEEE80211_RTS_MAX;
+	}
+
+	mn->rts_threshold = rtsthreshold;
+	ieee80211_mira_reset_collision_stats(mn);
+}
+
+int
+ieee80211_mira_get_rts_threshold(struct ieee80211_mira_node *mn,
+    struct ieee80211com *ic, struct ieee80211_node *ni, size_t framelen)
+{
+	int rtsrate = ieee80211_min_basic_rate(ic);
+	uint64_t txtime, rtsoverhead;
+	/* Magic number from MiRA paper ("cost/benefit ratio"). */
+	static const uint64_t k = MIRA_FP_1 + (MIRA_FP_1 / 2); /* 1.5 */
+
+	if (mn->probing || mn->rts_threshold >= IEEE80211_RTS_MAX)
+		return IEEE80211_RTS_MAX;
+
+	/* Use RTS only if potential gains outweigh overhead. */
+	txtime = ieee80211_mira_ht_txtime(framelen, ni->ni_txmcs,
+	    IEEE80211_IS_CHAN_2GHZ(ni->ni_chan),
+	    (ni->ni_flags & IEEE80211_NODE_HT_SGI20) ? 1 : 0);
+	rtsoverhead = ieee80211_mira_legacy_txtime(MIRA_RTSLEN, rtsrate, ic);
+	rtsoverhead += ieee80211_mira_legacy_txtime(MIRA_CTSLEN, rtsrate, ic);
+	/* convert to fixed-point */
+	txtime <<= MIRA_FP_SHIFT;
+	rtsoverhead <<= MIRA_FP_SHIFT;
+	if (txtime >= MIRA_FP_MUL(k, rtsoverhead))
+		return mn->rts_threshold;
+
+	return IEEE80211_RTS_MAX;
+}
+
+void
+ieee80211_mira_reset_collision_stats(struct ieee80211_mira_node *mn)
+{
+	mn->ifwnd_frames = 0;
+	mn->ifwnd_retries = 0;
+	mn->ifwnd_txfail = 0;
+}
+
 void
 ieee80211_mira_choose(struct ieee80211_mira_node *mn, struct ieee80211com *ic,
     struct ieee80211_node *ni)
@@ -1065,6 +1167,7 @@ ieee80211_mira_choose(struct ieee80211_mira_node *mn, struct ieee80211com *ic,
 		splx(s);
 		return;
 	} else {
+		ieee80211_mira_set_rts_threshold(mn, ic, ni);
 		ieee80211_mira_reset_driver_stats(mn);
 		ieee80211_mira_schedule_probe_timers(mn, ni);
 	}
@@ -1125,7 +1228,9 @@ ieee80211_mira_node_init(struct ieee80211_mira_node *mn)
 {
 	memset(mn, 0, sizeof(*mn));
 	mn->agglen = 1;
+	mn->rts_threshold = IEEE80211_RTS_MAX;
 	ieee80211_mira_reset_goodput_stats(mn);
+	ieee80211_mira_reset_collision_stats(mn);
 
 	timeout_set(&mn->probe_to[IEEE80211_MIRA_PROBE_TO_UP],
 	    ieee80211_mira_probe_timeout_up, mn);
diff --git a/sys/net80211/ieee80211_mira.h b/sys/net80211/ieee80211_mira.h
index 35ea4193fe7..9e6d5e7c385 100644
--- a/sys/net80211/ieee80211_mira.h
+++ b/sys/net80211/ieee80211_mira.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ieee80211_mira.h,v 1.4 2019/01/23 10:08:49 stsp Exp $	*/
+/*	$OpenBSD: ieee80211_mira.h,v 1.5 2019/02/27 04:10:40 stsp Exp $	*/
 
 /*
  * Copyright (c) 2016 Stefan Sperling <stsp@openbsd.org>
@@ -86,6 +86,15 @@ struct ieee80211_mira_node {
 
 	/* Goodput statistics for each MCS. */
 	struct ieee80211_mira_goodput_stats g[IEEE80211_HT_RATESET_NUM_MCS];
+
+	/* Interference observation window (see MiRA paper section 5.2). */
+	int ifwnd;
+	uint32_t ifwnd_frames;
+	uint32_t ifwnd_retries;
+	uint32_t ifwnd_txfail;
+
+	/* Current RTS threshold for this node. */
+	int rts_threshold;
 };
 
 /* Initialize rate control state. */
@@ -98,4 +107,8 @@ void	ieee80211_mira_choose(struct ieee80211_mira_node *,
 /* Cancel timeouts scheduled by ieee80211_mira_choose(). */
 void	ieee80211_mira_cancel_timeouts(struct ieee80211_mira_node *);
 
+/* Returns RTS threshold to be used for a frame about to be transmitted. */
+int	ieee80211_mira_get_rts_threshold(struct ieee80211_mira_node *,
+    struct ieee80211com *, struct ieee80211_node *, size_t);
+
 #endif /* _NET80211_IEEE80211_MIRA_H_ */