%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{doublecol}
%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{amssymb}
\usepackage{amsbsy,natbib}
\usepackage{amsthm}
\usepackage{amsfonts,amsmath,bm}
\usepackage[dvipsone]{epsfig}
\RequirePackage{graphics,epsf}

%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%

\LRH{Comparative analysis of the prototype and the simulator of a
new load balancing algorithm}

\RRH{R.F. de Mello, L.C. Trevelin, M.S.V. de Paiva and L.T. Yang}

\VOL{1}

\ISSUE{1/2/3}

\PUBYEAR{2004}

\setcounter{page}{1}

\LRH{Comparative analysis of the prototype and the simulator of a
new load balancing algorithm}

\RRH{R.F. de Mello, L.C. Trevelin, M.S.V. de Paiva and L.T. Yang}

\VOL{I}

\ISSUE{1/2/3}

\PUBYEAR{2004}

\BottomCatch

\title{Comparative analysis of the prototype and the simulator
of a new load balancing algorithm for heterogeneous computing
environments}

\authorA{R.F. de Mello*}

\affA{Institute of Mathematical Sciences and Computing, \\
University of S\~{a}o Paulo, S\~{a}o Carlos, Brazil \\ E-mail:
mello@icmc.usp.br \\ *Corresponding author}

\authorB{L.C. Trevelin}

\affB{Department of Computer Science, \\ Federal University of
S\~{a}o Carlos, Brazil \\ E-mail: trevelin@dc.ufscar.br}

\authorC{M.S.V. de Paiva}

\affC{Department of Electrical Engineering, \\ S\~{a}o Carlos
Engineering School, \\ University of S\~{a}o Paulo, Brazil
\\ E-mail: mstela@sel.eesc.usp.br,}

\authorD{Laurence Tianruo Yang}

\affD{Department of Computer Science, \\ St Francis Xavier
University, Canada \\ E-mail: lyang@stfx.ca}

\begin{abstract}
The availability of low cost hardware has increased the
development of distributed systems. The allocation of resources
in these systems may be optimised through the use of a load
balancing algorithm. The load balancing algorithms are
responsible for the homogeneous distribution of the occupation in
the environment, with the aim of obtaining gains on the final
performance. This paper presents and analyses a new load
balancing algorithm that is based on a logical computer tree
hierarchy. The analysis is made using results obtained by a
simulator and a prototype of this algorithm. The algorithm
simulations show a significant performance gain, by lowering the
response times and the number of messages that pass through the
communication system to perform the load balancing operations.
After good results were obtained by the simulations, a prototype
was built and validated such results.
\end{abstract}

\KEY{load balancing algorithm; heterogeneous environments; high
performance; simulation; prototype.}

