alloc: Load balancing for algo A

Currently only the first enabled PDCH will be used. Beside the
throughput this will also limit the number of TBFs:

  - number of UL TBFs <= 7
  - number of DL TBFs <= 32

This commit changes the allocation algorithm to use the PDCH with the
least number of attached TBFs. This will improve the troughput in
both directions and the UL limits:

  - number of UL TBFs <= min(32, N_PDCH * 7) UL TBFs

Ticket: #1794
Sponsored-by: On-Waves ehf

3 files changed, 191 insertions, 91 deletions

diff --git a/tests/alloc/AllocTest.cpp b/tests/alloc/AllocTest.cpp
index 5a91f6a6..b918132c 100644
--- a/tests/alloc/AllocTest.cpp
+++ b/tests/alloc/AllocTest.cpp
@@ -110,11 +110,11 @@ static void test_alloc_a()
 {
 	/* slots 2 - 3 */
 	test_alloc_a(GPRS_RLCMAC_DL_TBF, 0x0c, 32);
-	test_alloc_a(GPRS_RLCMAC_UL_TBF, 0x0c, 7);
+	test_alloc_a(GPRS_RLCMAC_UL_TBF, 0x0c, 14);
 
 	/* slots 1 - 5 */
 	test_alloc_a(GPRS_RLCMAC_DL_TBF, 0x1e, 32);
-	test_alloc_a(GPRS_RLCMAC_UL_TBF, 0x1e, 7);
+	test_alloc_a(GPRS_RLCMAC_UL_TBF, 0x1e, 28);
 }
 
 static void dump_assignment(struct gprs_rlcmac_tbf *tbf, const char *dir)
@@ -557,13 +557,13 @@ static void test_successive_allocation(algo_t algo, unsigned min_class,
 	}
 
 	printf("  Successfully allocated %d UL TBFs\n", counter);
-	OSMO_ASSERT(counter >= expect_num);
+	OSMO_ASSERT(counter == expect_num);
 }
 
 static void test_successive_allocation()
 {
 	test_successive_allocation(alloc_algorithm_a, 1, 1, TEST_MODE_UL_AND_DL,
-		7, "algorithm A (UL and DL)");
+		32, "algorithm A (UL and DL)");
 	test_successive_allocation(alloc_algorithm_b, 10, 10, TEST_MODE_UL_AND_DL,
 		7, "algorithm B class 10 (UL and DL)");
 	test_successive_allocation(alloc_algorithm_b, 12, 12, TEST_MODE_UL_AND_DL,
@@ -574,29 +574,29 @@ static void test_successive_allocation()
 		18, "algorithm B class 1-29 (UL and DL)");
 
 	test_successive_allocation(alloc_algorithm_a, 1, 1, TEST_MODE_DL_AND_UL,
-		7, "algorithm A (DL and UL)");
+		32, "algorithm A (DL and UL)");
 	test_successive_allocation(alloc_algorithm_b, 10, 10, TEST_MODE_DL_AND_UL,
 		7, "algorithm B class 10 (DL and UL)");
 
 	test_successive_allocation(alloc_algorithm_a, 1, 1, TEST_MODE_DL_AFTER_UL,
-		7, "algorithm A (DL after UL)");
+		32, "algorithm A (DL after UL)");
 	test_successive_allocation(alloc_algorithm_b, 10, 10, TEST_MODE_DL_AFTER_UL,
-		7, "algorithm B class 10 (DL after UL)");
+		32, "algorithm B class 10 (DL after UL)");
 
 	test_successive_allocation(alloc_algorithm_a, 1, 1, TEST_MODE_UL_AFTER_DL,
-		7, "algorithm A (UL after DL)");
+		32, "algorithm A (UL after DL)");
 	test_successive_allocation(alloc_algorithm_b, 10, 10, TEST_MODE_UL_AFTER_DL,
 		7, "algorithm B class 10 (UL after DL)");
 
 	test_successive_allocation(alloc_algorithm_a, 1, 1, TEST_MODE_UL_ONLY,
-		7, "algorithm A (UL only)");
+		32, "algorithm A (UL only)");
 	test_successive_allocation(alloc_algorithm_b, 10, 10, TEST_MODE_UL_ONLY,
 		7, "algorithm B class 10 (UL only)");
 
 	test_successive_allocation(alloc_algorithm_a, 1, 1, TEST_MODE_DL_ONLY,
-		7, "algorithm A (DL ONLY)");
+		32, "algorithm A (DL ONLY)");
 	test_successive_allocation(alloc_algorithm_b, 10, 10, TEST_MODE_DL_ONLY,
-		7, "algorithm B class 10 (DL ONLY)");
+		32, "algorithm B class 10 (DL ONLY)");
 }
 
 int main(int argc, char **argv)
