\documentstyle[tgrind,11pt]{article} 
\setlength{\parindent}{0.5in}


\newpage
\vspace{\baselineskip}
\vspace{\baselineskip}
\title{\hfill\break \hfill\break Dynamic Hierarchical Caching \\ for the
World Wide Web} 
\author{Martha H Greenberg \\ AUP Supervisor: David R. Karger}
\date{February 6, 1997}

\begin{document}
\maketitle
\thispagestyle{empty}
\newpage
\begin{raggedright}
\setlength{\parindent}{0.5in}
\section{The Project}
\indent

The World Wide Web is a system for distributing documents, including
hypertext, images, sound files, plain text, audio, animations
and applications.  One of the most visible problems for the web today
is slow response time due to overloaded networks and servers.  Very
popular web sites get too many queries at once and respond very slowly
or not at all.

A web document is uniquely identified by a Uniform Resource Locator
(URL).  The URL for a document contains the protocol that should be used
to ask for the document, the name of the machine which has the document
(the content server), and the pathname by which the machine can identify
the document.  In the simplest web scheme, a client will directly
request the document from the content server every time the user
requests to see the document.

Caching is the storage of retrieved documents locally for further use.
Therefore, it is not necessary to connect to the content server the
next time that document is requested.  This technique reduces the number of
requests the content server must process.  A proxy server is a machine
that receives requests from a number of machines; it then either serves
the request itself, denies the request or forwards the request to the
real server.  A proxy cache server is a proxy server that caches the
information that went through the proxy.  Since the proxy server is
usually closer (in terms of network throughput) and less loaded than the
content server, the client sees a faster response to their query.
Caching also saves network bandwidth to the content server.

In current hierarchical caching schemes, the hierarchy of machines is
fixed.  Neighbors are other caches which are on the same level of the
hierarchy.  Parents are on a higher level, and children on a lower
level.  A cache will make a request to another cache, usually its
parent, if it does not have a valid copy of the document being
requested.  If no other caches have the document, it will request the
document from the content server.  Machines higher in the hierarchy are
responsible indirectly for more clients and will be asked for more
distinct documents.


In the Harvest/Squid scheme, each machine knows a list of
neighbors and parents to whom it can make requests.  The network
administrator must give the cache a list of what other caches it can
ask, and whether they are neighbors or parents.  This list is the same
for all documents, so if the cache receives multiple requests for
different documents that it does not have, it asks the same set of
caches for all of them.


A major problem with current hierarchical caching schemes is that caches
near the top of the hierarchy are responsible for a very large number of
distinct documents and may become overloaded processing queries for
those documents.  The ultimate goal of this project is to set up a
system in which it is very unlikely for a single caching server to
become overloaded with queries relative to other caching servers.

I have been working for David R. Karger in the Algorithms groups of
the Theory of Computation Group of the Laboratory for Computer Science.
He has designed an algorithm that may solve this problem.  My project
was intended to determine if this algorithm would work in the current
Internet, and if it would be more efficient than the schemes that are
currently in use.


The proposed new algorithm differs in that there is a unique hierarchy
of parents for each URL.  The cache builds this hierarchy in a number of
steps.  First, an abstract tree of degree $d$ is constructed.  This tree
and the degree $d$ depend on only on the number of caching servers.
Then a hashing function maps {\tt(tree node, URL)} pairs to caching servers.
When the cache gets a request for a document, it picks a random leaf in
the abstract tree, computes the path from the leaf to the root, and then
maps the abstract tree nodes onto actual caching servers using the URL.
The cost to the new algorithm is that the cache must have a near-recent list
of all the proxy servers in the cache system.  This is a benefit, since
no caching server is at the top of any fixed hierarchy, all
caching servers will be responsible for about the same
number of distinct documents and queries.


I have implemented this algorithm by modifying the Squid caching and
proxying system from the National Laboratory for Applied Network
Research (developed from the Harvest project at the University of
Colorado).  In order to do this, I have also extended the currently used
cache protocol to allow the machines to communicate which machines on
the network are using this algorithm.  They also have to pass along
where they are in the hierarchy for a particular document, so that the
next machine does not have to recompute the entire hierarchy.

I have  implemented this algorithm for determining what cache to
ask for a particular document.  I have also integrated it with
Squid so that Squid uses this algorithm for determining what other
caches to ask for a document, rather than using its fixed
hierarchy.



\section{Code Overview}
\indent

All changes are against Squid version 1.1.3.  All the changes to the
Squid code are set off by the comments (DH stands for Dynamic
Hierarchy):
\begin{verbatim}
	/* begin DH changes */
	/* end DH changes */
\end{verbatim}


When Squid starts up, if it is run with the -d option, the variable
opt\_dynamic\_hierarchy get set.  The rest of the changes are conditional
on that variable.

