\section{The Broker}
\label{sec-broker}

We start with an overview of the broker architecture,
then describe a very simple broker implementation
to present the reader a concrete picture of this model.
We then discuss the broker in  more detail and
examine responsibilities, components, and possible applications.


\subsection{Architecture}

The central idea in the SuperWeb architecture is a computing broker,
which collects and monitors resources, and services requests for these
resources.  A user interacts with the broker in two
ways, by registering or requesting resources.
%
The broker matches clients with host machines for running
computations.  Figure~\ref{fig-register} depicts the interaction
between three hosts and the broker after a client has submitted
three tasks. The broker sends the tasks to the three
hosts which had previously registered their CPUs. To avoid
contention at the broker, it does not ship actual client tasks,
but rather sends a URL pointer to the tasks. The hosts then directly
retrieve the chosen task from the client.

\begin{figure}[htbp]
\centerline{\psfig{figure=superweb.ps,height=2in}}
%
\caption[Broker]{\label{fig-register}
{\em
Three host machines receive client tasks from the broker.
}}
\end{figure}

A key design feature of this architecture is that the host software
  runs completely at the user-level, and only requires that
registered machines have a WWW browser, such as Netscape, which can
run untrusted code, such as Java applets.
We do not require clients to actually have access (e.g., login
privileges) to the host machines running their code. 


% This part can be put in the prototype section
%
%While the broker model supports the use of different languages and
%executables, we currently support only Java.  This provides a
%universal language for SuperWeb, and simplifies the implementation.


\subsection{Prototype Implementation}

We exemplify the idea of brokers with the very first prototype of
SuperWeb that we implemented using Netscape browsers and Java applets.
This was a rudimentary implementation based on HORB \cite{HORB}. It
had poor performance and none of the enhancements discussed later.
Nevertheless, it is a good practical illustration of how SuperWeb can
be implemented.

% To illustrate the idea of SuperWeb brokers, we implemented a simple
% prototype using Netscape clients and Java applets. This rudimentary
% implementation is based on the HORB object request broker \cite{HORB},
% and offers none of the enhancements discussed later.  

In the prototype, hosts register their CPU by visiting a broker web page.
This causes
the host to download a Java applet, which stays in contact with the
broker and downloads client's Java/HORB objects for execution until the
user leaves that broker web page.  Clients submit tasks by visiting a
different web page and submitting a form to request resources.  On
this form, they specify the Java program (also a URL) they wish to
have executed.

As clients request resources, the broker maps these to the next
available host, using a simple round-robin algorithm.  Once a host is
selected, the broker retrieves the client applet (URL) and submits it
to the host.  The host then starts executing it and delivers the
result directly to the client. Finally, after finishing a task, the
host contacts the broker again and signals its readiness for new
tasks.

%Since we were not satisfied with the performance results, we are now
%working on a more sophisticated broker version, Javelin
%\cite{javelin}, that is more optimized for speed and implements more
%features. In Section \ref{sec:Measurements},


\subsection{Broker Responsibilities}

The broker is responsible for three main activities:  registering hosts,
accepting client requests, and overseeing the interaction between the
client and host.

\begin{description}
\item[Registering hosts:]

  Owners of machines can register with the broker, 
allowing their computer to become part of the SuperWeb.
They  specify when
their machines can be used and what percentage of resources are
available.
%  The broker will send and execute a microbenchmark on the host
%  to determine its compute characteristics.


\item[Accepting client requests:]

Users make requests to the broker for the use of resources.  A typical
request would ask for a particular quality of service.  This includes
such properties as a time limit (how soon the results should be
returned), required bandwidth, memory, floating point accuracy, etc.
It could even include a request for a particular type of machine, or
group of machines.  

\item[Overseeing client/host interaction:]