\REF{to this paper should be made as follows: de Mello, R.F.,
Trevelin, L.C., de Paiva, M.S.V. and Yang, L.T. (2004)
`Comparative analysis of the prototype
  and the simulator of a new load balancing algorithm for
heterogeneous computing environments', Int. J. High Performance
Computing and Networking, Vol. 1, Nos. 1/2/3, pp.64--74.}

\BIO{Rodrigo Fernandes de Mello is a Professor at The Institute
of Mathematical Sciences and Computing at the University of
S\~{a}o Paulo, S\~{a}o Carlos, Brazil. He completed his PhD
degree from University of S\~{a}o Paulo, S\~{a}o Carlos in 2003.
 Since 1998 he has been researching in distributed
systems, real time kernels and internet.}

\maketitle

\section{INTRODUCTION}

\noindent The availability of low cost microprocessors and the
evolution of computing networks have increased and enabled the
construction of distributed systems. On such systems, the
processes are executed on network computers and communicate to
each other to perform a collaborative computing task. In order to
distribute the processes among the computers of these systems, a
load balancing algorithm may be adopted.

The load balancing algorithms are responsible for the equal
distribution of the processes load among the computers of an
environment. \cite{Krueger and Livny} demonstrate that load
balancing methods can reduce the average and standard deviation
of processes response times. Shorter response times are
desirable, as they are related to high performance in the
execution of the processes.

The load balancing algorithms involve four policies:
transference, selection, location and information
\citep{Shivaratrietal,Sinha}. The transference policy determines
whether a computer is in a suitable state to participate in a
task transfer, either as server or receiver of the processes. The
selection policy defines the process that should be transferred
from the busiest computer to the idlest one. The location policy
is responsible to find a suitable transfer partner (sender or
receiver) for a computer once the transfer policy has decided
about its state. A serving computer offers the processes when it
is overloaded, a receiving computer requests processes when it is
idle. The information policy defines when and how the information
on the computers' availability is updated on the system.

Several load balancing methods have been proposed
\citep{Shivaratrietal,Zhou and Ferrari,Theimer and Lantz}.
 According to \cite{Shivaratrietal}, these algorithms can be
subdivided into:

\begin{itemize}
\item server-initiated
\item receiver-initiated
\item symmetric initiated
\item stable server-initiated
\item stable symmetrically initiated.
\end{itemize}
Out of these algorithm classes, the one that shows the highest performance
is the stable symmetrically initiated.

Despite recent works on load balancing (\citealp{Hui and
Chanson,Mitzenmacher00,Anderson and
Abraham,Amir,Kostinetal,Figueira and Berman,Zomaya and
Teh,Zhang,Mitzenmacher01,Woodside and
Monforton,Pageetal,Hsuetal}), the studies and algorithms from
\cite{Krueger and Livny}, \cite{Zhou and Ferrari}, \cite{Theimer
and Lantz} and \cite{Shivaratrietal} have been considered the
main works for this area. The recent work does bring significant
contributions to the processes' performance and reduction of the
number of messages on the computer network. The recent work in
this area, presented in this paper, is based on the main studies
of the load balancing area.

\begin{figure}
\centerline{\epsffile{R:/SANTYPE/JOURNALS/TAYLOR&FRANCIS/LMBD/34(02)/174543/images/F03.eps}}
\caption{A 2-D, 9-velocity lattice (Q9D2) model A 2-D, 9-velocity
lattice (Q9D2) model A 2-D, 9-velocity lattice (Q9D2) model A 2-D,
9-velocity lattice (Q9D2) model A 2-D, 9-velocity lattice (Q9D2)
model A 2-D, 9-velocity lattice (Q9D2) model\label{fig2}}
\end{figure}

Later on,
\cite{Melloetal02a,Melloetal02b,Melloetal02c,Melloetal02d}, during
others studies on clusters and distributed systems, observed and
proposed a new method for load balancing. Through these studies
they concluded that by choosing a load index based on the process
behaviour and on the computer capacity at the environment, it would
be possible to obtain better results \citep{Melloetal03}. Based on
these studies, the authors show a comparative study between the
Lowest load balancing algorithm using the new load index and the
original Stable Symmetrically Initiated algorithm. According to the
obtained results in \cite{Melloetal03}, the improved Lowest
algorithm shows the highest performance. These analyses confirm
that the adequate load index choice modifies the behaviour of the
load balancing algorithm.

Vital aspects for the success of a load balancing algorithm are:
stability on the number of messages generated in order to not
overload the communication system; support for environments
composed of heterogeneous computers and processes; low cost
update on the environment load information; low cost choice for
the ideal computers to execute a process received by the system;
stability on high load; system scalability, and short response
times. The study and analysis of each of the above mentioned
aspects influenced the definition of a new load balancing
algorithm named TLBA (Tree Load Balancing Algorithm).

\begin{figure*}%%5
\centerline{\epsffile{R:/SANTYPE/JOURNALS/TAYLOR&FRANCIS/lmmp/21(05)/147125/Images/F05.eps}}
\caption{Effect of multiple welds on mechanical properties of
single-pass (SP) and double-pass (DP) Cp-Ti weldments compared with
the as-received material (B): (a) yield strength, (b) ultimate
strength, (c) elongation, and (d) hardness.\label{fig5}}
\end{figure*}

This paper presents the TLBA, a new load balancing algorithm
focusing on environments where: high scalability; support for
heterogeneous processes and computers; small number of messages
that pass through the communication system; stability on high
loads, and short response times are desired. A comparative study
between the TLBA and the improved Lowest algorithm has been
realised by \cite{Melloetal03} using simulators. The TLBA is
compared to improved Lowest algorithm, because the last yielded
better results than Stable symmetrically initiated. After
simulating and proving the performance gains of TLBA, a prototype
has been implemented. This prototype was submitted to tests and the
results confirmed the values obtained through the simulations.

\begin{table*}[htbp]
\begin{center}
\caption{Response time variation of the lowest
algorithm to the different occupations of the process}
\begin{tabular}{|l|c|c|}
\hline &{\it Average response time of the} &{\it Average response
time}\\ {\it Occupation}&{\it
 improved lowest algorithm}& {\it of the TLBA}
\\ \hline 1.00~E~+~01 & { 6.1275533000~E+~05}&
{6.0450143000~E~+~05}
\\ \hline {1.00~E~+~02}& { 6.3940207300~E~+~06}&
{6.3176135300~E~+~06} \\ \hline { 1.00~E~+~03}&
{6.4152160200~E~+~07}& {6.3446532460~E~+~07}
\\ \hline {1.00~E~+~04}& {6.4098737963~E~+~08}&
{6.3473560175~E~+~08} \\ \hline {1.00~E~+~05}& {
6.4189585691~E~+~09}& {6.3476263532~E~+~09} \\ \hline {
1.00~E~+~06}& {6.5020352364~E~+~10}& {6.3476532508~E~+~10}
\\ \hline {1.00~E~+~07}& {6.4361410067~E~+~11}&
{6.3476559492~E~+~11} \\ \hline {1.00~E~+~08}& {
6.4261208947~E~+~12}& {6.3476562200~E~+~12} \\ \hline {
1.00~E~+~09}& {6.4770720080~E~+~13}& {6.3476562470~E~+~13}
\\ \hline {1.00~E~+~10}& {6.4230638584~E~+~14}&
{6.3476562497~E~+~14} \\ \hline {1.00~E~+~11}& {
6.5764266304~E~+~15}& {6.3476562500~E~+~15} \\ \hline {
1.00~E~+~12}& {6.4104959239~E~+~16}& {6.3476562500~E~+~16}
\\ \hline
\end{tabular}
\label{tab1}
\end{center}
\end{table*}

The paper has been divided into the following Sections: Section 2
presents the State of Art; Section 3 presents the Tree Load
Balancing algorithm; Section 4 presents comparative studies based
on simulations; Section 5 presents the TLBA prototype and compares
it to the results obtained on the simulations; Section 6 presents
the conclusions.

\section{STATE OF THE ART}

Among the main studies on load balancing, we may highlight the
ones by \cite{Zhou and Ferrari}, \cite{Theimer and Lantz},
\cite{Shivaratrietal}, and \cite{Melloetal03}. Other recent works
were proposed \citep{Hui and Chanson,Mitzenmacher00,Anderson and
Abraham,Amir,Kostinetal,Figueira and Berman, Zomaya and
Teh,Zhang,Mitzenmacher01,Woodside and Monforton,Pageetal,
Hsuetal}; however they do not offer significant performance
contributions. These recent works are also based on the studies
of \cite{Zhou and Ferrari}, \cite{Theimer and
 Lantz} and \cite{Shivaratrietal92}.

\cite{Zhou and Ferrari} evaluate four server-initiated load
balancing algorithms, i.e., initiated by the most overloaded
computer. These algorithms are: Disted, Global, Central, Random and
Lowest. On Disted, when a computer realises any alteration on its
load, it emits messages to the other computers to inform them about
its current load. On Global, there is a computer that centralises
all the computers' load information on that environment and this
centralising computer sends broadcasts to the environment in order
to keep the other ones updated about the situation. On Central, as
on Global, a central computer receives all the load information of
the system; however, it does not update the other computers about
it. This centralising computer decides about the resources
allocation at the environment. On Random, no information about the
environment load is handled. On this algorithm, a computer is
selected at random in order to receive a process to be initiated.
On Lowest, the load information is sent when demanded. When a
computer starts a process, it requests information and analyses the
loads of a small set of computers and submits the processes to the
idlest one. The idlest computer has the shortest processes queue.

When \cite{Zhou and Ferrari} analysed the Disted, Global,
Central, Random and Lowest algorithms, they reached the
conclusion that all of them show a performance higher than the
one presented by a system with no load balancing at all. However,
the Lowest algorithm showed the highest performance of all. This
algorithm generates demand messages to transfer the process,
causes a lower overload on the communication system and, thus,
allows the incremental growth of the environment. The number of
generated messages in an environment does not depend on the
number of computers.

\cite{Theimer and Lantz} have implemented algorithms similar to
the Central, Disted and Lowest ones. Nevertheless, they have
analysed such algorithms in systems composed of a larger number
of computers (about 70). For the Disted and Lowest ones, some
process receiver and sender groups were created. The
communication within these groups was made by using a multicast
protocol, in order to minimise the messages exchange among the
computers. Computers with load lower than an inferior limit
participate in the process receiver group whilst the computers
with load higher than a superior limit participate in the process
sender group.

\begin{table}[htbp]
\begin{center}
\caption{Lowest algorithm response times for
the different process occupation at a heterogeneous system}
\begin{tabular}{|c|c|}
\hline
{\it Average response time of the} &{\it Average response time}\\
{\it improved lowest algorithm}& {\it of the TLBA}\\
{6.1275533000~E+~05}& {6.0450143000~E~+~05}\\\hline
{ 6.3940207300~E~+~06}&{6.3176135300~E~+~06} \\ \hline
{6.4152160200~E~+~07}& {6.3446532460~E~+~07}\\ \hline
{6.4098737963~E~+~08}&{6.3473560175~E~+~08} \\ \hline
{6.4189585691~E~+~09}& {6.3476263532~E~+~09} \\ \hline
{6.5020352364~E~+~10}& {6.3476532508~E~+~10}\\ \hline
{6.4361410067~E~+~11}&{6.3476559492~E~+~11} \\ \hline
{6.4261208947~E~+~12}& {6.3476562200~E~+~12} \\ \hline
{6.4770720080~E~+~13}& {6.3476562470~E~+~13}\\ \hline
{6.4230638584~E~+~14}&{6.3476562497~E~+~14} \\ \hline
{6.5764266304~E~+~15}& {6.3476562500~E~+~15} \\ \hline
{6.4104959239~E~+~16}& {6.3476562500~E~+~16}\\ \hline
\end{tabular}
\label{tab1}
\end{center}
\end{table}

Theimer and Lantz recommend decentralised algorithms such as
Lowest and Disted, as they do not generate single points of fault
as Central does. Central presents the highest performance for
small and medium size networks but it degrades on large
environments.

Through the analyses, \cite{Theimer and Lantz} concluded that
algorithms such as Lowest work with the probability of a computer
being idle. They assume system homogeneity as they use the size
of the CPU's waiting queue as load index. The process behaviour
is not analysed; therefore, the actual load of each computer is
not measured.

\cite{Shivaratrietal} analyse the algorithms, server-initiated,
receiver-initiated, symmetrically initiated, adaptative
symmetrically initiated and stable symmetrically initiated. In
these studies, the length of the process waiting queue at the CPU
was considered as the load index. This measure has been chosen
because it is simple and therefore, consumes fewer resources.

Shivaratri et al. have concluded that the receiver-initiated
algorithms present a higher performance than the server-initiated
ones, such as Lowest. In their conclusions, the algorithm that
showed the highest final performance was the stable symmetrically
initiated one. This algorithm preserves the history of the load
information exchanged in the system and takes actions to transfer
the processes by using this information.

\cite{Melloetal03} analyse a load index based on the process
behaviour as well as on the system computers capacity. The
authors propose a comparison between the Stable Symmetrically
Initiated algorithm by \cite{Shivaratrietal} and the improved
Lowest algorithm. The improved Lowest uses an analysis of the
process behaviour, as well as the system computers' capacity as
load index. Through these studies, it was concluded that, by
using a new load index, the Lowest algorithm provides better
response times. These results were reached through the simulation
of homogeneous and heterogeneous environments.

\section{THE TREE LOAD BALANCING ALGORITHM}

The TLBA algorithm, named Tree Load Balancing Algorithm, creates
a virtual interconnecting tree among the computers of the system.
On this tree, each computer of an $N$ level sends its updated
load information to the $N-1$ level computers. The lower the
level is, the closer it is to the root. The root is located on
level zero.

The selection of the best computer to execute a process received
by the system, works as a deep search on the interconnecting
tree. Thus, a level $N$ computer may define which of its branches
located in level $N+1$ presents the lowest occupation, by
re-passing a search message that is propagated through all the
branches of the tree until it finds the idlest computer.

The tree may be defined as a non-cyclic connected graph. $ G=(
X,U)$ being a graph, where $X$ is the set of vertices and $U$ is
the set of edges which interconnects an ordered pair. This graph
presents $n>2$, where $n$ is the maximum number of elements of
the vertices set and satisfies the following properties:

\begin{itemize}
\item $G$ is connected and non-cyclic
\item $G$ is non-cyclic and has $n-1$ edges
\item $G$ is connected and has $n-1$ edges
\item $G$ is non-cyclic and, by adding one edge, only one cycle is created
\item $G$ is connected, but stops being so if one edge is suppressed
\item Every $G$'s vertices pair is connected by only one simple chain.
\end{itemize}
After defining the tree, it is necessary to define the  levels
that make it up. Being the same oriented graph $G=(X,U)$ shown
before, a partition of $N$ of the set $X$ may be defined as:
\[
N=\{N0, N1,\ldots, Nr\}
\]
where the elements $N0,N1,\ldots,Nr$, called levels, are arranged
by the inclusion of their $R^{-1}(xi)$ as follows:

\begin{itemize}
\item $N0=\{xi/R^{-1} (xi)=\{\}\}$
\item $N1=\{xi/R^{-1}(xi)C N0\}$
\item $N2=\{xi/R^{-1}(xi)C(N0 U N1)\}$
\item $Nr=\{xi/R^{-1}(xi)C U (de k=0a r-1)Nk\}$
\end{itemize}
$R^{-1}(xi)$ is the set of predecessor vertices of an element
$xi$ of the set of vertices $X$. Every vertice $xi$ only has
predecessors in the previous levels. The last level of the tree
is depicted by $R^{+}(Nr)=\{\}$, where $Nr$ is the largest level
and $R+(Nr)$ the set of vertices which succeed the level $Nr$.

\subsection{Information policy}

On TLBA, each computer of the system has an updated table with
the occupation information. This table includes information about
the computer as well about the other computers in its subtree.
The subtree of a computer $\alpha$, located on level $N$, is
given by all the computers from the level $N+1$, which succeed to
a computer through an oriented arch. The computer $\alpha$
participates in this subtree, being defined as its father.

The computers at level {\it N~+~}1 send information about their
load to the predecessor computer located on the level {\it N}.
The father computer generates a single number that represents its
occupation and the one of its subtree. To make this calculation,
the father computer sums up the occupation related to the
capacities of each computer of its subtree, generating a single
load value for the subtree controlled by it. The load value is
propagated until the root node.

A computer located in level $N+1$ only sends its load information
when the change exceeds a certain threshold percentage value.
Assuming a threshold of 5{\%}, the current load is compared to
the one taken at the latest reading; if the current load is 5{\%}
above or below the previous load, then the load information is
sent to the father computer, which is located in the level {\it
N}. The definition of this threshold allows the decrease in the
number of messages related to the information update on the
system. Decreasing the communication system load increases the
stability (Shivaratri et al., 1992).

\subsection{Load index calculation}

The load index used by TLBA is based on the analysis of the CPU
and memory resources consumed by the processes. This load index
proposed by \cite{Melloetal} is detailed as following.

Consider as the occupation of the computing resources $O_r
(t,i)$, where: $i$ identifies the analysed computer; $r$ is the
computing resource analysed (CPU and main memory) and $t$ is the
occupation reading instant.

%Consider the equation (1) as the percentage of CPU resource occupation,
%where: {\it $\lambda $} is the total quantum of each process; {\it $\mu $}
%is portion of the time {\it $\lambda $} in which the CPU was effectively
%used by one process and {\it p} is the number of system processes.
%\begin{equation}
%\label{eq1}
%{\rm O}_{cpu} =\frac{\sum\nolimits_{i=0}^p {\frac{\mu _i }{\lambda _i }}
%}{p}
%\end{equation}
%Consider the equation (2) as the percentage of main memory resource
%occupation, where: {\it $\theta $} is the total amount of main memory; {\it
%$\sigma $} is the amount of main memory used by a process and {\it p} is the
%number of system processes.
%\begin{equation}
%\label{eq2}
%{\rm O}_{mem} =\frac{\left( {\sum\nolimits_{i=0}^p {\sigma _i } }
%\right)}{\theta }
%\end{equation}
%The new load index, {\it I}$_{comp}$, is defined by the equation (3), where:
%${\rm O}_{cpu} $ is the percentage of CPU resource occupation and ${\rm
%O}_{mem} $ is the percentage of main memory resource occupation.
%\begin{equation}
%\label{eq3}
%I_{comp} =\frac{(O_{cpu} +O_{mem} )}{2}
%\end{equation}
%This load index considers the CPU and memory occupations of each computer of
%the system. The occupation of each resource is divided by its total
%capacity, generating an occupation percentage. By summing up the CPU and
%memory occupations it is generated as a single index, which is handled by
%the whole system.
%
%This load index helps the load balancing algorithm \newline
%to define the load states of the computers with \newline
%higher precision. This precision improves the homogeneity of load
%distribution (Shivaratri et al., 1992; Mello \newline
%et al., 2003).
%
%{\small {\bf 3.3 Location policy}}
%
%The selection of the best computer to execute a process received by the
%system is made by using the tables contained in each computer of the tree.
%Each computer has the updated information related to its subtree. This
%information is propagated until it reaches the root computer of the system,
%located at level zero. A request to execute the process in the system is
%always received by the root computer and this computer starts a deep search
%through the tree until it finds the best computer of the environment.
%
%The deep search in the tree is started on the root computer. This computer
%compares its load to the ones belonging to the other computers of its
%subtree. Observe that the root computer does not have the load information
%of all system computers. The root computer has only a load value that
%resumes the load of its subtrees. If the root computer had all system
%computers' load it could send the process directly to the laziest node. This
%technique would be similar to the Central algorithm (Zhou and Ferrari,
%1987), generating many messages, overloading the computer network. In case
%the root computer has the lowest load, it executes the process. If not, it
%sends a request to the best computer of its subtree, which continues the
%same searching process until it finds the idlest computer in the system.
%
%{\small {\bf 3.4 Transference policy}}
%
%The TLBA provides support for the check pointing and migration of processes
%initiated in the system. When a computer updates its local load information
%it also analyses the percentage occupation of the system. In case the system
%load is above a pre-determined limit it generates an analysis message for
%the migration of processes that will follow. This message is sent to the
%root computer of the system, which calculates the average occupation of the
%whole system.
%
%The average occupation of the whole system is calculated by dividing the
%total load of the system by the number of computers. The root computer is
%capable of making this calculation as it has the updated load information of
%the whole system. This value, calculated by the root computer, is sent back
%to the computer that has sent an analysis message for the migration that
%will follow.
%
%The computer that sent an analysis message for the succeeding migration
%compares its load to the average load of the remaining computers of the
%system. If its load is higher than the other ones, it starts the check
%pointing and requests the root computer to search for the idlest computer in
%the system (Section 3.3). After finding the idlest computer, it submits one
%of its processes. If its load is lower or similar to the ones belonging to
%the remaining computers in the system, it does not make the check pointing
%and migration of processes.
%
%{\small {\bf 3.5 Other considerations}}
%
%The computers participate in the tree through the decisions made by a
%Broker. This Broker is a software component, which receives interested
%computers' requisitions in participating in the tree. The Broker defines
%where a computer will be put. The goal of the Broker is to create a balanced
%tree according to the computer's capacity. The computer's capacity is
%measured though a benchmark program; this program is run before the computer
%is placed in the tree.
%
%The computers of a higher or lower level detect the failure of a computer.
%The higher levels identify failures when trying to send load information
%(Section 3.1). The lower levels identify failures when selecting the best
%computer to run a process (Section 3.3). Once a computer detects a failure
%it sends a message to the Broker, which remounts the tree structure. The
%Broker can be running on several computers avoiding a single point of
%failure. If a system administrator does not want to use the Broker, he/she
%can manually configure the environment, setting the tree levels and
%computers per level. However, manual configurations cannot use the
%advantages of the failure treatment offered by the Broker.
%
%Another relevant aspect is that the system administrator defines the number
%of nodes per tree level. Several nodes per level can increase the generated
%messages between levels, overloading the computer network. Fewer nodes per
%level make difficult, the deep search to find the best computer to run a
%process (Section 3.3).
%
%{\small {\bf 4 SIMULATIONS}}
%
%The simulations compare the behaviour of the TLBA to the improved Lowest
%(Mello et al., 2003). The improved Lowest is chosen because it showed a
%better performance than the Stable Symmetrically Initiated (Mello et al.,
%2003) which was proposed by Shivaratri et al. (1992) as the best solution.
%The simulations are subdivided into the following groups:
%
%\begin{itemize}
%\item simulations analysing a small system composed of computers with homogeneous and heterogeneous processing capacity
%\item simulations analysing a large system composed of computers with homogeneous and heterogeneous processing capacity
%\item simulations to analyse the number of messages that pass through the TLBA and improved Lowest communication system.
%\end{itemize}
%These simulation groups permit analyses of TLBA on different systems and to
%check its possibilities. We \newline
%used seven computers for the small system and 781 for the large ones. These
%numbers were chosen just to create symmetrical trees for the tests. For
%seven computers it created a tree composed of three levels, where it was two
%computers per level. For 781 computers it created a tree composed by five
%levels, where it was five computers \newline
%per level.
%
%This section uses tables to present the simulation results, because they
%show more data precision. A Poisson point distribution was used to simulate
%the process arrival at the system; the same probability distribution
%function used by Zhou and Ferrari (1987), Theimer and Lantz (1988) and
%Shivaratri et al. (1992).
%
%The following sections show the simulation groups and their respective
%analyses.
%
%{\small {\bf 4.1 Comparing TLBA and improved lowest average response times
%on small systems}}
%
%Table 1 presents the results obtained by the simulations conducted on an
%environment composed of seven homogeneous computers. The improved Lowest
%algorithm considered a subset of three computers to define the idlest one
%and, therefore, to receive a process initiated in the system. The Poisson
%probability distribution function used to define the processes arrival has
%an average of 100~seconds. The capacity of each computer in the system is
%368 cycles per millisecond. 320 processes have been submitted to the system.
%
%Table 2 shows the results obtained on the simulations conducted in an
%environment composed of seven heterogeneous computers. In this simulation we
%used a Poisson probability distribution function to define the processes
%arrival with average of 100~seconds. The capacity of four computers of the
%system is 368 cycles per \newline
% \newline
% \newline
%millisecond and the other three computers have processing capacity of 139
%cycles per millisecond. 320 processes have been submitted to the system and
%a subset of three computers was considered to find the idlest computer in
%the improved Lowest algorithm.
%
%{\small {\bf Table 1~~~}}{\small {\it Response time variation of the lowest
%algorithm to the different occupations of the process}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Occupation per process }}{\small (cycles)}{\small  }&
%{\small {\it Average response time of the improved lowest algorithm in a homogeneous environment }}{\small (ms)}{\small  }&
%{\small {\it Average response time of the TLBA in a homogeneous environment }}{\small (ms)}{\small  } \\
%\hline
%{\small 1.00~E~+~01}&
%{\small 6.1275533000~E+~05}&
%{\small 6.0450143000~E~+~05} \\
%\hline
%{\small 1.00~E~+~02}&
%{\small 6.3940207300~E~+~06}&
%{\small 6.3176135300~E~+~06} \\
%\hline
%{\small 1.00~E~+~03}&
%{\small 6.4152160200~E~+~07}&
%{\small 6.3446532460~E~+~07} \\
%\hline
%{\small 1.00~E~+~04}&
%{\small 6.4098737963~E~+~08}&
%{\small 6.3473560175~E~+~08} \\
%\hline
%{\small 1.00~E~+~05}&
%{\small 6.4189585691~E~+~09}&
%{\small 6.3476263532~E~+~09} \\
%\hline
%{\small 1.00~E~+~06}&
%{\small 6.5020352364~E~+~10}&
%{\small 6.3476532508~E~+~10} \\
%\hline
%{\small 1.00~E~+~07}&
%{\small 6.4361410067~E~+~11}&
%{\small 6.3476559492~E~+~11} \\
%\hline
%{\small 1.00~E~+~08}&
%{\small 6.4261208947~E~+~12}&
%{\small 6.3476562200~E~+~12} \\
%\hline
%{\small 1.00~E~+~09}&
%{\small 6.4770720080~E~+~13}&
%{\small 6.3476562470~E~+~13} \\
%\hline
%{\small 1.00~E~+~10}&
%{\small 6.4230638584~E~+~14}&
%{\small 6.3476562497~E~+~14} \\
%\hline
%{\small 1.00~E~+~11}&
%{\small 6.5764266304~E~+~15}&
%{\small 6.3476562500~E~+~15} \\
%\hline
%{\small 1.00~E~+~12}&
%{\small 6.4104959239~E~+~16}&
%{\small 6.3476562500~E~+~16} \\
%\hline
%\end{tabular}
%\label{tab1}
%\end{center}
%\end{table}
%
%{\small {\bf Table 2~~~}}{\small {\it Lowest algorithm response times for
%the different process occupation at a heterogeneous system}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Occupation per process }}{\small (cycles)}{\small  }&
%{\small {\it Average response time of the improved lowest algorithm in a heterogeneous environment }}{\small (ms)}{\small  }&
%{\small {\it Average response time of the TLBA in a heterogeneous environment }}{\small (ms)}{\small  } \\
%\hline
%{\small 1.00~E~+~01}&
%{\small 8.7436701000~E~+~05}&
%{\small 8.3431215000~E~+~05} \\
%\hline
%{\small 1.00~E~+~02}&
%{\small 8.9294303600~E~+~06}&
%{\small 8.6260096700~E~+~06} \\
%\hline
%{\small 1.00~E~+~03}&
%{\small 8.9918432930~E~+~07}&
%{\small 8.6541094870~E~+~07} \\
%\hline
%{\small 1.00~E~+~04}&
%{\small 8.9724402245~E~+~08}&
%{\small 8.6569206619~E~+~08} \\
%\hline
%{\small \textsc{1.00~E}}{\small ~}{\small \textsc{+~05}}&
%{\small 8.9697114641~E~+~09}&
%{\small 8.6572026521~E~+~09} \\
%\hline
%{\small 1.00~E~+~06}&
%{\small 9.0185968863~E~+~10}&
%{\small 8.6572308610~E~+~10} \\
%\hline
%{\small 1.00~E~+~07}&
%{\small 9.0240793834~E~+~11}&
%{\small 8.6572336769~E~+~11} \\
%\hline
%{\small 1.00~E~+~08}&
%{\small 8.9810014499~E~+~12}&
%{\small 8.6572339589~E~+~12} \\
%\hline
%{\small 1.00~E~+~09}&
%{\small 8.9777274689~E~+~13}&
%{\small 8.6572339869~E~+~13} \\
%\hline
%{\small 1.00~E~+~10}&
%{\small 8.9860080004~E~+~14}&
%{\small 8.6572339897~E~+~14} \\
%\hline
%{\small 1.00~E~+~11}&
%{\small 8.9554548820~E~+~15}&
%{\small 8.6572339900~E~+~15} \\
%\hline
%{\small 1.00~E~+~12}&
%{\small 8.9532098574~E~+~16}&
%{\small 8.6572339900~E~+~16} \\
%\hline
%\end{tabular}
%\label{tab2}
%\end{center}
%\end{table}
%
%Analysing the results presented in Tables 1 and 2 we can conclude that the
%average response times of TLBA are lower than the ones generated by the
%improved Lowest algorithm. Thus, we can conclude that TLBA offers higher
%performance and consequently the better results.
%
%{\small {\bf 4.2 Comparing TLBA and improved lowest average response times
%on large systems}}
%
%The following simulations compare the improved Lowest to the TLBA in a
%homogeneous environment composed of 781 computers. On these simulations,
%35,145 processes were submitted to the environment, based on the Poisson
%probability distribution function with average 100~seconds. Each computer
%capacity is 368~cycles/ms. For the Lowest algorithm it considered a subset
%of eleven computers that were selected on a random basis and their loads
%were analysed to allow the definition of the idlest computer. Table 3
%presents the results obtained on the simulations.
%
%The same environment composed of 781 computers was simulated, however, this
%time computers with heterogeneous capacities were used: 391 of them had a
%368~cycles/ms capacity and 390 of them had a 139~cycles/ms capacity. The
%results obtained on these simulations are shown in Table 4.
%
%{\small {\bf Table~3~~~}}{\small {\it Response time related to the
%occupation per process of lowest algorithm}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Occupation per process }}{\small (cycles)}{\small  }&
%{\small {\it Average response time of the improved lowest algorithm in a homogeneous environment }}{\small (ms)}{\small  }&
%{\small {\it Average response time of the TLBA in a homogeneous environment }}{\small (ms)}{\small  } \\
%\hline
%{\small 1.00~E~+~04}&
%{\small 6.2159995608~E~+~08}&
%{\small 6.2156474184~E~+~08} \\
%\hline
%{\small 1.00~E~+~05}&
%{\small \textsc{6.2469085561}}{\small ~}{\small \textsc{E}}{\small ~}{\small \textsc{+}}{\small ~}{\small \textsc{09}}&
%{\small 6.2465734548~E~+~09} \\
%\hline
%{\small 1.00~E~+~06}&
%{\small 6.2500016636~E~+~10}&
%{\small 6.2496667285~E~+~10} \\
%\hline
%{\small 1.00~E~+~07}&
%{\small 6.2503193101~E~+~11}&
%{\small 6.2499760509~E~+~11} \\
%\hline
%{\small 1.00~E~+~08}&
%{\small 6.2503454303~E~+~12}&
%{\small 6.2500069804~E~+~12} \\
%\hline
%{\small 1.00~E~+~09}&
%{\small 6.2503491403~E~+~13}&
%{\small 6.2500100731~E~+~13} \\
%\hline
%{\small 1.00~E~+~10}&
%{\small 6.2503482897~E~+~14}&
%{\small 6.2500103823~E~+~14} \\
%\hline
%{\small 1.00~E~+~11}&
%{\small 6.2503475474~E~+~15}&
%{\small 6.2500104132~E~+~15} \\
%\hline
%{\small 1.00~E~+~12}&
%{\small 6.2503488649~E~+~16}&
%{\small 6.2500104163~E~+~16} \\
%\hline
%\end{tabular}
%\label{tab3}
%\end{center}
%\end{table}
%
%{\small {\bf Table~4~~~}}{\small {\it Response times obtained at different
%process occupations of lowest algorithm}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Occupation per process }}{\small (cycles)}{\small  }&
%{\small {\it Average Response Time of the Improved Lowest Algorithm in an homogeneous environment }}{\small (ms)}{\small  }&
%{\small {\it Average Response Time of the TLBA in an homogeneous environment }}{\small (ms)}{\small  } \\
%\hline
%{\small 1.00~E~+~04}&
%{\small 9.0352098932~E~+~08}&
%{\small 9.0349469055~E~+~08} \\
%\hline
%{\small \textsc{1.00~E~+~05}}&
%{\small 9.0661207290~E~+~09}&
%{\small 9.0658727685~E~+~09} \\
%\hline
%{\small \textsc{1.00~E~+~06}}&
%{\small 9.0692197539~E~+~10}&
%{\small 9.0689656981~E~+~10} \\
%\hline
%{\small 1.00~E~+~07}&
%{\small 9.0695255607~E~+~11}&
%{\small 9.0692749095~E~+~11} \\
%\hline
%{\small 1.00~E~+~08}&
%{\small 9.0695560153~E~+~12}&
%{\small 9.0693058444~E~+~12} \\
%\hline
%{\small 1.00~E~+~09}&
%{\small 9.0695569517~E~+~13}&
%{\small 9.0693089372~E~+~13} \\
%\hline
%{\small 1.00~E~+~10}&
%{\small 9.0695613143~E~+~14}&
%{\small 9.0693092466~E~+~14} \\
%\hline
%{\small 1.00~E~+~11}&
%{\small 9.0695587575~E~+~15}&
%{\small 9.0693092776~E~+~15} \\
%\hline
%{\small 1.00~E~+~12}&
%{\small 9.0695602819~E~+~16}&
%{\small 9.0693092806~E~+~16} \\
%\hline
%\end{tabular}
%\label{tab4}
%\end{center}
%\end{table}
%
%Analysing the results presented in Tables 3 and 4 we can conclude that the
%average response times of TLBA are lower than the ones generated by the
%improved Lowest algorithm. Thus, we can conclude that TLBA offers higher
%performance and consequently, better results.
%
%{\small {\bf 4.3 Simulations that analyse the number of messages generated
%for the TLBA and improved lowest algorithms}}
%
%Simulations were carried out to analyse the traffic of messages exchanged
%among the computers when using the TLBA and improved Lowest algorithms. The
%simulated environment is composed of seven computers segmented into three
%levels with two computers on each level. In the improved Lowest case, the
%subset of computers analysed before the load balancing operation is composed
%of three computers. The number of processes that arrive at the system varies
%from 10 to 350. The Poisson probability distribution function related to the
%process arrival has an average of 3~s. Each computer capacity is 368 cycles
%per millisecond.
%
%The graph on Figure 2 shows the number of messages exchanged among the
%computers on Lowest algorithm and among TLBA levels.
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.27in,height=2.10in]{sample2.eps}}
%\label{fig2}
%\end{figure}
%
%{\small {\bf Figure 2~~~}}{\small {\it Number of messages exchanged among
%the computers on lowest and TLBA algorithms}}
%
%Due to the TLBA tree format it is possible to segment each level at a
%physically distinct network and this causes less overload on the
%communication system. Figure 2 shows three simulated situations: the first
%one using the TLBA where there is a physically distinct network for each
%level; the improved Lowest, and the TLBA in a physically single network.
%
%The TLBA generates fewer messages per level than the ones generated by the
%improved lowest. The number of messages that pass through the communication
%network is much higher on lowest. Even when using the TLBA in a single
%network, there is a significant decrease in the number of messages when
%compared to the lowest.
%
%Both TLBA and improved Lowest show variations in the number of messages
%depending on the number of executed processes. Lowest generates messages
%based on the computers subset analysed to initiate a load balancing
%operation, whilst TLBA generates a deep search message about the tree to
%search the best computer to execute the process. The TLBA also generates
%updating messages on the environment occupation and these messages run from
%the leaves to the root of the virtual tree.
%
%Analysing Table 5, we may conclude that the number of messages on the TLBA
%is 8.647 times lower. The TLBA on a single network generates 2.88235 times
%less messages than the improved Lowest. In both situations the TLBA causes
%less overload to the communication system.
%
%{\small {\bf Table 5~~~}}{\small {\it Number of messages achieved at 350
%processes of the environment}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small {\it Improved lowest}}&
%{\small {\it TLBA}}&
%{\small {\it TLBA at a single network}} \\
%\hline
%{\small 2,450}&
%{\small 283.3333}&
%{\small 850.00} \\
%\hline
%\end{tabular}
%\label{tab5}
%\end{center}
%\end{table}
%
%{\small {\bf 4.4 Simulations varying the number of computers per level}}
%
%Simulations were conducted to analyse the impacts caused by the variation on
%the number of levels and number of computers per level that make up the TLBA
%tree.
%
%The environment used on these simulations contained 781 homogeneous
%computers with a capacity of 368 cycles per millisecond. 3,000 processes
%were submitted to the environment based on the Poisson probability
%distribution function with average 3~seconds. Three situations were
%simulated for the TLBA:
%
%\begin{itemize}
%\item the first one had two levels with one computer at the first level and 780 at the second one
%\item the second one had five levels with five computers \newline
%per level
%\item the third one had 781 levels with one computer per level.
%\end{itemize}
%Figure 3 shows the results obtained on the TLBA and improved Lowest
%algorithm. We may note that Lowest generates a constant number of messages
%that are equal to 69,000.00, whilst the number of messages on TLBA varies
%according to the number of levels and computers per level. This variation is
%about 182.36 for five levels, 5,996.00 for two levels and 566,133.00 for 781
%levels.
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.39in,height=2.45in]{sample3.eps}}
%\label{fig3}
%\end{figure}
%
%{\small {\bf Figure 3~~~}}{\small {\it Messages exchanged among computers
%segmented by level}}
%
%The choice for an intermediate number of levels generates a lower traffic on
%the communication system, which increases the system scalability. When a
%computer per level is used, there is an overload on the communication among
%the computers, which decreases the final efficiency of the system making it
%not scalable. The overload happens due to the number of levels roamed to
%find out the best computer in the system to execute a received process and
%to update the information that propagates forward to the root computer.
%
%The definition of an intermediate number of levels allows the creation of
%subnets. Each subnet is formed by a number of computers. The system
%segmentation into levels composed of physically distinct networks generates
%a lower traffic on the communication system, as most of the messages are
%exchanged among the computers of a certain level, which transit on the
%physical network of this level. To create a subnet, a switch per level is
%necessary. For instance, a switch is used to interconnect the computer
%placed in a n level, to ones of the {\it n}~--~1 level. A computer of the
%{\it n}~--~1 level needs to have two network interface cards, one to connect
%to {\it n} level through one switch and another to connect to {\it n}~--~2
%level. To create different subnets, the system administrator must define the
%tree structure as static, so he/she cannot use the broker as implemented so
%far (Section 3.5).
%
%{\small {\bf 5 COMPARATIVE STUDY OF THE TLBA PROTOTYPE AND SIMULATOR}}
%
%In order to confirm the TLBA's feasibility, a prototype was implemented
%using the Linux operating system as the test environment. This section
%compares the results obtained on the executions of this prototype to the
%simulation results GNU/GCC Supported Platforms (2003).
%
%The prototype was submitted to two environment configurations: a homogeneous
%one and a heterogeneous one. The homogeneous environment was composed of
%seven computers with a 368~cycles/ms capacity. The heterogeneous environment
%was composed of two computers with a 139~cycles/ms capacity and five
%computers with a 368~cycles/ms capacity. The simulated and real environment
%used the same parameters that permit comparison of both.
%
%Table 6 presents the results obtained on the prototype executions and the
%simulation results at homogeneous environments. The executions were carried
%out on processes that occupy 10,330,000 cycles in three distinct situations.
%In the first case, processes that occupied only CPU, without doing the
%context switch, were submitted. In the second case, processes that occupied
%the CPU and made calls to the kernel's sleep function were submitted, which
%totalled 512,500~ms per process. In the third and last case, processes that
%made up sleep time of 1,024,000~ms each were submitted. These sleep times
%were defined so that the processes could last a longer time to be completed,
%which allowed the whole system to have more processes executing
%simultaneously. In all cases, 350 processes were submitted to the
%environment using a Poisson function for probability distribution of process
%arrival with average 3~seconds. Two computers per level were defined to make
%up a communication tree among the TBLA modules, as shown on Figure 4. All
%computers were connected through a 100~Mbits switch.
%
%{\small {\bf Table 6~~~}}{\small {\it Response times at the homogeneous
%environment (using the prototype and the simulator)}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|l|}
%\hline
%{\footnotesize {\it Cycles}}&
%{\footnotesize {\it Simulator }}{\footnotesize (ms)}{\footnotesize  }&
%{\footnotesize {\it Prototype }}{\footnotesize (ms)}{\footnotesize  }&
%{\footnotesize {\it Variation}} \\
%\hline
%{\footnotesize 10330000}&
%{\footnotesize 698,125.60}&
%{\footnotesize 697,645.00}&
%{\footnotesize 0.00068889} \\
%\hline
%{\footnotesize 10330000~+~512500~sleep~ms}&
%{\footnotesize 1,210,625.60}&
%{\footnotesize 1,194,509.00}&
%{\footnotesize 0.013492239} \\
%\hline
%{\footnotesize 10330000~+~024000~sleep~ms}&
%{\footnotesize 1,722,125.60}&
%{\footnotesize 1,760,153.00}&
%{\footnotesize 0.022081664} \\
%\hline
%\end{tabular}
%\label{tab6}
%\end{center}
%\end{table}
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.33in,height=1.73in]{sample4.eps}}
%\label{fig4}
%\end{figure}
%
%\begin{center}
%{\small {\bf Figure 4~~~}}{\small {\it Connecting tree created by TLBA}}
%\end{center}
%
%The number and occupation of processes submitted to the environment were
%defined to obtain a TLBA analysis for high load environments. The three
%analysed cases showed the results in situations where there are load peaks;
%situations where the high load is maintained for an average period of time;
%situations where the load is maintained for long periods of time.
%
%Observing Table 6, a small variation between the actual and simulated values
%may be noted. This variation is from 0.068889{\%} to 2.2081664{\%}. The low
%variation in results validates the simulator use for the feasibility
%analysis on the creation of load balancing environments with the TLBA. The
%graph on Figure 5 shows these results.
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.12in,height=2.33in]{sample5.eps}}
%\label{fig5}
%\end{figure}
%
%{\small {\bf Figure~5}}{\small ~~~}{\small {\it Response times for the
%prototype executions and simulations in a homogeneous environment}}
%
%Table 7 shows the average number of load balancing messages exchanged on the
%actual environment, represented by the prototype and simulation executions.
%The variation on the number of messages between the actual system and the
%simulated one is 5.8823529{\%}, and this figure also confirms that the
%simulator can be used to forecast the behaviour of a certain environment
%that aims to use the TLBA.
%
%{\small {\bf Table 7~~~}}{\small {\it Messages passing through the network
%to the actual and simulated environments}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small }&
%{\small {\it Per level}}&
%{\small {\it Total}} \\
%\hline
%{\small Simulator}&
%{\small 283.3333333}&
%{\small 850.00} \\
%\hline
%{\small Prototype}&
%{\small 300.00}&
%{\small 900.00} \\
%\hline
%{\small Variation}&
%{\small 0.058823529}&
%{\small 0.058823529} \\
%\hline
%\end{tabular}
%\label{tab7}
%\end{center}
%\end{table}
%
%Table 7 shows a column for the number of messages exchanged among the levels
%and another one for the \newline
%total messages exchanged on the environment, if the option of using a single
%network is chosen, the number of generated messages is found on the `Total'
%column. If the option of using physically distinct networks is chosen, the
%average number of messages is found on the `per level' column.
%
%The actual executions and simulations on the heterogeneous environment were
%conducted according to the same pattern followed on the homogeneous
%environment. The heterogeneous environment was composed of 5 computers with
%a 368 cycles/ms capacity and 2 computers with a 139 cycles/ms capacity.
%
%Table 8 shows the results obtained on the executions of the TLBA prototype
%and simulator in a determined heterogeneous environment. The processes were
%submitted on the same three situations previously defined for the
%homogeneous environment. On each test, 350 processes were submitted to the
%environment by using a Poisson distribution function with average of
%3~seconds. It may be noted that the variation between the simulated response
%times and the actual ones was from 1 to 4{\%}. The graph on Figure 6 shows
%these results.
%
%{\small {\bf Table 8}}{\small ~~~}{\small {\it Response times in the
%heterogeneous environment (using the prototype and the simulator)}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|l|}
%\hline
%{\small {\it Cycles}}&
%{\small {\it Simulator }}{\small (ms)}{\small  }&
%{\small {\it Prototype }}{\small (ms)}{\small  }&
%{\small {\it Variation}} \\
%\hline
%{\small 10330000}&
%{\small 781,348.89}&
%{\small 750,352.93}&
%{\small 0.04} \\
%\hline
%{\small 10330000~+~512500 ms de sleep}&
%{\small 1,293,848.89}&
%{\small 1,279,203.00}&
%{\small 0.01} \\
%\hline
%{\small 10330000~+~024000 ms de sleep}&
%{\small 1,805,348.89}&
%{\small 1,742,498.00}&
%{\small 0.04} \\
%\hline
%\end{tabular}
%\label{tab8}
%\end{center}
%\end{table}
%
%Table 9 shows the number of messages generated \newline
%both on the actual environment (prototype) and on \newline
%the simulated one. It may be noted tat the variation \newline
%between the expected and actual number of messages is about 7{\%}.
%
%\begin{figure}[htbp]
%\centerline{\includegraphics[width=3.28in,height=2.88in]{sample6.eps}}
%\label{fig6}
%\end{figure}
%
%{\small {\bf Figure 6~~~}}{\small {\it Response times for the prototype
%executions and simulations at a heterogeneous environment}}
%
%{\small {\bf Table 9~~~}}{\small {\it Messages passing through the network
%to the actual and simulated environments}}
%
%\begin{table}[htbp]
%\begin{center}
%\begin{tabular}{|l|l|l|}
%\hline
%{\small }&
%{\small {\it Per level}}&
%{\small {\it Total}} \\
%\hline
%{\small Simulator}&
%{\small 257.00}&
%{\small 771.00} \\
%\hline
%{\small Prototype}&
%{\small 275.00}&
%{\small 825.00} \\
%\hline
%{\small Variation}&
%{\small 0.070038911}&
%{\small 0.070038911} \\
%\hline
%\end{tabular}
%\label{tab9}
%\end{center}
%\end{table}
%
%As it may be observed, the values obtained on the simulations were confirmed
%afterwards by the prototype execution and this validates the simulations. It
%can also be highlighted that all actual executions were conducted with the
%aim of overloading the system. Thus, the comparisons between the prototype
%(actual system) and simulator could be made under extreme situations. In
%these situations the low variation of the number of exchanged messages to
%perform the load balancing operations and processes response times were
%confirmed.
%
%{\small {\bf 6 CONCLUSIONS}}
%
%The paper analyses the TLBA algorithm, which creates a virtual connecting
%tree to update the information on the system occupation. This tree is used
%to carry out deep searches that allow the idlest computer to be found as
%this computer is the one that should execute a process received by the
%system at a certain instant. Analysing the simulations presented on Section
%4, it was concluded that the TLBA algorithm decreases the number of messages
%generated at a certain environment and generates shorter response times than
%the improved Lowest algorithm (Mello et al., 2003).
%
%In order to confirm the results obtained on the simulations, a prototype was
%implemented on the Linux operating system. This prototype was submitted to
%tests whose results confirmed the low variation on the response times and
%the number of exchanged messages on the load balancing operations.
%
%The low variations between the TLBA prototype and simulator confirmed the
%simulator usefulness to forecast \newline
%the behaviour of environments that use the TLBA \newline
%for load balancing and, consequently, the validation of the comparisons made
%between the TLBA and improved \newline
%Lowest algorithms (Section 4) where TLBA showed the best results.

\sectiona{ACKNOWLEDGMENT}

We would like to thank Dr. Gonzalo Travieso for his collaboration
in this work.

\bibliographystyle{apalike}

\begin{thebibliography}{99}
\bibitem[\protect\citeauthoryear{Amir}{2000}]{Amir} %%1
Amir, Y. {\it et al.} (2000) `An opportunity cost approach for
job assignment in a scalable computing cluster', {\it IEEE
Transactions on Parallel and Distributed Systems}, July, Vol.~11,
No.~7, pp.760--768.