diff --git a/tests/alloc/AllocTest.err b/tests/alloc/AllocTest.err
index db956017..3f9fc832 100644
--- a/tests/alloc/AllocTest.err
+++ b/tests/alloc/AllocTest.err
@@ -1,19 +1,19 @@
 No TFI available.
-- Failed allocating TS=2, no USF available
+- Failed to allocate a TS, no USF available
+No TFI available.
+- Failed to allocate a TS, no USF available
 No TFI available.
-- Failed allocating TS=1, no USF available
-- Failed allocating TS=3, no USF available
 No suitable uplink slots available
 No suitable uplink slots available
 No suitable uplink slots available
 No suitable uplink slots available
-- Failed allocating TS=3, no USF available
+No TFI available.
 No suitable uplink slots available
 No TFI available.
 No TFI available.
-- Failed allocating TS=3, no USF available
+No TFI available.
 No suitable uplink slots available
-- Failed allocating TS=3, no USF available
+No TFI available.
 No suitable uplink slots available
 No TFI available.
 No TFI available.
diff --git a/tests/alloc/AllocTest.ok b/tests/alloc/AllocTest.ok
index 89393fc3..3602d8c0 100644
--- a/tests/alloc/AllocTest.ok
+++ b/tests/alloc/AllocTest.ok
@@ -8619,13 +8619,38 @@ Mass test: TS0(OOOOOOOO)TS7 MS_Class=28
 Mass test: TS0(OOOOOOOO)TS7 MS_Class=29
 Going to test assignment with many TBF, algorithm A (UL and DL)
  TBF[0] class 1 reserves ...C....
- TBF[1] class 1 reserves ...C....
- TBF[2] class 1 reserves ...C....
- TBF[3] class 1 reserves ...C....
- TBF[4] class 1 reserves ...C....
+ TBF[1] class 1 reserves ....C...
+ TBF[2] class 1 reserves .....C..
+ TBF[3] class 1 reserves ......C.
+ TBF[4] class 1 reserves .......C
  TBF[5] class 1 reserves ...C....
- TBF[6] class 1 reserves ...C....
-  Successfully allocated 7 UL TBFs
+ TBF[6] class 1 reserves ....C...
+ TBF[7] class 1 reserves .....C..
+ TBF[8] class 1 reserves ......C.
+ TBF[9] class 1 reserves .......C
+ TBF[10] class 1 reserves ...C....
+ TBF[11] class 1 reserves ....C...
+ TBF[12] class 1 reserves .....C..
+ TBF[13] class 1 reserves ......C.
+ TBF[14] class 1 reserves .......C
+ TBF[15] class 1 reserves ...C....
+ TBF[16] class 1 reserves ....C...
+ TBF[17] class 1 reserves .....C..
+ TBF[18] class 1 reserves ......C.
+ TBF[19] class 1 reserves .......C
+ TBF[20] class 1 reserves ...C....
+ TBF[21] class 1 reserves ....C...
+ TBF[22] class 1 reserves .....C..
+ TBF[23] class 1 reserves ......C.
+ TBF[24] class 1 reserves .......C
+ TBF[25] class 1 reserves ...C....
+ TBF[26] class 1 reserves ....C...
+ TBF[27] class 1 reserves .....C..
+ TBF[28] class 1 reserves ......C.
+ TBF[29] class 1 reserves .......C
+ TBF[30] class 1 reserves ...C....
+ TBF[31] class 1 reserves ....C...
+  Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm B class 10 (UL and DL)
  TBF[0] class 10 reserves ...DDCD.
  TBF[1] class 10 reserves ...DDCD.
