\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
-\usepackage{newtxtext}
-\usepackage[cmintegrals]{newtxmath}
-%\usepackage{mathptmx,helvet,courier}
+%\usepackage{newtxtext}
+%\usepackage[cmintegrals]{newtxmath}
+\usepackage{mathptmx,helvet,courier}
\usepackage{amsmath}
\usepackage{graphicx}
network performance and the message size, the time of the reception of the
message also varies.
-In the following of this paper, Section~\ref{BT algo} describes the Bertsekas
-and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we present a
-possible problem in the convergence conditions. Section~\ref{Best-effort}
-presents the best effort strategy which provides an efficient way to reduce the
-execution times. This strategy will be compared with other ones, presented in
-Section~\ref{Other}. In Section~\ref{Virtual load}, the virtual load mechanism
-is proposed. Simulations allowed to show that both our approaches are valid
-using a quite realistic model detailed in Section~\ref{Simulations}. Finally we
-give a conclusion and some perspectives to this work.
+In the following of this paper, Section~\ref{sec.bt-algo} describes the
+Bertsekas and Tsitsiklis' asynchronous load balancing algorithm. Moreover, we
+present a possible problem in the convergence conditions.
+Section~\ref{sec.besteffort} presents the best effort strategy which provides an
+efficient way to reduce the execution times. This strategy will be compared
+with other ones, presented in Section~\ref{sec.other}. In
+Section~\ref{sec.virtual-load}, the virtual load mechanism is proposed.
+Simulations allowed to show that both our approaches are valid using a quite
+realistic model detailed in Section~\ref{sec.simulations}. Finally we give a
+conclusion and some perspectives to this work.
\section{Bertsekas and Tsitsiklis' asynchronous load balancing algorithm}
-\label{BT algo}
+\label{sec.bt-algo}
In order prove the convergence of asynchronous iterative load balancing
Bertsekas and Tsitsiklis proposed a model
the amount of load of processor $i$ at time $t+1$ is given by:
\begin{equation}
x_i(t+1)=x_i(t)-\sum_{j\in V(i)} s_{ij}(t) + \sum_{j\in V(i)} r_{ji}(t)
-\label{eq:ping-pong}
+\label{eq.ping-pong}
\end{equation}
x_3(t)=99.99\\
x_3^2(t)=99.99\\
\end{eqnarray*}
-In this case, processor $2$ can either sends load to processor $1$ or processor
-$3$. If it sends load to processor $1$ it will not satisfy condition
-(\ref{eq:ping-pong}) because after the sending it will be less loaded that
+In this case, processor $2$ can either sends load to processor $1$ or processor
+$3$. If it sends load to processor $1$ it will not satisfy condition
+(\ref{eq.ping-pong}) because after the sending it will be less loaded that
$x_3^2(t)$. So we consider that the \emph{ping-pong} condition is probably to
strong. Currently, we did not try to make another convergence proof without this
condition or with a weaker condition.
algorithm.
\section{Best effort strategy}
-\label{Best-effort}
+\label{sec.besteffort}
In this section we describe a new load-balancing strategy that we call
\emph{best effort}. First, we explain the general idea behind this strategy,
Concretely, once $s_{ij}$ has been evaluated as before, it is simply divided by
some configurable factor. That's what we named the ``parameter $k$'' in
-Section~\ref{Results}. The amount of data to send is then $s_{ij}(t) = (\bar{x}
-- x^i_j(t))/k$.
-\FIXME[check that it's still named $k$ in Sec.~\ref{Results}]{}
+Section~\ref{sec.results}. The amount of data to send is then $s_{ij}(t) =
+(\bar{x} - x^i_j(t))/k$.
+\FIXME[check that it's still named $k$ in Sec.~\ref{sec.results}]{}
\section{Other strategies}
-\label{Other}
+\label{sec.other}
Another load balancing strategy, working under the same conditions, was
previously developed by Bahi, Giersch, and Makhoul in
\section{Virtual load}
-\label{Virtual load}
+\label{sec.virtual-load}
In this section, we present the concept of \emph{virtual load}. In order to
use this concept, load balancing messages must be sent using two different kinds
\FIXME{describe integer mode}
\section{Simulations}
-\label{Simulations}
+\label{sec.simulations}
In order to test and validate our approaches, we wrote a simulator
using the SimGrid
characteristics of the running platform, etc. Then several metrics
are issued that permit to compare the strategies.
-The simulation model is detailed in the next section (\ref{Sim
- model}), and the experimental contexts are described in
-section~\ref{Contexts}. Then the results of the simulations are
-presented in section~\ref{Results}.
+The simulation model is detailed in the next section (\ref{sec.model}), and the
+experimental contexts are described in section~\ref{sec.exp-context}. Then the
+results of the simulations are presented in section~\ref{sec.results}.
\subsection{Simulation model}
-\label{Sim model}
+\label{sec.model}
In the simulation model the processors exchange messages which are of
two kinds. First, there are \emph{control messages} which only carry
\end{algorithm}
\paragraph{}\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}}
+ 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{sec.virtual-load}}
\subsection{Experimental contexts}
-\label{Contexts}
+\label{sec.exp-context}
In order to assess the performances of our algorithms, we ran our
simulator with various parameters, and extracted several metrics, that
\subsection{Experimental results}
-\label{Results}
+\label{sec.results}
In this section, the results for the different simulations will be presented,
and we'll try to explain our observations.
