\section{Design}
\label{design}


\subsection{Basic Design Issues}

One of the most important goals of our design is to minimize the administrative
overhead associated with installing a broker, registering host resources and
client tasks.  Since Web browsers are available on almost every platform and
architecture, and common to almost every user, our framework facilitates these
operations.  Similarly, in implementing the broker, we want to leverage
existing HTTP server technology and ways of extending server functionality
using CGI scripts~\cite{cgi-draft} or servlets~\cite{Sun96c}. In other words,
we want our architecture to be build on top of the existing Internet
infrastructure.

% Additionally, since dial-up accounts and mobile computing are common practice
% we want clients to be able to disconnect from the network after having
% submitted a task and to retrieve the result later.  Similarly, we expect
% hosts to be able to receive a task, compute it off-line, and return the
% results when the network connection is re-established. 
%{\em This probably
%should go into the goals section.}

Consequently, our design is based on the following premises:
\begin{description}
\item[Tasks:] A task on which a host can operate is represented as an applet
embedded in an HTML page.  It resides on an HTTP server and is accessible
through a URL.
\item[Hosts:] The simplest form of a host is just a Java-enabled web browser.
To work on a task the host opens the corresponding URL.
\item[Clients:] 
Clients encode tasks as applets.
We do
not assume that clients have to run their own HTTP server.  In fact, similar
to hosts, the simplest form of a client is just a Java-enabled web browser that
uploads an HTML page containing an applet to a server, and submits the URL of this page to a broker.
\item[Broker:]  The broker manages a pool of available hosts and a ready queue
of tasks, each represented by a URL.  It schedules tasks to be run on hosts, possibly
taking into account meta-level information such as machine characteristics or
the availability of a JIT compiler.
\item[Server:]  The server is an HTTP server that performs two separate
functions.  First, it stores clients' applets and serves them to hosts;
secondly, it provides point-to-point communication among hosts by serving as a
smart router.
\end{description}

\begin{figure}[htbp]
\centerline{\psfig{figure=figs/steps.eps,width=4in,clip=}}
\caption{\em {Steps involved in the remote execution of an applet.}}
\label{fig:remote_execution}
\end{figure}

Figure~\ref{fig:remote_execution} shows the steps involved in the remote execution of an applet.
These steps are:
\begin{enumerate}
\item The client uploads the applet and an embedding HTML page on an HTTP
server.  Clients running their own HTTP server may skip the first step.
\item The client registers the corresponding URL with a broker.
\item The host registers with the broker its intention to execute tasks,
and retrieves the URL of a task.
\item The host downloads the HTML page from the HTTP server, and executes its embedded applet.
\item The host stores the result at the server site.  If communication between cooperating
hosts is required, messages are stored at, and retrieved from, the server site.
\item The client retrieves the result.
\end{enumerate}

Our model supports ``subcontracting'' where hosts simultaneously act as clients: a host can
register part of its work with a broker to be done by other hosts.

\subsection{Design Implications}
\label{design_implications}

