[PATCH 1/8] util: add util_linear_map

[PATCH 1/8] util: add util_linear_map

[James Prestwood]

This has been needed elsewhere but generally shortcuts could be
taken mapping with ranges starting/ending with zero. This is a
more general linear mapping utility to map values between any
two ranges.
---
 src/util.c | 30 ++++++++++++++++++++++++++++++
 src/util.h | 11 +++++++++++
 2 files changed, 41 insertions(+)

diff --git a/src/util.c b/src/util.c
index a4a78fb6..a6ab9d85 100644
--- a/src/util.c
+++ b/src/util.c
@@ -312,6 +312,36 @@ bool util_ip_prefix_tohl(const char *ip, uint8_t *prefix_out,
 	return true;
 }
 
+/*
+ * Linearly maps @value (expected to be within range @a_start and @a_end) to
+ * a new value between @b_start and @b_end.
+ *
+ * Returns: false if
+ *   @value is not between @a_start and @a_end
+ *   @a_start/@a_end or @b_start/@b_end are equal.
+ */
+bool util_linear_map(double value, double a_start, double a_end,
+			double b_start, double b_end, double *mapped_value)
+{
+	/* Check value is within a's range */
+	if (a_start < a_end) {
+		if (value < a_start || value > a_end)
+			return false;
+	} else if (a_start > a_end) {
+		if (value > a_start || value < a_end)
+			return false;
+	} else
+		return false;
+
+	if (b_start == b_end)
+		return false;
+
+	*mapped_value = b_start + (((b_end - b_start) / (a_end - a_start)) *
+					(value - a_start));
+
+	return true;
+}
+
 struct scan_freq_set {
 	uint16_t channels_2ghz;
 	struct l_uintset *channels_5ghz;
diff --git a/src/util.h b/src/util.h
index dafa446d..9f3f0a57 100644
--- a/src/util.h
+++ b/src/util.h
@@ -106,6 +106,17 @@ static inline bool util_ip_subnet_match(uint8_t prefix_len,
 		  ~((1u << (8 - (prefix_len % 8))) - 1));
 }
 
+/*
+ * Linearly maps (interpolates) 'value' from range 'a' to range 'b'
+ *
+ * Fails if:
+ *    - value is not between a and b
+ *    - a_start == a_end
+ *    - b_start == b_end
+ */
+bool util_linear_map(double value, double a_start, double a_end,
+			double b_start, double b_end, double *mapped_value);
+
 typedef void (*scan_freq_set_func_t)(uint32_t freq, void *userdata);
 
 struct scan_freq_set *scan_freq_set_new(void);
-- 
2.34.1

[PATCH 2/8] unit: add linear mapping test

[James Prestwood]

---
 unit/test-util.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)

diff --git a/unit/test-util.c b/unit/test-util.c
index 0bfd1587..214d4819 100644
--- a/unit/test-util.c
+++ b/unit/test-util.c
@@ -184,6 +184,75 @@ static void ip_prefix_test(const void *data)
 	}
 }
 
+struct linear_map_case {
+	double value;
+	double a_start;
+	double a_end;
+	double b_start;
+	double b_end;
+	double expected;
+
+	bool fails : 1;
+};
+
+struct linear_map_case cases[] = {
+	/* Value out of range */
+	{
+		.value = 100,
+		.a_start = 1,
+		.a_end = 3,
+		.b_start = 10,
+		.b_end = 12,
+		.fails = true,
+	},
+	/* Ascending start range */
+	{
+		.value = 1,
+		.a_start = 0,
+		.a_end = 2,
+		.b_start = 10,
+		.b_end = 12,
+		.expected = 11,
+	},
+	/* Descending start range */
+	{
+		.value = 1,
+		.a_start = 2,
+		.a_end = 0,
+		.b_start = 10,
+		.b_end = 12,
+		.expected = 11,
+	},
+	/* Negatives */
+	{
+		.value = -1,
+		.a_start = -2,
+		.a_end = 0,
+		.b_start = 0,
+		.b_end = 2,
+		.expected = 1,
+	},
+};
+
+static void test_linear_map(const void *data)
+{
+	double mapped;
+	unsigned int i;
+
+	for (i = 0; i < L_ARRAY_SIZE(cases); i++) {
+		struct linear_map_case *c = &cases[i];
+		bool ret = util_linear_map(c->value, c->a_start, c->a_end,
+						c->b_start, c->b_end, &mapped);
+		if (c->fails) {
+			assert(ret == false);
+			continue;
+		}
+
+		assert(ret);
+		assert(mapped == c->expected);
+	}
+}
+
 int main(int argc, char *argv[])
 {
 	l_test_init(&argc, &argv);
@@ -192,6 +261,7 @@ int main(int argc, char *argv[])
 	l_test_add("/util/get_domain/", get_domain_test, NULL);
 	l_test_add("/util/get_username/", get_username_test, NULL);
 	l_test_add("/util/ip_prefix/", ip_prefix_test, NULL);
+	l_test_add("/util/test_linear_map", test_linear_map, NULL);
 
 	return l_test_run();
 }
