hodec2: to balance congestion, use overload percent

For balancing load across congested cells and across congested TCH/*
kinds, instead of comparing the number of lchans above the configured
congestion threshold, compare the percent of lchans of overload.

In short, using a percentage prevents cells with less min-free-slots to
fill up 100% while neighbor cells still may have several free lchans
available.

An obvious example of why this is desirable is illustrated by
test_balance_congestion_by_percentage.ho_vty:

Cell A has min-free-slots 2, and has all slots occupied.
Cell B has min-free-slots 4, and has 2 slots remaining free.

If we count congested lchans as in current master: cell A has a
congestion count of 2: two more lchans in use than "allowed". If we move
one lchan over to cell B, it ends up with a congestion count of 3, which
is worse than 2. So when counting lchans, we decide that cell A should
remain full.

Instead, when comparing percentage of remaining lchans, we would see
that cell A is loaded 100% above congestion (2 of 2 remaining lchans in
use), but when moving one lchan to cell B, that would only be 75% loaded
above its treshold (3 of 4 remaining lchans in use). So a percentage
comparison would cause a handover to cell B.

Related: SYS#5259
Change-Id: I55234c6c99eb02ceee52be0d7388bea14304930f

4 files changed, 57 insertions, 23 deletions

diff --git a/doc/manuals/chapters/handover.adoc b/doc/manuals/chapters/handover.adoc
index 4de744b9e..56e9aea46 100644
--- a/doc/manuals/chapters/handover.adoc
+++ b/doc/manuals/chapters/handover.adoc
@@ -511,9 +511,11 @@ periodical congestion check attempts to distribute MS to less loaded neighbor
 cells. Every time, the one MS that will suffer the least RXLEV loss while still
 reducing congestion will be instructed to move first.
 
-If a cell and its neighbors are all loaded past their `min-free-slots`
-settings, the algorithmic aim is equal load: a load-based handover will never
-cause the target cell to be more congested than the source cell.
+If a cell and its neighbors are all loaded past their `min-free-slots` settings,
+the algorithmic aim is to improve the percentage of load above the
+`min-free-slots` setting: a load-based handover always requires the target cell
+to have a lower load percentage after handover than the source cell had before
+handover.
 
 The min-free-slots setting is a tradeoff between immediate voice service
 availability and optimal reception levels. A sane choice could be:
diff --git a/src/osmo-bsc/handover_decision_2.c b/src/osmo-bsc/handover_decision_2.c
index c265f5fa3..0362c9b95 100644
--- a/src/osmo-bsc/handover_decision_2.c
+++ b/src/osmo-bsc/handover_decision_2.c
@@ -25,6 +25,7 @@
 #include <stdbool.h>
 #include <errno.h>
 #include <limits.h>
+#include <math.h>
 
 #include <osmocom/bsc/debug.h>
 #include <osmocom/bsc/gsm_data.h>
@@ -387,6 +388,26 @@ static bool codec_type_is_supported(struct gsm_subscriber_connection *conn,
 	return false;
 }
 
+#define LOAD_PRECISION 6
+
+/* Return a number representing overload, i.e. the fraction of lchans used above the congestion threshold.
+ * Think of it as a percentage of used lchans above congestion, just represented in a fixed-point fraction with N
+ * decimal digits of fractional part. If there is no congestion (free_tch >= min_free_tch), return 0.
+ */
+static int32_t load_above_congestion(int free_tch, int min_free_tch)
+{
+	int32_t v;
+	OSMO_ASSERT(free_tch >= 0);
+	/* Avoid division by zero when no congestion threshold is set, and return zero overload when there is no
+	 * congestion. */
+	if (free_tch >= min_free_tch)
+		return 0;
+	v = min_free_tch - free_tch;
+	v *= pow(10, LOAD_PRECISION);
+	v /= min_free_tch;
+	return v;
+}
+
 /*
  * Check what requirements the given cell fulfills.
  * A bit mask of fulfilled requirements is returned.
@@ -443,7 +464,7 @@ static void check_requirements(struct ho_candidate *c)
 {
 	uint8_t requirement = 0;
 	unsigned int penalty_time;
-	int current_overbooked;
+	int32_t current_overbooked;
 	c->requirements = 0;
 
 	/* Requirement A */
