Title:	WebWave: Globally Load Balanced Fully Distributed
	Caching of Hot Published Documents

Author: Abdelsalam Heddaya and Sulaiman Mirdad

Date: October 10, 1996

Abstract:

Document publication service over such a large network as the Internet
challenges us to harness available server and network resources to meet
fast growing demand.  In this paper, we show that large-scale dynamic
caching can be employed to globally minimize server idle time, and hence
maximize the aggregate throughput of the whole service.  Given the
distributed nature of the system, a successful caching mechanism must
satisfy three properties: (1) that it maximize the global throughput of the
system, (2) that it be completely distributed in the sense of operating
only on the basis of local information, and (3) that it require no naming
service that introduces a scalability bottleneck.

In this paper, we develop a precise definition, which we call "tree
load-balance", of what it means for a mechanism to satisfy these three
goals, and present two algorithms that achieve them.  Both algorithms
compute the request rate that should be allocated to each cache server, so
that global throughput is maximized.  The first algorithm, WebFold, is a
centralized one that is provably optimal with respect to throughput.  The
second algorithm, WebWave, whose optimality is evidenced by simulation, is
a fully distributed diffusion-based protocol.  Both algorithms assume that
cache copies are placed on the routing tree that connects the cached
document's home server with its clients.  As a consequence, document
requests can find cache copies without resorting to a cache directory of
any kind.  The results herein apply only to immutable documents; we do not
consider the cache consistency problem.