\section{Introduction}

Users demand responsiveness from interactive applications such as
image editors, scientific visualization tools, modelling tools based
on physical simulations, and games.  Such applications react to
aperiodically arriving messages that arise from user actions.  In
response to each message, the application program executes a message
handler, the call to which forms the root node of an activation tree
that unfolds as computation progresses.  The computation represented
by the tree creates visual and aural feedback for the user.  This
feedback helps determine the subsequent actions of the user.  The
aperiodicity in message arrival is a result of having a ``human in the
control loop.''  To be responsive, the application must execute the
activation tree induced by each message as quickly as the user
reasonably expects.

At one point, creating applications that were responsive in this sense
was relatively easy since the user's machine was very predictable from
the point of view of the programmer.  Today, however, the user's
machine is becoming increasingly less predictable due to operating
system jobs, daemons, other users' jobs, and the like.  These external
factors make the actual computation rate the programmer can expect
vary in complex ways.  Further, the user's machine may simply not be
fast enough or have enough memory to perform some computations
responsively.  On the other hand, the user's machine is no longer
alone --- there are many other hosts on the local area network which
it can talk to.  As the overheads of remote execution facilities such
as remote procedure call (RPC) systems, object request brokers (ORBs),
and distributed shared memory (DSM) systems decline, it becomes more
tempting to execute smaller chunks of work remotely to achieve the
responsiveness that interactive applications require.  Unfortunately,
the overwhelming majority of networks and hosts do not provide any
sort of resource reservations, or even priority-based scheduling that
a programmer could build upon to make a group of hosts behave in a
more predictable fashion than an individual host.  However, these
environments provide increasingly sophisticated measurement tools.

A best effort real-time service would greatly simplify building
interactive applications in this context.  Using such a service, the
programmer would specify time bounds for executing the activation tree
rooted at a procedure call and the service would attempt to meet the
bounds by measuring the system and using the remote execution
facility.  The design space for such a service is vast.  My approach
is to dynamically map the nodes of the activation tree to appropriate
hosts as the tree unfolds during execution, making each mapping
decision in pursuit of the goal of achieving the overall bounds on the
tree.

The core problem that needs to be solved to make such a service
possible is a dynamic mapping problem: We are given a stream of
aperiodically arriving activation trees.  Each tree has an associated
upper and lower bound on its execution time and its structure becomes
known only as we sequentially execute it.  We can execute an
activation tree node on any one of a group of uncoordinated but
measurable hosts interconnected with a measurable network.  The hosts
and network can all have unrelated computation and communication
traffic on them.  Under these conditions how do we map the nodes of
the trees to the hosts so that the percentage of trees that execute
within their desired bounds is maximized?

My thesis is that this dynamic mapping problem can be solved using
history-based prediction. History-based prediction involves predicting
the future values of a series using a window of previous values.  In
essence, the idea is to monitor the system and the application and use
our measurements to predict how their behaviors will evolve.  Each
node is then mapped to the host which best serves to match the
predicted future application behavior to the predicted future system
behavior.  By adapting our mapping strategy as the activation tree
is traversed, we can better explore the system and handle erroneous
predictions.

There is strong evidence that history-based prediction is an effective
way to approach this dynamic mapping problem.  The evidence comes from
two distinct threads of investigation.  The first thread involves an
extensive analysis of load traces collected on a large number of hosts
from four common classes (experimental and production compute
clusters, desktop workstations, and compute servers) on which we
expect to run our interactive applications.  The analysis strongly
suggests that load is predictable from its history. The second thread
involves using history-based prediction of execution times to achieve
near optimal performance for a simplified variant of the dynamic
mapping problem.

Extensive analysis of host load traces reveals three properties which
strongly suggest that host load is predictable from past load
measurements.  These properties are self-similarity, epochal behavior
of local frequency content, and the phase space behavior of the load.
Self-similarity implies a long-memory process where the future depends
on a long stretch of the past in a possibly complex way.  By epochal
behavior of the local frequency content, we mean that the manner in
which the load varies (the frequency content of the load signal) is
relatively stable for long periods of time (epochs.)  Because each
epoch is long, we have an extended opportunity to understand the
behavior within it.  The third property is that the phase space
behavior of the load is relatively simple, and thus easier to predict.

I have developed a fast, simple, and near optimal history-based
prediction algorithm for a simplified variant of the dynamic mapping
problem and evaluated it through extensive, realistic simulation based
on the load traces.  In the simplified problem only leaf nodes are
mapped and communication costs are ignored. There are several conclusions
to draw from the results.  First, dynamic mapping can make a
significant difference in the percentage of calls that meet their
deadlines - in many cases the near-optimal algorithm allows almost
100\% of calls to meet their deadlines while random or host-specific
mappings barely manage 30-40\% of the calls.  The second conclusion to
draw from my experience is that developing a good history-based
prediction algorithm for even the simplified problem is a non-trivial
undertaking.  Simple algorithms behave badly, while complex generic
approaches such as neural networks work well, but have overheads that
are far too high.  However, there is a middle ground --- effective yet
efficient algorithms do exist.  The final conclusion is that there remains
room for improvement.

For my thesis, I will extend these two threads of investigation to
develop a history-based prediction algorithm for the full dynamic
mapping problem.  The algorithm will be developed using a realistic
trace-driven simulation environment based on host load traces, network
traces, and traces of activation trees collected from real
applications.  Because of its highly realistic nature, I intend to
also evaluate the algorithm using the simulator and a set of
benchmarks.  In addition, I will incorporate my algorithm into a
lightweight distributed object system to show that it can work in a
real system.

We begin this proposal in Section~\ref{sec:app_model}, which explains
our model of interactive applications and responsiveness in detail.
Section~\ref{sec:mach_model} describes our machine model and the
assumptions we make about available services.  We describe our
execution model for activation trees in
Section~\ref{sec:act_tree_model}.  This leads to
Section~\ref{sec:dyn_map_prob}, which describes the dynamic mapping
problem, and Section~\ref{sec:hist_pred}, which describes our
history-based prediction approach to the problem and contrasts it with
other approaches.  The next two sections present our preliminary
results. In Section~\ref{sec:load_traces} we describe our analysis of
host load traces, while in Section~\ref{sec:simple_prob} we discuss
our results for the simplified dynamic mapping problem.
Section~\ref{sec:outline} outlines the thesis work and
Section~\ref{sec:contrib} describes the expected contributions.
Finally, Section~\ref{sec:related_work} differentiates this thesis
from related work.