# HG changeset patch
# User Thomas Klausner <tk@giga.or.at>
# Date 1573813301 -3600
# Node ID 46656b52ae97845dd46cf36cb8b0b6f6e7327a87
# Parent  de90cf7f381e77501c1f4607a19c06f1bb212c70
rt_load_balance: improve algorithm

The extension now looks at the candidates with the highest
score. Among those it increases the score for all of them with
the lowest load by +1. Then it randomly gives one of them another
+1 boost.

diff -r de90cf7f381e -r 46656b52ae97 extensions/rt_load_balance/rt_load_balance.c
--- a/extensions/rt_load_balance/rt_load_balance.c	Tue Oct 15 16:26:23 2019 +0200
+++ b/extensions/rt_load_balance/rt_load_balance.c	Fri Nov 15 11:21:41 2019 +0100
@@ -30,9 +30,22 @@
 *********************************************************************************************************/
 
 #include <freeDiameter/extension.h>
+#include <limits.h>
+#include <time.h>
+
+struct best_candidate_entry {
+    long load;
+    struct rtd_candidate *cand;
+};
+
+static unsigned int seed;
+
+#define MODULE_NAME "rt_load_balance"
 
 /*
- * Load balancing extension. Send request to least-loaded node.
+ * Load balancing extension. Send request to least-loaded node: Add a
+ * score of 1 to the least loaded candidates among those with highest
+ * score.
  */
 
 /* The callback for load balancing the requests across the peers */
@@ -40,37 +53,82 @@
 {
 	struct fd_list *lic;
 	struct msg * msg = *pmsg;
-	
+	int max_score = -1;
+	int max_score_count = 0;
+
 	TRACE_ENTRY("%p %p %p", cbdata, msg, candidates);
-	
+
 	CHECK_PARAMS(msg && candidates);
-	
+
+
 	/* Check if it is worth processing the message */
 	if (FD_IS_LIST_EMPTY(candidates))
 		return 0;
 
-	/* load balancing */
+	/* find out maximal score and how many candidates have it */
 	for (lic = candidates->next; lic != candidates; lic = lic->next) {
 		struct rtd_candidate * cand = (struct rtd_candidate *) lic;
-		struct peer_hdr *peer;
-		long to_receive, to_send, load;
-		int score;
-		CHECK_FCT(fd_peer_getbyid(cand->diamid, cand->diamidlen, 0, &peer));
-		CHECK_FCT(fd_peer_get_load_pending(peer, &to_receive, &to_send));
-                load = to_receive + to_send;
-		/* other routing mechanisms need to add to the
-		 * appropriate entries so their base value is high
-		 * enough that they are considered */
+		if (max_score < cand->score) {
+			max_score = cand->score;
+			max_score_count = 1;
+		}
+		else if (cand->score == max_score) {
+			max_score_count++;
+		}
+	}
+
+	if (max_score_count > 0) {
+		/* find out minimum load among those with maximal
+		 * score, and how many candidates have it */
+		struct best_candidate_entry best_candidates[max_score_count];
+		long min_load = LONG_MAX;
+		int min_load_count = 0;
+		int j;
+
+		for (j = 0, lic = candidates->next; lic != candidates; lic = lic->next) {
+			struct rtd_candidate * cand = (struct rtd_candidate *) lic;
+			if (cand->score == max_score) {
+				long to_receive, to_send, load;
+				struct peer_hdr *peer;
+				CHECK_FCT(fd_peer_getbyid(cand->diamid, cand->diamidlen, 0, &peer));
+				CHECK_FCT(fd_peer_get_load_pending(peer, &to_receive, &to_send));
+				load = to_receive + to_send;
+
+				best_candidates[j].cand = cand;
+				best_candidates[j].load = load;
+				j++;
 
-		/* logarithmic scaling */
-                int load_log = 0;
-                while (load > 0) {
-                    load_log++;
-                    load /= 2;
-                }
-		score = cand->score;
-		cand->score -= load_log;
-		TRACE_DEBUG(FULL, "evaluated peer `%.*s', score was %d, now %d", (int)cand->diamidlen, cand->diamid, score, cand->score);
+				if (min_load > load) {
+					min_load = load;
+					min_load_count = 1;
+				} else if (min_load == load) {
+					min_load_count++;
+				}
+			}
+		}
+
+		/* increase score by 1 for all entries with minimum
+		 * load, and further increase by 1 for one randomly
+		 * chosen candidate */
+		if (min_load_count > 0) {
+			int lucky_candidate = rand_r(&seed) % min_load_count;
+			int i;
+			for (j = 0, i = 0; j < max_score_count; j++) {
+				struct best_candidate_entry *entry = best_candidates+j;
+				if (entry->load == min_load) {
+					struct rtd_candidate *cand = entry->cand;
+					long old_score = cand->score;
+					cand->score++;
+					TRACE_DEBUG(FULL, "%s: boosting peer `%.*s', score was %d, now %d; load was %ld", MODULE_NAME, (int)cand->diamidlen, cand->diamid, old_score, cand->score, entry->load);
+
+					if (i == lucky_candidate) {
+						cand->score++;
+						TRACE_DEBUG(FULL, "%s: boosting lucky peer `%.*s', score was %d, now %d; load was %ld", MODULE_NAME, (int)cand->diamidlen, cand->diamid, old_score, cand->score, entry->load);
+					}
+					i++;
+				}
+			}
+		}
 	}
 
 	return 0;
@@ -85,6 +143,8 @@
 	/* Register the callback */
 	CHECK_FCT(fd_rt_out_register(rt_load_balancing, NULL, 10, &rt_load_balancing_hdl));
 
+	seed = (unsigned int)time(NULL);
+
 	TRACE_DEBUG(INFO, "Extension 'Load Balancing' initialized");
 	return 0;
 }
@@ -97,4 +157,4 @@
 	return ;
 }
 
-EXTENSION_ENTRY("rt_load_balance", rt_load_balance_entry);
+EXTENSION_ENTRY(MODULE_NAME, rt_load_balance_entry);