X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/loba-papers.git/blobdiff_plain/15d3f44fef95b56cc33864881efb29f7b1b7e9ae..e5b137c77dc66ab0403d1b711352d7df14235075:/loba-besteffort/loba-besteffort.tex?ds=inline

diff --git a/loba-besteffort/loba-besteffort.tex b/loba-besteffort/loba-besteffort.tex
index ee788a5..b95f6d5 100644
--- a/loba-besteffort/loba-besteffort.tex
+++ b/loba-besteffort/loba-besteffort.tex
@@ -56,9 +56,7 @@
 \begin{abstract}
   Most of the time, asynchronous load balancing algorithms are extensively 
   studied from a theoretical point of view. The Bertsekas and Tsitsiklis'
-  algorithm~\cite
-  %[section~7.4]
-  {bertsekas+tsitsiklis.1997.parallel} is undeniably the best known algorithm for which the asymptotic convergence proof is given. 
+  algorithm~\cite{bertsekas+tsitsiklis.1997.parallel} is undeniably the best known algorithm for which the asymptotic convergence proof is given. 
   From a
   practical point of view, when a node needs to balance a part of its load to
   some of its neighbors, the algorithm's description is unfortunately too succinct, and no details are given on what is really sent and how the load balancing decisions are taken. In this paper, we
@@ -68,8 +66,7 @@
   and their variations \cite{bcvc07:bc}, both load transfer and load information messages are dissociated. 
   To speedup the convergence time of the load balancing process, we propose {\it a clairvoyant virtual load} heuristic. This heuristic allows a node receiving a load
   information message to integrate the future virtual load (if any) in its load's list, even if the load has not been received yet. This leads to have predictive snapshots of nodes' loads at each iteration of the load balancing process.  Consequently, the notified node sends a real part of its load to some of
-  its neighbors taking into account the virtual load it will receive in the subsequent time-steps. Based on the SimGrid simulator, some series of test-bed scenarios are considered and many QoS metrics are evaluated to show the usefulness of the proposed algorithm.  %In order to validate our approaches, we have defined a
- % simulator based on SimGrid which allowed us to conduct many experiments.
+  its neighbors taking into account the virtual load it will receive in the subsequent time-steps. Based on the SimGrid simulator, some series of test-bed scenarios are considered and several QoS metrics are evaluated to show the usefulness of the proposed algorithm.
 \end{abstract}
 
 % \begin{keywords}
@@ -172,7 +169,7 @@ decentralized conflict resolution. The developed algorithms are proven to conver
 
 In~\cite{tripathi2017non} a LB algorithm based on game theory is proposed for distributed data centers. The authors formulate the LB problem as a non-cooperative game among front-end proxy servers and characterize the structure of Nash equilibrium. Based on the obtained Nash equilibrium structure, they derive a LB algorithm to compute the Nash equilibrium. They show through simulations that the proposed algorithm ensures fairness among the users and a good average latency across all client regions. A hybrid task scheduling and load balancing dependent and independent tasks for master-slaves platforms are addressed in~In~\cite{liu2017dems}. To minimize the response time of the submitted jobs, the proposed algorithm which is called DeMS is split into three stages: i) communication overhead reduction between masters and slaves,  ii) task migration to keep the workload balanced iii) and precedence task graphs partitioning. 
 
