Measuring the Performance of Prefetching Proxy Caches

Poster Abstract

Problem and Motivation

The growth of the WWW and difficulties associated with heterogeneous network connectivity have motivated the use of web caches. By storing objects closer to the clients, web caches offer the benefits of reduced bandwidth usage, reduced server load, and lower retrieval latencies.

While the client may appreciate the indirect benefits of reduced bandwidth and server loads, reduced latencies are the most visible advantage. To further improve client latencies, prefetching is often proposed in an attempt to retrieve objects in advance of a client request. This idea has been implemented in a number of browser add-ons and at least one commercial proxy cache.

While anecdotal evidence may be available to point to the efficacy of such methods, it is difficult to measure precisely the improvement in latency. This work describes the Simultaneous Proxy Evaluation (SPE) architecture, which enables the simultaneous evaluation of multiple proxies on a live request stream and network connection.

Background and Related Work

It is useful to be able to assess the performance of proxy caches, both for consumers selecting the appropriate system for a particular situation and also for developers working on alternative proxy implementations. Traditionally, proxy cache algorithms are simulated on a benchmark log of object requests (e.g., [3]). Implemented systems are usually tested by processing artificial datasets with representative characteristics of real logs such as object size distributions and repetition rates (e.g. [1]). In either case the primary metrics (page hit rate, byte hit rate) can be calculated and latency improvements can be estimated.

Simulating a caching algorithm, however, requires detailed knowledge of the algorithms (not always possible for some systems such as most commercial implementations). Comparing implemented systems as black-boxes overcomes this drawback, but often entails applying artificially generated request loads on an isolated network.

Using captured trace logs eliminates uncertainties associated with artificial logs, but since the average lifetime of a web page is short (less than two months [5]), any captured log loses value quickly as more objects referenced in it change or become inaccessible. Additionally, unless logs are recorded carefully, it is possible for proxy cache logs to reflect an inaccurate request ordering (perhaps recording the order of satisfied requests). Finally, since cache performance may depend partly on the client population, commonly available trace logs may not generate performance measurements relevant to a particular situation.

Caches that prefetch on the basis of the contents of the pages being served, such as CacheFlow and Wcol [2,4] need at least to have access to the links within web pages -- something that is not available from logs. Even if page contents were logged, caches that perform prefetching may prefetch objects that are not on the user request logs and thus have unknown characteristics of size and retrieval costs.

Approach and Uniqueness

Our approach extends both aspects of evaluation methodologies. Instead of simulating systems, or evaluating systems on an isolated network, we suggest evaluating implemented systems with a live network connection. This provides the data needed for content-based prefetching methods and allows for performance measurement based on actual network conditions. Additionally, our method uses a live request stream, again allowing for measurement under real network conditions, and eliminating problems of inaccurate or out-of-date trace logs.

The use of live data, however, precludes the possibility of reproducing experiments, as both request loads and network characteristics change over time. The primary need for reproducibility, though, is to allow comparisons between systems. The SPE architecture addresses this issue by allowing for the evaluation of multiple proxies simultaneously.

In the SPE architecture, all client requests are sent to a single proxy, called the multiplier, which sends a copy of the request to each proxy under evaluation. Each proxy cache attempts to fill the request, either from cache, or by fetching it by way of a common parent cache, called the collector. By using the collector, only one copy of the request is issued to the origin server. Since the multiplier returns the response of just one of the proxies, the whole architecture appears to actual clients as a single proxy cache. By forming a wrapper around each proxy, the evaluation architecture can produce logs to measure network usage and response times as seen by a client. In order to accurately measure response times, though, the collector must be able to return cached objects with the same overall speed as a cache miss. Additionally, to prevent multiple copies of otherwise uncachable requests, either the collector must be able to cache what are normally considered uncachable requests (e.g. those with cgi or ? in the URL or those requests using the POST method) or the multiplier must pull those requests from the stream and fetch them directly instead of sending them on to the tested proxies.

Results and Contributions

A subset of the SPE architecture (the multiplier) has been implemented and tested on two representative problems: measuring the bandwidth savings of three competing proxy caches (some utilizing prefetching), and measuring the changes in latency when connecting to a remote second-level proxy cache. These experiments illustrate the use of the architecture to answer typical proxy evaluation questions.

The SPE architecture is not intended to replace existing evaluation mechanisms. Instead, it complements other approaches as while it provides objective measurements on live data, experiments built on it generally cannot be replicated and so must be repeated when one needs to compare the performance of existing proxies to that of a new proxy. Additionally, the use of artificial request loads is often desirable in order to measure performance under alternate loads (e.g. loads higher than currently available).

In this work we characterize evaluation methodologies in terms of the workloads used and algorithm implementation. By extending these dimensions to include live workload and real systems and network, and by comparing multiple proxies simultaneously, the SPE architecture provides a new approach to proxy cache evaluation that is complementary to existing methods and allows for the evaluation of content-based prefetching proxy caches.

References

[1] J. Almeida and P. Cao. Measuring Proxy Performance with the Wisconsin Proxy Benchmark. In the Third Int'l Web Cache Workshop, 1998.

[2] CacheFlow Inc. http://www.cacheflow.com. 1998.

[3] J. Shim, P. Scheuermann, and R. Vingralek. A case for delay-conscious caching of web documents. In Proc. of Sixth Int'l WWW Conference, 1997.

[4] K. Chinen and S. Yamaguchi. An interactive prefetching proxy server for improvement of WWW latency. In Proc. 7th Annual Conf. of the Internet Society, 1997.

[5] F. Douglis, A. Feldmann, B. Krishnamurthy, and J. Mogul. Rate of change and other metrics: a live study of the World Wide Web. In Proc. of USENIX Symp. on Internet Tech. and Systems, 1997.

Presented at the AT&T Student Research Symposium (a regional ACM Student Research Competition), November 13, 1998. Awarded First Place, PhD Division.

Poster presented at the ACM International Student Research Competition, March 24-28, 1999. Awarded Third Place, Graduate Category.

[That's me in the suit at the AT&T competition.]

Back to Brian Davison's publications