webcache.tex

柯老师网站上找到的

\chapter{Web cache as an application}
\label{chap:webcache}

All applications described above are ``virtual'' applications, in the sense
that they do not actually transfer their own data in the simulator; all 
that matter is the \emph{size} and the \emph{time} when data are transferred.
Sometimes we may want applications to transfer their own data in simulations.
One such example is web caching, where we want HTTP servers to send HTTP 
headers to caches and clients. These headers contain 
page modification time information and other caching directives, which are 
important for some cache consistency algorithms.

In the following, we first describe general issues regarding
transmitting application-level data in \ns, then we discuss special
issues, as well as APIs, related to transmitting application data
using TCP as transport. We will then proceed to discuss the internal
design of HTTP client, server, and proxy cache. 

\section{Using application-level data in \ns}

\begin{figure}[tb]
  \begin{center}
    \centerline{\includegraphics{app-dataflow}}
    \caption{Examples of application-level data flow}
    \label{fig:app-dataflow}
  \end{center}
\end{figure}

In order to transmit application-level data in \ns, we provide a 
uniform structure to pass data among applications, and to
pass data from applications to transport agents (Figure
\ref{fig:app-dataflow}). It has three major components: 
a representation of a uniform application-level data unit (ADU), a 
common interface to pass data between applications, and two mechanisms
to pass data between applications and transport agents.

\subsection{ADU} 

The functionality of an ADU is similar to that of a Packet. It needs to
pack user data into an array, which is then included in the user data
area of an \ns packet by an Agent (this is not supported by current
Agents. User must derive new agents to accept user data from
applications, or use an wrapper like TcpApp. We'll discuss this
later). 

Compared with Packet, ADU provides this functionality in a different
way. In Packet, a common area is allocated for all packet headers; an
offset is used to access different headers in this area. In ADU this
is not applicable, because some ADU allocates their space dynamically
according the the availability of user data. For example, if we want
to deliver an OTcl script between applications, the size of the script
is undetermined beforehand. Therefore, we choose a less efficient but
more flexible method. Each ADU defines its own data members, and
provides methods to serialize them (i.e., pack data into an array and
extract them from an array). For example, in the abstract base class
of all ADU, AppData, we have:

\begin{program}
        class AppData \{
        private:
                AppDataType type_;  // ADU type
        public:
                struct hdr \{
                        AppDataType type_;
                \};
        public:
                AppData(char* b) \{
                        assert(b != NULL);
                        type_ = ((hdr *)b)->type_;
                \}
                virtual void pack(char* buf) const;
        \}
\end{program}

Here \code{pack(char* buf)} is used to write an AppData object
into an array, and \code{AppData(char* b)} is used to build a new
AppData from a ``serialized'' copy of the object in an array.

When deriving new ADU from the base class, users may add more data,
but at the same time a new \code{pack(char *b)} and a new constructor 
should be provided to write and read those new data members from an
array. For an example as how to derive from an ADU, look at 
\ns/webcache/http-aux.h.

\subsection{Passing data between applications}

The base class of Application, Process, allows applications to pass
data or request data between each other. It is defined as follows:
\begin{program}
        class Process \{
        public: 
                Process() : target_(0) \{\}
                inline Process*& target() \{ return target_; \}

                virtual void process_data(int size, char* data) = 0;
                virtual void send_data(int size, char* data = 0);

        protected:
                Process* target_;
        \};
\end{program}

Process enables Application to link together. 
%{\bf TBA}

\subsection{Transmitting user data over UDP}

Currently there are no supports in class Agent to transmit user
data. There are two ways to  transmit serialized ADU through transport
agents. First, for UDP agent (and all agents derived from there), we
can derive from class UDP and add a new method
\code{send(int nbytes, char *userdata)} to pass user data from
Application to Agent. To pass data from an Agent to an Application is
somewhat trickier: each agent has a pointer to its attached
application, we dynamically cast this pointer to an AppConnector and
then call \code{AppConnector::process_data()}.

As an example, we illustrate how class HttpInvalAgent is
implemented. It is based on UDP, and is inteded to deliver web cache
invalidation messages (\ns/webcache/inval-agent.h). It is defined as:

\begin{program}
        class HttpInvalAgent : public Agent \{
        public: 
                HttpInvalAgent();

                virtual void recv(Packet *, Handler *);
                virtual void send(int realsize, AppData* data);

        protected:
                int off_inv_;
        \};
\end{program}

Here \code{recv(Packet*, Handler*)} overridden to extract user data,
and a new \code{send(int, AppData*)} is provided to include user data
in packetes. An application (HttpApp) is attached to an HttpInvalAgent
using \code{Agent::attachApp()} (a dynamic cast is needed). In
\code{send()}, the following code is used to write user data from
AppData to the user data area in a packet:

\begin{program}
        Packet *pkt = allocpkt(data->size());
        hdr_inval *ih = (hdr_inval *)pkt->access(off_inv_);
        ih->size() = data->size();
        char *p = (char *)pkt->accessdata();
        data->pack(p);
\end{program}

In \code{recv()}, the following code is used to read user data from
packet and to deliver to the attached application:

\begin{program}
        hdr_inval *ih = (hdr_inval *)pkt->access(off_inv_);
        ((HttpApp*)app_)->process_data(ih->size(), (char *)pkt->accessdata());
        Packet::free(pkt);
\end{program}


\subsection{Transmitting user data over TCP}
\label{sec:webcache-tcpapp}

Transmitting user data using TCP is trickier than doing that over UDP,
mainly because of TCP's reassembly queue is only available for
FullTcp. We deal with this problem by abstracting a TCP connection as
a FIFO pipe. 

As indicated in section \ref{sec:upcalls}, transmission of application data
can be implemented via agent upcalls. Assuming we are using TCP agents, 
all data are delivered in sequence, which means we can view the TCP 
connection as a FIFO pipe. We emulate user data transmission over TCP
as follows. We first provide buffer 
for application data at the sender. Then we count the bytes received at the 
receiver. When the receiver has got all bytes of the current data transmission,
it then gets the data directly from the sender. Class Application/TcpApp is 
used to implement this functionality.

A TcpApp object contains a pointer to a transport agent, presumably either
a FullTcp or a SimpleTcp.
\footnote{A SimpleTcp agent is used solely for web caching simulations. It 
is actually an UDP agent. It has neither error recovery nor flow/congestion
control. It doesn't do packet segmentation. Assuming a loss-free network 
and in-order packet delivery,
SimpleTcp agent simplifies the trace files 
and hence aids the debugging of application protocols, which, in our case, 
is the web cache consistency protocol.}
(Currently TcpApp doesn't support asymmetric TCP agents, i.e., sender is
separated from receiver). It provides the following OTcl interfaces:

\begin{itemize}
\item \code{connect}: Connecting another TcpApp to this one. This
  connection is bi-directional, i.e., only one call to \code{connect} is 
  needed, and data can be sent in either direction. 
\item \code{send}: It takes two arguments: \code{(nbytes, str)}.
  \code{nbytes} is the ``nominal'' size of application data. \code{str} 
  is application data in string form.
\end{itemize}

In order to send application data in binary form, TcpApp provides a 
virtual C++ method \code{send(int nbytes, int dsize, const char *data)}.
In fact, this is the method used to implement the OTcl method \code{send}.
Because it's difficult to deal with binary data in Tcl, no OTcl interface
is provided to handle binary data. \code{nbytes} is the number of bytes 
to be transmitted, \code{dsize} is the actual size of the array \code{data}.

TcpApp provides a C++ virtual method \code{process_data(int size, char*data)}
to handle the received data. The default handling is to treat the data 
as a tcl script and evaluate the script. But it's easy to derive a class
to provide other types of handling.

Here is an example of using Application/TcpApp. A similar example is 
\code{Test/TcpApp-2node} in \ns/tcl/test/test-suite-webcache.tcl.
First, we create FullTcp agents and connect them:

\begin{program}
        set tcp1 [new Agent/TCP/FullTcp]
        set tcp2 [new Agent/TCP/FullTcp]
        # {\cf Set TCP parameters here, e.g., window_, iss_, \ldots}

        $ns attach-agent $n1 $tcp1
        $ns attach-agent $n2 $tcp2
        $ns connect $tcp1 $tcp2
        $tcp2 listen
\end{program}

Then we Create TcpApps and connect them:

\begin{program}
        set app1 [new Application/TcpApp $tcp1]
        set app2 [new Application/TcpApp $tcp2]
        $app1 connect $app2
\end{program}

Now we let \code{$app1} %$
be sender and \code{$app2} %$ 
be receiver:

\begin{program}
        $ns at 1.0 "$app1 send 100 \bs"$app2 app-recv 100\bs""
\end{program} %$

Where \code{app-recv} is defined as:

\begin{program}
        Application/TcpApp instproc app-recv { size } {
                global ns
                puts "[$ns now] app2 receives data $size from app1"
        }
\end{program}

\subsection{Class hierarchy related to user data handling}

We conclude this section by providing a hierarchy of classes involved
in this section (Figure \ref{fig:appdata-hier}).

\begin{figure}[tb]
  \begin{center}
    \includegraphics{appdata-hier}
    \caption{Hierarchy of classes related to application-level data handling}
    \label{fig:appdata-hier}
  \end{center}
\end{figure}


\section{Overview of web cache classes}
\label{sec:webcache-class}

There are three major classes related to web cache, as it is in the
real world: client (browser), server, and cache. Because they share a
common feature, i.e., the HTTP protocol, they are derived from the
same base class \code{Http} (Name of OTcl class, it's called
\code{HttpApp} in C++). For the following reasons, it's not a real
Application.  First, an HTTP object (i.e., client/cache/server) may
want to maintain multiple concurrent HTTP connections, but an
Application contains only one \code{agent_}.  Also, an HTTP object
needs to transmit real data (e.g., HTTP header) and that's provided by
TcpApp instead of any Agent. Therefore, we choose to use a standalone
class derived from TclObject for common features of all HTTP objects,
which are managing HTTP connections and a set of pages.  In the rest
of the section, we'll discuss these functionalities of Http. In the
next three sections, we'll in turn describe HTTP client, cache and
server.

\subsection{Managing HTTP connections}
\label{sec:webcache-connection}

Every HTTP connection is embodied as a TcpApp
object. Http maintains a hash of TcpApp objects, which are all of 
its active connections. It assumes that to any other Http, it 
has only one HTTP connection. It also allows dynamic establishment and 
teardown of connections. Only OTcl interface is provided for establishing,
tearing down a connection and sending data through a connection.

\paragraph{OTcl methods}
Following is a list of OTcl interfaces related to connection management 
in Http objects:

\begin{alist}
id & return the id of the Http object, which is the id of the node the object
is attached to. \\

get-cnc \tup{client} & return the TCP agent associated with \$client (Http object).\\

is-connected \tup{server} & return 0 if not connected to \$server, 1 otherwise.\\

send \tup{client} \tup{bytes} \tup{callback} & send \$bytes of data to 
\$client. When it's done, execute \$callback (a OTcl command). \\

connect \tup{client} \tup{TCP} & associate a TCP agent with \$client (Http object). That agent will be used to send packets \emph{to} \$client. \\

disconnect \tup{client} & delete the association of a TCP agent with \$client.
Note that neither the TCP agent nor \$client is not deleted, only the 
association is deleted.\\
\end{alist}

\paragraph{Configuration parameter}

By default, Http objects use Agent/SimpleTcp as transport agents
(section \ref{sec:webcache-tcpapp}). They can also use Agent/FullTcp
agents, which allows Http objects to operate in a lossy network.
Class variable code{TRANSPORT\_} is used for this purpose. E.g.,
\code{Http set TRANSPORT\_ FullTcp} tells all Http objects use
FullTcp agents.

This configuration should be done \emph{before} simulation starts, and 
it should not change during simulation, because FullTcp agents do not 
inter-operate with SimpleTcp agents.

\subsection{Managing web pages}
\label{sec:webcache-page}

Http also provides OTcl interfaces to manage a set of pages. The 
real management of pages are handled by class \code{PagePool} and its
subclasses. Because different HTTP objects have different requirements
for page management, we allow different PagePool subclasses to be attached
to different subclasses of Http class. Meanwhile, we export
a common set of PagePool interfaces to OTcl through
Http. For example, a browser may use a PagePool only to generate a 
request stream, so its PagePool only needs to contain a list of URLs. But
a cache may want to store page size, last modification time of every page 
instead of a list of URLs. However, this separation is not clearcut in 
the current implementation. 

Page URLs are represented in the form of:
\code{\tup{ServerName}:\tup{SequenceNumber}}
where the {\tt ServerName} is the name of OTcl object, and 
every page in every server should have a unique {\tt SequenceNumber}. 
Page contents are ignored. Instead, every page contains several 
\emph{attributes}, which are represented in OTcl as a list of the following 
(\tup{name} \tup{value}) pairs: ``modtime \tup{val}'' (page 
modification time), ``size \tup{val}'' (page size), and ``age \tup{val}''\}
The ordering of these pairs is not significant.

Following is a list of related OTcl methods.

\begin{alist}
set-pagepool \tup{pagepool} & set page pool \\

enter-page \tup{pageid} \tup{attributes} & add a page with id \$pageid
into pool. \$attributes is the attributes of \$pageid, as described above. \\

get-page \tup{pageid} & return page attributes in the format described 
above. \\

get-modtime \tup{pageid} & return the last modification time of the page 
\$pageid. \\

exist-page \tup{pageid} & return 0 if \$pageid doesn't exist in this 
Http object, 1 otherwise. \\