Merge branch 'master' of ssh://info.iut-bm.univ-fcomte.fr/loba

[loba.git] / ALGORITHMS

diff --git a/ALGORITHMS b/ALGORITHMS
index f576427a758b146f7ada964e367a16aebb09a9ea..cc601b3848663f68cc21851e123a8b151480b385 100644 (file)
--- a/ALGORITHMS
+++ b/ALGORITHMS
@@ -1,10 +1,39 @@
 DESCRIPTIONS DES ALGORITHMES D'ÉQUILIBRAGE
 
 DESCRIPTIONS DES ALGORITHMES D'ÉQUILIBRAGE
 

+bulk
+====
+N'ordonne pas les voisins. Cherche le nombre de voisins de charge minimum et 
+le nombre de voisins de charge inferieure. En fonction de leur egalité ou non, 
+un parametre alpha est caclulé. En cas d'egalité, alpha=1/(NB_voisins_charge_minimale +1) 
+sinon alpha=1/(NB_voisins_charge_minimale +2). Chaque voisin dont la charge est inferieure 
+recoit alpha*(myLoad - charge_du_voisin). Ensuite, une correction est effectuée
+pour respecter la regle de Bertsekas.
+
+lln pour Least Loaded Neighbors
+===============================
+A l'origine écrit par Raphaël.
+Comme simple, mais tous les voisins de charge inferieure reçoivent de la charge 
+pas seulement un voisin de charge minimale. N'ordonne pas les voisins, et ne respecte 
+pas la regle de Bertsekas. Le parametre alpha vaut toujours (1/NB_voisins_charge_inferiure+1).
+
+besteffort
+==========
+Ordonne les voisins du moins chargé au plus chargé.
+Trouve ensuite, en les prenant dans ce ordre, le nombre maximal de
+voisins tels que tous ont une charge inférieure à la moyenne des
+charges des voisins sélectionnés, et de soi-même.
+
+Les transferts de charge sont ensuite fait en visant cette moyenne pour
+tous les voisins sélectionnés.  On envoie une quantité de charge égale
+à (moyenne - charge_du_voisin).
+
+

 fairstrategy
 ============
 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.
+Ordonne les voisins du plus chargé au moins chargé.
+Ensuite, 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.
 
 [*] en réalité, un voisin moins chargé à qui on peut envoyer delta de
     charge sans devenir moins chargé que lui.
 


@@ -28,6 +57,16 @@ ou bien
     - Algorithme 6 (p.111) dans la thèse de Abdallah Makhoul.
 
 
     - Algorithme 6 (p.111) dans la thèse de Abdallah Makhoul.
 
 

+makhoul2
+========
+Comme makhoul, mais la différence est calculée avec la charge courante
+(intégrant donc les envois déjà faits).
+
+Références:
+    - le code source :-(
+      cf. MAKHOUL.txt
+
+

 none
 ====
 Aucun équilibrage.  Peut-être utile pour tester/déboguer le code.
 none
 ====
 Aucun équilibrage.  Peut-être utile pour tester/déboguer le code.