@@ -8682,13 +8707,38 @@ Going to test assignment with many TBF, algorithm B class 1-29 (UL and DL)
   Successfully allocated 18 UL TBFs
 Going to test assignment with many TBF, algorithm A (DL and UL)
  TBF[0] class 1 reserves ...C....
- TBF[1] class 1 reserves ...C....
- TBF[2] class 1 reserves ...C....
- TBF[3] class 1 reserves ...C....
- TBF[4] class 1 reserves ...C....
+ TBF[1] class 1 reserves ....C...
+ TBF[2] class 1 reserves .....C..
+ TBF[3] class 1 reserves ......C.
+ TBF[4] class 1 reserves .......C
  TBF[5] class 1 reserves ...C....
- TBF[6] class 1 reserves ...C....
-  Successfully allocated 7 UL TBFs
+ TBF[6] class 1 reserves ....C...
+ TBF[7] class 1 reserves .....C..
+ TBF[8] class 1 reserves ......C.
+ TBF[9] class 1 reserves .......C
+ TBF[10] class 1 reserves ...C....
+ TBF[11] class 1 reserves ....C...
+ TBF[12] class 1 reserves .....C..
+ TBF[13] class 1 reserves ......C.
+ TBF[14] class 1 reserves .......C
+ TBF[15] class 1 reserves ...C....
+ TBF[16] class 1 reserves ....C...
+ TBF[17] class 1 reserves .....C..
+ TBF[18] class 1 reserves ......C.
+ TBF[19] class 1 reserves .......C
+ TBF[20] class 1 reserves ...C....
+ TBF[21] class 1 reserves ....C...
+ TBF[22] class 1 reserves .....C..
+ TBF[23] class 1 reserves ......C.
+ TBF[24] class 1 reserves .......C
+ TBF[25] class 1 reserves ...C....
+ TBF[26] class 1 reserves ....C...
+ TBF[27] class 1 reserves .....C..
+ TBF[28] class 1 reserves ......C.
+ TBF[29] class 1 reserves .......C
+ TBF[30] class 1 reserves ...C....
+ TBF[31] class 1 reserves ....C...
+  Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm B class 10 (DL and UL)
  TBF[0] class 10 reserves ...DDCD.
  TBF[1] class 10 reserves ...DDCD.
@@ -8700,37 +8750,37 @@ Going to test assignment with many TBF, algorithm B class 10 (DL and UL)
   Successfully allocated 7 UL TBFs
 Going to test assignment with many TBF, algorithm A (DL after UL)
  TBF[0] class 1 reserves ...C....
- TBF[1] class 1 reserves ...C....
- TBF[2] class 1 reserves ...C....
- TBF[3] class 1 reserves ...C....
- TBF[4] class 1 reserves ...C....
+ TBF[1] class 1 reserves ....C...
+ TBF[2] class 1 reserves .....C..
+ TBF[3] class 1 reserves ......C.
+ TBF[4] class 1 reserves .......C
  TBF[5] class 1 reserves ...C....
- TBF[6] class 1 reserves ...C....
- TBF[7] class 1 reserves ...C....
- TBF[8] class 1 reserves ...C....
- TBF[9] class 1 reserves ...C....
+ TBF[6] class 1 reserves ....C...
+ TBF[7] class 1 reserves .....C..
+ TBF[8] class 1 reserves ......C.
+ TBF[9] class 1 reserves .......C
  TBF[10] class 1 reserves ...C....
- TBF[11] class 1 reserves ...C....
- TBF[12] class 1 reserves ...C....
- TBF[13] class 1 reserves ...C....
- TBF[14] class 1 reserves ...C....
+ TBF[11] class 1 reserves ....C...
+ TBF[12] class 1 reserves .....C..
+ TBF[13] class 1 reserves ......C.
+ TBF[14] class 1 reserves .......C
  TBF[15] class 1 reserves ...C....
- TBF[16] class 1 reserves ...C....
- TBF[17] class 1 reserves ...C....
- TBF[18] class 1 reserves ...C....
- TBF[19] class 1 reserves ...C....
+ TBF[16] class 1 reserves ....C...
+ TBF[17] class 1 reserves .....C..
+ TBF[18] class 1 reserves ......C.
+ TBF[19] class 1 reserves .......C
  TBF[20] class 1 reserves ...C....
