+\begin{algorithm}
+ \caption{Load-balancing}
+ \label{algo.lb}
+ \While{true}{%
+ \While{\VAR{ctrl\_fifo} is not empty}{%
+ pop a message from \VAR{ctrl\_fifo}\;
+ identify the sender of the message,
+ and update the current knowledge of its load\;
+ }
+ run the load-balancing algorithm to make the decision about load transfers\;
+ \ForEach{neighbor $n$}{%
+ send a control messages to $n$\;
+ }
+ ensure that the main loop does not iterate too fast\;
+ }
+\end{algorithm}
+
+\paragraph{}
+For the sake of simplicity, a few details were voluntary omitted from
+these descriptions. For an exhaustive presentation, we refer to the
+actual source code that was used for the experiments%
+\footnote{As mentioned before, our simulator relies on the SimGrid
+ framework~\cite{casanova+legrand+quinson.2008.simgrid}. For the
+ experiments, we used a pre-release of SimGrid 3.7 (Git commit
+ 67d62fca5bdee96f590c942b50021cdde5ce0c07, available from
+ \url{https://gforge.inria.fr/scm/?group_id=12})}, and which is
+available at
+\url{http://info.iut-bm.univ-fcomte.fr/staff/giersch/software/loba.tar.gz}.
+
+\FIXME{ajouter des détails sur la gestion de la charge virtuelle ?
+par ex, donner l'idée générale de l'implémentation. l'idée générale est déja décrite en section~\ref{Virtual load}}
+
+\subsection{Experimental contexts}
+\label{Contexts}
+
+In order to assess the performances of our algorithms, we ran our
+simulator with various parameters, and extracted several metrics, that
+we will describe in this section.
+
+\paragraph{Load balancing strategies}
+
+Several load balancing strategies were compared. We ran the experiments with
+the \emph{Best effort}, and with the \emph{Makhoul} strategies. \emph{Best
+ effort} was tested with parameter $k = 1$, $k = 2$, and $k = 4$. Secondly,
+each strategy was run in its two variants: with, and without the management of
+\emph{virtual load}. Finally, we tested each configuration with \emph{real},
+and with \emph{integer} load.
+
+To summarize the different load balancing strategies, we have:
+\begin{description}
+\item[\textbf{strategies:}] \emph{Makhoul}, or \emph{Best effort} with $k\in
+ \{1,2,4\}$
+\item[\textbf{variants:}] with, or without virtual load
+\item[\textbf{domain:}] real load, or integer load
+\end{description}
+%
+This gives us as many as $4\times 2\times 2 = 16$ different strategies.
+
+\paragraph{End of the simulation}
+
+The simulations were run until the load was nearly balanced among the
+participating nodes. More precisely the simulation stops when each node holds
+an amount of load at less than 1\% of the load average, during an arbitrary
+number of computing iterations (2000 in our case).
+
+Note that this convergence detection was implemented in a centralized manner.
+This is easy to do within the simulator, but it's obviously not realistic. In a
+real application we would have chosen a decentralized convergence detection
+algorithm, like the one described by Bahi, Contassot-Vivier, Couturier, and
+Vernier in \cite{10.1109/TPDS.2005.2}.
+
+\paragraph{Platforms}
+
+In order to show the behavior of the different strategies in different
+settings, we simulated the executions on two sorts of platforms. These two
+sorts of platforms differ by their underlaid network topology. On the one hand,
+we have homogeneous platforms, modeled as a cluster. On the other hand, we have
+heterogeneous platforms, modeled as the interconnection of a number of clusters.
+
+The clusters were modeled by a fixed number of computing nodes interconnected
+through a backbone link. Each computing node has a computing power of
+1~GFlop/s, and is connected to the backbone by a network link whose bandwidth is
+of 125~MB/s, with a latency of 50~$\mu$s. The backbone has a network bandwidth
+of 2.25~GB/s, with a latency of 500~$\mu$s.
+
+The heterogeneous platform descriptions were created by taking a subset of the
+Grid'5000 infrastructure\footnote{Grid'5000 is a French large scale experimental
+ Grid (see \url{https://www.grid5000.fr/}).}, as described in the platform file
+\texttt{g5k.xml} distributed with SimGrid. Note that the heterogeneity of the
+platform here only comes from the network topology. Indeed, since our
+algorithms currently do not handle heterogeneous computing resources, the
+processor speeds were normalized, and we arbitrarily chose to fix them to
+1~GFlop/s.
+
+Then we derived each sort of platform with four different number of computing
+nodes: 16, 64, 256, and 1024 nodes.
+
+\paragraph{Configurations}
+
+The distributed processes of the application were then logically organized along
+three possible topologies: a line, a torus or an hypercube. We ran tests where
+the total load was initially on an only node (at one end for the line topology),
+and other tests where the load was initially randomly distributed across all the
+participating nodes. The total amount of load was fixed to a number of load
+units equal to 1000 times the number of node. The average load is then of 1000
+load units.
+
+For each of the preceding configuration, we finally had to choose the
+computation and communication costs of a load unit. We chose them, such as to
+have three different computation over communication cost ratios, and hence model
+three different kinds of applications:
+\begin{itemize}
+\item mainly communicating, with a computation/communication cost ratio of $1/10$;
+\item mainly computing, with a computation/communication cost ratio of $10/1$ ;
+\item balanced, with a computation/communication cost ratio of $1/1$.
+\end{itemize}
