ALGORITHMS

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