X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba.git/blobdiff_plain/673a449fe2844c664860cd553d83926fb8b66ceb..4d5ec9803b74d0f3e9c002a92a748bd08b6640ac:/ALGORITHMS diff --git a/ALGORITHMS b/ALGORITHMS index 449fc12..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 @@ -48,7 +86,13 @@ Comme makhoul, mais la différence est calculée avec la charge courante Références: - le code source :-( - cf. makhoul.txt + cf. MAKHOUL.txt + + +makhoul3 +======== +Comme makhoul mais, dans le ratio 1/(N+1), N correspond au nombre de +voisins moins chargés. none