ALGORITHMS

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