Implement loba_besteffort.

diff --git a/ALGORITHMS b/ALGORITHMS
index 11e70999d94b00d001bee22e63375c941b90989c..449fc12e18d8d2c2c67785318e5fdb4dbb950e08 100644 (file)
--- 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 0d476f49b6f3ff0e3bf14a98c9a9e41a6ffbcc56..f95d336a2009f6e63adb2d3c7d25c4dd31ee26e1 100644 (file)
--- 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 18e8c0c790591c1df0fa654e41d6e11847714431..fa7273075397ebe1b673850c560e31f219c7a947 100644 (file)
--- 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: