Define macros for the names "best effort" and "Makhoul".

[loba-papers.git] / loba-besteffort / loba-besteffort.tex

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index d97c653be563ee1915ef68bb7ee074fa40bf5dd2..36b1fbe1d1049c4cd29fe450e4e2ac535ebda5fd 100644 (file)
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -27,6 +27,9 @@
 
 \newcommand{\VAR}[1]{\textit{#1}}
 
 
 \newcommand{\VAR}[1]{\textit{#1}}
 

+\newcommand{\besteffort}{\emph{best effort}}
+\newcommand{\makhoul}{\emph{Makhoul}}
+

 \begin{document}
 
 \begin{frontmatter}
 \begin{document}
 
 \begin{frontmatter}


@@ -54,7 +57,7 @@
   the most well known algorithm for which the convergence proof is given. From a
   practical point of view, when a node wants to balance a part of its load to
   some of its neighbors, the strategy is not described.  In this paper, we
   the most well known algorithm for which the convergence proof is given. From a
   practical point of view, when a node wants to balance a part of its load to
   some of its neighbors, the strategy is not described.  In this paper, we

-  propose a strategy called \emph{best effort} which tries to balance the load
+  propose a strategy called \besteffort{} which tries to balance the load

   of a node to all its less loaded neighbors while ensuring that all the nodes
   concerned by the load balancing phase have the same amount of load.  Moreover,
   asynchronous iterative algorithms in which an asynchronous load balancing
   of a node to all its less loaded neighbors while ensuring that all the nodes
   concerned by the load balancing phase have the same amount of load.  Moreover,
   asynchronous iterative algorithms in which an asynchronous load balancing


@@ -101,7 +104,7 @@ Although  the Bertsekas  and Tsitsiklis'  algorithm describes  the  condition to
 ensure the convergence,  there is no indication or  strategy to really implement
 the load distribution. In other word, a node  can send a part of its load to one
 or   many  of   its  neighbors   while  all   the  convergence   conditions  are
 ensure the convergence,  there is no indication or  strategy to really implement
 the load distribution. In other word, a node  can send a part of its load to one
 or   many  of   its  neighbors   while  all   the  convergence   conditions  are

-followed. Consequently,  we propose a  new strategy called  \emph{best effort}
+followed. Consequently,  we propose a  new strategy called  \besteffort{}

 that tries to balance the load of  a node to all its less loaded neighbors while
 ensuring that all the nodes concerned  by the load balancing phase have the same
 amount of  load.  Moreover, when real asynchronous  applications are considered,
 that tries to balance the load of  a node to all its less loaded neighbors while
 ensuring that all the nodes concerned  by the load balancing phase have the same
 amount of  load.  Moreover, when real asynchronous  applications are considered,


@@ -210,12 +213,12 @@ algorithm.
 \label{sec.besteffort}
 
 In this section we describe a new load-balancing strategy that we call
 \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,
+\besteffort{}.  First, we explain the general idea behind this strategy,

 and then we describe some variants of this basic strategy.
 
 \subsection{Basic strategy}
 
 and then we describe some variants of this basic strategy.
 
 \subsection{Basic strategy}
 

-The general idea behind the \emph{best effort} strategy is that each processor,
+The general idea behind the \besteffort{} strategy is that each processor,

 that detects it has more load than some of its neighbors, sends some load to the
 most of its less loaded neighbors, doing its best to reach the equilibrium
 between those neighbors and himself.
 that detects it has more load than some of its neighbors, sends some load to the
 most of its less loaded neighbors, doing its best to reach the equilibrium
 between those neighbors and himself.


@@ -289,7 +292,7 @@ Section~\ref{sec.results}.  The amount of data to send is then $s_{ij}(t) =
 Another load balancing strategy, working under the same conditions, was
 previously developed by Bahi, Giersch, and Makhoul in
 \cite{bahi+giersch+makhoul.2008.scalable}.  In order to assess the performances
 Another load balancing strategy, working under the same conditions, was
 previously developed by Bahi, Giersch, and Makhoul in
 \cite{bahi+giersch+makhoul.2008.scalable}.  In order to assess the performances

-of the new \emph{best effort}, we naturally chose to compare it to this anterior
+of the new \besteffort{}, we naturally chose to compare it to this anterior

 work.  More precisely, we will use the algorithm~2 from
 \cite{bahi+giersch+makhoul.2008.scalable} and, in the following, we will
 reference it under the name of Makhoul's.
 work.  More precisely, we will use the algorithm~2 from
 \cite{bahi+giersch+makhoul.2008.scalable} and, in the following, we will
 reference it under the name of Makhoul's.


@@ -501,7 +504,7 @@ we will describe in this section.
 \subsubsection{Load balancing strategies}
 
 Several load balancing strategies were compared.  We ran the experiments with
 \subsubsection{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
+the \besteffort{}, and with the \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},
   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},


@@ -509,7 +512,7 @@ and with \emph{integer} load.
 
 To summarize the different load balancing strategies, we have:
 \begin{description}
 
 To summarize the different load balancing strategies, we have:
 \begin{description}

-\item[\textbf{strategies:}] \emph{Makhoul}, or \emph{Best effort} with $k\in
+\item[\textbf{strategies:}] \makhoul{}, or \besteffort{} with $k\in

   \{1,2,4\}$
 \item[\textbf{variants:}] with, or without virtual load
 \item[\textbf{domain:}] real load, or integer load
   \{1,2,4\}$
 \item[\textbf{variants:}] with, or without virtual load
 \item[\textbf{domain:}] real load, or integer load


@@ -714,7 +717,14 @@ platform sizes.  Some bars are missing, specially for large platforms.  This is
 either because the algorithm did not reach the convergence state in the
 allocated time, or because we simply decided not to run it.
 
 either because the algorithm did not reach the convergence state in the
 allocated time, or because we simply decided not to run it.
 

-\FIXME{donner les premières conclusions, annoncer le plan de la suite}
+\FIXME{annoncer le plan de la suite}
+
+\subsubsection{The \besteffort{} strategy}
+
+Looking at the graph on figure~\ref{fig.results1}, we can see that the
+\besteffort{} strategy is not too bad, compared to the \makhoul{} strategy.
+
+\FIXME{donner les premières conclusions}

 \FIXME{comparer be/makhoul -> be tient la route (parler du cas réel uniquement)}
 
 \subsubsection{With the virtual load extension}
 \FIXME{comparer be/makhoul -> be tient la route (parler du cas réel uniquement)}
 
 \subsubsection{With the virtual load extension}