@@ -626,17 +647,25 @@ static void check_requirements(struct ho_candidate *c)
 
 	/* Requirement C */
 
-	/* the nr of lchans surpassing congestion on the target cell must be <= the lchans surpassing congestion on the
-	 * current cell _after_ handover/assignment */
-	current_overbooked = c->current.min_free_tch - c->current.free_tch;
+	/* the load percentage above congestion on the target cell *after* HO must be < the load percentage above
+	 * congestion on the current cell, hence the - 1 on the target. */
+	current_overbooked = load_above_congestion(c->current.free_tch, c->current.min_free_tch);
 	if (requirement & REQUIREMENT_A_TCHF) {
-		int target_overbooked = c->target.min_free_tchf - c->target.free_tchf;
-		if (target_overbooked + 1 <= current_overbooked - 1)
+		int32_t target_overbooked = load_above_congestion(c->target.free_tchf - 1, c->target.min_free_tchf);
+		LOGPHOLCHANTOBTS(c->current.lchan, c->target.bts, LOGL_DEBUG,
+				 "current overbooked = %s%%, TCH/F target overbooked after HO = %s%%\n",
+				 osmo_int_to_float_str_c(OTC_SELECT, current_overbooked, LOAD_PRECISION - 2),
+				 osmo_int_to_float_str_c(OTC_SELECT, target_overbooked, LOAD_PRECISION - 2));
+		if (target_overbooked < current_overbooked)
 			requirement |= REQUIREMENT_C_TCHF;
 	}
 	if (requirement & REQUIREMENT_A_TCHH) {
-		int target_overbooked = c->target.min_free_tchh - c->target.free_tchh;
-		if (target_overbooked + 1 <= current_overbooked - 1)
+		int32_t target_overbooked = load_above_congestion(c->target.free_tchh - 1, c->target.min_free_tchh);
+		LOGPHOLCHANTOBTS(c->current.lchan, c->target.bts, LOGL_DEBUG,
+				 "current overbooked = %s%%, TCH/H target overbooked after HO = %s%%\n",
+				 osmo_int_to_float_str_c(OTC_SELECT, current_overbooked, LOAD_PRECISION - 2),
+				 osmo_int_to_float_str_c(OTC_SELECT, target_overbooked, LOAD_PRECISION - 2));
+		if (target_overbooked < current_overbooked)
 			requirement |= REQUIREMENT_C_TCHH;
 	}
 
diff --git a/tests/handover/test_balance_congestion_by_percentage.ho_vty b/tests/handover/test_balance_congestion_by_percentage.ho_vty
index e00636e7d..09d215103 100644
--- a/tests/handover/test_balance_congestion_by_percentage.ho_vty
+++ b/tests/handover/test_balance_congestion_by_percentage.ho_vty
@@ -29,6 +29,7 @@ set-ts-use trx 1 0 states        *    TCH/F TCH/F TCH/F TCH/F -     -     *
 meas-rep lchan * * * * rxlev 40 rxqual 0 ta 0 neighbors 30
 expect-no-chan
 
-# bts 0 is full, but by counting lchans above congestion, it should remain full.
+# bts 0 is full, by target_overbooked_after_ho==75% < current_overbooked_before_ho==100%, a congestion balancing to bts
+# 1 is performed.
 congestion-check
-expect-no-chan
+expect-ho from lchan 0 0 1 0 to lchan 1 0 5 0
diff --git a/tests/handover/test_balance_congestion_tchf_tchh.ho_vty b/tests/handover/test_balance_congestion_tchf_tchh.ho_vty
index 7f9039f78..62f07bff2 100644
--- a/tests/handover/test_balance_congestion_tchf_tchh.ho_vty
+++ b/tests/handover/test_balance_congestion_tchf_tchh.ho_vty
@@ -6,46 +6,48 @@ network
 
 create-bts trx-count 1 timeslots	c+s4	TCH/F	TCH/F	TCH/F	TCH/F	TCH/H	TCH/H	TCH/H
 