-Several LB techniques, based on artificial intelligence, have also been proposed in the literature:  genetic algorithm (GA) \cite{subrata2007artificial}, honey bee behavior \cite{krishna2013honey, kwok2004new},  tabu search  \cite{subrata2007artificial} and fuzzy logic \cite{salimi2014task}. The main strength of these techniques comes from their ability to seek in large search spaces, which arises in many combinatorial optimization problems. For instance, the works in~\cite{cao2005grid, shen2014achieving} have been proposed to tackle the load balancing problem using the multiagent approach where each agent is responsible for load balancing for a subset of nodes in the network. The agent objective is to minimize jobs' response time and host idle time dynamically. In~\cite{GrosuC05}, the authors formulate the load balancing problem as a non-cooperative game among users. They use the Nash equilibrium as the solution of this game to optimize the response time of all jobs in the entire system. The proposed scheme guarantees the optimal task allocation for each user with low time complexity. A game theoretic approach to tackle the static load balancing problem is also investigated in~\cite{PenmatsaC11}. To provide fairness to all users in  the system, the load balancing problem is formulated as a non-cooperative game among the users to minimize the response time of the submitted users' jobs. As in~\cite{GrosuC05}, the authors use the concept of Nash equilibrium as the solution of a non-cooperative game. Simulation results show that the proposed scheme offers near optimal solutions compared to other existing techniques in terms of fairness.
+Several LB techniques, based on artificial intelligence, have also been proposed in the literature:  genetic algorithm (GA) \cite{subrata2007artificial}, honey bee behavior \cite{krishna2013honey, kwok2004new},  tabu search  \cite{subrata2007artificial} and fuzzy logic \cite{salimi2014task}. The main strength of these techniques comes from their ability to seek in large search spaces, which arises in many combinatorial optimization problems. For instance, the works in~\cite{cao2005grid, shen2014achieving} have been proposed to tackle the load balancing problem using the multi-agent approach where each agent is responsible for load balancing for a subset of nodes in the network. The agent objective is to minimize jobs' response time and host idle time dynamically. In~\cite{GrosuC05}, the authors formulate the load balancing problem as a non-cooperative game among users. They use the Nash equilibrium as the solution of this game to optimize the response time of all jobs in the entire system. The proposed scheme guarantees the optimal task allocation for each user with low time complexity. A game theoretic approach to tackle the static load balancing problem is also investigated in~\cite{PenmatsaC11}. To provide fairness to all users in  the system, the load balancing problem is formulated as a non-cooperative game among the users to minimize the response time of the submitted users' jobs. As in~\cite{GrosuC05}, the authors use the concept of Nash equilibrium as the solution of a non-cooperative game. Simulation results show that the proposed scheme offers near optimal solutions compared to other existing techniques in terms of fairness.
 
 
 
