% This is an article which I have kindly donated as an example of a LaTeX
% file. I advise that you do not read it, merely look at the LaTeX constructs.
\documentstyle[11pt,a4]{article}

\author{D.M. Baillie}
\title{Interim Report}
\pagestyle{headings}

\begin{document}
\maketitle
\section{Introduction}
The following short document outlines the simulation experiments and
presents some initial results from a static stochastic load balancing
algorithm (slba) running on a homogeneous distributed computer system.

Previous work in this area includes an optimal solution presented
in~\cite{Tantawi:Optimal} using the technique of cost functions---such
analytical solutions require `perfect' information and are computationally
expensive. The previous best heuristic\cite{Stank:Using} cuts down on the
information requirement but is still of O(N); the size of the network is a
limiting factor in both these models.  One solution to this problem is not to
try to balance all the network all the time---the approach of the current
algorithm, it is therefore not restricted to 4 or 5 machines as in the previous
mentioned algorithms.

\section{Background to simulation}
We are trying to demonstrate two things: that the algorithm can lead to a
significant improvement in system performance, and that the algorithm is
near optimal over the required system performance vectors. The main
performance measure of interest is response time, but this has to be
maximised subject to a throughput constraint.

To achieve the above aims, the technique of simulation is used. In order
to be able to describe the behaviour of the system in time, one needs to
specify the system architecture, the scheduling strategy and the nature of
the jobs (i.e.\ arrival patterns and service patterns). The system
architecture is defined by the structure of the simulation program itself,
as mentioned above this consists of a number of processors (resources)
which can communicate with one another (not necessarily shared medium or
supporting broadcasts). Communication overhead between the processors is
assumed to be negligible at the moment. The scheduling strategy used at
each resource is processor sharing with a fixed timeslice; this was chosen
to meet the throughput constraint, effectively modelling a multi-tasking
resource. The job arrivals form a poisson process and come equipped with
exponentially distributed service requirements. As the only resource being
modelled at this stage is the processor, jobs do not have any
communication requirements. In addition, for further simplicity at this
stage the processors are assumed to be of unit speed.

The  above defines a very simple system with  few  parameters:  number  of
resources; mean  arrival  rate; mean processing requirements and timeslice
in scheduling strategy. It  is  important  to keep the system as simple as
possible at an early stage as the algorithm itself is complex enough to
introduce many new variables. The simplicity of the system at this stage
also makes it (theoretically!) possible to compare the performance of the
algorithm with the optimal scheduling strategy but some work would be
needed to evaluate the analytical optimal strategy for the exact system
described above.

\section{Simulation results}
\subsection{Experiment 1}
The ultimate aim is to achieve the best possible response time for a given
period of execution, determined by the performance of the algorithm---the best
strategy for the least cost.

There are thus two main parameters that can be adjusted; the period of
execution and the algorithm itself (or aspects of it in this case). The first
experiment investigates these factors in various fixed, stable network
conditions. The conditions were made intentionally harsh for the algorithm by
making the arrival and service rates at each processor the same, thus giving
very little opportunity for a difference in load to occur. Because of this only
five machines were used for this experiment. The prediction was that, for the
algorithm to be effective, it would have to be executed at a rate greater than
the average arrival rate in order to recognise fluctuations in load---if the
scheduling period were too large machines would receive twice or three times
the input for long periods of time.

Returning to the parameters, it was decided to test the algorithm from periods
of between 0.5 and 32 to give a range of values on either side of the arrival
rates used (0.1, 0.13). 0.5 was the minimum as this was the fixed timeslice
used in the scheduling strategy at each host. 7200 time units were simulated to
give the system time to reach a steady state.

While varying the timeslice two slightly different versions of the algorithm
were used by adjusting the `power' of the payoff function. The payoff function
is central to the algorithm and so will be discussed here. It represents the
probability of getting a good response time if a job were to be started on that
machine at the time of evaluation of the function. It therefore must be a
function of the expected load of the machine for the interval of the job run.
Obviously there are many subtleties to this function but for simplicity the
queue length combined with the number of hosts currently `connected' to the
machine evaluating the function was used.

What constitutes a `good' response estimate is given in terms of the queue
length and is called the `power' of a machine. In its most general form the
payoff function can thus be interpreted as
\begin{equation}
\frac{\hbox{number above which state estimate gives a good probability of $<$
50\%}}{2*\hbox{state estimate}}
\end{equation}
 and for the top line read power. Pictured graphically, the function is shown
in figure~\ref{piccy}
\begin{figure}
\vspace{1.5in}
\caption{{\tt Payoff function}\label{piccy}}
\end{figure}
The x-axis is the state estimate, here simply runqueue length $+$ number
of `connected' machines and the y-axis is the probability returned by the
payoff function. Figure~\ref{piccy} shows the function for a power value
of 2. If the state estimate rises above 2, the probability drops, but
while the state estimate $<$ 2 the probability is high. In the algorithm
this would effectively mean that queue lengths\footnote{state estimates
to be more precise but it's simpler to think in terms of queue lengths}
above 2 would prompt the algorithm to be dissatisfied with the current
state and search elsewhere for a less loaded resource while queue lengths
below 2 would precipitate a high probability, attracting jobs.

Experiment~1, determining the effect of the period of the algorithm on
various fixed, stable network states was performed for 2 values of power,
giving two different payoff functions. The first power was the average
queue length (determined from the average arrival and service rates) so
that if the expected load was greater than the average queue length the
probability of a payoff decreased prompting a bad response and triggering
a search elsewhere. This was called the optimistic power because it tends
to look for better sites even when the current queue length is average.
The second power was chosen to give a higher probability of a payoff than
a penalty while the average conditions existed---this power was called
pessimistic as it assumes the average queue length is acceptable and only
prompts for exploration of another site if the average queue length is
exceeded. It was predicted that the lower the power, the more frequently
the algorithm would have to be run, reflecting the need for it to work
harder to meet the increased performance demands.

Table~\ref{exp1} shows the results from the experiment. The numbers in
each column represent the mean of the average response time from each
host. Two independent sets of results were obtained giving ten value of
average response time in total; as each host is under identical conditions
in this experiment the mean of the average is an acceptable performance
measure. The average theoretical response time and queue length
respectively are shown in the second row. The last row shows the average
response time when no algorithm is running which agree closely with the
theory.

The first two columns show the results from $\lambda = 0.1$ and $\mu =
0.15$ at each host. The two main features of these results are that the
response time degrades fairly evenly with the period of execution and the
response time does not start to improve until the algorithm is run at
approximately twice the rate of job arrivals. This agrees with the
prediction that the faster the algorithm is run, the better it can respond
to changes in conditions. The optimistic payoff function performs slightly
better, this is due to the power being an integer in this case (the
problem with this is highlighted in the next set of results), the 50\%
value is reached when the queue length is exactly 2, the average length
used as the power. The pessimistic algorithm on the other hand still has a
probability of 63\% when the queue length is two and 42\% when it is
three, compared to only 33\% in the optimistic case. Finally it should be
noted that while an improvement of 6 is possible, it would require an
unacceptably high execution rate in practice. It is hoped that this can be
dramatically improved on with better automaton designs (not even
stochastic automata were used in this experiment), payoff functions,
feedback and increased network size.

The second pair of columns was designed to show the effect on response
time of increasing the service rate with respect to the arrival rate,
equivalent to making the jobs shorter. This was not very successful, as
the figures show, there being hardly any increase in response time and
certainly not at an acceptable period of execution. This was due to the
shortcomings in the payoff functions which, because it is evaluated in
terms of queue length $+$ number of `connected' hosts, only receives
values at the points 1,2,\ldots As the average queue length is less than
1, this means that the {\em maximum} payoff for the optimistic column was
only 50\%, never allowing learning to take place. The pessimistic case
gives values of 75\%, 37\% taking the 75\% value in the majority of cases,
making the algorithm in effect, negligable.

The third pair of columns shows the effect of increasing the arrival rate
i.e.\ putting a heavier load on the system---as predicted, little
improvement is noticed until the rate of algorithm execution exceeds the
arrival rate. For the optimistic function the increase in response time is
of the same order as for the first pair of columns; the pessimistic payoff
function is much less successful which is slightly surprising given that
the larger the average queue length, the smaller the difference between
the two functions. This can most likely be explained by the increased
`sensitivity' of the algorithm at high average queue lengths---the variance
of which increases as an inverse square law function of the arrival and
service rates.

Overall the results are encouraging given the number of simplifying
assumptions made and the coarseness of the algorithm at this stage.

\subsection{Experiment 2}
As was mentioned previously, conditions were made particularly harsh for
the algorithm, $\lambda$ and $\mu$ being identical at each site. The
second experiment is to determine how the load is distributed when
$\lambda$ and $\mu$ are different at each site (although still the same
throughout the run of the simulation) giving more realistic network
conditions. It was intended to use the same network conditions as
Stankovic in demonstrating his algorithm and compare the performance of
the two algorithms but the correctness of Stankovic's results are somewhat
in question. Aside from this only a preliminary set of results have been
obtained and more detailed experiments have yet to be performed so these
results will not be presented yet.

\begin{table}
\begin{center}
\begin{tabular}{||l|l|l|l|l|l|l||} \hline
period & \multicolumn{2}{c|}{$\lambda = 0.1, \mu = 0.15$} & 
         \multicolumn{2}{c|}{$\lambda = 0.1, \mu = 0.25$} & 
         \multicolumn{2}{c||}{$\lambda = 0.13, \mu = 0.15$} \\ \hline
    & \multicolumn{2}{c|}{20.0, 2.0} & \multicolumn{2}{c|}{6.67, 0.67} &
      \multicolumn{2}{c||}{50.0, 6.5} \\ \hline
& optim	& pessim & optim & pessim & optim & pessim \\ \hline
0.5 & 14.438 & 15.658 & 7.939 & 6.295 & 33.311 & 43.396 \\ \hline
1.0 & 16.135 & 17.310 & 7.631 & 6.491 & 37.385 & 44.531\\ \hline
2.0 & 17.075 & 18.357 & 8.046 & 7.115 & 43.418 & 51.787\\ \hline
4.0 & 19.592 & 19.634 & 9.535 & 7.373 & 47.841 & 54.727 \\ \hline
8.0 & 22.237 & 26.082 & 11.691 & 7.474 & 60.966 & 71.082 \\ \hline
16.0 & 25.374 & 25.611 & 12.412 & 8.133 & 63.692 & 91.936\\ \hline
32.0 & 43.085 & 32.987 & 16.150 & 7.212 & 99.806 & 117.321\\ \hline
$\infty$ & \multicolumn{2}{c|}{20.135} & \multicolumn{2}{c|}{7.073} & 
           \multicolumn{2}{c||}{45.877} \\ \hline
\end{tabular}
\end{center}
\caption{{\tt Results from first experiment}\label{exp1}}
\end{table}
\begin{thebibliography}{99}

\bibitem{Tantawi:Optimal} Asser N. Tantawi and Don Towsley, {\em Optimal Static
Load Balancing in a Distributed Computer System}, Journal of the ACM, April 1985.

\bibitem{Stank:Using} John A. Stankovic and Ravi Mirchandaney, {\em Using
Stochastic Learning Automata for Job Scheduling in a Distributed Processing
System}, Journal of Parallel and Distributed Processing, Dec.1986.

\end{thebibliography}
\end{document}