\bibitem[\protect\citeauthoryear{Anderson and Abraham}{2000}]{Anderson and Abraham} %%1
Anderson, J.R. and Abraham, S. (2000) `Performance-based
constraints for multidimensional networks', {\it IEEE
Transactions on Parallel and Distributed Systems} January,
Vol.~11, No.~1, pp.21--35.

\bibitem[\protect\citeauthoryear{Figueira and Berman}{2001}]{Figueira and Berman} %%1
Figueira, S.M. and Berman, F. (2001) `A slowdown model for
applications executing on time-shared clusters of workstations',
 {\it IEEE Transactions on Parallel and Distributed
Systems}, June, Vol. 12, No. 6, pp.653--670.

\bibitem[\protect\citeauthoryear{GNU/GCC Supported Platforms}{2003}]{GNU} %%1
GNU/GCC Supported Platforms (2003) URL:
http://gcc.gnu.org/install/specific.html, Consulted in: 25th
June, http://www.icmc.usp.br/$\sim $mello.

\bibitem[\protect\citeauthoryear{Hsu et al}{2000}]{Hsuetal} %%1
Hsu, T. {\it et al}. (2000) `Task allocation on a network of
\newline processors', {\it IEEE Transactions on Parallel
and Distributed Systems}, December, Vol. 49, No. 12,
 pp.1339--1353.

\bibitem[\protect\citeauthoryear{Hui and Chanson}{1999}]{Hui and Chanson} %%1
Hui, C. and Chanson, S.T. (1999) `Hydrodynamic load balancing',
 {\it IEEE Transactions on Parallel and Distributed
Systems}, November, Vol. 10, No. 11, pp.1118--1137.

\bibitem[\protect\citeauthoryear{Kostin et~al.}{2000}]{Kostinetal} %%1
Kostin, A.E., Aybay, I. and Oz, G. (2000) `A randomised
contention-based load-balancing protocol for a distributed
multiserver queuing system', {\it IEEE Transactions on Parallel
and Distributed Systems}, December, Vol. 11, No. 12,
 pp.1252--1273.

\bibitem[\protect\citeauthoryear{Krueger and Livny}{1987}]{Krueger and Livny} %%1
Krueger, P. and Livny, M. (1987) `The diverse objectives of
distributed scheduling policies', {\it Proc. Seventh Int'l Conf.
Distributed Computing Systems}, IEEE CS Press, Los Alamitos,
Calif., No. 801, (microfiche only), pp.242--249.

\bibitem[\protect\citeauthoryear{Mello et~al}{2003}]{Melloetal03} %%1
Mello, R.F. {\it et al}. (2003) `Comparative study of the
server-initiated lowest algorithm using a load balancing index
based on the process behaviour for heterogeneous environment,
accepted for publication in the special issue of cluster
computing of the Kluwer', {\it The Journal of Networks, Software
Tools and Applications.}

\bibitem[\protect\citeauthoryear{Mello et~al.}{2002b}]{Melloetal02b} %%1
Mello, R.F., Paiva, M.S. and Trevelin, L.C. (2002b) `OpenTella: a
peer-to-peer protocol for the load balancing in a system formed
by a cluster from clusters', {\it 4th International Symposium on
High Performance Computing ISHPC-IV}, Japan, May.

