Mercurial > hg > freeDiameter

comparison extensions/rt_load_balance/rt_load_balance.c @ 1390:46656b52ae97

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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.
author Thomas Klausner <tk@giga.or.at>
date Fri, 15 Nov 2019 11:21:41 +0100
parents 38e4a7c318ac
children 1a9c73262a88
comparison
equal deleted inserted replaced
1389:de90cf7f381e 1390:46656b52ae97
28 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF * 28 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF *
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * 29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
30 *********************************************************************************************************/ 30 *********************************************************************************************************/
31 31
32 #include <freeDiameter/extension.h> 32 #include <freeDiameter/extension.h>
33 #include <limits.h>
34 #include <time.h>
35
36 struct best_candidate_entry {
37 long load;
38 struct rtd_candidate *cand;
39 };
40
41 static unsigned int seed;
42
43 #define MODULE_NAME "rt_load_balance"
33 44
34 /* 45 /*
35 * Load balancing extension. Send request to least-loaded node. 46 * Load balancing extension. Send request to least-loaded node: Add a
47 * score of 1 to the least loaded candidates among those with highest
48 * score.
36 */ 49 */
37 50
38 /* The callback for load balancing the requests across the peers */ 51 /* The callback for load balancing the requests across the peers */
39 static int rt_load_balancing(void * cbdata, struct msg ** pmsg, struct fd_list * candidates) 52 static int rt_load_balancing(void * cbdata, struct msg ** pmsg, struct fd_list * candidates)
40 { 53 {
41 struct fd_list *lic; 54 struct fd_list *lic;
42 struct msg * msg = *pmsg; 55 struct msg * msg = *pmsg;
43 56 int max_score = -1;
57 int max_score_count = 0;
58
44 TRACE_ENTRY("%p %p %p", cbdata, msg, candidates); 59 TRACE_ENTRY("%p %p %p", cbdata, msg, candidates);
45 60
46 CHECK_PARAMS(msg && candidates); 61 CHECK_PARAMS(msg && candidates);
47 62
63
48 /* Check if it is worth processing the message */ 64 /* Check if it is worth processing the message */
49 if (FD_IS_LIST_EMPTY(candidates)) 65 if (FD_IS_LIST_EMPTY(candidates))
50 return 0; 66 return 0;
51 67
52 /* load balancing */ 68 /* find out maximal score and how many candidates have it */
53 for (lic = candidates->next; lic != candidates; lic = lic->next) { 69 for (lic = candidates->next; lic != candidates; lic = lic->next) {
54 struct rtd_candidate * cand = (struct rtd_candidate *) lic; 70 struct rtd_candidate * cand = (struct rtd_candidate *) lic;
55 struct peer_hdr *peer; 71 if (max_score < cand->score) {
56 long to_receive, to_send, load; 72 max_score = cand->score;
57 int score; 73 max_score_count = 1;
58 CHECK_FCT(fd_peer_getbyid(cand->diamid, cand->diamidlen, 0, &peer)); 74 }
59 CHECK_FCT(fd_peer_get_load_pending(peer, &to_receive, &to_send)); 75 else if (cand->score == max_score) {
60 load = to_receive + to_send; 76 max_score_count++;
61 /* other routing mechanisms need to add to the 77 }
62 * appropriate entries so their base value is high 78 }
63 * enough that they are considered */
64 79
65 /* logarithmic scaling */ 80 if (max_score_count > 0) {
66 int load_log = 0; 81 /* find out minimum load among those with maximal
67 while (load > 0) { 82 * score, and how many candidates have it */
68 load_log++; 83 struct best_candidate_entry best_candidates[max_score_count];
69 load /= 2; 84 long min_load = LONG_MAX;
70 } 85 int min_load_count = 0;
71 score = cand->score; 86 int j;
72 cand->score -= load_log; 87
73 TRACE_DEBUG(FULL, "evaluated peer `%.*s', score was %d, now %d", (int)cand->diamidlen, cand->diamid, score, cand->score); 88 for (j = 0, lic = candidates->next; lic != candidates; lic = lic->next) {
89 struct rtd_candidate * cand = (struct rtd_candidate *) lic;
90 if (cand->score == max_score) {
91 long to_receive, to_send, load;
92 struct peer_hdr *peer;
93 CHECK_FCT(fd_peer_getbyid(cand->diamid, cand->diamidlen, 0, &peer));
94 CHECK_FCT(fd_peer_get_load_pending(peer, &to_receive, &to_send));
95 load = to_receive + to_send;
96
97 best_candidates[j].cand = cand;
98 best_candidates[j].load = load;
99 j++;
100
101 if (min_load > load) {
102 min_load = load;
103 min_load_count = 1;
104 } else if (min_load == load) {
105 min_load_count++;
106 }
107 }
108 }
109
110 /* increase score by 1 for all entries with minimum
111 * load, and further increase by 1 for one randomly
112 * chosen candidate */
113 if (min_load_count > 0) {
114 int lucky_candidate = rand_r(&seed) % min_load_count;
115 int i;
116 for (j = 0, i = 0; j < max_score_count; j++) {
117 struct best_candidate_entry *entry = best_candidates+j;
118 if (entry->load == min_load) {
119 struct rtd_candidate *cand = entry->cand;
120 long old_score = cand->score;
121 cand->score++;
122 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);
123
124 if (i == lucky_candidate) {
125 cand->score++;
126 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);
127 }
128 i++;
129 }
130 }
131 }
74 } 132 }
75 133
76 return 0; 134 return 0;
77 } 135 }
78 136
83 static int rt_load_balance_entry(char * conffile) 141 static int rt_load_balance_entry(char * conffile)
84 { 142 {
85 /* Register the callback */ 143 /* Register the callback */
86 CHECK_FCT(fd_rt_out_register(rt_load_balancing, NULL, 10, &rt_load_balancing_hdl)); 144 CHECK_FCT(fd_rt_out_register(rt_load_balancing, NULL, 10, &rt_load_balancing_hdl));
87 145
146 seed = (unsigned int)time(NULL);
147
88 TRACE_DEBUG(INFO, "Extension 'Load Balancing' initialized"); 148 TRACE_DEBUG(INFO, "Extension 'Load Balancing' initialized");
89 return 0; 149 return 0;
90 } 150 }
91 151
92 /* Unload */ 152 /* Unload */
95 /* Unregister the callbacks */ 155 /* Unregister the callbacks */
96 CHECK_FCT_DO(fd_rt_out_unregister(rt_load_balancing_hdl, NULL), /* continue */); 156 CHECK_FCT_DO(fd_rt_out_unregister(rt_load_balancing_hdl, NULL), /* continue */);
97 return ; 157 return ;
98 } 158 }
99 159
100 EXTENSION_ENTRY("rt_load_balance", rt_load_balance_entry); 160 EXTENSION_ENTRY(MODULE_NAME, rt_load_balance_entry);
"Welcome to our mercurial repository"