webcache.tex

柯老师网站上找到的

set-page-generator \tup{pagepool} & attach a PagePool to generate 
random page IDs.\\

set-interval-generator \tup{ranvar} & attach a random variable to generate
random request intervals.\\
\end{alist}


\section{Web server}
\label{seccom:webcache-server}

Class Http/Server models behavior of a HTTP server. Its
configuration is very simple. All that a user needs to do is to create 
a server, attach a PagePool and wait:

\begin{program}
        set server [new Http/Server $ns $node] \; attach \$server to \$node;
        $server set-page-generator $pgp \; attach a page pool;
\end{program}

An Http/Server object waits for incoming requests after simulation starts.
Usually clients and caches initiates connection to an Http/Server. But 
it still has its own \code{connect} method, which allows an Http/Server 
object to actively connect to a certain cache (or client). Sometimes this
is useful, as explained in Test/TLC1::set-groups\{\} in 
\ns/tcl/test/test-suite-webcache.tcl.

An Http/Server object accepts two types of requests: GET and IMS.  GET
request models normal client requests. For every GET request, it
returns the attributes of the requested page.  IMS request models
If-Modified-Since used by TTL algorithms for cache consistency. For
every IMS (If-Modified-Since) request, it compares the page
modification time given in the request and that of the page in its
PagePool. If the time indicated in the request is older, it sends back
a response with very small size, otherwise it returns all of the page 
attributes with response size equal the real page size.


\section{Web cache}
\label{sec:webcache-cache}

Currently 6 types of web caches are implemented, including 
the base class Http/Cache. Its five derived subclasses 
implement 5 types of cache consistency algorithms: Plain old TTL, 
adaptive TTL, Omniscient TTL, Hierarchical multicast invalidation, 
and hierarchical multicast invalidation plus direct request.

In the following we'll only describe the base class Http/Cache, because 
all the subclasses involves discussion of cache consistency algorithms 
and it does not seem to be appropriate here.

\subsection{Http/Cache}
\label{sec:webcache-cache-base}

Class Http/Cache models behavior of a simple HTTP cache with infinite 
size. It doesn't contain removal algorithm, nor consistency algorithm. 
It is not intended to be used by itself. Rather, it is meant to be a 
base class for experimenting with various cache consistency algorithms and
other cache algorithms. 

\paragraph{Creation and startup}

Creating an Http/Cache requires the same set of parameters as
Http/Client and Http/Server. After creation, a cache needs to connect 
to a certain server. Note that this creation can also be done dynamically,
when a request comes in and the cache finds that it's not connected to 
the server. However, we do not model this behavior in current code.
Following code is an example:

\begin{program}
        set cache [new HttpCache $ns $node] \; attach cache to \$node;
        $cache connect $server \; connect to \$server;
\end{program}

Like Http/Server, an Http/Cache object waits for requests (and packets
from server) after it's initialized as above. When hierarchical
caching is used, the following can be used to create the hierarchy:

\begin{program}
        $cache set-parent $parent \; set parent cache;
\end{program}

Currently all TTL and multicast invalidation caches support hierarchical
caching. However, only the two multicast invalidation caches allows 
multiple cache hierarchies to inter-operate.

\paragraph{OTcl methods}

Although Http/Cache is a SplitObject, all of its methods are in OTcl. 
Most of them are used to process an incoming request. Their relations can
be illustrated with the flowchart below, followed by explainations:

\begin{figure}[h]
  \begin{center}
    \includegraphics{cache-flowchart}
    \caption{Handling of incoming request in Http/Cache}
    \label{fig:webcache-handle-request}
  \end{center}
\end{figure}

\begin{alist}
get-request \tup{client} \tup{type} \tup{pageid} & 
The entry point of processing any request. It checks if the requested 
page \$pageid exists in the cache's page pool, then call either 
\code{cache-hit} or \code{cache-miss}. \\

cache-miss \tup{client} \tup{type} \tup{pageid} & 
This cache doesn't have the page. Send a request to server (or parent 
cache) to refetch the page if it hasn't already done so. Register 
\$client in a list so that when the cache gets the page, it'll forward
the page to all clients who have requested the page. \\

cache-hit \tup{client} \tup{type} \tup{pageid} &
Checks the validatity of the cached page. If it's valid, send \$client
the cached page, otherwise refetch the page. \\ 

is-consistent \tup{client} \tup{type} \tup{pageid} & 
Returns 1 if \$pageid is valid. This is intended to be overridden by 
subclasses. \\

refetch \tup{client} \tup{type} \tup{pageid} & 
Refetch an invalid page from server. This is intended to be overridden 
by subclasses. \\
\end{alist}


\section{Putting together: a simple example}
\label{sec:webcache-example}

We have seen all the pieces, now we present a script which provides a
complete view of all pieces together. First, we build topology and 
other usual initializations:

\begin{program}
        set ns [new Simulator]

        # Create topology/routing
        set node(c) [$ns node] 
        set node(e) [$ns node]
        set node(s) [$ns node]
        $ns duplex-link $node(s) $node(e) 1.5Mb 50ms DropTail
        $ns duplex-link $node(e) $node(c) 10Mb 2ms DropTail 
        $ns rtproto Session
\end{program}

Next we create the Http objects:

\begin{program}
        # HTTP logs
        set log [open "http.log" w]

        # Create page pool as a central page generator. Use PagePool/Math
        set pgp [new PagePool/Math]
        set tmp [new RandomVariable/Constant] \;# Page size generator;
        $tmp set val_ 1024  \;# average page size;
        $pgp ranvar-size $tmp
        set tmp [new RandomVariable/Exponential] \;# Page age generator;
        $tmp set avg_ 5 \;# average page age;
        $pgp ranvar-age $tmp

        set server [new Http/Server $ns $node(s)] \;# Create a server and link it to the central page pool;
        $server set-page-generator $pgp
        $server log $log

        set cache [new Http/Cache $ns $node(e)] \;# Create a cache;
        $cache log $log

        set client [new Http/Client $ns $node(c)] \;# Create a client;
        set tmp [new RandomVariable/Exponential] \;# Poisson process as request sequence;
        $tmp set avg_ 5 \;# average request interval;
        $client set-interval-generator $tmp
        $client set-page-generator $pgp
        $client log $log

        set startTime 1 \;# simulation start time;
        set finishTime 50 \;# simulation end time;
        $ns at $startTime "start-connection"
        $ns at $finishTime "finish"
\end{program} %$

Then we define a procedure which will be called after simulation
starts.  The procedure will setup connections among all Http objects.
\begin{program}
        proc start-connection {} {
                global ns server cache client
                $client connect $cache
                $cache connect $server
                $client start-session $cache $server
        }
\end{program} %$

At the end, the usual closing:
\begin{program}
        proc finish {} {
                global ns log
                $ns flush-trace
                flush $log
                close $log
                exit 0
        }
        $ns run
\end{program}

This script is also available at \ns/tcl/ex/simple-webcache.tcl. 
Examining its output \code{http.log}, one will find that the result of 
the absense cache consistency algorithm results in a lot of stale hits. 
This can be easily remedied by replacing ``new Http/Cache'' line with:
\code{set cache [new Http/Cache/TTL $ns $node(e)]}. For more complicated
cache consistency algorithm examples, see 
\ns/tcl/test/test-suite-webcache.tcl.

\section{Http trace format}
\label{sec:webcache-trace}

The trace file of Http agents are constructed in a similar way as the
SRM trace files. It consists of multiple entries, each of which
occupies one line.  The format of each entry is:

\begin{tabular}[h]{c|c|c}
  Time & ObjectID & Object Values
\end{tabular}

There are three types of objects: client ({\bf C}), cache ({\bf E})
and server ({\bf S}). Following is a complete enumeration of all possible 
events and value types associated with these three types of objects.

\begin{center}
  \begin{tabular}[h]{c|c|l}
    \emph{Object Type} & \emph{Event Type} & \emph{Values} \\ \hline
    E & HIT & \tup{Prefix} \\
    E & MISS & \tup{Prefix} z \tup{RequestSize} \\
    E & IMS & \tup{Prefix} z \tup{Size} t \tup{CacheEntryTime} \\
    E & REF & p \tup{PageID} s \tup{ServerID} z \tup{Size} \\
    E & UPD & p \tup{PageID} m \tup{LastModifiedTime} z \tup{PageSize} \\
    &     & s \tup{ServerID} \\ 
    E & GUPD & z \tup{PageSize} \\
    E & SINV & p \tup{PageID} m \tup{LastModTime} z \tup{PageSize} \\
    E & GINV & p \tup{PageID} m \tup{LastModTime} \\
    E & SPF & p \tup{PageID} c \tup{DestCache} \\
    E & RPF & p \tup{PageID} c \tup{SrcCache} \\
    E & ENT & p \tup{PageID} m \tup{LastModifiedTime} z \tup{PageSize} \\
    &     & s \tup{ServerID} \\ \hline
    C & GET & p \tup{PageID} s \tup{PageServerID} z \tup{RequestSize}\\
    C & STA & p \tup{PageID} s \tup{OrigServerID} l \tup{StaleTime}\\
    C & RCV & p \tup{PageID} s \tup{PageServerID} l \tup{ResponseTime} z \tup{PageSize}\\ \hline
    S & INV & p \tup{PageID} m \tup{LastModifiedTime} z \tup{Size} \\
    S & UPD & p \tup{PageID} m \tup{LastModifiedTime} z \tup{Size} \\
    S & SND & p \tup{PageID} m \tup{LastModifiedTime} z \tup{PageSize} \\
      &     & t \tup{Requesttype} \\
    S & MOD & p \tup{PageID} n \tup{NextModifyTime} \\
  \end{tabular}
\end{center}

\tup{Prefix} is the information common to all trace entries. It includes:

\begin{center}
  \begin{tabular}[h]{c|c|c}
    p \tup{PageID} & c \tup{RequestClientID} & s \tup{PageServerID}
  \end{tabular}
\end{center}

\emph{Short Explaination of event operations}: 

\begin{center}
  \begin{tabular}[h]{c|c|l}
    \emph{Object Type} & \emph{Event Type} & \emph{Explaination} \\ \hline
    E & HIT & Cache hit. PageSererID is the id of the ``owner'' of the page. \\
    E & MISS & Cache miss. In this case the cache will send a request to the
    server to fetch the page. \\
    E & IMS & If-Modified-Since. Used by TTL procotols to validate an expired 
    page. \\
    E & REF & Page refetch. Used by invalidation protocols to refetch an 
    invalidated page. \\
    E & UPD & Page update. Used by invalidation protocols to ``push'' updates\\
      & & from parent cache to children caches. \\
    E & SINV & Send invalidation. \\
    E & GINV & Get invalidation. \\
    E & SPF & Send a pro forma \\
    E & RPF & Receive a pro forma \\
    E & ENT & Enter a page into local page cache. \\ 
    \hline
    C & GET & Client sends a request for a page. \\
    C & STA & Client gets a stale hit. OrigModTime is the modification time \\
    & & in the web server, CurrModTime is the local page's modification time.\\
    C & RCV & Client receives a page. \\
    \hline
    S & SND & Server send a response. \\
    S & UPD & Server pushes a page update to its ``primary cache''. Used by
    invalidation protocol only. \\
    S & INV & Server sends an invalidation message. Used by invalidation 
    protocol only. \\
    S & MOD & Server modified a page. The page will be modified next
    at \tup{NextModifyTime}. \\
  \end{tabular}
\end{center}


\section{Commands at a glance}
\label{sec:webcachecommand}

Following are the web cache related commands:
\begin{flushleft}
\code{set server [new Http/Server <sim> <s-node>]}\\
This creates an instance of an Http server at the specified <s-node>. An
instance of the simulator <sim> needs to be passed as an argument.


\code{set client [new Http/Client <sim> <c-node>]}\\
This creates an instance of a Http client at the given <c-node>.


\code{set cache [new Http/Cache <sim> <e-node>}\\
This command creates a cache.


\code{set pgp [new PagePool/<type-of-pagepool>]}\\
This creates a pagepool of the type specified. The different types of pagepool
currently implemented are:\\
PagePool/Math, PagePool/CompMath, PagePool/ProxyTrace and PagePool/Client.
See section \ref{sec:webcache-pagepool} for details on Otcl interface for
each type of Pagepool.


\code{$server set-page-generator <pgp>}\\
\code{$server log <handle-to-log-file>}\\
The above commands consist of server configuration. First the server is
attached to a central page pool <pgp>. Next it is attached to a log file.


\begin{program}
client set-page-generator <pgp>
$client set-interval-generator <ranvar> 
$client log <handle-to-log-file>
\end{program}
These consist configuration of the Http client. It is attached to a central
page pool <pgp>. Next a random variable <ranvar> is attached to the client
that is used by it (client) to generate intervals between two consecutive
requests. Lastly the client is attached to a log file for logging its events.


\code{$cache log <log-file>}\\
This is part of cache configuration that allows the cache to log its
events in a log-file. 


\code{$client connect <cache>}\\
\code{$cache connect <server>}\\
Once the client, cache, and server are configured, they need to be
connected as shown in above commands.


\code{$client start-session <cache> <server>}\\
This starts sending request for a random page from the client to the
<server> via <cache>.

\end{flushleft}
\endinput

% Local Variables:
% TeX-master: "everything"
% LocalWords:
% End:
% LocalWords:  HTTP tb app dataflow ADU OTcl AppData AppDataType struct hdr buf
% LocalWords:  const AppConnector inline int TclCL HttpApp webcache http nbytes
% LocalWords:  userdata HttpInvalAgent inteded inval recv realsize inv FullTcp
% LocalWords:  SimpleTcp bi str dsize Tcl tcl tcp iss ns TcpApps Mb ms DropTail
% LocalWords:  tmp val RandomVariable pgp ranvar avg startTime finishTime proc