The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Web caching and Zipf-like distributions: evidence and implications
Abstract
This paper addresses two unresolved issues about Web caching. The first issue is whether Web requests from a fixed user community are distributed according to Zipf's (1929) law. The second issue relates to a number of studies on the characteristics of Web proxy traces, which have shown that the hit-ratios and temporal locality of the traces exhibit certain asymptotic properties that are uniform across the different sets of the traces. In particular, the question is whether these properties are inherent to Web accesses or whether they are simply an artifact of the traces. An answer to these unresolved issues will facilitate both Web cache resource planning and cache hierarchy design. We show that the answers to the two questions are related. 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 precisely, 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 correlation 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 documents follows a Zipf-like distribution. We find that the model yields asymptotic behaviour 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 correlations and other structures, a simple model for an independent request stream following a Zipf-like distribution is sufficient to capture certain asymptotic properties observed at Web proxies.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Cost-aware WWW proxy caching algorithms
Cao, P., & Irani, S. (1997) · Cited by 925
Self-citationCoffman, E. G., & Denning, P. J. (1973) · Medical Entomology and Zoology · Cited by 694
Characteristics of WWW Client-based Traces
Cunha, C. R., Azer Bestavros, C., & Crovella, M. E. (1995) · OpenBU (Boston University) · Cited by 587
Characterizing reference locality in the WWW
Almeida, V., Bestavros, A., Crovella, M., & de Oliveira, A. (2002) · Fourth International Conference on Parallel and Distributed Information Systems · doi:10.1109/pdis.1996.568672 · Cited by 464
Denning, P. J. (1980) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1980.230464 · Cited by 396
Replacement policies for a proxy cache
Rizzo, L., & Vicisano, L. (2000) · IEEE/ACM Transactions on Networking · doi:10.1109/90.842139 · Cited by 302
A caching relay for the World Wide Web
Glassman, S. (1994) · Computer Networks and ISDN Systems · doi:10.1016/0169-7552(94)90130-9 · Cited by 292
World Wide Web Cache Consistency
Gwertzman, J. S., & Seltzer, M. (1996) · Cited by 263
The Measured Access Characteristics of World-Wide-Web Client Proxy Caches
Duska, B. M., Marwood, D., & Feeley, M. J. (1997) · Cited by 193
Cited by
A survey on security issues in service delivery models of cloud computing
Subashini, S., & Kavitha, V. (2011) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2010.07.006 · Cited by 2,625
Summary cache: a scalable wide-area Web cache sharing protocol
Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (2000) · IEEE/ACM Transactions on Networking · doi:10.1109/90.851975 · Cited by 1,811
Self-citationA survey and comparison of peer-to-peer overlay network schemes
Lua, E. K., Crowcroft, J., Pias, M., Sharma, R., & Lim, S. (2005) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2005.1610546 · Cited by 1,496
FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers
Shanmugam, K., Golrezaei, N., Dimakis, A. G., Molisch, A. F., & Caire, G. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2281606 · Cited by 1,246
Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility
Rowstron, A., & Druschel, P. (2001) · Proceedings of the eighteenth ACM symposium on Operating systems principles · doi:10.1145/502034.502053 · Cited by 1,218
Living on the edge: The role of proactive caching in 5G wireless networks
Bastug, E., Bennis, M., & Debbah, M. (2014) · IEEE Communications Magazine · doi:10.1109/mcom.2014.6871674 · Cited by 1,146
A Survey on Mobile Edge Networks: Convergence of Computing, Caching and Communications
Wang, S., Zhang, X., Zhang, Y., Wang, L., YANG, J., & Wang, W. (2017) · IEEE Access · doi:10.1109/access.2017.2685434 · Cited by 952
PNUTS: Yahoo!'s hosted data serving platform
Cooper, B. F., Ramakrishnan, R., Srivastava, U., Silberstein, A., Bohannon, P., Jacobsen, H.-A., Puz, N., Weaver, D., & Yerneni, R. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454167 · Cited by 958
Workload analysis of a large-scale key-value store
Atikoglu, B., Xu, Y., Frachtenberg, E., Jiang, S., & Paleczny, M. (2012) · Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems · doi:10.1145/2254756.2254766 · Cited by 901
Restful web services vs. "big"' web services: making the right architectural decision
Pautasso, C., Zimmermann, O., & Leymann, F. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367606 · Cited by 879
Youtube traffic characterization: a view from the edge
Gill, P., Arlitt, M., Li, Z., & Mahanti, A. (2007) · Proceedings of the 7th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1298306.1298310 · Cited by 852
Measurement, modeling, and analysis of a peer-to-peer file-sharing workload
Gummadi, K. P., Dunn, R. J., Saroiu, S., Gribble, S. D., Levy, H. M., & Zahorjan, J. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945475 · Cited by 818
On the placement of Web server replicas
Qiu, L., Padmanabhan, V. N., & Voelker, G. M. (2002) · Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) · doi:10.1109/infcom.2001.916655 · Cited by 798
A workload characterization study of the 1998 World Cup Web site
Arlitt, M., & Jin, T. (2000) · IEEE Network · doi:10.1109/65.844498 · Cited by 766
A survey of Web cache replacement strategies
Podlipnig, S., & Böszörmenyi, L. (2003) · ACM Computing Surveys · doi:10.1145/954339.954341 · Cited by 760
Statistics and Social Network of YouTube Videos
Cheng, X., Dale, C., & Liu, J. (2008) · 2008 16th Interntional Workshop on Quality of Service · doi:10.1109/iwqos.2008.32 · Cited by 720
FemtoCaching: Wireless video content delivery through distributed caching helpers
Golrezaei, N., Shanmugam, K., Dimakis, A. G., Molisch, A. F., & Caire, G. (2012) · 2012 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2012.6195469 · Cited by 711
Survey of Fog Computing: Fundamental, Network Applications, and Research Challenges
Mukherjee, M., Shu, L., & Wang, D. (2018) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2814571 · Cited by 684
A survey of web caching schemes for the Internet
Wang, J. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/505696.505701 · Cited by 682
Toward Secure and Dependable Storage Services in Cloud Computing
Wang, C., Wang, Q., Ren, K., Cao, N., & Lou, W. (2012) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2011.24 · Cited by 643
He, Y., Zhao, N., & Yin, H. (2018) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2017.2760281 · Cited by 569
Analyzing Peer-To-Peer Traffic Across Large Networks
Sen, S., & Wang, J. (2004) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2004.826277 · Cited by 586
An analysis of Internet content delivery systems
Saroiu, S., Gummadi, K. P., Dunn, R. J., Gribble, S. D., & Levy, H. M. (2002) · ACM SIGOPS Operating Systems Review · doi:10.1145/844128.844158 · Cited by 546
On the scale and performance of cooperative Web proxy caching
Wolman, A., Voelker, M., Sharma, N., Cardwell, N., Karlin, A., & Levy, H. M. (1999) · Proceedings of the seventeenth ACM symposium on Operating systems principles · doi:10.1145/319151.319153 · Cited by 496
Hierarchical Web caching systems: modeling, design and experimental results
Che, H., Tung, Y., & Wang, Z. (2002) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2002.801752 · Cited by 491
Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs
Bolosky, W. J., Douceur, J. R., Ely, D., & Theimer, M. (2000) · Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems · doi:10.1145/339331.339345 · Cited by 484
Interactive analytical processing in big data systems: a cross-industry study of MapReduce workloads
Chen, Y., Alspaugh, S., & Katz, R. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2367502.2367519 · Cited by 469
Power and energy management for server systems
Bianchini, R., & Rajamony, R. (2004) · Computer · doi:10.1109/mc.2004.217 · Cited by 453
Wireless Device-to-Device Caching Networks: Basic Principles and System Performance
Ji, M., Caire, G., & Molisch, A. F. (2016) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2015.2452672 · Cited by 444
Deriving traffic demands for operational IP networks: methodology and experience
Feldmann, A., Greenberg, A., Lund, C., Reingold, N., Rexford, J., & True, F. (2001) · IEEE/ACM Transactions on Networking · doi:10.1109/90.929850 · Cited by 430
Network-Aware Operator Placement for Stream-Processing Systems
Pietzuch, P., Ledlie, J., Shneidman, J., Roussopoulos, M., Welsh, M., & Seltzer, M. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.105 · Cited by 428
Content-Centric Sparse Multicast Beamforming for Cache-Enabled Cloud RAN
Tao, M., Chen, E., Zhou, H., & Yu, W. (2016) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2578922 · Cited by 423
Summary cache: a scalable wide-area Web cache sharing protocol
Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (1998) · Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/285237.285287 · Cited by 422
Self-citationCoded caching with nonuniform demands
Niesen, U., & Maddah-Ali, M. A. (2014) · 2014 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) · doi:10.1109/infcomw.2014.6849235 · Cited by 415
The LCD interconnection of LRU caches and its analysis
Laoutaris, N., Che, H., & Stavrakakis, I. (2006) · Performance Evaluation · doi:10.1016/j.peva.2005.05.003 · Cited by 383
Scale and performance in the Denali isolation kernel
Whitaker, A., Shaw, M., & Gribble, S. D. (2002) · ACM SIGOPS Operating Systems Review · doi:10.1145/844128.844147 · Cited by 377
Caching in information centric networking: A survey
Zhang, G., Li, Y., & Lin, T. (2013) · Computer Networks · doi:10.1016/j.comnet.2013.07.007 · Cited by 358
Information-centric networking: seeing the forest for the trees
Ghodsi, A., Shenker, S., Koponen, T., Singla, A., Raghavan, B., & Wilcox, J. (2011) · Proceedings of the 10th ACM Workshop on Hot Topics in Networks · doi:10.1145/2070562.2070563 · Cited by 321
Self-citationWireless caching: technical misconceptions and business barriers
Paschos, G., Bastug, E., Land, I., Caire, G., & Debbah, M. (2016) · IEEE Communications Magazine · doi:10.1109/mcom.2016.7537172 · Cited by 321
Deep Reinforcement Learning for Cooperative Content Caching in Vehicular Edge Computing and Networks
Qiao, G., Leng, S., Maharjan, S., Zhang, Y., & Ansari, N. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2945640 · Cited by 321
An analysis of live streaming workloads on the internet
Sripanidkulchai, K., Maggs, B., & Zhang, H. (2004) · Proceedings of the 4th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1028788.1028795 · Cited by 317
Seeling, P., Reisslein, M., & Kulapala, B. (2004) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2004.5342293 · Cited by 309
Less pain, most of the gain: incrementally deployable ICN
Fayazbakhsh, S. K., Lin, Y., Tootoonchian, A., Ghodsi, A., Koponen, T., Maggs, B., Ng, K. C., Sekar, V., & Shenker, S. (2013) · Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM · doi:10.1145/2486001.2486023 · Cited by 307
Self-citationLearning-based optimization of cache content in a small cell base station
Blasco, P., & Gunduz, D. (2014) · 2014 IEEE International Conference on Communications (ICC) · doi:10.1109/icc.2014.6883600 · Cited by 298
Analyzing peer-to-peer traffic across large networks
Sen, S., & Wang, J. (2002) · Proceedings of the second ACM SIGCOMM Workshop on Internet measurment - IMW '02 · doi:10.1145/637201.637222 · Cited by 290
Li, L., Zhao, G., & Blum, R. S. (2018) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2820021 · Cited by 282
Context-Aware Proactive Content Caching With Service Differentiation in Wireless Networks
Muller, S., Atan, O., van der Schaar, M., & Klein, A. (2017) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2636139 · Cited by 281
Workload analysis of a large-scale key-value store
Atikoglu, B., Xu, Y., Frachtenberg, E., Jiang, S., & Paleczny, M. (2012) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2318857.2254766 · Cited by 268
Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-Time Popularities
Sadeghi, A., Sheikholeslami, F., & Giannakis, G. B. (2018) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2017.2787979 · Cited by 257
Understanding the Characteristics of Internet Short Video Sharing: A YouTube-Based Measurement Study
Cheng, X., Liu, J., & Dale, C. (2013) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2013.2265531 · Cited by 266
Karamchandani, N., Niesen, U., Maddah-Ali, M. A., & Diggavi, S. N. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2557804 · Cited by 265
Traffic Modeling and Proportional Partial Caching for Peer-to-Peer Systems
Hefeeda, M., & Saleh, O. (2008) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2008.918081 · Cited by 259
The Role of Caching in Future Communication Systems and Networks
Paschos, G. S., Iosifidis, G., Tao, M., Towsley, D., & Caire, G. (2018) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2018.2844939 · Cited by 259
A versatile and accurate approximation for LRU cache performance
Fricker, C., Robert, P., & Roberts, J. W. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.3974 · Cited by 257
WebInSight: making web images accessible
Bigham, J. P., Kaminsky, R. S., Ladner, R. E., Danielsson, O. M., & Hempton, G. L. (2006) · Proceedings of the 8th international ACM SIGACCESS conference on Computers and accessibility · doi:10.1145/1168987.1169018 · Cited by 161
WebinSitu: a comparative analysis of blind and sighted browsing behavior
Bigham, J. P., Cavender, A. C., Brudvik, J. T., Wobbrock, J. O., & Ladner, R. E. (2007) · Proceedings of the 9th international ACM SIGACCESS conference on Computers and accessibility · doi:10.1145/1296843.1296854 · Cited by 153
Learning Based Content Caching and Sharing for Wireless Networks
Song, J., Sheng, M., Quek, T. Q. S., Xu, C., & Wang, X. (2017) · IEEE Transactions on Communications · doi:10.1109/tcomm.2017.2713384 · Cited by 144
Cachier: Edge-Caching for Recognition Applications
Drolia, U., Guo, K., Tan, J., Gandhi, R., & Narasimhan, P. (2017) · 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2017.94 · Cited by 148
Caching in Base Station with Recommendation via Q-Learning
Guo, K., Yang, C., & Liu, T. (2017) · 2017 IEEE Wireless Communications and Networking Conference (WCNC) · doi:10.1109/wcnc.2017.7925848 · Cited by 54
Power Law Distributions in Information Retrieval
Petersen, C., Simonsen, J. G., & Lioma, C. (2016) · ACM Transactions on Information Systems · doi:10.1145/2816815 · Cited by 46
Dynamic adaptive streaming over popularity-driven caching in Information-Centric Networks
Li, W., Oteafy, S. M. A., & Hassanein, H. S. (2015) · 2015 IEEE International Conference on Communications (ICC) · doi:10.1109/icc.2015.7249238 · Cited by 18
(2002)
Metadata
- Authors
- Breslau, L., Cao, P., Fan, L., Phillips, G., & Shenker, S.
- Venue
- IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320)
- Publisher
- IEEE
- Published
- 1999
- Pages
- 126-134 vol.1
- OpenAlex
- W2112053513
- Cited by
- 3,467
- References
- 9
- FWCI
- 63.95
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.