%Our approach of
Using plain web browsers enables everyone to easily participate in Javelin.
However, for purposes of security, a Java-enabled web browser disallows
applets from:
%\begin{itemize}
%\item
opening a network connection to any computer other than the server from which it
was downloaded;
%\item
listening for network connections; and
%\item
accessing the local file system.
%\end{itemize}
These restrictions imply that:
%\begin{enumerate}
%\item
communication among hosted applets must be routed through their associated servers, and that
%\item
file access implies network access.
%\end{enumerate}
%As a consequence, the server has to function as a gateway
%for any communication to the client or to other applets (e.g., in the case of a
%parallel program running on multiple hosts).  
%Additionally, the Java API only provides an interface to
%the TCP and UDP protocols.  Since applets are not allowed to listen for or
%accept network connections on any port of the local system, the broker cannot
%send datagrams to an applet.  Although communication can still be established
%through a shared namespace by exchanging files, it is highly inefficient.  The
%next section discusses alternative communication channels.
%Furthermore, applets are not allowed to access the local file system.  Thus
%data can only be stored persistently at the broker or the client, and every
%file access involves communication.
%All communication must be routed through the server, which
%additionally may serve as a file system to large numbers of clients and
%hosts.  This makes a single server a bottleneck.  We propose to use a network of
%servers instead.  Then clients and hosts as well as files are migrated between
%servers that are connected by high bandwidth communication channels.
%A host can be migrated between brokers by making the corresponding
%daemon download a new daemon from the broker it is moving to, and then terminating
%itself.
%Similarly, registration information is migrated between brokers by asking other
%brokers for URLs.  
%Since only neighboring brokers are contacted URLs are
%distributed in waves originating at the site of initial registration.  Thus,
%on one hand URLs are distributed slowly over the network, but on the other
%hand applets are likely to be downloaded by local hosts.
%The physical migration of applets is supposed to reduce the number
%of requests at the original site, but must respect
%synchronization dependencies between applets in terms of sharing memory at
%some site all applets can connect to.  Since communication stubs do not reduce
%the number of hits we propose to perform physical balancing of applets only at
%the time of submission by redirecting clients' requests to upload an applet.
%Especially, a client's request can be redirected multiple times.
%Additionally, we propose to distribute large numbers of applets that need to
%be synchronized to several brokers by providing a library to the application
%programmer implementing virtual shared memory. 
%{\em However, the final paper
%will describe migration in networks of servers more detailed.}
Furthermore, an applet is not allowed to create instances of classes that are
given by a stream of bytes\footnote{{\tt Object java.lang.Class.newInstance()}}
(that might have been received from the network).  Therefore, a daemon must ask
the underlying web browser to open a new location\footnote{{\tt void java.applet.AppletContext.showDocument( URL url )}},
and so initiate the downloading of the embedded applet with one step of
indirection.  Unfortunately, the corresponding Java API call is restricted to
applets that are currently displayed within the Web browser.  Thus, the daemon
must live in a different browser window or a different frame than applets
executed on behalf of clients.

Even though these considerations seem to complicate applications programming,
the programmer using our architecture does not have to concern herself with
any of these restrictions; they are hidden in libraries, as discussed in
Section~\ref{sec:language}.

In the future, we may use signed applets to alleviate some of these
restrictions without compromising host security.  The appletviewer
already allows applets in Java archives that are signed by a trusted entity
%(with the JDK 1.1 tool {\tt javakey})
to run with the same full rights as local applications.  That is, such applets
are not subject to the sandbox restrictions of the Java security model.
A signed daemon applet may implement a less restrictive security manager, for example
allowing an applet to communicate with its peer applets using native Java
network classes (instead of an abstraction layer hiding the routing through
servers).  This reduces the server load substantially and opens our
infrastructure to new applications, such as a distributed web
crawler.  It is an interesting research challenge to design a security model
for Javelin that is powerful enough to support a wide range of distributed
applications without compromising host security.


%\subsection{Broker/Server Services}
%\label{design:services}

%In order to submit applets, clients need to upload them to a server.  The
%clients are provided a home directory (a private namespace), and a
%mechanism to upload files on the HTTP server.
%%In terms of server technology, the site that hosts the HTTP server runs in
%%addition an FTP server, and clients get a temporary FTP account.  Basically,
%%clients are provided with a private namespace, namely their home directory,
%%and a mechanism to upload files on the HTTP server.  
%Furthermore, the broker allows clients to register and unregister URLs, and
%allows hosts to retrieve URLs.
%%Most of these services are implemented with servlets.

%%To
%%ensure {\em at-most-once} semantics it exploits IP-address based access
%%control mechanisms provided by today's HTTP servers, i.e., initially an HTML
%%page is not accessible and when a host retrieves the corresponding URL,
%%access is restricted to the host's IP-address.

