Exploiting Regularities in Web Traffic Patterns for Cache Replacement |
| |
Authors: | Cohen Kaplan |
| |
Affiliation: | (1) AT&T Labs — Research, 180 Park Avenue, Florham Park, NJ 07932, USA. edith@research.att.com., US;(2) Tel Aviv University, Tel Aviv 69978, Israel. haimk@math.tau.ac.il., IL |
| |
Abstract: | Abstract. Caching web pages at proxies and in web servers' memories can greatly enhance performance. Proxy caching is known to reduce
network load and both proxy and server caching can significantly decrease latency. Web caching problems have different properties
than traditional operating systems caching, and cache replacement can benefit by recognizing and exploiting these differences.
We address two aspects of the predictability of traffic patterns: the overall load experienced by large proxy and web servers,
and the distinct access patterns of individual pages.
We formalize the notion of ``cache load' under various replacement policies, including LRU and LFU, and demonstrate that
the trace of a large proxy server exhibits regular load. Predictable load allows for improved design, analysis, and experimental
evaluation of replacement policies. We provide a simple and (near) optimal replacement policy when each page request has an
associated distribution function on the next request time of the page. Without the predictable load assumption, no such online
policy is possible and it is known that even obtaining an offline optimum is hard. For experiments, predictable load enables
comparing and evaluating cache replacement policies using partial traces , containing requests made to only a subset of the pages.
Our results are based on considering a simpler caching model which we call the interval caching model . We relate traditional and interval caching policies under predictable load, and derive (near)-optimal replacement policies
from their optimal interval caching counterparts. |
| |
Keywords: | , Caching, Interval caching, Varying page sizes and fetching costs, Predictable load, Inter-request time distribution, |
本文献已被 SpringerLink 等数据库收录! |
|