ALGORITHMS

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