%Although abstractions of storage and communication channels as well as
%synchronization constructs can be implemented by hosts and clients on top of
%a file system that can be accessed by both, dedicated {\em services} at the
%broker site can provide better performance as well as convenience.

%Recently developed HTTP servers can be extended in two ways, either by using
%the Common Gateway Interface~\cite{cgi-draft} and spawning a new process, or
%by installing servlets~\cite{Sun96c}.
%Servlets
%%, in contrast to Applets,
%are small Java programs like applets, but are executed at the server side and,
%like CGI scripts, allow for the dynamic creation of Web pages.  They can
%either be embedded into Web pages or invoked like CGI scripts.  Currently,
%Servlets are supported by JavaSoft's Jeeves\cite{Sun96c} and W3C's
%Jigsaw\cite{jigsaw}.  However, we feel that Servlets will be supported by most
%HTTP servers released in the near future.

%We have found the servlet approach to be a very convenient way of extending
%the functionality of HTTP servers with application-specific services.
%Actually, in our prototype implementation, we even allow the application to
%upload its own new servlets.  Unfortunately, ensuring security is not easy.
%Thus, we envision that in the final deployed system, only a fixed set of
%servlets will be provided.  One of the most interesting open research
%questions is how much resources (CPU time, memory, disk space) an individual
%user should be able to get on such servers.

%We propose to extend the HTTP server by services that allow an efficient
%implementation of parallel programming paradigms, efficient communication and
%convenience functions such as wrapping an applet around compiled Java classes
%or an HTML page around an applet.
%%  {\em However, the
%% final paper will present a service to wrap an applet around a compiled class.}


%\subsection{Communication}
%\label{design:communication}

%Since fast communication is crucial for parallel programs, services allowing
%for efficient {\em message passing} should be provided.  In general, messages
%between applets must be routed through the broker, because an applet cannot
%open a network connection to any site other than the one from which it was
%loaded.  Additionally, the Java API only provides an interface to the TCP and
%UDP protocols.  Since applets are not allowed to listen for or accept network
%connections on any port of the local system, the broker cannot send datagrams
%to an applet.

%Basically, there are two possibilities to enable message passing.  A routing
%service at the broker site can either link two {\em permanent} or two
%{\em temporary} socket connections possibly running a connection-less protocol
%such as HTTP (which is directly supported by the Java API) on top of TCP.
%%Either a permanent socket connection can be established or a connection-less
%%protocol such as HTTP can be used.
%These alternative approaches present a trade-off between performance and the
%maximum number of hosts that can be served by a single broker, since the
%number of socket connections that can be kept open at the same time is usually
%limited.

%Obviously, if no routing service is in place, one must be requested before
%establishing a socket connection to the broker site.
%%Similarly, a socket connection requires a peer at the server site.  Thus,
%%before establishing a socket connection to the server site, the creation of a
%%peer must be requested by connecting to the HTTP server.
%Figure~\ref{fig:applet_socket_connection} shows the steps involved in
%establishing a logical communication channel between two applets.

%\begin{figure}[htbp]
%\centerline{\psfig{figure=figs/AppletSocketConnection.eps,width=4.2in,clip=}}
%\caption{\em {Steps involved in establishing a communication channel between
%two applets.}}
%\label{fig:applet_socket_connection}
%\end{figure}

%When HTTP is used, the receiver must continuously invoke its routing service
%to pick up messages, since applets cannot listen for HTTP requests from the
%router.  Unfortunately, clients and hosts continuously connecting to the HTTP
%server increase contention as well as its work load, and thus affect the
%overall performance.  This can be avoided by delaying responses to HTTP
%requests, and returning tokens sporadically to avoid time-outs at the
%requesting site.

