From b2a9557c04c983935ab89d840cdf652b392fb39b Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Wed, 23 Feb 2011 23:50:56 +0100 Subject: [PATCH 1/1] Try to describe load-balancing algorithms. --- ALGORITHMS | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100644 ALGORITHMS diff --git a/ALGORITHMS b/ALGORITHMS new file mode 100644 index 0000000..69a2545 --- /dev/null +++ b/ALGORITHMS @@ -0,0 +1,36 @@ +DESCRIPTIONS DES ALGORITHMES + +fairstrategy +============ +Tant qu'il reste un voisin moins chargé[*] que soi-même, envoyer une +certaine quantité de charge (delta = 0.001 dans le code) à tous les +voisins moins chargés que soi-même. +[*] en réalité, un voisin moins chargé à qui on peut envoyer delta de + charge sans devenir moins chargé que lui. + +Q: à quoi sert le tri du départ ? + +makhoul +======= +Ordonne les voisins du moins chargé au plus chargé puis calcule les +différences de charge entre soi-même et chacun des voisins. + +Ensuite, pour chaque voisin, dans l'ordre, et tant qu'on reste plus +chargé que le voisin en question, on lui envoie 1/(N+1) de la +différence calculée au départ, avec N le nombre de voisins. + +none +==== +Aucun équilibrage. Peut-être utile pour tester/déboguer le code. + +simple +====== +Tentative de respecter simplement les conditions de Bertsekas. +Parmi les voisins moins chargés que soi, on sélectionne : + - un des moins chargés (vmin) ; + - un des plus chargés (vmax), +puis on équilibre avec vmin en s'assurant que notre charge reste +toujours supérieure à celle de vmin et à celle de vmax. + +On envoie donc (avec "self" pour soi-même) : + min((load(self) - load(vmin)) / 2, (load(self) - load(vmax))) -- 2.39.5