The broker must match host machines with client tasks.
Conceptually, the broker itself sends the tasks to the hosts
(and is responsible for sending the results back to the client).
% In this approach, the host may not know what client it serves,
% and the client may not know what host runs its tasks.
In practice, this would make the broker a bottleneck. Therefore,
in the actual implementation the broker only ``introduces'' the
client and the host to one another and is not involved in further
communication. In this scheme the broker is only responsible for
keeping accounting and other bookkeeping information for the host
and the client and is not involved in the transfer of tasks, data,
or results between them.

% Instead of these anonymous exchanges, we can also use a host-driven or
% a client-driven model.  In the host-driven (seller) model, hosts are
% presented with a list of potential clients/buyers (represented as URLs
% to the client tasks), and the hosts choose what they wish to compute.
% In the client-driven (buyer) model, clients choose from a list of
% hosts.  In this case, the broker returns a ticket to the client; part
% of this ticket contains the URL to the host, so that the client can
% connect to the resources and use them.
%
% These two approaches--- which of course can be combined--- have some
% advantages over the anonymous transactions in the basic model:
% First, the broker does not have to choose the best match between a
% client and a host; it just has to present a list of suitable matches.
% Second, the broker does not necessarily have to handle the shipping
% of the program, input, and output between the host and client.

\end{description}

Client applications are not limited to sequential computations.  Users can
submit computations that involve  parallel or distributed subtasks,
and the broker can map a request onto multiple computers:  either
a tightly-coupled network of workstations, or a number of scattered
resources, depending on the communication requirements.
Furthermore, the brokers themselves may be distributed processes,
allowing this model to scale very well as thousands of machines
register.

% Thus, the overall scheme is as follows:
%  Hosts register a fraction of
%  their computing resources (CPU time, memory, bandwidth, disk space)
%  with resource brokers. Upon a computation request, the broker
%  maps the computation (possibly involving parallel or distributed
%  subtasks) onto the available computing resources, potentially using
%  thousands of computers.


\subsection{Broker Modules}

The broker consists of three modules: the interface, the
scheduler, and the accounting module.

\begin{description}

\item[Broker Interface:]

  This is what users see when registering their machines or requesting
resources.  The initial version of this module is the most
straightforward to build, as it is just a web page with forms for the
client or hosts to fill in.

\item[Scheduler:]

The scheduler has the job of assigning incoming tasks to available resources,
based on the specified task requirements and hosts capabilities.
  The scheduling algorithm is
  heuristic, since mapping resources optimally is computationally
  infeasible, especially in the scale and with the range of variables
  envisioned. Moreover, the broker has only incomplete information,
  since hosts might become unreachable or might make false claims about
  their capabilities, like CPU power, memory and disk space, network
  bandwidth, or deadlines.  To estimate the host capabilities, the
  broker does not trust the host completely, but instead runs small
  micro-benchmarks to characterize the resources and determine the
  machine's capabilities.
  The results are  used to heuristically find a good match
  between task requirements and host machines.


% The scheduler knows the capabilities of the host machines and
% the requirements of the tasks submitted by the clients. 
% The clients are responsible for specifying the desired computational
% resources, CPU power, memory and disk space, network bandwidth as well
% as constraints on when and for how long the task should be executed.

\item[Accounting Module:]

This module keeps track of the charges incurred by the client, and
credits gained by the hosts.  This can be viewed as part of the
scheduler, since the cost of the services rendered is related to what
host is chosen.

\end{description}

