\section{Initial experience with image composition application}
\label{sec:app}

To gain experience with the requirements of resource-aware
data-intensive programs, we are developing a prototype for a
multi-site image composition application. This application processes
weather images from multiple geographically-distributed sites and
delivers the final image to a single client. A composition operation
takes two images as input and generates a single image as output.  The
composition is achieved by comparing the image pixel-by-pixel and
selecting one of the two pixels based on a selection function.  If the
two images are not of equal size, a coordinate-mapping function is
used to determine which pixels should be compared. This processing is
modeled on {\em Pathfinder}, one of the major data-processing program
used by NASA to process satellite images~\cite{ACHARYA96}. Similar
programs are currently being developed to process data from the Earth
Observation System~\cite{eos}
satellites. Figure~\ref{fig:app-schematic} illustrates the structure
of the application.

\begin{figure}
\psrotatefirst
\vspace*{-0.5in}
\centerline{\psfig{file=adaptbase.ps,angle=270,height=4in}}
\caption{Adaptbase: an adaptive image composition application. The stacks
represent image servers and the rounded boxes represent composition
operations.}
\label{fig:app-schematic}
\end{figure}

There are two kinds of variations in network bandwidth that can impact
performance of adaptbase: (1) {\em spatial} variations, i.e. stable
differences between in bandwidth available over different links; and
(2) {\em temporal} variations, i.e. changes in the bandwidth of
individual links that persist for a significant period of
time. Spatial variations are primarily caused by differences in the
connectivity of the servers and/or the client.  Temporal variations,
on the other hand, are caused by changes in cross-traffic patterns and
end-point load.

Currently, the dominant mode of data access over wide-area networks is
to move data from servers to the clients and to perform all processing
at the clients. This strategy imposes an inherent limitation on the
extent to which clients can adapt to variations in network
bandwidth. Since all data has to be moved to the client, the primary
dimension of flexibility is the order in which the data is
processed. An example of such techniques is {\em
query-scrambling}~\cite{AmsalegFT96,AmsalegFTU96} which tries to hide
initial delay in data arrival as well as bursty data arrival by
reordering the data-processing operations.  Such techniques cannot,
however, deal with persistent variations in bandwidth. For example, if
the bandwidth to one of the servers is much lower than the bandwidth
to other servers, strategies that perform all processing at the client
can provide limited benefit.

Function-shipping has been widely used for its ability to reduce
communication costs for applications that digest their input (or
significantly reduce its size in some other way). It also allows
resource-limited clients to use server resources. By
function-shipping, we mean strategies that that offload some of the
processing operations on to one or more servers. In addition to
reducing the communication costs and the need for client resources,
function-shipping also provides an additional dimension of flexibility
for adapting to changes in network bandwidth. For example, if a
client's connection to the network becomes poor (as happens in
Figure~\ref{fig:bw-var}(b)), it can offload some or all of the
processing to one or more of the servers and download only the final
result. In the context of this application, function-shipping
corresponds to placement of the composition operations at the 
servers.

This problem has some unique characteristics. First, the adaptation
technique should be {\em agile}.  As shown in
Figure~\ref{fig:bw-var}(a), network bandwidth can change rapidly
within short periods of time and an adaptation technique that is slow
to react can lose opportunities for performance improvement.  Second,
the adaptation technique should be {\em cautious} as too rapid a
reaction can degrade performance for two reasons: (1) changes in
network bandwidth are often transient (see Figure~\ref{fig:bw-var}(a)
for examples) and (2) the cost of modifying the processing plan can be
significant.  It is, therefore, important to react only to relatively
stable and significant changes in the network bandwidth. As is
obvious, there is a tension between the need for agility and the need
for caution.  Finally, the adaptation technique should be {\em
parsimonious}. Measuring network bandwidth is not free and algorithms
that are profligate in sensing the network can incur more cost than
the potential benefit they might provide. Being too parsimonious,
however, can significantly reduce the effectiveness of the adaptation
algorithm by limiting the amount of information available.

We assume a demand-driven pipelined processing model. The composition
operations are scheduled by passing data from the leaves to the root
of the composition tree so that the result finally appears at the
root. The data-flow is demand-driven in that no operator sends its
result to the next operator until it receives a request for the
data. An iterative hill-climbing algorithm is to compute the placement
of the composition operations. It initially places all composition
operations at the client. Each iteration of the algorithm has four
steps: (1) determine the critical path (that is, the path that takes
the longest time; (2) for each operator on the critical path,
determine the best location (3) select the operator whose
repositioning achieves the greatest gain; (4) reposition the selected
operator. Figure~\ref{fig:app-sample} shows a sample placement.

\begin{figure}
\psrotatefirst
\vspace*{-0.5in}
\centerline{\psfig{file=sample-placement.ps,angle=270,height=4in}}
\caption{Sample placement of composition operations}
\label{fig:app-sample}
\end{figure}

We have used two versions of this algorithm. The first version, which
we refer to as {\em one-shot}, uses information available at the
beginning of the computation to determine the placement. In this case,
the placement is not changed during the computation. The second
version, which we refer to as {\em dynamic}, periodically repositions
operations using information acquired during the computation. To
compute the new placement for operations, it uses the same basic
algorithm as {\em one-shot} albeit with three variations that take
care of problems of switching placements as the computation is in
progress. First, a clean switch between old and new placements is
achieved by using a barrier between all the servers and the client.
This barrier ensures that (1) all servers are aware of the switch-over
and (2) all servers switch-over at the same point in the execution.
Second, messages used to implement barrier are sent over a special
channel. This avoids long barrier-induced idle times as barrier
messages no longer wait behind data messages. Third, the algorithm to
compute new placement is run as a separate thread from the main
processing. This allows the new placement to computed in parallel with
processing. The algorithm to compute the placement is run on the
client. 

\subsection{Experiments}

To study the impact of adaptation for this application, we performed
two sets of experiments. The first set of experiments used a version
of the application with the {\em one-shot} placement algorithm. These
experiments measured the impact of adapting to spatial variations.
The second set of experiments used a version of the application with
the {\em dynamic} placement algorithm. These experiments measured the
impact of adapting to temporal variations. 

To drive these experiments, and to understand the nature of network
bandwidth variations, we conducted a week-long study of network speeds
between twenty geographically dispersed hosts on the Internet.  We
repeatedly transferred a 16~KB message between host-pairs and used
return trip time to compute an estimate of the network bandwidth.  We
collected information for every host-pair over two days. We collected
a total of 40 traces. To characterize the nature of variation, we
computed three metrics.  First, what is the range of spatial
variation? That is, what is the range of variation of bandwidth across
different connections? Second, what is the range of temporal
variation? That is, what the range of variation of bandwidth over
individual connections? Third, how frequently does the bandwidth
change and once the change happens, how stable is the new value?

Figure~\ref{fig:long-bw-var} presents the first two metrics for all
host-pairs (connections) traced. We see that there is two to three
orders of magnitude variation in the bandwidth across connections
(spatial variation) as well as two to three orders of magnitude
variation in the bandwidth within individual
connections. 

\begin{figure}
\begin{tabular}{cc}
\psfig{file=max-bw-range.ps,width=3in}&
\psfig{file=norm-range.ps,width=3in}\\
(a) Spatial variation  &
(b) Temporal variation \\ 
\end{tabular}
\caption{Long-term variation in bandwidth. The values presented in the 
spatial variation graph are the estimated inherent bandwidth measures 
for the different links. The maximum bandwidth seen over two days
is used as the estimate. The values presented in the temporal variation
graph are normalized temporal variation measures. This measure is 
computed as the ratio of the range of bandwidth seen over two 
days and the minimum bandwidth seen over the same period. }
\label{fig:long-bw-var}
\end{figure}

To characterize the frequency and stability of bandwidth variation for
individual connections, we computed the average time between
significant bandwidth changes for each connection. We computed this
metric as the average runlength assuming a jitter threshold of
10\%. Figure~\ref{fig:bw-runlength} presents the results. The median
average runlength is 110 seconds.

\begin{figure}
\centerline{\psfig{file=bw-runlength.ps,height=3in}}
\caption{Stability of bandwidth variation. This graph presents 
the average runlength assuming a jitter threshold of 10\%. The median
average runlength is 110 seconds.}
\label{fig:bw-runlength}
\end{figure}

To evaluate the impact of adaptation, we compared the performance of
the two versions of the application for eight image sources and 300
network configurations.  We generated the network configurations by
constructing the complete graph amongst all the image sources and the
client and randomly assigning a trace from the bandwidth study to each
connection. For the purpose of the experiment, the computation is
assumed to consist of composition of eight sequences of 180 images -
one sequence from each source. The output consists of 180 images
delivered to the client. We used the average interarrival time between
result images as the metric of performance. Figure~\ref{fig:results}
compares impact of adapting to spatial and temporal variations.  The
metric used in both these graphs is performance improvement over a
fixed placement that places all composition operations at the client.
We note that adapting to spatial variation provides a large
performance advantage. Furthermore, adapting to temporal provides a
consistent and significant performance improvement over and above the
performance improvement achieved by adapting to spatial variation.

\begin{figure}
\begin{tabular}{cc}
\psfig{file=one-shot-vs-static-bushy-600.ps,width=3in}&
\psfig{file=global-vs-one-shot-bushy-600.ps,width=3in}\\
(a) Spatial variation  &
(b) Temporal variation \\ 
\end{tabular}
\caption{Impact of adaptation. Graph (a) shows the impact of 
adapting to spatial variations; graph (b) shows the impact 
of adapting to temporal variations. Performance improvement
is computed relative to a placement that positions all 
composition operations at the client. }
\label{fig:results}
\end{figure}