\bibitem[\protect\citeauthoryear{Mello et~al.}{2002c}]{Melloetal02c} %%1
Mello, R.F., Paiva, M.S. and Trevelin, L.C. (2002c) `Analysis on
the significant information to update the tables on occupation of
resources by using a peer-to-peer protocol', {\it 16th Annual
International Symposium on High Performance Computing Systems and
Applications}, Moncton, New-Bruncwick, Canada, June.

\bibitem[\protect\citeauthoryear{Mello et~al.}{2002d}]{Melloetal02d} %%1
Mello, R.F., Paiva, M.S. and Trevelin, L.C. (2002d) `A java
cluster management service', {\it IEEE International Symposium on
Network Computing and Applications}, Cambridge, Massachusetts,
USA, February\vvp{}.

\bibitem[\protect\citeauthoryear{Mello et~al.}{2002a}]{Melloetal02a} %%1
Mello, R.F., Paiva, M.S., Trevelin, L.C. and Gonzaga, A. (2002a)
`Model for resources load evaluation in clusters by  using a
peer-to-peer protocol', {\it The 2002 International Conference on
Parallel and Distributed Processing Techniques and Applications},
Las Vegas, USA, June.

\bibitem[\protect\citeauthoryear{Mitzenmacher}{2000}]{Mitzenmacher00} %%1
Mitzenmacher, M. (2000) `How useful is old information?',  {\it
IEEE Transactions on Parallel and Distributed Systems}, January,
Vol. 11, No. 1, pp.6--20.