- TBF[21] class 1 reserves ...C....
- TBF[22] class 1 reserves ...C....
- TBF[23] class 1 reserves ...C....
- TBF[24] class 1 reserves ...C....
+ TBF[21] class 1 reserves ....C...
+ TBF[22] class 1 reserves .....C..
+ TBF[23] class 1 reserves ......C.
+ TBF[24] class 1 reserves .......C
  TBF[25] class 1 reserves ...C....
- TBF[26] class 1 reserves ...C....
- TBF[27] class 1 reserves ...C....
- TBF[28] class 1 reserves ...C....
- TBF[29] class 1 reserves ...C....
+ TBF[26] class 1 reserves ....C...
+ TBF[27] class 1 reserves .....C..
+ TBF[28] class 1 reserves ......C.
+ TBF[29] class 1 reserves .......C
  TBF[30] class 1 reserves ...C....
- TBF[31] class 1 reserves ...C....
+ TBF[31] class 1 reserves ....C...
   Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm B class 10 (DL after UL)
  TBF[0] class 10 reserves ...DDCD.
@@ -8768,13 +8818,38 @@ Going to test assignment with many TBF, algorithm B class 10 (DL after UL)
   Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm A (UL after DL)
  TBF[0] class 1 reserves ...U....
- TBF[1] class 1 reserves ...U....
- TBF[2] class 1 reserves ...U....
- TBF[3] class 1 reserves ...U....
- TBF[4] class 1 reserves ...U....
+ TBF[1] class 1 reserves ....U...
+ TBF[2] class 1 reserves .....U..
+ TBF[3] class 1 reserves ......U.
+ TBF[4] class 1 reserves .......U
  TBF[5] class 1 reserves ...U....
- TBF[6] class 1 reserves ...U....
-  Successfully allocated 7 UL TBFs
+ TBF[6] class 1 reserves ....U...
+ TBF[7] class 1 reserves .....U..
+ TBF[8] class 1 reserves ......U.
+ TBF[9] class 1 reserves .......U
+ TBF[10] class 1 reserves ...U....
+ TBF[11] class 1 reserves ....U...
+ TBF[12] class 1 reserves .....U..
+ TBF[13] class 1 reserves ......U.
+ TBF[14] class 1 reserves .......U
+ TBF[15] class 1 reserves ...U....
+ TBF[16] class 1 reserves ....U...
+ TBF[17] class 1 reserves .....U..
+ TBF[18] class 1 reserves ......U.
+ TBF[19] class 1 reserves .......U
+ TBF[20] class 1 reserves ...U....
+ TBF[21] class 1 reserves ....U...
+ TBF[22] class 1 reserves .....U..
+ TBF[23] class 1 reserves ......U.
+ TBF[24] class 1 reserves .......U
+ TBF[25] class 1 reserves ...U....
+ TBF[26] class 1 reserves ....U...
+ TBF[27] class 1 reserves .....U..
+ TBF[28] class 1 reserves ......U.
+ TBF[29] class 1 reserves .......U
+ TBF[30] class 1 reserves ...U....
+ TBF[31] class 1 reserves ....U...
+  Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm B class 10 (UL after DL)
  TBF[0] class 10 reserves .....U..
  TBF[1] class 10 reserves .....U..
@@ -8786,13 +8861,38 @@ Going to test assignment with many TBF, algorithm B class 10 (UL after DL)
   Successfully allocated 7 UL TBFs
 Going to test assignment with many TBF, algorithm A (UL only)
  TBF[0] class 1 reserves ...U....
- TBF[1] class 1 reserves ...U....
- TBF[2] class 1 reserves ...U....
- TBF[3] class 1 reserves ...U....
- TBF[4] class 1 reserves ...U....
+ TBF[1] class 1 reserves ....U...
+ TBF[2] class 1 reserves .....U..
+ TBF[3] class 1 reserves ......U.
+ TBF[4] class 1 reserves .......U
  TBF[5] class 1 reserves ...U....
