X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba.git/blobdiff_plain/5e43cdf74cfa40b69f5e7e9eb3957c43f4accb86..01d46f8470e36e1823d897496e0d915770bc867b:/ALGORITHMS?ds=sidebyside diff --git a/ALGORITHMS b/ALGORITHMS index 4a9b03c..53fe1f3 100644 --- a/ALGORITHMS +++ b/ALGORITHMS @@ -1,17 +1,46 @@ 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électionnes, et de soi-même. +charges des voisins sélectionnés, et de soi-même. -Les transferts de charge sont ensuite fait en visant cette moyenne pour +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 ============ Ordonne les voisins du plus chargé au moins chargé. @@ -24,6 +53,15 @@ tous les voisins moins chargés que soi-même. 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 @@ -51,6 +89,12 @@ Références: cf. MAKHOUL.txt +makhoul3 +======== +Comme makhoul mais, dans le ratio 1/(N+1), N correspond au nombre de +voisins moins chargés. + + none ==== Aucun équilibrage. Peut-être utile pour tester/déboguer le code.