\section{Introduction}

I propose to develop a best effort distributed real time service for
building interactive applications.  Using this service, a programmer
will be able to specify deadlines for executing the activation tree
rooted at a procedure call.  The system will do its best to meet the
deadlines by dynamically mapping nodes (procedure calls) of the
activation tree to appropriate hosts as the tree unfolds.  Part of
this process will be to use the deadlines the programmer placed on the
root node to recursively induce deadlines for child nodes.

Mechanisms to support migrating the thread of control at procedure
call points already exist in the form of RPC, DSM, and distributed
object systems.  The challenge is to develop a powerful mapping
algorithm to select the appropriate host at each procedure call point
such that meeting the programmer specified deadlines for the whole
activation tree is highly likely.  

Instead of using reservations, or relying on a global scheduler of
some sort, my approach is based on simple and fast prediction of
procedure call execution times given a local history of past execution
times.  If I could predict the execution time of a procedure call on
each of the hosts it could be assigned to, choosing which host to
assign it to would be clearer.  Indeed, predicting whether or not the
call will meet its deadline a host would be sufficient.

Predicting whether or not a call will make its deadline when mapped to
a particular host is a difficult undertaking since it depends on many
dynamic properties of the distributed computing environment (load on
hosts, available bandwidth and latency along paths in the network) and
of the program (activation tree structure, distribution of program
state.)  However, three factors simplify matters.  First, since we
make this prediction in the context of an activation tree, we have
more freedom.  If we miss a child node's deadline, all is not lost
since we can adjust the deadline of the next child.  Indeed, we might
be more aggressive early in the tree in order to better explore our
environment.  The second factor is because we are interested only in
meeting the deadline and not in the actual execution time of the node,
there are many possible satisfactory mappings.  In comparison, systems
that attempt to minimize the execution time are trying to find one of
a much smaller set of satisfactory mappings.  The final factor is that
because we are attempting to predict a value that depends on several
underlying processes instead of predicting the underlying processes
themselves, we can hope for some benefit from the central limit
theorem (although not much, due to the self-similar nature of those
processes.)

It is important that the overhead of prediction be on par with the
overhead of the remote execution mechanism so that prediction has
minimal effect on what calls can be profitably executed remotely.  The
overhead the remote execution mechanism determines minimum amount of
work a procedure call must do before it makes sense to use the
mechanism.  The overhead of prediction should not appreciably affect
this minimum mapping granularity.  This granularity is in the
millisecond range for modern remote execution systems such as DCE RPC
or CORBA RMI, but future remote execution overheads will likely be
much lower given fast low latency networks and protocol stacks.
Researchers have already built simple LANs for workstations with
microsecond application-to-application latencies.  The in-application
overheads of RPC in lightweight systems like LDOS are also in that
range (about O(100) more expensive than purely local calls or around 5
microseconds on a Pentium Pro 200.)  The target overhead of our
prediction schemes is in this range.

There is significant evidence that prediction is possible.  I have
identified self-similariy in host load measurements and other
researchers have identified it in various measurements of networks.
Self-similarity is indicative of a ``long memory'' process - which
means that the future depends strongly on past, albeit in a possibly
complex way.  This dependency suggests that predicting, for example,
future load conditions based on past load conditions is possible.

There is also reason to believe that prediction is tractable.  I have
discovered epochal behavior in host load measurements - for a long
period of time (300-500 second mean), the local spectrum of the load
signal remains relatively constant and then transitions abruptly as
the signal enters the next equally stable and long lived spectral
epoch.  Because a spectral epoch is relatively long, many measurements
may be taken during the duration, making it more likely that a
reasonable model of the behavior of the load during the epoch will
emerge while there is still plenty of time to gainfully apply it.

Experience strongly suggests that prediction will be highly effective.
I have developed and evaluated fast and simple prediction-based
mapping algorithms for a simplfied variant of the problem where
mapping is limited to leaf nodes and communication costs are zero.
The quantitatively best of these leaf node mapping algorithms, called
selectors, has near optimal performance for sub-second units of work
and has an execution time of about 10 microseconds.  

[Simulation - how to develop this alg]

I intend to incorporate my prediction-based mapping algorithm into
LDOS, a lightweight distributed object system I have developed.  LDOS
supports multiple instances of an objects via replication for
stateless objects and distribution for objects with state.  An object
instance can be selected dynamically when a method is invoked.  The
mapping algorithm will be incorporated into object references, local
proxies or ``smart pointers'' for remote objects, and will act as a
metaobject protocol.  It may be possible to specialize the mapping
algorithm as part of the IDL compile process.  It is important to note
that my mapping algorithm will not be specific to LDOS or to any
specific instance or kind of remote execution mechanism.


The structure of this proposal is as follows.  In
section~\ref{sec:app_model} we describe our model of an interactive
application and give examples.  In section~\ref{sec:env_model}, we
describe the kind of distributed computing environment we intend to
support.  In section~\ref{sec:map_primitive} we describe the semantics
of the MAP primitive we will provide.  The following section,
section~\ref{sec:approach} describes and defends our
application-centric predictive approach to providing the map
primitive.  In section~\ref{sec:load_traces} we present results of a
detailed analysis of load traces collected in examples of our target
environments which suggests our prediction based approach will work.
In section~\ref{sec:simulator} we describe the simulator we have
implemented.  Section~\ref{sec:sel_desc} describes the simple
algorithms we have developed for a restricted version of the mapping
problem and section~\ref{sec:sel_perf} illustrates the performance of
these algorithms.  Section~\ref{sec:extensions} describes the
extensions and contributions we intend to make in the thesis and
provides a timetable.  Section~\ref{sec:conclusions} concludes.