\section{The dynamic mapping problem}
\label{sec:dyn_map_prob}

In order to be responsive (Section~\ref{sec:app_model}), each
individual application tree generated during a run of an interactive
application should be executed as quickly as the user expects, but
there is no benefit to executing the tree too quickly.  As illustrated
in Figure~\ref{fig:exectimenode}, we formalize this as lower and upper
bounds, $t_{min}$ and $t_{max}$, on the execution time of the tree.  The
application developer supplies these bounds at time $t_{now}$ as part
of the mapping request
\begin{center}
\MAP
\verb.procedure(inargs,outargs,inoutargs,state). \IN $[t_{min},t_{max}]$
\end{center}
which asks us to execute the activation tree rooted at the call to
\verb.procedure. such that $t_{now}+t_{min} \leq t_{exec}
\leq t_{now}+t_{max}$, where $t_{exec}$ is the execution time of the
tree.  Our performance metric is the percentage of such mapping
requests that meet their bounds.  We desire a mapping algorithm that
maximizes this metric.

The dynamic mapping problem induced by this specification is as
follows: 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?


%These bounds are becoming more difficult to achieve given
%the increasing complexity of the user's machine and the increasing
%resource requirements of the applications.  However, the user's
%machine is not alone on the network, and we can reasonably expect to
%be able to execute tasks on other hosts of the network to help meet
%the bounds.  Indeed, as the network gets faster, this is increasingly
%tempting.

%Using the network and other hosts in this way is a difficult task for
%the application programmer.  Further, implementing specific mechanisms
%to use the network environment in specific applications means that the
%wheel will be reinvented many times.  It makes more sense to abstract
%this functionality into a service that the application programmer can
%simply use, instead of having to write his own. 


%\begin{figure}
%\epsfxsize=4in
%\centerline{
%\epsfbox{timing_constraints.epsf}
%}
%\caption{Upper and lower bounds.}
%\label{fig:timingconstraints}
%\end{figure}


%If the node meets its
%upper bound, there is a slack time, $t_{slack}$, before the upper
%bound.  The communication times depend on the amount of data
%transfered and on the state of the network.



%How do we map the nodes of aperiodically arriving,
%dynamically unfolding activation trees to the hosts of an
%uncoordinated but measurable distributed system so that the chances of
%meeting deadlines placed on the execution times of whole trees are
%maximized?
%In essence, the system will make use
%of the freedom it has in choosing which host shall execute a node to
%ameliorate the uncertainty it faces from the application and the
%computing environment.

%system would attempt to meet those deadlines by mapping the
%nodes of the tree to different hosts of the network as the tree
%unfolds. The service will attempt to achieve the upper and lower bounds by
%dynamically mapping the nodes of the unfolding activation tree to the
%hosts of the computing environment.  The activation tree is executed
%sequentially, and when mapping a particular node, only the prior nodes
%in the depth-first traversal of the tree and the structure they form
%are known.  The successor nodes in the traversal and the overall
%structure of the tree are unknown when mapping a given node.
%Similarly, when mapping a node, the past behavior of the hosts and
%network are known, but the future behavior is unknown.  It is the
%service's job to succeed in meeting the bounds in the face of this
%uncertainty.  In essence, the service will make use of the freedom it
%has in choosing which host shall execute a node to ameliorate the
%uncertainty it faces from the application and the computing
%environment.


%To meet the responsiveness goals required by our model of interactive
%applications (Section~\ref{sec:app_model}) on the kinds of common
%computing environments encompassed by our machine model
%(Section~\ref{sec:mach_model}), we propose to build a best effort real
%time service that will let the application programmer place upper and
%lower bounds (deadlines) on the execution time of an activation tree
%rooted at a particular procedure call.  The form of this service will
%be the \MAP primitive
%\begin{center}
%\MAP \texttt{procedure(inargs, outargs, inoutargs, state)} 
%      \IN $[t_{min},t_{max}]$
%\end{center}
%which attempts to execute the activation tree rooted at the call to
%\verb.procedure. such that it completes within $t_{max}$ seconds but
%no sooner than $t_{min}$ seconds.  For interactive applications, the
%call to the message handler would be performed using the \MAP
%primitive.  Together, the upper and lower bounds serve as a way of
%expressing a human perceptual range where broaching the bounds leads
%to noticeably different delays.  For periodic mappings, the two bounds
%also serve as a way to specify a jitter constraint.  

% In the remainder of this section, we first describe the form of our
%hypothetical best effort real-time service and what the bounds mean.
%Next, we list the assumptions we make in addressing the dynamic
%mapping problem.  Finally, we describe our simple model for the
%execution time of an activation tree.  We will use this model in
%Section~\ref{sec:simple_prob} to describe a simplified version of the
%dynamic mapping problem for which we give extensive results.