Jia Wang
Skip Abstract Section
Abstract
The World Wide Web can be considered as a large distributed information system that provides access to shared data objects. As one of the most popular applications currently running on the Internet, the World Wide Web is of an exponential growth in size, which results in network congestion and server overloading. Web caching has been recognized as one of the effective schemes to alleviate the service bottleneck and reduce the network traffic, thereby minimize the user access latency. In this paper, we first describe the elements of a Web caching system and its desirable properties. Then, we survey the state-of-art techniques which have been used in Web caching systems. Finally, we discuss the research frontier in Web caching.
- G. Abdulla, E. A. Fox, M. Abrams, and S. Williams, WWW proxy traffic characterization with application to caching (http://csgrad.cs.vt.edu/abdulla/proxy/proxy-char.ps).]]Google Scholar
- M. Abrams, C. R. Standridge, G. Abdulla, S. Williams, and E. A. Fox, Caching proxies: limitations and potentials, Proceedings of the 4th International WWW Conference, Boston, MA, Dec. 1995.]]Google Scholar
- C. Aggarwal, J. L. Wolf, and P. S. Yu, Caching on the World Wide Web, IEEE Transactions on Knowledge and data Engineering, Vol. 11, No. 1, January/February 1999.]] Google ScholarDigital Library
- B. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of ACM, 13(7), pp. 422-426, July 1970.]] Google ScholarDigital Library
- K. Bharat and A. Broder, Measuring the Web (http//www.research.digital.com/SRC/whatsnew/sem.html).]]Google Scholar
- P. Barford, A. Bestavros, A. Bradley, and M. E. Crovella, Changes in Web client access patterns: characteristics and caching implications, World Wide Web (special issue on Characterization and Performance Evaluation), 1999.]] Google ScholarDigital Library
- A. Bestavros and C. Cunha, Server-initiated document dissemination for the WWW, IEEE Data Engineering Bulletin, Sept. 1996.]]Google Scholar
- L. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenker, Web caching and Zipf-like distributions: evidence and implications, Proceedings of Infocom'99.]]Google Scholar
- S. Bhattacharjee, K. Calvert, and E. W. Zegura, Self-organizing wide-area network caches, IEEE Infocom'98, April 1998.]]Google ScholarCross Ref
- J. C. Bolot and P. Hoschka, Performance engineering of the World-Wide Web: Application to dimensioning and cache design, Proceedings of the 5th International WWW Conference, Paris, France, May 1996.]] Google ScholarDigital Library
- V. Cate, Alex - a global file system, Proceedings of the 1992 USENIX File System Workshop, pp. 1-12, May 1992.]]Google Scholar
- M. Crovella and P. Batford, The network effects of prefetching, Proceedings of Infocom'98.]]Google Scholar
- R. Caceres, F. Douglis, A. Feldmann, G. Glass, and M. Rabinovich, Web proxy caching: the devil is in the details, ACM Performance Evaluation Review, 26(3): pp. 11-15, December 1998.]] Google ScholarDigital Library
- A. Chankhunthod, P. B. Danzig, C. Neerdaels, M. F. Schwartz, and K. J. Worrel, A hierarchical Internet object cache, Usenix'96, January 1996.]] Google ScholarDigital Library
- P. Cao and S. Irani, Cost-aware WWW proxy caching algorithms, Proceedings of the 1997 Usenix Symposium on Internet Technologies and Systems (USITS-97), Monterey, CA, Dec. 1997.]] Google ScholarDigital Library
- J. Challenger, A. Iyengar, and P. Dantzig, A scalable system for consistently caching dynamic Web data, Proceedings of Infocom'99.]]Google Scholar
- C. R. Cunha, and C. F. B. Jaccoud, Determining WWW user's next access and its application to pre-fetching, Proceedings of ISCC'97: The second IEEE Symposium on Computers and Communications, July 1997.]] Google ScholarDigital Library
- E. Cohen, B. Krishnamurthy, and J. Rexford, Improving end-to-end performance of the Web using server volumes and proxy filters, Proceedings of Sigcomm'98.]] Google ScholarDigital Library
- E. Cohen, B. Krishnamurthy, and J. Rexford, Evaluating server-assisted cache replacement in the Web, Proceedings of the European Symposium on Algorithms-98, 1998.]] Google ScholarDigital Library
- E. Cohen, B. Krishnamurthy, and J. Rexford, Efficient algorithms for predicting requests to Web servers, Proceedings of Infocom'99.]]Google Scholar
- P. Cao and C. Liu, Maintaining strong cache consistency in the World Wide Web, Proceedings of the 17th IEEE International Conference on Distributed Computing Systems, May 1997.]] Google ScholarDigital Library
- K. Chinen and S. Yamaguchi, An interactive prefetching proxy server for improvement of WWW latency, Proceedings of INET'97, June 1997.]]Google Scholar
- P. Cao, J. Zhang, and K. Beach, Active cache: caching dynamic contents on the Web, Proceedings of IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing (Middleware'98), pp. 373-388.]]Google Scholar
- G. V. Dias, G. Cope, and R. Wijayaratne, A smart Internet caching system (http://www.isoc.org.ar/inet96/proc/a4/a4_3.htm).]]Google Scholar
- F. Douglis, A. Feldmann, B. Krishnamurthy, and J. Mogul, Rate of change and other metrics: a live study of the World-Wide Web, Proceedings of the 1997 Usenix Symposium on Internet Technologies and Systems (USITS-97), Dec. 1997.]] Google ScholarDigital Library
- B. M. Duska, D. Marwood, and M. J. Feelay, The measured access characteristics of World Wide Web client proxy caches, Proceedings of USENIX Symposium on Internet Technologies and Systems (http://cs.ubc.ca/spider/feeley/wwwap/wwwap.html).]] Google ScholarDigital Library
- A. Dingle and T. Partl, Web cache coherence, Fifth International World Wide Web Conference, Paris, France, 1996.]] Google ScholarDigital Library
- D. Ewing, R. Hall, and M. Schwartx, A measurement study of Internet file transfer traffic, Technical Report CU-CS-571-92, University of Colorado, Dept. of Computer Science, Boulder, Colorado, January 1992.]]Google Scholar
- L. Fan, P. Cao, J. Almeida, and A. Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, Proceedings of Sigcomm'98.]] Google ScholarDigital Library
- A. Feldmann, R. Caceres, F. Douglis, G. Glass, and M. Rabinovich, Performance of Web proxy caching in heterogeneous bandwidth environments, Proceedings of Infocom'99.]]Google Scholar
- L. Fan, P. Cao, W. Lin, and Q. Jacobson, Web prefetching between low-bandwidth clients and proxies: potential and performance, Proceedings of the Sigmetrics'99.]] Google ScholarDigital Library
- S. Galssman, A cache relay for the WWW, Proceedings of the 1st International WWW Conference, Geneva, Switzerland, May 1994 (http://www.research.digital.com/SRC/personal/Steve_Glassman/CachingTheWeb.ps).]]Google Scholar
- S. Gadde, M. Rabinovich, and J. Chase, Reduce, reuse, recycle: an approach to building large Internet caches, Proceedings of the HotOS'97 Workshop, May 1997 (http://www.cs.duke.edu/ari/cisi/crisp-recycle/crisp-recycle.htm).]] Google ScholarDigital Library
- J. Gwetzman and M. Seltzer, The case for geographical pushing-caching, HotOS Conference, 1994 (ftp://dasftp.harvadr.edn/techreports/tr-34-94.ps.gz).]] Google ScholarDigital Library
- J. Gwetzman and M. Seltzer, World Wide Web cache consistency, Proceedings of the USENIX Technical Conference, pp. 141-152, January 1996.]] Google ScholarDigital Library
- A. Heddaya, S. Mirdrad, and D. Yates, Diffusion based caching along routing paths (http://cswww.bu.edu/faculty/heddaya/Pepers-NonTR/webcachewkp.ps.Z).]]Google Scholar
- Hypertext Transfer Protocol --- HTTP/1.0, RFC 1945.]]Google Scholar
- Hypertext Transfer Protocol --- HTTP/1.1, RFC 2068.]]Google Scholar
- J. Jung and K. Chon, Nation-wide caching project in Korea - design and experimentation, Proceedings of the 2nd Web Cache Workshop (http://ircache.nlanr.net/Cache/Workshop97/Papers/Jaeyeon/jaeyeon.html).]]Google Scholar
- M. R. Korupolu and M. Dahlin, Coordinated placement and replacement for large-scale distributed caches, Proceedings of the IEEE Workshop on Internet Applications, July 1999 (Technical Report TR-98-30, Department of Computer Science, University of Texas at Austin, December 1998).]] Google ScholarDigital Library
- D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, STOC 1997.]] Google ScholarDigital Library
- T. M. Kroeger, D. D. E. Long, and J. C. Mogul, Exploring the bounds of Web latency reduction from caching and prefetching, Proceedings of the 1997 Usenix Symposium on Internet Technologies and Systems, Monterey, CA, Dec. 1997.]] Google ScholarDigital Library
- M. R. Korupolu, C. G. Plaxton and R. Rajaraman, Placement algorithms for hierarchical cooperative caching, Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1999.]] Google ScholarDigital Library
- P. Krishnan and B. Sugla, Utility of cooperating Web proxy caches, Computer Networks and ISDN Systems, pp. 195-203, April 1998.]] Google ScholarDigital Library
- B. Krishnamurthy and C. E. Wills, Study of piggyback cache validation for proxy caches in the World Wide Web, Proceedings of the 1997 USENIX Symposium on Internet Technology and Systems, pp. 1-12, December 1997.]] Google ScholarDigital Library
- B. Krishnamurthy and C. E. Wills, Piggyback server invalidation for proxy cache coherency, Proceedings of the WWW-7 Conference, pp. 185-194, 1998.]] Google ScholarDigital Library
- B. Krishnamurthy and C. E. Wills, Proxy cache coherency and replacement - towards a more complete picture, ICDC99, June 1999.]]Google ScholarCross Ref
- I. Lovric, Internet cache protocol extension, Internet Draft <draft-lovric-icp-ext-01.txt>.]]Google Scholar
- A. Luotonen and K. Altis, World Wide Web proxies, Computer Networks and ISDN Systems, First International Conference on WWW, April 1994.]] Google ScholarDigital Library
- T. S. Loon and V. Bharghavan, Alleviating the latency and bandwidth problems in WWW browsing, Proceedings of the 1997 Usenix Symposium on Internet Technologies and Systems (USITS-97), Dec. 1997.]] Google ScholarDigital Library
- U. Legedza and J. Guttag, Using network-level support to improve cache routing, Computer Networks and ISDN Systems 30, 22-23, pp. 2193-2201, Nov. 1998.]] Google ScholarDigital Library
- B. Li, M. J. Golin, G. F. Italiano, X. Deng, and K. Sohraby, On the optimal placement of Web proxies in the Internet, Proceedings of Infocom'99.]]Google Scholar
- E. Levy-Abegnoli, A. Iyengar, J. Song, and D. Dias, Design and performance of Web server accelerator, Proceedings of Infocom'99.]]Google Scholar
- P. Lorenzetti, L. Rizzo, and L. Vicisano, Replacement policies for a proxy cache (http://www.iet.unipi.it/luigi/research.html).]]Google Scholar
- I. Melve, Client-cache communication, Internet Draft <draft-melve-clientcache-com-00.txt>.]]Google Scholar
- E. P. Markatos and C. E. Chronaki, A TOP-10 approach to prefetching on Web, Proceedings of INET'98.]]Google Scholar
- R. Malpani, J. Lorch, and D. Berger, Making World Wide Web caching servers cooperate, Proceedings of the 4th International WWW Conference, Boston, MA, Dec. 1995 (http://www.w3j.com/1/lorch.059/paper/059.html).]]Google Scholar
- S. Michel, K. Nguyen, A. Rosenstein, L. Zhang, S. Floyd and V. Jacobson, Adaptive Web caching: towards a new caching architecture, Computer Network and ISDN Systems, November 1998.]] Google ScholarDigital Library
- I. Melve, L. Slettjord, T. Verschuren, and H. Bekker, Building a Web caching system - architectural considerations, Proceedings of the 8th Joint European Networking Conference, Edinburgh, Scotland, May 1997.]]Google Scholar
- M. Nabeshima, The Japan cache project: an experiment on domain cache, Computer Networks and ISDN System, September 1997.]] Google ScholarDigital Library
- D. Povey and J. Harrison, A distributed Internet cache, Proceedings of the 20th Australian Computer Science Conference, Sydney, Australia, Feb. 1997.]]Google Scholar
- T. Palpanas and A. Mendelzon, Web prefetching using partial match prediction, Proceedings of WCW'99.]]Google Scholar
- V. N. Padmanabhan and J. C. Mogul, Using predictive prefetching to improve World Wide Web latency, proceedings of Sigcomm'96.]]Google Scholar
- M. Rabinovich, Issues in Web content replication.]]Google Scholar
- M. Rabinovich, J. Chase, and S. Gadde, Not all hits are created equal: cooperative proxy caching over a wide-area network, Computer Networks And ISDN Systems 30, 22-23, pp. 2253-2259, Nov. 1998.]] Google ScholarDigital Library
- Relais: cooperative caches for the World Wide Web, 1998 (http://www-sor.inria.fr/projects/relais/).]]Google Scholar
- C. Roadknight and I. Marshall, Variations in cache behavior, Computer Networks and ISDN Systems, pp. 733-735, April 1998.]] Google ScholarDigital Library
- A. Rousskov and D. Wessels, Cache Digest, Proceedings of 3rd International WWW Caching Workshop, June 1998.]]Google ScholarDigital Library
- P. Rodriguez, C. Spanner, and E. W. Biersack, Web caching architectures: hierarchical and distributed caching, Proceedings of WCW'99.]]Google Scholar
- P. Scheuermann, J. Shim, and R. Vingralek, A case for delay-conscious caching of Web documents, Proceedings of the 6th International WWW Conference, Santa Clara, Apr. 1997.]] Google ScholarDigital Library
- R. Tewari, M. Dahlin, H. Vin, and J. Kay, Beyond hierarchies: design considerations for distributed caching on the Internet, Technical Report TR98-04, Department of Computer Science, University of Texas at Austin, February 1998.]] Google ScholarDigital Library
- R. Tewari, H. Vin, A. Dan, and D. Sitaram, Resource based caching for Web servers, Proceedings of SPIE/ACM Conference on Multimedia Computing and Networking (MMCN), January 1998.]]Google Scholar
- V. Valloppillil and K. W. Ross, Cache array routing protocol v1.0, Internet Draft <draft-vinod-carp-v1-03.txt>.]]Google Scholar
- Z. Wang, Cachemesh: a distributed cache system for World Wide Web, Web Cache Workshop, 1997.]]Google Scholar
- D. Wessels, Intelligent caching for World-Wide Web objects, Proceedings of INET'95, Honolulu, Hawaii, June 1995 (http://info.isoc.org/HMP/PAPER/139/archive/papers.ps.9505216).]]Google Scholar
- K. J. Worrell, Invalidation in large scale network object caches, M.S. Thesis, Department of Computer Science, University of Colorado, Boulder, Colorado, December 1994 (ftp://ftp.cs.colorado.edu/pub/cs/techreports/schwartz/WorrellThesis.ps.Z).]]Google Scholar
- R. P. Wooster and M. Abrams, Proxy caching that estimates page load delays, Proceedings of the 6th International WWW Conference, April 1997 (http://www.cs.vt.edu/chitra/docs/www6r/).]] Google ScholarDigital Library
- S. Williams, M. Abrams, C. R. Standridge, G. Abdulla, and E. A. Fox, Removal policies in network caches for World-Wide Web documents, Proceedings of Sigcomm'96.]] Google ScholarDigital Library
- D. Wessels and K. Claffy, Internet cache protocol (IPC), version 2, RFC 2186.]] Google ScholarDigital Library
- D. Wessels and K. Claffy, Application of Internet cache protocol (IPC), version 2, RFC 2187.]] Google ScholarDigital Library
- J. Yin, L. Alvisi, M. Dahlin, and C. Lin, Using leases to support server-driven consistency in large-scale systems, Proceedings of the 18th International Conference on Distributed Computing System (ICDCS'98), May 1998.]] Google ScholarDigital Library
- P. S. Yu and E. A. MacNair, Performance study of a collaborative method for hierarchical caching in proxy servers, Computer Networks and ISDN Systems, pp. 215-224, April 1998.]] Google ScholarDigital Library
- J. Yang, W. Wang, R. Muntz, and J. Wang, Access driven Web caching, UCLA Technical Report #990007.]]Google Scholar
Index Terms
- A survey of web caching schemes for the Internet
Index terms have been assigned to the content through auto-classification.
Recommendations
Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches
Although direct-mapped caches suffer from higher miss ratios as compared to set-associative caches, they are attractive for today's high-speed pipelined processors that require very low access times. Victim caching was proposed by Jouppi [1] as an ...
Comments