-# both TCH/H and TCH/F have one lchan above congestion, nothing happens
+# both TCH/H and TCH/F have one lchan = 33% above congestion, nothing happens
 set-ts-use trx 0 0 states		*	TCH/F	TCH/F	-	-	TCH/HH  TCH/HH  -
 meas-rep lchan * * * * rxlev 10 rxqual 0 ta 0
 congestion-check
 expect-no-chan
 
-# TCH/F = +1, TCH/H = +2 above congestion. Moving a TCH/H to TCH/F would just reverse the situation to F=+2 H=+1. Nothing happens.
+# TCH/F = +1 = 33%, TCH/H = +2 = 66% above congestion.
+# Moving a TCH/H to TCH/F would just reverse the situation to F=+2=66%. Nothing happens.
 set-ts-use trx 0 0 states		*	TCH/F	TCH/F	-	-	TCH/HH  TCH/HH  TCH/H-
 meas-rep lchan * * * * rxlev 10 rxqual 0 ta 0
 congestion-check
 expect-no-chan
 
-# F=+1 H=+3. Balance to F=+2 H=+2
+# F=+1=33% H=+3=100%. Balance to F=+2=66% (which is < 100%) and H=+2=66%
 set-ts-use trx 0 0 states		*	TCH/F	TCH/F	-	-	TCH/HH  TCH/HH  TCH/HH
 meas-rep lchan * * * * rxlev 10 rxqual 0 ta 0
 congestion-check
 expect-ho from lchan 0 0 5 0 to lchan 0 0 3 0
 
-# Now the exact same thing, just with different min-free-slots settings for
-# tch/f vs tch/h
+# Now similar load percentages, just with different min-free-slots settings for tch/f vs tch/h.
 
 network
  handover2 min-free-slots tch/f 3
  handover2 min-free-slots tch/h 5
 
-# both TCH/H and TCH/F have one lchan above congestion, nothing happens
+# TCH/F has 1/3 = 33%, TCH/H has 1/5 = 20% overload.
+# Moving one to TCH/H would mean 40% overload on TCH/H, which is above the current TCH/F of 33%.
+# Nothing happens.
 set-ts-use trx 0 0 states		*	TCH/F	TCH/F	-	-	TCH/HH  -	-
 meas-rep lchan * * * * rxlev 20 rxqual 0 ta 0
 congestion-check
 expect-no-chan
 
-# TCH/F = +1, TCH/H = +2 above congestion. Moving a TCH/H to TCH/F would just
-# reverse the situation to F=+2 H=+1. Nothing happens.
+# TCH/F = +1 = 33%, TCH/H = +2 = 40% above congestion. Moving a TCH/H to TCH/F would result
+# in F=+2=66%>40%. Nothing happens.
 set-ts-use trx 0 0 states		*	TCH/F	TCH/F	-	-	TCH/HH  TCH/H-  -
 meas-rep lchan * * * * rxlev 20 rxqual 0 ta 0
 congestion-check
 expect-no-chan
 
-# F=+1 H=+3. Balance to F=+2 H=+2
-set-ts-use trx 0 0 states		*	TCH/F	TCH/F	-	-	TCH/HH  TCH/HH  -
+# F=+1=33% H=+4=80%. Balance to F=+2=66%<80% and H=+3=60%
+set-ts-use trx 0 0 states		*	TCH/F	TCH/F	-	-	TCH/HH  TCH/HH  TCH/H-
 meas-rep lchan * * * * rxlev 20 rxqual 0 ta 0
 congestion-check
 expect-ho from lchan 0 0 5 0 to lchan 0 0 3 0