Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol
Li Fan, Pei Cao and Jussara Almeida
Computer Sciences Department
University of Wisconsin-Madison
Andrei Z. Broder
Systems Research Center
Digital Equipment Corporation
cao@cs.wisc.edu
To Appear in SIGCOMM'98.
The corrected version of the 12-page paper in SIGCOMM'98 is here.
The implementation of Summary Cache in Squid 1.1.14 is here.
Here is the 20-page technical report version in HTML.
Here is technical report in compressed postscript. The technical report can be referenced as Technical Report
1361, Department of Computer Science, University of Wisconsin-Madison, Feb 1998.
List of typos in the paper in the SIGCOMM'98 Proceedings:
- Page 256, table 1, the Max. Hit Ratio for UPisa trace is 49%, not 40%;
- Page 259, the right column, (1 - e^(kn/m))^k should be (1-e^(-kn/m))^k;
- Page 262, second column, "Each proxy needs about 200MB to represent all
the summaries plus another 8MB to represent its own counters."
Thank you all for pointing out the typos.
Abstract
The sharing of caches among Web proxies is an important technique to
reduce Web traffic and alleviate network bottlenecks. Nevertheless it
is not widely deployed due to the overhead of existing protocols. In
this paper we demonstrate the benefits of cache sharing, measure the
overhead of the existing protocols, and propose a new protocol called
``Summary Cache''. In this new protocol, each proxy keeps a summary
of the cache directory of each participating proxy, and checks these
summaries for potential hits before sending any queries. Two factors
contribute to our protocol's low overhead: the summaries are updated
only periodically, and the directory representations are very
economical, as low as 8 bits per entry. Using trace-driven
simulations and a prototype implementation, we show that, compared to
existing protocols such as the Internet Cache Protocol (ICP), Summary
Cache reduces the number of inter-cache protocol messages by a
factor of 40 to 65}, reduces the bandwidth consumption by over 50%,
eliminates 75% and 95% of the protocol CPU overhead, all while maintain
ing
almost the same cache hit ratio as ICP. Hence Summary Cache scales to
a large number of proxies.