- TBF[6] class 1 reserves ...U....
-  Successfully allocated 7 UL TBFs
+ TBF[6] class 1 reserves ....U...
+ TBF[7] class 1 reserves .....U..
+ TBF[8] class 1 reserves ......U.
+ TBF[9] class 1 reserves .......U
+ TBF[10] class 1 reserves ...U....
+ TBF[11] class 1 reserves ....U...
+ TBF[12] class 1 reserves .....U..
+ TBF[13] class 1 reserves ......U.
+ TBF[14] class 1 reserves .......U
+ TBF[15] class 1 reserves ...U....
+ TBF[16] class 1 reserves ....U...
+ TBF[17] class 1 reserves .....U..
+ TBF[18] class 1 reserves ......U.
+ TBF[19] class 1 reserves .......U
+ TBF[20] class 1 reserves ...U....
+ TBF[21] class 1 reserves ....U...
+ TBF[22] class 1 reserves .....U..
+ TBF[23] class 1 reserves ......U.
+ TBF[24] class 1 reserves .......U
+ TBF[25] class 1 reserves ...U....
+ TBF[26] class 1 reserves ....U...
+ TBF[27] class 1 reserves .....U..
+ TBF[28] class 1 reserves ......U.
+ TBF[29] class 1 reserves .......U
+ TBF[30] class 1 reserves ...U....
+ TBF[31] class 1 reserves ....U...
+  Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm B class 10 (UL only)
  TBF[0] class 10 reserves .....U..
  TBF[1] class 10 reserves .....U..
@@ -8804,37 +8904,37 @@ Going to test assignment with many TBF, algorithm B class 10 (UL only)
   Successfully allocated 7 UL TBFs
 Going to test assignment with many TBF, algorithm A (DL ONLY)
  TBF[0] class 1 reserves ...C....
- TBF[1] class 1 reserves ...C....
- TBF[2] class 1 reserves ...C....
- TBF[3] class 1 reserves ...C....
- TBF[4] class 1 reserves ...C....
+ TBF[1] class 1 reserves ....C...
+ TBF[2] class 1 reserves .....C..
+ TBF[3] class 1 reserves ......C.
+ TBF[4] class 1 reserves .......C
  TBF[5] class 1 reserves ...C....
- TBF[6] class 1 reserves ...C....
- TBF[7] class 1 reserves ...C....
- TBF[8] class 1 reserves ...C....
- TBF[9] class 1 reserves ...C....
+ TBF[6] class 1 reserves ....C...
+ TBF[7] class 1 reserves .....C..
+ TBF[8] class 1 reserves ......C.
+ TBF[9] class 1 reserves .......C
  TBF[10] class 1 reserves ...C....
- TBF[11] class 1 reserves ...C....
- TBF[12] class 1 reserves ...C....
- TBF[13] class 1 reserves ...C....
- TBF[14] class 1 reserves ...C....
+ TBF[11] class 1 reserves ....C...
+ TBF[12] class 1 reserves .....C..
+ TBF[13] class 1 reserves ......C.
+ TBF[14] class 1 reserves .......C
  TBF[15] class 1 reserves ...C....
- TBF[16] class 1 reserves ...C....
- TBF[17] class 1 reserves ...C....
- TBF[18] class 1 reserves ...C....
- TBF[19] class 1 reserves ...C....
+ TBF[16] class 1 reserves ....C...
+ TBF[17] class 1 reserves .....C..
+ TBF[18] class 1 reserves ......C.
+ TBF[19] class 1 reserves .......C
  TBF[20] class 1 reserves ...C....
- TBF[21] class 1 reserves ...C....
- TBF[22] class 1 reserves ...C....
- TBF[23] class 1 reserves ...C....
- TBF[24] class 1 reserves ...C....
+ TBF[21] class 1 reserves ....C...
+ TBF[22] class 1 reserves .....C..
+ TBF[23] class 1 reserves ......C.
+ TBF[24] class 1 reserves .......C
  TBF[25] class 1 reserves ...C....
- TBF[26] class 1 reserves ...C....
- TBF[27] class 1 reserves ...C....
- TBF[28] class 1 reserves ...C....
- TBF[29] class 1 reserves ...C....
+ TBF[26] class 1 reserves ....C...
+ TBF[27] class 1 reserves .....C..
+ TBF[28] class 1 reserves ......C.
+ TBF[29] class 1 reserves .......C
  TBF[30] class 1 reserves ...C....
- TBF[31] class 1 reserves ...C....
+ TBF[31] class 1 reserves ....C...
   Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm B class 10 (DL ONLY)
  TBF[0] class 10 reserves ...DDCD.