\bibitem[\protect\citeauthoryear{Mitzenmacher}{2001}]{Mitzenmacher01} %%1
Mitzenmacher, M. (2001) `The power of two choices in randomised
load balancing', {\it IEEE Transactions on Parallel and
Distributed Systems}, October, Vol. 12, No. 10,
pp.1094--1104.

\bibitem[\protect\citeauthoryear{Page et~al.}{1993}]{Pageetal} %%1
Page, I, Jacob, T. and Chern, E. (1993) `Fast algorithms for
distributed resource allocation', {\it IEEE Transactions on
Parallel and Distributed Systems}, February, Vol. 4, No. 2,
pp.188--197.

\bibitem[\protect\citeauthoryear{Shivaratri et~al.}{1992}]{Shivaratrietal} %%1
Shivaratri, N.G., Krueger, P. and Singhal, M. (1992) `Load
distributing for locally distributed systems', {\it IEEE
Computer,} December, pp.33--44.

\bibitem[\protect\citeauthoryear{Sinha}{1997}]{Sinha} %%1
Sinha, P.K. (1997) {\it Distributed Operating Systems: Concepts
and Design}, IEEE Institute of Electrical and Electronics
Engineers, Inc, 345 East 47th Street, NY 10017--2394.

\bibitem[\protect\citeauthoryear{Theimer and Lantz}{1988}]{Theimer and Lantz} %%1
Theimer, M.M. and Lantz, K.A. (1988) `Finding idle machines in a
workstation-based distributed systems', {\it Proc. IEEE 8th Int.
Conf. on Distributed Computing Systems}, pp.112--122.

