Web Caching and Zipf-like Distributions: Evidence and Implications

Web Caching and Zipf-like Distributions: Evidence and Implications,10.1109/INFCOM.1999.749260,Lee Breslau,Pei Cao,Li Fan,Graham Phillips,Scott Shenker

Web Caching and Zipf-like Distributions: Evidence and Implications   (Citations: 1134)
BibTex | RIS | RefWorks Download
design. We show that the answers to the two questions are re- lated,. We first investigate the page request distribution seen by web proxy caches using traces from a variety of sources. We find that the distribution does not follow Zipf's law pre- cisely, but instead follows a Zipf-like distribution with the exponent varying from trace to trace. Furthermore, we find that there is only (i) a weak correlation between the access frequency of a web page and its size and (ii) a weak cor- relation between access frequency and its rate of change. We then consider a simple model where the web accesses are independent and the reference probability of the doc- uments follows a Zipf-like distribution. We find that the model yields asymptotic behaviors that are consistent with the experimental observations, suggesting that the various observed properties of hit-ratios and temporal locality are indeed inherent to web accesses observed by proxies. Finally, we revisit web cache replacement algorithms and show that the algorithm that is suggested by this simple model performs best on real trace data. The results indicate that while page requests do indeed reveal short-term corre- lations and other structures, a simple model for an inde- pendent request stream following a Zipf-like distribution is sufflciient to capture certain asymptotic properties observed at web proxies.
Conference: IEEE INFOCOM - INFOCOM , vol. 1, pp. 126-134, 1999
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: