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

This is joint work with Abdelsalam Heddaya. There is a technical report on this work at http://www.cs.bu.edu/techreports/96-024-webwave-theory.ps.Z.

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 have three properties: (1) maximize the global throughput of the system, (2) be completely distributed in the sense of operating only on the basis of local information, and (3) 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.