-- 
2.34.1

[PATCH 3/8] util: add util_exponential_decay

[James Prestwood]

This is copied from network.c that uses a static table to lookup
exponential decay values by index (generated from 1/pow(n, 0.3)).
network.c uses this for network ranking but it can be useful for
BSS ranking as well if you need to apply some exponential backoff
to a value.
---
 src/util.c | 28 ++++++++++++++++++++++++++++
 src/util.h |  2 ++
 2 files changed, 30 insertions(+)

diff --git a/src/util.c b/src/util.c
index a6ab9d85..b673b002 100644
--- a/src/util.c
+++ b/src/util.c
@@ -636,3 +636,31 @@ struct scan_freq_set *scan_freq_set_clone(const struct scan_freq_set *set,
 
 	return new;
 }
+
+/* First 64 entries calculated by 1 / pow(n, 0.3) for n >= 1 */
+static const double rankmod_table[] = {
+	1.0000000000, 0.8122523964, 0.7192230933, 0.6597539554,
+	0.6170338627, 0.5841906811, 0.5577898253, 0.5358867313,
+	0.5172818580, 0.5011872336, 0.4870596972, 0.4745102806,
+	0.4632516708, 0.4530661223, 0.4437850034, 0.4352752816,
+	0.4274303178, 0.4201634287, 0.4134032816, 0.4070905315,
+	0.4011753236, 0.3956154062, 0.3903746872, 0.3854221125,
+	0.3807307877, 0.3762772797, 0.3720410580, 0.3680040435,
+	0.3641502401, 0.3604654325, 0.3569369365, 0.3535533906,
+	0.3503045821, 0.3471812999, 0.3441752105, 0.3412787518,
+	0.3384850430, 0.3357878061, 0.3331812996, 0.3306602598,
+	0.3282198502, 0.3258556179, 0.3235634544, 0.3213395618,
+	0.3191804229, 0.3170827751, 0.3150435863, 0.3130600345,
+	0.3111294892, 0.3092494947, 0.3074177553, 0.3056321221,
+	0.3038905808, 0.3021912409, 0.3005323264, 0.2989121662,
+	0.2973291870, 0.2957819051, 0.2942689208, 0.2927889114,
+	0.2913406263, 0.2899228820, 0.2885345572, 0.2871745887,
+};
+
+double util_exponential_decay(unsigned int n)
+{
+	if (n > L_ARRAY_SIZE(rankmod_table))
+		return rankmod_table[L_ARRAY_SIZE(rankmod_table) - 1];
+
+	return rankmod_table[n];
+}
diff --git a/src/util.h b/src/util.h
index 9f3f0a57..8aef2985 100644
--- a/src/util.h
+++ b/src/util.h
@@ -141,4 +141,6 @@ struct scan_freq_set *scan_freq_set_clone(const struct scan_freq_set *set,
 
 DEFINE_CLEANUP_FUNC(scan_freq_set_free);
 
+double util_exponential_decay(unsigned int n);
+
 #endif /* __UTIL_H */
-- 
2.34.1

[PATCH 4/8] network: use util_exponential_decay

[James Prestwood]

---
 src/network.c | 35 ++++-------------------------------
 1 file changed, 4 insertions(+), 31 deletions(-)

diff --git a/src/network.c b/src/network.c
index cd8b0ee9..0a40a6c5 100644
--- a/src/network.c
+++ b/src/network.c
@@ -56,6 +56,7 @@
 #include "src/erp.h"
 #include "src/handshake.h"
 #include "src/band.h"
+#include "src/util.h"
 
 #define SAE_PT_SETTING "SAE-PT-Group%u"
 
@@ -212,31 +213,10 @@ void network_disconnected(struct network *network)
 		station_hide_network(network->station, network);
 }
 
