X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba.git/blobdiff_plain/81ad8abd7ccfa8f084f91d74e4628d0d539b173f..e2dc20f5c76435eb341f8ba275e9f1ec8e5d5791:/ALGORITHMS?ds=inline diff --git a/ALGORITHMS b/ALGORITHMS index f576427..d73b675 100644 --- a/ALGORITHMS +++ b/ALGORITHMS @@ -1,16 +1,67 @@ DESCRIPTIONS DES ALGORITHMES D'ÃQUILIBRAGE +2besteffort +=========== +Calcule la moyenne des charges des voisins et de soi-même. +Ordonne ensuite les voisins du moins chargé au plus chargé, et +effectue les transferts en prenant les voisins dans cet ordre. Les +transferts de charge sont faits en visant cette moyenne pour tous les +voisins. On envoie une quantité de charge égale à + min(moyenne - charge_du_voisin, charge_propre - moyenne), +tant que cette quantité est positive. + +NB: Ceci est une variante de besteffort, la différence étant la + moyenne visée. + + +besteffort +========== +Ordonne les voisins du moins chargé au plus chargé. +Trouve ensuite, en les prenant dans ce ordre, le nombre maximal de +voisins tels que tous ont une charge inférieure à la moyenne des +charges des voisins sélectionnés, et de soi-même. + +Les transferts de charge sont ensuite faits en visant cette moyenne pour +tous les voisins sélectionnés. On envoie une quantité de charge égale +à (moyenne - charge_du_voisin). + + +bulk +==== +N'ordonne pas les voisins. Cherche le nombre de voisins de charge +minimum et le nombre de voisins de charge inférieure. En fonction de +leur égalité ou non, un paramètre alpha est calculé. En cas d'égalité, + alpha = 1 / (NB_voisins_charge_minimale + 1), +sinon + alpha = 1 / (NB_voisins_charge_minimale + 2). + +Chaque voisin dont la charge est inférieure reçoit + alpha * (myLoad - charge_du_voisin). +Ensuite, une correction est effectuée pour respecter la règle de +Bertsekas. + + fairstrategy ============ -Tant qu'il reste un voisin moins chargé[*] que soi-même, envoyer une -certaine quantité de charge (delta = 0.001 dans le code) à tous les -voisins moins chargés que soi-même. +Ordonne les voisins du plus chargé au moins chargé. +Ensuite, tant qu'il reste un voisin moins chargé[*] que soi-même, +envoyer une certaine quantité de charge (delta = 0.001 dans le code) à +tous les voisins moins chargés que soi-même. [*] en réalité, un voisin moins chargé à qui on peut envoyer delta de charge sans devenir moins chargé que lui. Q: à quoi sert le tri du départ ? +lln pour Least Loaded Neighbors +=============================== +à l'origine écrit par Raphaël. Comme simple, mais tous les voisins de +charge inférieure reçoivent de la charge pas seulement un voisin de +charge minimale. N'ordonne pas les voisins, et ne respecte pas la +règle de Bertsekas. Le paramètre alpha vaut toujours + 1 / (NB_voisins_charge_inferieure + 1). + + makhoul ======= Ordonne les voisins du moins chargé au plus chargé puis calcule les @@ -28,6 +79,16 @@ ou bien - Algorithme 6 (p.111) dans la thèse de Abdallah Makhoul. +makhoul2 +======== +Comme makhoul, mais la différence est calculée avec la charge courante +(intégrant donc les envois déjà faits). + +Références: + - le code source :-( + cf. MAKHOUL.txt + + none ==== Aucun équilibrage. Peut-être utile pour tester/déboguer le code.