@@ -238,9 +235,8 @@ is linked to processor $2$ which is  also linked to processor $3$, but in which
 \end{align*}
 %{\bf RAPH, pourquoi il y a $x_3^2$?. Sinon il faudra reformuler la suite, c'est mal dit}
 
-Owing to the algorithm's specifications, processor $2$ can either send 
-a load to processor $1$ or processor
-$3$.  If it sends loads to processor $1$, it will not satisfy condition
+Owing to the algorithm's specifications, processor $2$ can either send a part of its load to processor $1$ or processor
+$3$.  If it sends to processor $1$, it will not satisfy condition
 \eqref{eq.ping-pong} because after that sending it will be less loaded than
 $x_3^2(t)$.  So we consider that the \emph{ping-pong} condition is probably too
 strong. %Currently, we did not try to make another convergence proof without this condition or with a weaker condition.
@@ -392,7 +388,7 @@ received yet.
 \section{Implementation with SimGrid and simulations}
 \label{sec.simulations}
 
-In order to test and validate our approache, we wrote a simulator
+In order to test and validate our approach, we wrote a simulator
 using the SimGrid
 framework~\cite{simgrid.web,casanova+giersch+legrand+al.2014.simgrid}.  This
 simulator, which consists of about 2,700 lines of C++, allows to run
@@ -751,12 +747,12 @@ that for small CCR values,  high communication costs play quite a significant ro
 communication becomes less important as the CCR values increase, since larger CCR values result in smaller communication times. The impact of CCR values were also tested on the performance of each algorithm in terms of idle times. From Figures~\ref{fig.results1} and ~\ref{fig.resultsN} virtual load scheme can be seen to achieve really good  average idle times, which is quite close to both its own simple version and its direct competitor {\it Bertsekas and Tsitsiklis} algorithm.  As expected, for coarse grain applications (CCR =10/1), idle times are close to 0 since processors are inactive most of the time compared to fine grain applications. 
 
 \smallskip 
-Taken as a whole, the results illustrated in Figures~\ref{fig.results1} and ~\ref{fig.resultsN} clearly show that our proposal outperforms the Betsekas and Tsistlikis algorithm. 
+Taken as a whole, the results illustrated in Figures~\ref{fig.results1} and ~\ref{fig.resultsN} clearly show that our proposal outperforms the Bertsekas and Tsitsiklis algorithm. 
 These results indicate that local load balancing decisions have a significant impact on the global 
-convergence time achieved by the compared strategies. This is because, upon load imbalance detection, assigning  an amount of load in an unfair way between neighbors will severely increase the total number of iterations required by the algorithm before reaching the final stable distributions. The reason of the poorer performance of {\it Bertsekas and tsistsilikis} algorithm  can be explained by the inconvenience of the iterative load balance policy adopted for load distribution between neighbors. Neighbors are selected in such a way that the {\it ping-pong} condition holds. Doing so, loads are not really assigned to processor neighbors which would allow them to be fairly balanced.  
+convergence time achieved by the compared strategies. This is because, upon load imbalance detection, assigning  an amount of load in an unfair way between neighbors will severely increase the total number of iterations required by the algorithm before reaching the final stable distributions. The reason of the poorer performance of {\it Bertsekas and Tsitsiklis} algorithm  can be explained by the inconvenience of the iterative load balance policy adopted for load distribution between neighbors. Neighbors are selected in such a way that the {\it ping-pong} condition holds. Doing so, loads are not really assigned to processor neighbors which would allow them to be fairly balanced.  
 
 \smallskip 
-Unlike the {\it Betsekas and Tsistlikis} algorithm, our approach is not really sensitive when dealing with realistic models of computation and communication. This is due to two main features: i) the use of "virtual load" transfers which allows nodes to predict the load they receive in the subsequent iterations steps, ii) and the greedy neighbors selection adopted by our algorithm at each time step in the load balancing process. The involved neighbors are selected in such a way that the load difference between the computational resources is minimized as much as possible. 
+Unlike the {\it Bertsekas and Tsitsiklis} algorithm, our approach is not really sensitive when dealing with realistic models of computation and communication. This is due to two main features: i) the use of "virtual load" transfers which allows nodes to predict the load they receive in the subsequent iterations steps, ii) and the greedy neighbors selection adopted by our algorithm at each time step in the load balancing process. The involved neighbors are selected in such a way that the load difference between the computational resources is minimized as much as possible. 
 
 \smallskip 
 Comparing the results of the extended version (with virtual load) to the results of the simple one, it can be observed in Figs.~\ref{fig.results1} and ~\ref{fig.resultsN} that the improved version gives the best performances. It always improves both convergence and idle times significantly in all figures. This is because, with virtual load transfers, the algorithm seeks greedily to ensure a certain degree of load balancing for processors by taking into account the information about the predictive loads not received yet. Consequently, this leads to optimizing the final convergence time of the load balancing process. Similarly, the extended version achieves much better results than the simple one when considering larger platforms, as shown in Figs.~\ref{fig.results1} and ~\ref{fig.resultsN}.
@@ -796,7 +792,7 @@ the virtual  load, most  of the time,  processors converge  to what is  called t
 obtain 10 9 8 7 6 6 7 8 9 10 instead of 8 8 8 8 8 8 8 8 8 8).
 
 \smallskip 
-To summarize  the simulation results led us to show that, with a few exceptions (without virtual load), our proposal is superior to the {\it Bertsekas and Tsiltsikis} algorithm in all the tested scenarios. The illustrated results indicate that network size, CCR values and initial load distribution have a significant impact on the algorithm's performances. Thus, this experimental study corroborates the usefulness of our algorithm, and confirms that when dealing with realistic model platforms, both  {\it best effort} strategy and {\it virtual load} transfers play an important role on the achieved idle and convergence times.
+To summarize  the simulation results led us to show that, with a few exceptions (without virtual load), our proposal is superior to the {\it Bertsekas and Tsitsiklis} algorithm in all the tested scenarios. The illustrated results indicate that network size, CCR values and initial load distribution have a significant impact on the algorithm's performances. Thus, this experimental study corroborates the usefulness of our algorithm, and confirms that when dealing with realistic model platforms, both  {\it best effort} strategy and {\it virtual load} transfers play an important role on the achieved idle and convergence times.
 
 
 
