-
\documentclass[smallextended]{svjour3}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\begin{document}
-\title{Best effort strategy and virtual load for asynchronous iterative load balancing}
+\title{Best effort strategy and virtual load
+ for asynchronous iterative load balancing}
\author{Raphaël Couturier \and
Arnaud Giersch \and
Abderrahmane Sider
}
-\institute{F. Author \at
- first address \\
- Tel.: +123-45-678910\\
- Fax: +123-45-678910\\
- \email{fauthor@example.com} % \\
-% \emph{Present address:} of F. Author % if needed
+\institute{R. Couturier \and A. Giersch \at
+ LIFC, University of Franche-Comté, Belfort, France \\
+ % Tel.: +123-45-678910\\
+ % Fax: +123-45-678910\\
+ \email{%
+ raphael.couturier@univ-fcomte.fr,
+ arnaud.giersch@univ-fcomte.fr}
\and
- S. Author \at
- second address
+ A. Sider \at
+ University of Béjaïa, Béjaïa, Algeria \\
+ \email{ar.sider@univ-bejaia.dz}
}
\maketitle
\section{Best effort strategy}
\label{Best-effort}
+\textbf{À traduire} 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électionnés, 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).
+
+~\\\textbf{Question} faut-il décrire les stratégies makhoul et simple ?
+
+\paragraph{simple} Tentative de respecter simplement les conditions de Bertsekas.
+Parmi les voisins moins chargés que soi, on sélectionne :
+\begin{itemize}
+\item un des moins chargés (vmin) ;
+\item un des plus chargés (vmax),
+\end{itemize}
+puis on équilibre avec vmin en s'assurant que notre charge reste
+toujours supérieure à celle de vmin et à celle de vmax.
+On envoie donc (avec "self" pour soi-même) :
+\[
+ \min\left(\frac{load(self) - load(vmin)}{2}, load(self) - load(vmax)\right)
+\]
+
+\paragraph{makhoul} Ordonne les voisins du moins chargé au plus chargé
+puis calcule les différences de charge entre soi-même et chacun des
+voisins.
+
+Ensuite, pour chaque voisin, dans l'ordre, et tant qu'on reste plus
+chargé que le voisin en question, on lui envoie 1/(N+1) de la
+différence calculée au départ, avec N le nombre de voisins.
+
+C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.
\section{Virtual load}
\label{Virtual load}
\subsection{Simulation model}
\label{Sim model}
+\begin{verbatim}
+Communications
+==============
+
+There are two receiving channels per host: control for information
+messages, and data for load transfers.
+
+Process model
+=============
+
+Each process is made of 3 threads: a receiver thread, a computing
+thread, and a load-balancer thread.
+
+* Receiver thread
+ ---------------
+
+ Loop
+ | wait for a message to come, either on data channel, or on ctrl channel
+ | push received message in a buffer of received messages
+ | -> ctrl messages on the one side
+ | -> data messages on the other side
+ +-
+
+ The loop terminates when a "finalize" message is received on each
+ channel.
+
+* Computing thread
+ ----------------
+
+ Loop
+ | if we received some real load, get it (data messages)
+ | if there is some real load to send, send it
+ | if we own some load, simulate some computing on it
+ | sleep a bit if we are looping too fast
+ +-
+ send CLOSE on data for all neighbors
+ wait for CLOSE on data from all neighbors
+
+ The loop terminates when process::still_running() returns false.
+ (read the source for full details...)
+
+* Load-balancing thread
+ ---------------------
+
+ Loop
+ | call load-balancing algorithm
+ | send ctrl messages
+ | sleep (min_lb_iter_duration)
+ | receive ctrl messages
+ +-
+ send CLOSE on ctrl for all neighbors
+ wait for CLOSE on ctrl from all neighbors
+
+ The loop terminates when process::still_running() returns false.
+ (read the source for full details...)
+\end{verbatim}
+
\subsection{Validation of our approaches}
\label{Results}