%Additionally, since every request increases the work load, the number of
%requests polling for some event must be minimized without introducing gaps to
%keep the overall overhead low.  We propose the use of {\em adaptive polling},
%i.e., a client or host polling the broker is returned a new polling interval
%that depends on the current work load, and all recently assigned intervals.
%%, and possibly other statistics.
%As long as all clients and hosts obey these intervals, the overall overhead is
%reduced, although it may increase for individual applications.
%%The final paper will present measurements for different work loads, and
%%different numbers of participants.

%%Furthermore, completed applets should query the broker for new parameters
%%before quitting the host to avoid the overhead of sending the same applet to a
%%different host.  However, reloading the applet to the same host may be
%%unnecessary, if the web browser uses a cache.


%\subsection{Implementation}

%Our implementation is based on an HTTP server entirely written in Java that
%runs servlets compatible with the API used by JavaSoft's Jeeves\cite{Sun96c}.  The
%broker is implemented as a servlet and schedules applets using a FIFO queue.
%Furthermore, servlets provide additional services such as form-based file
%upload (as described in {\em RFC 1867}), semaphores, a Linda tuple space and
%communication channels (as described in the previous section).  Since form-based
%file upload is supported by a broker servlet, clients can submit an applet by visiting
%a broker web page and filling out a form as shown in Figure~\ref{javelin.html}.
%The form data is posted to the servlet which creates a new directory for the task, wraps the
%applet into an HTML page residing in the task directory, and enqueues
%the corresponding URL in the task queue.

%\begin{figure}[htbp]
%\centerline{\psfig{figure=figs/Javelin.ps,width=3.4in,clip=}}
%\caption{\em {Submitting an applet to Javelin}}
%\label{javelin.html}
%\end{figure}

%Our daemon continuously polls a broker servlet until it receives an
%URL from the broker's queue. On receipt of the URL, the
%daemon asks the underlying Web browser to open it in one of two frames.  Since
%the URL points to a web page embedding an applet, the web browser is indirectly
%asked to download and execute an applet.  
%Unfortunately, in the current implementation of Netscape and Internet Explorer, 
%applet security does not prevent hostile applets from killing the daemon.


%\section{Experimental Results}
%
%Instead of the client having login access to all host machines participating
%in a computation all hosts have login access to their machines.


%\section{Conclusions}
%
%goals are achieved
%ease of use
%if the overhead of executing Java code within a web browser can be reduced
%dramatically and communication gets faster because of new technologies such as
%Fast-HTTP\cite{} or Internet 2\cite{} the proposed architecture performs well


\section{Javelin Prototype}
\label{prototype}

This section presents our prototype system.  It describes its core components, runtime
library, and API.


\subsection{Components}

The Javelin system requires at least a regular HTTP server.  File upload, routing, and the broker itself are
implemented as Java applications that are accessed via RMI as well as servlets that are compatible with the API
defined by JavaSoft \cite{Sun96c}.  Servlets allow for the smooth integration of Javelin into server technology that is
becoming more and more common in enterprises.  Optional servlets provide additional services such as form-based
file upload (as defined in {\em RFC 1867}), semaphores, and a Linda tuple space.
%Since form-based file upload is supported, clients can submit an applet by
%visiting a web page and simply filling out a form.
%%as shown in figure \ref{javelin.html}.
%The form data is posted to the servlet which creates a new directory, stores the applet, and
%wraps it into an HTML page.
In our prototype implementation, we even allow applications to upload their own
new servlets.  Unfortunately, ensuring security is not easy.  Thus, we envision
that in the final deployed system, only a fixed set of servlets will be
provided.  One of the most interesting open research questions is how much
resources (CPU time, memory, disk space) an individual user should be able to
get on such servers.

When the host registers with the broker, a daemon applet is downloaded 
that connects to the broker and blocks until the broker schedules an applet
to be run at this particular host.  On receipt of a URL, the daemon asks the underlying Web browser to open it in
a second frame.  Since the URL points to a web page embedding an applet, the web browser is indirectly asked to
download and execute an applet.  Unfortunately, in the current implementation of Netscape and Internet Explorer,
applet security does not prevent hostile applets from killing the daemon.  However,
these restrictions can be circumvented by running the daemon as an application.