-/* First 64 entries calculated by 1 / pow(n, 0.3) for n >= 1 */
-static const double rankmod_table[] = {
-	1.0000000000, 0.8122523964, 0.7192230933, 0.6597539554,
-	0.6170338627, 0.5841906811, 0.5577898253, 0.5358867313,
-	0.5172818580, 0.5011872336, 0.4870596972, 0.4745102806,
-	0.4632516708, 0.4530661223, 0.4437850034, 0.4352752816,
-	0.4274303178, 0.4201634287, 0.4134032816, 0.4070905315,
-	0.4011753236, 0.3956154062, 0.3903746872, 0.3854221125,
-	0.3807307877, 0.3762772797, 0.3720410580, 0.3680040435,
-	0.3641502401, 0.3604654325, 0.3569369365, 0.3535533906,
-	0.3503045821, 0.3471812999, 0.3441752105, 0.3412787518,
-	0.3384850430, 0.3357878061, 0.3331812996, 0.3306602598,
-	0.3282198502, 0.3258556179, 0.3235634544, 0.3213395618,
-	0.3191804229, 0.3170827751, 0.3150435863, 0.3130600345,
-	0.3111294892, 0.3092494947, 0.3074177553, 0.3056321221,
-	0.3038905808, 0.3021912409, 0.3005323264, 0.2989121662,
-	0.2973291870, 0.2957819051, 0.2942689208, 0.2927889114,
-	0.2913406263, 0.2899228820, 0.2885345572, 0.2871745887,
-};
-
 bool network_rankmod(const struct network *network, double *rankmod)
 {
 	struct network_info *info = network->info;
 	int n;
-	int nmax;
 
 	/*
 	 * Current policy is that only networks successfully connected
@@ -250,12 +230,7 @@ bool network_rankmod(const struct network *network, double *rankmod)
 	if (n < 0)
 		return false;
 
-	nmax = L_ARRAY_SIZE(rankmod_table);
-
-	if (n >= nmax)
-		n = nmax - 1;
-
-	*rankmod = rankmod_table[n];
+	*rankmod = util_exponential_decay(n);
 
 	return true;
 }
@@ -2018,10 +1993,8 @@ void network_rank_update(struct network *network, bool connected)
 
 		L_WARN_ON(n < 0);
 
-		if (n >= (int) L_ARRAY_SIZE(rankmod_table))
-			n = L_ARRAY_SIZE(rankmod_table) - 1;
-
-		network->rank = rankmod_table[n] * best_bss->rank + USHRT_MAX;
+		network->rank =
+			util_exponential_decay(n) * best_bss->rank + USHRT_MAX;
 	} else
 		network->rank = best_bss->rank;
 
-- 
2.34.1

[PATCH 5/8] scan: parse station count from BSS load IE

[James Prestwood]

This will be used in BSS ranking
---
 src/scan.c | 4 ++--
 src/scan.h | 1 +
 2 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/src/scan.c b/src/scan.c
index 2ffbef6d..64de57d2 100644
--- a/src/scan.c
+++ b/src/scan.c
@@ -1343,8 +1343,8 @@ static bool scan_parse_bss_information_elements(struct scan_bss *bss,
 								iter.len + 2);
 			break;
 		case IE_TYPE_BSS_LOAD:
-			if (ie_parse_bss_load(&iter, NULL, &bss->utilization,
-						NULL) < 0)
+			if (ie_parse_bss_load(&iter, &bss->sta_count,
+						&bss->utilization, NULL) < 0)
 				l_warn("Unable to parse BSS Load IE for "
 					MAC, MAC_STR(bss->addr));
 			else
diff --git a/src/scan.h b/src/scan.h
index 50adca7c..4c1ebc21 100644
--- a/src/scan.h
+++ b/src/scan.h
@@ -67,6 +67,7 @@ struct scan_bss {
 	uint8_t ssid[SSID_MAX_SIZE];
 	uint8_t ssid_len;
 	uint8_t utilization;
+	uint16_t sta_count;
 	uint8_t cc[3];
 	uint16_t rank;
 	uint64_t time_stamp;
-- 
2.34.1

[PATCH 6/8] scan: add ranking modifiers for utilization/station count

[James Prestwood]

The utilization rank factor already existed but was very rigid
and only checked a few values. This adds the (optional) ability
to start applying an exponentially decaying factor to both
utilization and station count after some threshold is reached.

This area needs to be re-worked in order to support very highly
loaded networks. If a network either doesn't support client
balancing or does it poorly its left up to the clients to choose
the best BSS possible given all the information available. In
these cases connecting to a highly loaded BSS may fail, or result
in a disconnect soon after connecting. In these cases its likely
better for IWD to choose a slightly lower RSSI/datarate BSS over
the conventionally 'best' BSS in order to aid in distributing
the network load.

The thresholds are currently optional and not enabled by default
but if set they behave as follows:

If the value is above the threshold it is mapped to an integer
between 0 and 30. (using a starting range of <value> - 255).
This integer is then used to index in the exponential decay table
to get a factor between 1 and 0. This factor is then applied to
the rank.

Note that as the value increases above the threshold the rank
will be increasingly effected, as is expected for an exponential
function. These option should be used with care as it may have
unintended consequences, especially with very high load networks.
i.e. you may see IWD roaming to BSS's with much lower signal if
there are high load BSS's nearby.

To maintain the existing behavior if there is no utilization
factor set in main.conf the legacy thresholds/factors will be
used.
---
 src/scan.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 86 insertions(+), 7 deletions(-)

diff --git a/src/scan.c b/src/scan.c
index 64de57d2..aeab6516 100644
--- a/src/scan.c
+++ b/src/scan.c
@@ -56,6 +56,8 @@
 static double RANK_2G_FACTOR;
 static double RANK_5G_FACTOR;
 static double RANK_6G_FACTOR;
+static uint32_t RANK_HIGH_UTILIZATION;
+static uint32_t RANK_HIGH_STATION_COUNT;
 static uint32_t SCAN_MAX_INTERVAL;
 static uint32_t SCAN_INIT_INTERVAL;
 
@@ -1681,10 +1683,77 @@ static struct scan_bss *scan_parse_result(struct l_genl_msg *msg,
 	return bss;
 }
 
-static void scan_bss_compute_rank(struct scan_bss *bss)
+static double scan_legacy_utilization_factor(uint8_t utilization)
 {
 	static const double RANK_HIGH_UTILIZATION_FACTOR = 0.8;
 	static const double RANK_LOW_UTILIZATION_FACTOR = 1.2;
+
+	if (utilization >= 192)
+		return RANK_HIGH_UTILIZATION_FACTOR;
+	else if (utilization <= 63)
+		return RANK_LOW_UTILIZATION_FACTOR;
+
+	return 1.0;
+}
+
+static double scan_get_load_factors(uint8_t utilization, uint16_t sta_count)
+{
+	double n;
+	double factor = 1.0;
+	/*
+	 * The exponential decay table has 64 entries (0 <= n <= 63) which range
+	 * from 1.0 to 0.28. For the utilization and station count factors we
+	 * likely don't want to adjust the rank so drastically (potentially a
+	 * 78% reduction in the worse case) so cap the index at 30 which equates
+	 * to ~64% at the worst case.
+	 */
+	static const uint8_t LOAD_DECAY_OFFSET = 30;
+
+	if (!RANK_HIGH_UTILIZATION) {
+		/*
+		 * To maintain existing behavior, if the utilization factor is
+		 * unset (default) fall back to the static thresholds and
+		 * factor weights.
+		 */
+		factor = scan_legacy_utilization_factor(utilization);
+		goto sta_count;
+	} else if (utilization < RANK_HIGH_UTILIZATION)
+		goto sta_count;
+
+	/* Map the utilization threshold -> 255 to rankmod_table indexes */
+	if (L_WARN_ON(!util_linear_map(utilization, RANK_HIGH_UTILIZATION,
+					255, 0, LOAD_DECAY_OFFSET, &n)))
+		goto sta_count;
+
+	factor = util_exponential_decay(n);
+
+sta_count:
+	if (!RANK_HIGH_STATION_COUNT || sta_count < RANK_HIGH_STATION_COUNT)
+		return factor;
+
+	/*
+	 * The station count is a uint16 so in theory it could be excessively
+	 * large. In practice APs generally can't handle anywhere near this so
+	 * put a cap at 255. If at some time in the future APs begin to handle
+	 * this level of capacity we could increase this.
+	 *
+	 * TODO: A warning is used here to make this visible. If we see cases
+	 * where this is happening we may need to give this another look.
+	 */
+	if (L_WARN_ON(sta_count > 255))
+		sta_count = 255;
+
+	if (L_WARN_ON(!util_linear_map(sta_count, RANK_HIGH_STATION_COUNT,
+					255, 0, LOAD_DECAY_OFFSET, &n)))
+		return factor;
+
+	factor *= util_exponential_decay(n);
+
+	return factor;
+}
+
+static void scan_bss_compute_rank(struct scan_bss *bss)
+{
 	static const double RANK_HIGH_SNR_FACTOR = 1.2;
 	static const double RANK_LOW_SNR_FACTOR = 0.8;
 	double rank;
@@ -1708,12 +1777,8 @@ static void scan_bss_compute_rank(struct scan_bss *bss)
 		rank *= RANK_6G_FACTOR;
 
 	/* Rank loaded APs lower and lightly loaded APs higher */
-	if (bss->have_utilization) {
-		if (bss->utilization >= 192)
-			rank *= RANK_HIGH_UTILIZATION_FACTOR;
-		else if (bss->utilization <= 63)
-			rank *= RANK_LOW_UTILIZATION_FACTOR;
-	}
+	if (bss->have_utilization)
+		rank *= scan_get_load_factors(bss->utilization, bss->sta_count);
 
 	if (bss->have_snr) {
 		if (bss->snr <= 15)
@@ -2599,6 +2664,20 @@ static int scan_init(void)
 	if (SCAN_MAX_INTERVAL > UINT16_MAX)
 		SCAN_MAX_INTERVAL = UINT16_MAX;
 
+	if (!l_settings_get_uint(config, "Rank", "HighUtilizationThreshold",
+					&RANK_HIGH_UTILIZATION))
+		RANK_HIGH_UTILIZATION = 0;
+
+	if (L_WARN_ON(RANK_HIGH_UTILIZATION > 255))
+		RANK_HIGH_UTILIZATION = 255;
+
+	if (!l_settings_get_uint(config, "Rank", "HighStationCountThreshold",
+					&RANK_HIGH_STATION_COUNT))
+		RANK_HIGH_STATION_COUNT = 0;
+
+	if (L_WARN_ON(RANK_HIGH_STATION_COUNT > 255))
+		RANK_HIGH_STATION_COUNT = 255;
+
 	return 0;
 }
 
-- 
2.34.1

[PATCH 7/8] doc: document [Rank].HighUtilization/StationCount thresholds

[James Prestwood]

---
 src/iwd.config.rst | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/src/iwd.config.rst b/src/iwd.config.rst
index 9dc0fe0c..1cb4b05d 100644
--- a/src/iwd.config.rst
+++ b/src/iwd.config.rst
@@ -341,6 +341,28 @@ autoconnect purposes.
        A value of 0.0 will disable the 6GHz band and prevent scanning or
        connecting on those frequencies.
 
+   * - HighUtilizationThreshold
+     - Values: unsigned integer value 0 - 255 (default: **0**, disabled)
+
+       **Warning: This is an experimental feature**
+
+       The BSS utilization threshold at which a negative rank factor begins to
+       be applied to the BSS. As the load increases for a BSS the ranking factor
+       decays exponentially, meaning the ranking factor will decrease
+       exponentially. Setting this can have very drastic effects on the BSS rank
+       if its utilization is high, use with care.
+
+   * - HighStationCountThreshold
+     - Values: unsigned integer value 0 - 255 (default: **0**, disabled)
+
+       **Warning: This is an experimental feature**
+
+       The BSS station count threshold at which a negative rank factor begins to
+       be applied to the BSS. As the station count increases for a BSS the
+       ranking factor decays exponentially, meaning the ranking factor will
+       decrease exponentially. Setting this can have very drastic effects on the
+       BSS rank if its station count is high, use with care.
+
 Scan
 ----
 
-- 
2.34.1

[PATCH 8/8] station: print client count in scan results

[James Prestwood]

---
 src/station.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/station.c b/src/station.c
index 71dc4c21..1238734f 100644
--- a/src/station.c
+++ b/src/station.c
@@ -425,7 +425,8 @@ static void station_print_scan_bss(const struct scan_bss *bss)
 		ptr += sprintf(ptr, ", snr: %d", bss->snr);
 
 	if (bss->have_utilization)
-		ptr += sprintf(ptr, ", load: %u/255", bss->utilization);
+		ptr += sprintf(ptr, ", load: %u/255, clients: %u",
+				bss->utilization, bss->sta_count);
 
 	l_debug("Processing BSS '%s' with SSID: %s, freq: %u, rank: %u, "
 			"strength: %i, data_rate: %u.%u%s",
-- 
2.34.1

Re: [PATCH 3/8] util: add util_exponential_decay

[Denis Kenzior]

Hi James,

On 11/19/24 8:24 AM, James Prestwood wrote:
> This is copied from network.c that uses a static table to lookup
> exponential decay values by index (generated from 1/pow(n, 0.3)).
> network.c uses this for network ranking but it can be useful for
> BSS ranking as well if you need to apply some exponential backoff
> to a value.
> ---
>   src/util.c | 28 ++++++++++++++++++++++++++++
>   src/util.h |  2 ++
>   2 files changed, 30 insertions(+)
> 
> diff --git a/src/util.c b/src/util.c
> index a6ab9d85..b673b002 100644
> --- a/src/util.c
> +++ b/src/util.c
> @@ -636,3 +636,31 @@ struct scan_freq_set *scan_freq_set_clone(const struct scan_freq_set *set,
>   
>   	return new;
>   }
> +
> +/* First 64 entries calculated by 1 / pow(n, 0.3) for n >= 1 */
> +static const double rankmod_table[] = {
> +	1.0000000000, 0.8122523964, 0.7192230933, 0.6597539554,
> +	0.6170338627, 0.5841906811, 0.5577898253, 0.5358867313,
> +	0.5172818580, 0.5011872336, 0.4870596972, 0.4745102806,
> +	0.4632516708, 0.4530661223, 0.4437850034, 0.4352752816,
> +	0.4274303178, 0.4201634287, 0.4134032816, 0.4070905315,
> +	0.4011753236, 0.3956154062, 0.3903746872, 0.3854221125,
> +	0.3807307877, 0.3762772797, 0.3720410580, 0.3680040435,
> +	0.3641502401, 0.3604654325, 0.3569369365, 0.3535533906,
> +	0.3503045821, 0.3471812999, 0.3441752105, 0.3412787518,
> +	0.3384850430, 0.3357878061, 0.3331812996, 0.3306602598,
> +	0.3282198502, 0.3258556179, 0.3235634544, 0.3213395618,
> +	0.3191804229, 0.3170827751, 0.3150435863, 0.3130600345,
> +	0.3111294892, 0.3092494947, 0.3074177553, 0.3056321221,
> +	0.3038905808, 0.3021912409, 0.3005323264, 0.2989121662,
> +	0.2973291870, 0.2957819051, 0.2942689208, 0.2927889114,
> +	0.2913406263, 0.2899228820, 0.2885345572, 0.2871745887,
> +};
> +
> +double util_exponential_decay(unsigned int n)
> +{
> +	if (n > L_ARRAY_SIZE(rankmod_table))

I changed '>' to '>=' to avoid overflow.  All 8 patches have been applied, thanks.

Regards,
-Denis