\bibitem[\protect\citeauthoryear{Woodside and Monforton}{1993}]{Woodside and Monforton} %%1
Woodside, C.M. and Monforton, G.G. (1993) `Fast allocation of
processes in distributed and parallel systems', {\it IEEE
Transactions on Parallel and Distributed Systems}, February, Vol.
4, No. 2, pp.164--174.

\bibitem[\protect\citeauthoryear{Zhang}{2001}]{Zhang} %%1
Zhang, Y. (2001) `Impact of workload and system parameters on
next generation cluster scheduling mechanisms', {\it IEEE
Transactions on Parallel and Distributed Systems}, September,
Vol. 12, No. 9, pp.967--985.

\bibitem[\protect\citeauthoryear{Zhou and Ferrari}{1987}]{Zhou and Ferrari} %%1
Zhou, S. and Ferrari, D. (1987) {\it An Experimental Study of
Load Balancing Performance}, Report No. UCB/CSD 87/336, Progress
Report No. 86.8, Computer Science Division (EECS), University of
California, Berkeley, California 94720, January, pp.1--27.

\bibitem[\protect\citeauthoryear{Zomaya and Teh}{2001}]{Zomaya and Teh} %%1
Zomaya, A.Y. and Teh, Y. (2001) `Observations on using genetic
algorithms for dynamic load-balancing', {\it IEEE Transactions on
Parallel and Distributed Systems}, September, Vol. 12, No. 9,
pp.899--911.
\end{thebibliography}
\end{document}