At the startup, Squid gets an initial list of all the hosts in network
from another server.  Right now, only one server can be specified.  TBhe
server's name can be compiled in, or specified when starting squid with
the -S option.

Squid then goes through its primary select loop.  In this loop, it
checks how long it has been since the last update.  If it is longer than
the set time, it gets a list of all the changes since the last update.

When Squid gets a request that is not in cache, Squid is told that there
is only one neighbor, a parent.  Instead of getting this parent from the
configuration file, as would be normally done, it calls {\tt dhGetParent()}.
This procedure builds a tree, maps the URL against the unit interval and
finds the correct parent for this machine in that tree.  This is done in
proto.c.

\section{Netserv}
\indent

Netserv uses a simple TCP based protocol to let hosts participate in the
network.  The client makes a TCP connection to the netserv server on the
assigned port (port 8999 was used for this implementation), and sends a
request.  The possible requests are: join $[\langle$points$\rangle]$,
dele, list, since $\langle$time$\rangle$, and help.  Join adds the host to the
network, dele deletes it from the network, list lists all the hosts in
the network, since returns all the changes since the specified time and
help prints a help message.  Join takes an optional argument of the
number of points on the unit interval that the host wants to take.
Since takes a mandatory argument of a time in seconds since 00:00:00
UTC, January 1, 1970 (the Unix epoch).

The server responds with a three-digit response code
followed by a human-readable explanation.  In the cases of list, since
and help, it also is followed by the requested information.  A response
code of the form 1xx indicates a usage message, 2xx indicates a
successful request and 4xx indicates a failed request.

\setlength{\parindent}{0in}
\section{Modified files from the Squid distribution}

	src/squid.h \\
	src/main.c \\
	src/proto.c \\
	src/Makefile.in \\



squid.h - add the global variables and include files needed for the new
	functions. 

main.c - add a flag (-d) to Squid to use the dynamic hierarchy code, and
	a flag (-S name) to change the default netserv server.
	get the list of hosts in the network, and keep it updated.

proto.c - change the code to call the dynamic functions when necessary,
	rather than the Squid ones.
	tell Squid there is only a single parent, and generate that.

Makefile.in - Add the new object files to the list of ones needed to
	generate the Squid binary and build the netserv program.

\section{Files added to Squid}

chash.h \\
chash.c \\
common.h \\
crc.h \\
crc.c \\
deal.h \\
deal.c \\
dhrand.h \\
dhrand.c \\
getnet.h \\
getnet.c \\
netserv.c \\


\subsection{Procedures}
chash.h - includes, defines, structures and procedure declarations that
        are used in chash.c

chash.c - procedures for making a consistent hash.
\begin{verbatim}
/* get a number of points for a machine */
int dhGetMachinePoints(char *hostname, int points);

/* add a machine,point pair to the unit interval */
int dhAddMachineToInterval(char *hostname, double d );

/* find the nearest machine to any point on the unit interval */
struct machplace * dhFindNearestMachine(double point);

/* construct the unit interval and fill it with hosts */
int dhBuildUI(); 

/* construct the tree until we find ourself in it */
int dhBuildTree(char *url, int n); 

/* take a hostname, and make an edge out of it.
edge * dhMakeEdge(char *host);

/* take a url and find the immediate parent */
edge * dhGetParent(char *url);

/* return the number of neighbors */
int dhNeighborsCount(edge *dhparent);
\end{verbatim}


common.h - definitions and structures that used in deal.c, getnet.c and
	netserv.c 


crc.h - includes, defines, structures and procedure declarations that
        are used in crc.c

crc.c - procedures for generating a crc32 hash.
\begin{verbatim}
/* compute the crc32 hash for a string */
long crc32(char *buf, int len);

/* initialization procedure that must be called before crc32 */
void init_crc32(); 
\end{verbatim}

deal.h - includes, defines, structures and procedure declarations that
	are used in deal.c

deal.c - Handle the requests made in netserv.c or getnet.c.
\begin{verbatim}
/* add a host to the host table, check for duplicates */
int addhost(char address[MAXADDR], time_t ntime, int np);

/* delete a host from the host table if it is there */
int delhost(char address[MAXADDR]);

/* print a list that represents the current network state */
int list(int newsockfd);

/* print out all the changes since time stime */
int since(int newsockfd, time_t stime);

/* dump the current network state to the dump file */
int dump();

/* read a dump file and construct a host table from it */
int readdump();
\end{verbatim}



dhrand.h - includes, defines, structures and procedure declarations that
        are used in dhrand.c

dhrand.c - non-system specific version of rand and srand, so that we get
	reliable results across platforms
\begin{verbatim}
/* generate a pseudo-random number */
int dhRand();

/* seed for generating a pseudo-random number */
void dhSrand(seed);
\end{verbatim}