\subsection{Load-Balancing Runtime Library}

In the current release, a client explicitly stores its applet at one or more servers and registers it with at least
one broker as shown in Figure \ref{fig:remote_execution}.  Load-balancing can be achieved by propagating applets between servers, and their URLs between hosts.
%The applet as well as the URL of the web page it is embedded in may be
%propagated between servers and hosts, respectively, by some load balancing scheme.  
Currently, both applets and URLs
are propagated only if some broker has insufficient applets to keep its hosts busy.
%We will refer to this scheme as {\em on demand propagation}.

Initially, the client cannot know how many --- if any --- hosts will be scheduled to run its applets.  Thus, it owns
the whole computation.  If a new host becomes available or a host finishes and becomes idle, work must be requested
from another host (where, here, the client is a special host).  As illustrated in Figure \ref{javelin_runtime}, the Javelin runtime
system implements a method to request work from other hosts.  This involves locating other hosts that run the same
applet, selecting a prospective host with work, and interrupting its ongoing computation.  If no work can be extracted from this host another host must be selected or the task request must be terminated.  The {\tt I\_WANT\_WORK} and
{\tt HERE\_IS\_WORK} messages are asynchronous.

\begin{figure}[htbp]
\centerline{\psfig{figure=figs/runtime.eps,width=3in,clip=}}
\caption{\em {The Javelin Runtime Library implementing work stealing.}}
\label{javelin_runtime}
\end{figure}


%\subsection{Work Stealing}

Currently, a prospective host is selected randomly from a local table that is updated
continuously (similar to Cilk \cite{blumofe94}).  Figure \ref{optimistic_propagation}
illustrates the implemented scheme.
%The current release implements a distributed location scheme called {\em optimistic propagation} and selects a
%victim from a local table of hosts by random (similar to Cilk \cite{}).  Figure \ref{optimistic_propagation} illustrates this scheme.
Each processor keeps a local table of hosts which it believes have work.
Initially, this table contains the client only.  In Figure \ref{optimistic_propagation_a},
host A issues a request for work to the client, because it is not aware of other
hosts.  The client cannot satisfy the request, but forwards it to host B.  It also adds
host A to its table of hosts that might have work, although there is no
guarantee that host A will actually get work.  We have experienced that this
optimistic update usually results in better performance compared to more
pessimistic schemes.  Host B splits its work, sends a portion to host A, and
updates its local table, because it is likely that A will have work in the
near future.
%it might need to steal work back later.
Finally, host A adds host B to its local table, because B might have more work.  The next time host A wants
more work it randomly sends a request to either the client or host B.  The random forwarding of requests
terminates unsuccessfully after a given number of hops.  There also is a maximum number of retries.  The time
between two retries is increased using exponential back-off.

\begin{figure}[htbp]
\begin{center}
\subfigure[]{\label{optimistic_propagation_a} \psfig{figure=figs/work_stealing1.eps,width=2.5in,clip=}}\quad\quad\hspace{1cm}
\subfigure[]{\label{optimistic_propagation_b} \psfig{figure=figs/work_stealing2.eps,width=2.5in,clip=}}
\vspace{1cm} \\
\subfigure[]{\label{optimistic_propagation_c} \psfig{figure=figs/work_stealing3.eps,width=2.5in,clip=}}\quad\quad\hspace{1cm}
\subfigure[]{\label{optimistic_propagation_d} \psfig{figure=figs/work_stealing4.eps,width=2.5in,clip=}}
\end{center}
\caption{\em {Random task request (work stealing) with optimistic propagation.  Local
tables of hosts that are assumed to have work are shown in gray.  The client
is idle, but host B has more work than it can handle.}}
\label{optimistic_propagation}
\end{figure}

The Javelin runtime system is implemented as a class of which each host must create an instance.
The host programmer cannot subclass it, since a host running within a
browser must already subclass {\tt java.applet.Applet} and the Java language does not support
multiple inheritance.


\subsection{High-Level API}
\label{high_level_api}

%As illustrated in Figure \ref{javelin_runtime}, a host must be aware of the distributed nature of the application and explicitly
%call {\tt I\_WANT\_WORK} to steal work from another host while work available locally is retrieved differently.
Using the low-level API presented in the previous section, the Javelin runtime
system calls a handler implemented by the host when a request for work arrives.
The handler thread must synchronize with the ongoing computation and, if
possible, extract work.  While flexible, this mechanism requires the programmer
to deal with complex synchronization problems.

To make programming the Javelin system easier, we have implemented a library
class that realizes a distributed task queue.  It automatically 
manages load balancing.  
The programmer simply
pushes tasks that may be executed remotely on its local stack and pops the topmost
task from the stack when it finishes its current task.  The stack itself is
implemented as a deque (double-ended queue) as shown in Figure
\ref{jstack}.
A pop on an empty deque triggers a task request being sent to
another host.  When a task request arrives, a task is removed from the
tail of the deque, if it is not empty; otherwise the request is forwarded.
%Figure \ref{jstack_usage} shows how {\tt JStack} is usually used by Javelin applications.
An example of an application that is based on our library
%creates tasks dynamically
is the raytracing program presented in Section \ref{raytracing}.  It is transparent to the application
whether a task is retrieved from the local deque or a remote host.  The
programmer is freed from any synchronization issues.

\begin{figure}[htbp]
\centerline{\psfig{figure=figs/deque.eps,width=3in,clip=}}
\caption{\em {Abstraction of a local task stack used to implement a distributed
task queue.}}
\label{jstack}
\end{figure}

%\begin{figure}
%\begin{verbatim}
%JStack stack = new JStack();
%for ( int i = 0; i < array_of_tasks.length; i++ )
%  stack.put( array_of_tasks[i] );
%
%while ( ( task = stack.pop() ) != null )
%{
%  task.run();
%}
%\end{verbatim}
%\caption{A Javelin application based on our library {\tt JStack}}
%\label{jstack_usage}
%\end{figure}


\subsection{Communication}

As discussed in Section \ref{design_implications}, any communication between applets must be routed through their associated servers.
Javelin defines a communication layer that provides the abstraction of a direct connection between applets.
%(layer four in terms of the OSI Reference Model).
It implements the classes {\tt JDatagramPacket}, {\tt JDatagramSocket}, and
{\tt JnetAddress} that mimic the native Java UDP classes in {\tt java.net},
but may be implemented on top of an arbitrary communication mechanism such as TCP
sockets, UDP sockets, RMI, NexusJava \cite{enabling}, or CORBA.

A {\tt JnetAddress} is built from the IP addresses of the host and the server it is attached to.
Figure~\ref{communication} illustrates how a message is routed from the sending
to the receiving applet.  When sending a packet to a {\tt JnetAddress} it is
{\em always} first send to the server the sender is associated with.  Then,
the server extracts the IP address of the destination host's server
from its {\tt JnetAddress}, and forwards the packet to that server.  Finally, the
packet is sent from the destination server to the destination host.

\begin{figure}[htbp]
\centerline{\psfig{figure=figs/comm.eps,width=4in,clip=}}
\caption{\em {Communication between two peer applets.}}
\label{communication}
\end{figure}

Since the number of socket connections that can be kept open at the same time is usually limited, not all servers
can be connected by {\em permanent} socket connections at any time.  However, any implementation of
{\tt JDatagramSocket} on top of a communication mechanism that requires a permanent socket connection must be
able to time multiplex between different connections.

The current release provides implementations of {\tt JDatagramSocket} on top of TCP and UDP sockets.
