ALGORITHMS

   1 DESCRIPTIONS DES ALGORITHMES D'ÉQUILIBRAGE
   2
   3 2besteffort
   4 ===========
   5 Calcule la moyenne des charges des voisins et de soi-même.
   6 Ordonne ensuite les voisins du moins chargé au plus chargé, et
   7 effectue les transferts en prenant les voisins dans cet ordre.  Les
   8 transferts de charge sont faits en visant cette moyenne pour tous les
   9 voisins.  On envoie une quantité de charge égale à
  10         min(moyenne - charge_du_voisin, charge_propre - moyenne),
  11 tant que cette quantité est positive.
  12
  13 NB: Ceci est une variante de besteffort, la différence étant la
  14     moyenne visée.
  15
  16
  17 besteffort
  18 ==========
  19 Ordonne les voisins du moins chargé au plus chargé.
  20 Trouve ensuite, en les prenant dans ce ordre, le nombre maximal de
  21 voisins tels que tous ont une charge inférieure à la moyenne des
  22 charges des voisins sélectionnés, et de soi-même.
  23
  24 Les transferts de charge sont ensuite faits en visant cette moyenne pour
  25 tous les voisins sélectionnés.  On envoie une quantité de charge égale
  26 à (moyenne - charge_du_voisin).
  27
  28
  29 bulk
  30 ====
  31 N'ordonne pas les voisins. Cherche le nombre de voisins de charge
  32 minimum et le nombre de voisins de charge inférieure. En fonction de
  33 leur égalité ou non, un paramètre alpha est calculé. En cas d'égalité,
  34         alpha = 1 / (NB_voisins_charge_minimale + 1),
  35 sinon
  36         alpha = 1 / (NB_voisins_charge_minimale + 2).
  37
  38 Chaque voisin dont la charge est inférieure reçoit
  39         alpha * (myLoad - charge_du_voisin).
  40 Ensuite, une correction est effectuée pour respecter la règle de
  41 Bertsekas.
  42
  43
  44 fairstrategy
  45 ============
  46 Ordonne les voisins du plus chargé au moins chargé.
  47 Ensuite, tant qu'il reste un voisin moins chargé[*] que soi-même,
  48 envoyer une certaine quantité de charge (delta = 0.001 dans le code) à
  49 tous les voisins moins chargés que soi-même.
  50 [*] en réalité, un voisin moins chargé à qui on peut envoyer delta de
  51     charge sans devenir moins chargé que lui.
  52
  53 Q: à quoi sert le tri du départ ?
  54
  55
  56 lln pour Least Loaded Neighbors
  57 ===============================
  58 À l'origine écrit par Raphaël.  Comme simple, mais tous les voisins de
  59 charge inférieure reçoivent de la charge pas seulement un voisin de
  60 charge minimale. N'ordonne pas les voisins, et ne respecte pas la
  61 règle de Bertsekas. Le paramètre alpha vaut toujours
  62         1 / (NB_voisins_charge_inferieure + 1).
  63
  64
  65 makhoul
  66 =======
  67 Ordonne les voisins du moins chargé au plus chargé puis calcule les
  68 différences de charge entre soi-même et chacun des voisins.
  69
  70 Ensuite, pour chaque voisin, dans l'ordre, et tant qu'on reste plus
  71 chargé que le voisin en question, on lui envoie 1/(N+1) de la
  72 différence calculée au départ, avec N le nombre de voisins.
  73
  74 Références:
  75     - Algorithm 2 dans
  76       http://portal.acm.org/citation.cfm?id=1459693.1459708
  77       http://info.iut-bm.univ-fcomte.fr/staff/giersch/biblio.html#bahi_giersch_makhoul.2008.scalable
  78 ou bien
  79     - Algorithme 6 (p.111) dans la thèse de Abdallah Makhoul.
  80
  81
  82 makhoul2
  83 ========
  84 Comme makhoul, mais la différence est calculée avec la charge courante
  85 (intégrant donc les envois déjà faits).
  86
  87 Références:
  88     - le code source :-(
  89       cf. MAKHOUL.txt
  90
  91
  92 makhoul3
  93 ========
  94 Comme makhoul mais, dans le ratio 1/(N+1), N correspond au nombre de
  95 voisins moins chargés.
  96
  97
  98 none
  99 ====
 100 Aucun équilibrage.  Peut-être utile pour tester/déboguer le code.
 101
 102
 103 simple
 104 ======
 105 Tentative de respecter simplement les conditions de Bertsekas.
 106 Parmi les voisins moins chargés que soi, on sélectionne :
 107     - un des moins chargés (vmin) ;
 108     - un des plus chargés (vmax),
 109 puis on équilibre avec vmin en s'assurant que notre charge reste
 110 toujours supérieure à celle de vmin et à celle de vmax.
 111
 112 On envoie donc (avec "self" pour soi-même) :
 113     min((load(self) - load(vmin)) / 2, (load(self) - load(vmax)))