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électionnes, et de soi-même.
   9
  10 Les transferts de charge sont ensuite fait 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 fairstrategy
  16 ============
  17 Ordonne les voisins du plus chargé au moins chargé.
  18 Ensuite, tant qu'il reste un voisin moins chargé[*] que soi-même,
  19 envoyer une certaine quantité de charge (delta = 0.001 dans le code) à
  20 tous les voisins moins chargés que soi-même.
  21 [*] en réalité, un voisin moins chargé à qui on peut envoyer delta de
  22     charge sans devenir moins chargé que lui.
  23
  24 Q: à quoi sert le tri du départ ?
  25
  26
  27 makhoul
  28 =======
  29 Ordonne les voisins du moins chargé au plus chargé puis calcule les
  30 différences de charge entre soi-même et chacun des voisins.
  31
  32 Ensuite, pour chaque voisin, dans l'ordre, et tant qu'on reste plus
  33 chargé que le voisin en question, on lui envoie 1/(N+1) de la
  34 différence calculée au départ, avec N le nombre de voisins.
  35
  36 Références:
  37     - Algorithm 2 dans
  38       http://portal.acm.org/citation.cfm?id=1459693.1459708
  39       http://info.iut-bm.univ-fcomte.fr/staff/giersch/biblio.html#bahi_giersch_makhoul.2008.scalable
  40 ou bien
  41     - Algorithme 6 (p.111) dans la thèse de Abdallah Makhoul.
  42
  43
  44 makhoul2
  45 ========
  46 Comme makhoul, mais la différence est calculée avec la charge courante
  47 (intégrant donc les envois déjà faits).
  48
  49 Références:
  50     - le code source :-(
  51       cf. MAKHOUL.txt
  52
  53
  54 none
  55 ====
  56 Aucun équilibrage.  Peut-être utile pour tester/déboguer le code.
  57
  58
  59 simple
  60 ======
  61 Tentative de respecter simplement les conditions de Bertsekas.
  62 Parmi les voisins moins chargés que soi, on sélectionne :
  63     - un des moins chargés (vmin) ;
  64     - un des plus chargés (vmax),
  65 puis on équilibre avec vmin en s'assurant que notre charge reste
  66 toujours supérieure à celle de vmin et à celle de vmax.
  67
  68 On envoie donc (avec "self" pour soi-même) :
  69     min((load(self) - load(vmin)) / 2, (load(self) - load(vmax)))