%  \begin{figure}[htbp]
%  \vspace{0.1in}
%  %\centerline{\psfig{figure=figs/bw-get-t3d.eps,height=2in}
%  \caption[Broker]{\label{fig-kiviat}
%  {\em
%  Performance characteristics of three clients:  a PC, a Sun, and a Cray.
%  The broker will run a micro-benchmark to determine these characteristics,
%  then use this data to help map tasks to these machines.
%  }}
%  \end{figure}

\subsection{Examples and Uses}

We envision three types of users for the broker: the typical
user looking for some extra computational power;
supercomputer users, looking to acquire hundreds or thousands of
machines; and Internet station owners, who otherwise
have no usable computing resources of their own.

\begin{description}
\item[Typical User:] The average user already has a complete
  workstation, but occasionally needs extra resources.  He is willing
  to trade some of his CPU time (by registering his machine), in
  return for cycles from other machines.  This is a win-win situation
  since most machines have idle cycles. For example, many users would
  not hesitate to register their machine after hours, or during their
  coffee break or meetings.
  
  An important prospective source of clients and hosts is the
  multi-player game software market.  There already exist chess,
  bridge, flight-simulator and other game servers that allow real-time
  gaming over the Internet among subscribers (users) or with a
  computer as opponent.  A single centralized server is hardly
  powerful enough for an interactive virtual reality game, or computer opponent
  for strategy games, which essentially are distributed computations.
  Under the SuperWeb model, the server can play the role of a broker
  and users may register their machines as hosts during idle time. The
  registered hosts can be used by the server itself or by other
  currently active subscribers that have slow machines. In exchange,
  the owner of a host may get a reduced subscription fee or other
  bonuses. 
  
  Another possibility are software {\em parasites}, which we define as
  useful computations that run in the background.  A user downloading
  a game, for example, can pay for it by willingly allowing a parasite
  to use part of her computer resources while she plays the game.
  
\item[Supercomputing:] Large scale supercomputing is another potential
  application of our system.
%  While other systems, such as MPI, PVM,
%  and Legion are geared specifically toward parallel applications and
%  relatively fast communication, SuperWeb has one significant advantage.
  Since SuperWeb requires no operating system changes, and
  clients need no direct access to all hosts, the potential pool of
  participating machines is very large. Therefore, for course-grained
  parallel tasks with little communication, we could feasibly support the
  worlds largest supercomputer.
  
  Using such a large number of machines is probably too expensive,
  since most people would register their machines in return for
  something more than curiosity.
%  On the other hand, perhaps we would
%  bank on such curiosity for our first massive supercomputing test:
%  "Be part of the first teraflop computation.  Just register 1 CPU
%  hour with the broker by midnight, January 1st, 1998.  We'll do the
%  rest."
%
%it would be reasonable to expect that
%many users would be willing to donate an hour of their machine's time to
%running such an experiment.  I.e., normally a user registering their
%machine would expect something in return, but in this case they may do
%so out of curiosity.
%
%  
  Corporations may be willing to pay for the use of thousands of
  machines in order to run large parallel applications, but only if their
  work is secure and the results can be trusted.  This issue is
  discussed later in Section~\ref{sec:Crypto}.


\item[Internet Stations:]  

% There is a great deal of hype over the release of new Internet stations:
  Another emerging technology is the Internet station (also
  called \emph{thin client}, \emph{web station} or \emph{network
    computer}): a relatively cheap box that allows connection to the
  Internet.  Internet stations lack a general purpose operating system
  and can only run programs that are downloaded.  The broker model
  would provided such clients with the ability to choose an arbitrary
  host for all sorts of computing services.
\end{description}




%------------
\subsection{Broker Extensions}

We plan to incorporate the following features in future implementations of
the SuperWeb broker.

\begin{description}
  
\item[Other languages support:] Currently we support only Java for
  client tasks.  We can extend the implementation to allow
  arbitrary executables and languages. Also, we might make use of other
  mobile languages, like the ``E'' programming language \cite{elang}
  or the \emph{limbo} language from the \emph{inferno} operating
  system \cite{inferno}, which promise better security features or
  faster execution.
  
\item[Verifying results:] One important concern is the integrity of
  the result returned from an anonymous host to the client.  The
  broker could assist the client in verifying that the output from
  client computations is correct and can be trusted.
%  Otherwise a machine could claim to be more
%  powerful than it is, then just return bad results.
  
\item[Service requests:] Instead of just providing requests for hosts,
  the broker could provide requests for particular services, such as
  ``Run Fast Fourier Transform on this input'', or ``produce a graph
  of this data using Excel 4.0''.  (There already exist projects of
  this nature \cite{netsolve,NEOS}.) This notion could also be
  embraced by sites serving the network computers mentioned above.
\end{description}






