]> AND Private Git Repository - loba-papers.git/blobdiff - supercomp11/supercomp11.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
virtual load
[loba-papers.git] / supercomp11 / supercomp11.tex
index 81ee704bb811b9edf219d5f5ea9a92611f54705d..2d6b32f9fe83416293c196b9ed81a48505003692 100644 (file)
@@ -49,7 +49,7 @@ Moreover,  asynchronous  iterative  algorithms  in which  an  asynchronous  load
 balancing  algorithm is  implemented most  of the  time can  dissociate messages
 concerning load transfers and message  concerning load information.  In order to
 increase  the  converge of  a  load balancing  algorithm,  we  propose a  simple
-heuristic called \emph{virtual load} which allows a node that receives an load
+heuristic called \emph{virtual load} which allows a node that receives a load
 information message  to integrate the  load that it  will receive later  in its
 load (virtually) and consequently sends a (real) part of its load to some of its
 neighbors.  In order to  validate our  approaches, we  have defined  a simulator
@@ -268,6 +268,31 @@ C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.
 \section{Virtual load}
 \label{Virtual load}
 
+In this section,  we present the concept of \texttt{virtual  load}.  In order to
+use this concept, load balancing messages must be sent using two different kinds
+of  messages:  load information  messages  and  load  balancing messages.   More
+precisely, a node  wanting to send a part  of its load to one  of its neighbors,
+can first send  a load information message containing the load  it will send and
+then it  can send the load  balancing message containing data  to be transfered.
+Load information  message are really  short, consequently they will  be received
+very quickly.  In opposition, load  balancing messages are often bigger and thus
+require more time to be transfered.
+
+The  concept  of  \texttt{virtual load}  allows  a  node  that received  a  load
+information message to integrate the load that it will receive later in its load
+(virtually)  and consequently send  a (real)  part of  its load  to some  of its
+neighbors. In fact,  a node that receives a load  information message knows that
+later it  will receive the  corresponding load balancing message  containing the
+corresponding data.  So  if this node detects it is too  loaded compared to some
+of its neighbors  and if it has enough  load (real load), then it  can send more
+load  to  some of  its  neighbors  without waiting  the  reception  of the  load
+balancing message.
+
+Doing  this, we  can  expect a  faster  convergence since  nodes  have a  faster
+information of the load they will receive, so they can take in into account.
+
+\textbf{Question} Est ce qu'on donne l'algo avec virtual load?
+
 \section{Simulations}
 \label{Simulations}