From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Fri, 25 Feb 2011 14:55:23 +0000 (+0100)
Subject: Implement loba_besteffort.
X-Git-Tag: v0.1~94
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba.git/commitdiff_plain/673a449fe2844c664860cd553d83926fb8b66ceb

Implement loba_besteffort.
---

diff --git a/ALGORITHMS b/ALGORITHMS
index 11e7099..449fc12 100644
--- a/ALGORITHMS
+++ b/ALGORITHMS
@@ -1,5 +1,17 @@
 DESCRIPTIONS DES ALGORITHMES D'ÉQUILIBRAGE
 
+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.
+
+Les transferts de charge sont ensuite fait en visant cette moyenne pour
+tous les voisins sélectionnés.  On envoie une quantité de charge égale
+à (moyenne - charge_du_voisin).
+
+
 fairstrategy
 ============
 Ordonne les voisins du plus chargé au moins chargé.
diff --git a/TODO b/TODO
index 0d476f4..f95d336 100644
--- a/TODO
+++ b/TODO
@@ -1,11 +1,3 @@
-* Create git repo for papers.
-   Done.
-
-* Implement algorithm discussed on Feb. 23 with R.C.
-
-* Implement makhoul2 algorithm?
-   See source code for omnet++.
-
 * Implement some random initial distribution of load
    Options -r seed, -R [algo ?]
 
diff --git a/loba_besteffort.cpp b/loba_besteffort.cpp
index 18e8c0c..fa72730 100644
--- a/loba_besteffort.cpp
+++ b/loba_besteffort.cpp
@@ -6,8 +6,29 @@ XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(loba);
 
 void loba_besteffort::load_balance()
 {
-    // write code here...
-    xbt_die("Load-balancing algorithm besteffort not implemented!");
+    pneigh_sort_by_load(std::less<double>());
+    print_loads_p(false, xbt_log_priority_debug);
+
+    unsigned bound = pneigh.size();
+    double sum = get_load();
+    for (unsigned i = 0 ; i < bound ; ++i) {
+        if (get_load() <= pneigh[i]->get_load()) {
+            bound = i;
+        } else {
+            double newsum = sum + pneigh[i]->get_load();
+            if (pneigh[i]->get_load() <= newsum / (i + 2))
+                sum = newsum;
+            else
+                bound = i;
+        }
+    }
+
+    double mean = sum / (bound + 1);
+    for (unsigned i = 0 ; i < bound ; ++i) {
+        double transfer = mean - pneigh[i]->get_load();
+        send(pneigh[i], transfer);
+        XBT_DEBUG("sent %g to %s", transfer, pneigh[i]->get_name());
+    }
 }
 
 // Local variables: