\documentclass[11pt]{article} 
 
\begin{document}
\begin{raggedright}
\setlength{\parindent}{0.5in}

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

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 won't be 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 will be 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 is
intended to determine if this algorithm will work in the current
Internet, and if it will 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 will implement this algorithm using 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 will also have to extend the currently used cache
protocol to allow the machines to communicate which machines on the
network are using this algorithm.  They will 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 will have to implement this algorithm for determining what cache to
ask for a particular document.  I will also need to integrate 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.



\begin{thebibliography}{9}


\bibitem{scale} Bowman, C., Peter B. Danzig, Udi Manber and Michael
        F. Schwartz. \textsl{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. \textsl{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.  \textsl{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, \textsl{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. \textsl{A Distributed Testbed for
	National Information Provisioning}.  Available at \\
	\verb+http://www.nlanr.net/Cache/+

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


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


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



\end{thebibliography}

\end{raggedright}
\end{document}