getnet.h - includes, defines, structures and procedure declarations that
        are used in getnet.c

getnet.c - Get what other machines are on the network, and keep this
updated.
\begin{verbatim}
/* get the initial network */
int getnet();

/* get the changes since ltime */
int getupdate(time_t ltime);

/* parse the log file and do the changes indicated */
int readupdate();

/* add this host to the network */
int addself();

/* delete this host from the network */
int delself();

/* open a socket to the server */
int sopen();
\end{verbatim}

netserv.c - Separate program that will maintain and serve the list of
who is on the network.
\begin{verbatim}
/* main loop. start up, wait for connections and deal with them */
int main(int argc, char *argv[]);

/* print a usage message */
void nsusage(char *name);

/* check what we received and call the appropriate function */
int deal(char caddr_new[MAXADDR], int newsockfd, time_t ntime, 
	char buf[MAXLINE], FILE *logPtr); 

/* dump and exit on a signal */
int myexit();
\end{verbatim}

\section{Future Improvements}

Currently, this code searches through the list of hosts with a linear
search.  Changing this to a binary search would be faster, particularly
when a large number of hosts are in the list. 

Another improvement for the future would be to send the host's current
position in the tree along with the request to the parent.  This would 

pass path, perhaps in a MIME header
IP address vs hostname
data structures
add edge info, particularly what HTTP port
add dh variables to squid.conf



\section{Outcome}

code builds.  code runs.  need more testing to determine whether works
or not.
Due to time constraints, 
The evaluation of the performance of this system is beyond the
 scope of this paper.

\begin{appendix}

\section{New code}

\subsection{chash.h}
\tgrindfile{chash.h.tex}
\subsection{chash.c}
\tgrindfile{chash.c.tex}
\subsection{common.h}
\tgrindfile{common.h.tex}
\subsection{crc.h}
\tgrindfile{crc.h.tex}
\subsection{crc.c}
\tgrindfile{crc.c.tex}
\subsection{deal.h}
\tgrindfile{deal.h.tex}
\subsection{deal.c}
\tgrindfile{deal.c.tex}
\subsection{dhrand.h}
\tgrindfile{dhrand.h.tex}
\subsection{dhrand.c}
\tgrindfile{dhrand.c.tex}
\subsection{getnet.h}
\tgrindfile{getnet.h.tex}
\subsection{getnet.c}
\tgrindfile{getnet.c.tex}
\subsection{netserv.c}
\tgrindfile{netserv.c.tex}

\section{Modified Squid Code}
\subsection{squid.h}
\tgrindfile{squid.h.tex}
\subsection{main.c}
\tgrindfile{main.c.tex}
\subsection{proto.c}
\tgrindfile{proto.c.tex}

\end{appendix}


\newpage
\begin{thebibliography}{9}


\bibitem{scale} Bowman, C., Peter B. Danzig, Udi Manber and Michael
        F. Schwartz. {\sl Scalable Internet Resource Discovery: Research
        Problems and Approaches}. Communications of the ACM, 37(8),
        pp. 98-107, August 1994.


\bibitem{hier}Chankhunthod, Anawat, Peter B. Danzig, Chuck Neerdaels,
        Michael F. Schwartz and Kurt J. Worrell. {\sl A Hierarchical
        Internet Object Cache}. Technical Report 95-611, Computer
        Science Department, University of Southern California, Los
        Angeles, California, March 1995.

\bibitem{harvest}
	Hardy, Darren R., Michael F. Schwartz, Duane Wessels.  {\sl Harvest
	User's Manual}.
	Available at \\
	\verb+http://harvest.transarc.com/afs/transarc.com/public/trg/Harvest/user-manual/+


\bibitem{karger}
	Karger, David R., et al, {\sl Relieving Hot Spots on the
	World Wide Web}. Available at \\
	\verb+http://theory.lcs.mit.edu/~karger/Papers/web.ps.gz+


\bibitem{ncache}Wessels, Duane. {\sl A Distributed Testbed for
	National Information Provisioning}.  Available at \\
	\verb+http://www.nlanr.net/Cache/+

\bibitem{duane1}Wessels, Duane. {\sl  Intelligent Caching for
        World-Wide Web Objects}. Interdisciplinary Telecommunications
        Program, University of Colorado - Boulder, 1995. M.S. Thesis.


\bibitem{icp}Wessels, Duane. {\sl Internet Cache Protocol (ICP)
                     version 2}. Available at \\
                     \verb+http://www.nlanr.net/Cache/ICP/ICP-id.txt+


\bibitem{squid}Wessels, Duane. {\sl Squid Internet Object Cache}.
	Available at \\
	\verb+http://www.nlanr.net/Squid/+



\end{thebibliography}

\end{raggedright}
\end{document}


