A survey of web caching schemes for the Internet

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.

REFERENCES

• 1: 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).
• 2: 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.
• 3: Charu Aggarwal , Joel L. Wolf , Philip S. Yu, Caching on the World Wide Web, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.94-107, January 1999 [doi>10.1109/69.755618]
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: K. Bharat and A. Broder, Measuring the Web (http//www.research.digital.com/SRC/whatsnew/sem.html).
• 6: Paul Barford , Azer Bestavros , Adam Bradley , Mark Crovella, Changes in Web client access patterns: Characteristics and caching implications, World Wide Web, v.2 n.1-2, p.15-28, 1999 [doi>10.1023/A:1019236319752]
• 7: A. Bestavros and C. Cunha, Server-initiated document dissemination for the WWW, IEEE Data Engineering Bulletin, Sept. 1996.
• 8: L. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenker, Web caching and Zipf-like distributions: evidence and implications, Proceedings of Infocom'99.
• 9: S. Bhattacharjee, K. Calvert, and E. W. Zegura, Self-organizing wide-area network caches, IEEE Infocom'98, April 1998.
• 10: Jean-Chrysostome Bolot , Philipp Hoschka, Performance engineering of the World Wide Web: application to dimensioning and cache design, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.1397-1405, May 1996, Paris, France
• 11: V. Cate, Alex - a global file system, Proceedings of the 1992 USENIX File System Workshop, pp. 1-12, May 1992.
• 12: M. Crovella and P. Batford, The network effects of prefetching, Proceedings of Infocom'98.
• 13: Ramón Cáceres , Fred Douglis , Anja Feldmann , Gideon Glass , Michael Rabinovich, Web proxy caching: the devil is in the details, ACM SIGMETRICS Performance Evaluation Review, v.26 n.3, p.11-15, Dec. 1998 [doi>10.1145/306225.306230]
• 14: A. Chankhunthod, P. B. Danzig, C. Neerdaels, M. F. Schwartz, and K. J. Worrel, A hierarchical Internet object cache, Usenix'96, January 1996.
• 15: 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.
• 16: J. Challenger, A. Iyengar, and P. Dantzig, A scalable system for consistently caching dynamic Web data, Proceedings of Infocom'99.
• 17: Carlos R. Cunha , Carlos F. B. Jaccoud, Determining WWW User's Next Access and Its Application to Pre-fetching, Proceedings of the 2nd IEEE Symposium on Computers and Communications (ISCC '97), p.6, July 01-03, 1997
• 18: Edith Cohen , Balachander Krishnamurthy , Jennifer Rexford, Improving end-to-end performance of the Web using server volumes and proxy filters, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.241-253, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 19: Edith Cohen , Balachander Krishnamurthy , Jennifer Rexford, Evaluating Server-Assisted Cache Replacement in the Web, Proceedings of the 6th Annual European Symposium on Algorithms, p.307-319, August 24-26, 1998
• 20: E. Cohen, B. Krishnamurthy, and J. Rexford, Efficient algorithms for predicting requests to Web servers, Proceedings of Infocom'99.
• 21: C. Liu , P. Cao, Maintaining Strong Cache Consistency in the World-Wide Web, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.12, May 27-30, 1997
• 22: K. Chinen and S. Yamaguchi, An interactive prefetching proxy server for improvement of WWW latency, Proceedings of INET'97, June 1997.
• 23: 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.
• 24: G. V. Dias, G. Cope, and R. Wijayaratne, A smart Internet caching system (http://www.isoc.org.ar/inet96/proc/a4/a4_3.htm).
• 25: 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.
• 26: 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).
• 27: Adam Dingle , Tomáš Pártl, Web cache coherence, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.907-920, May 1996, Paris, France
• 28: 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.
• 29: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.254-265, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 30: A. Feldmann, R. Caceres, F. Douglis, G. Glass, and M. Rabinovich, Performance of Web proxy caching in heterogeneous bandwidth environments, Proceedings of Infocom'99.
• 31: Li Fan , Pei Cao , Wei Lin , Quinn Jacobson, Web prefetching between low-bandwidth clients and proxies: potential and performance, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.178-187, May 01-04, 1999, Atlanta, Georgia, United States
• 32: 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).
• 33: S. Gadde , M. Rabinovich , J. Chase, Reduce, Reuse, Recycle: An Approach to Building Large Internet Caches, Proceedings of the 6th Workshop on Hot Topics in Operating Systems (HotOS-VI), p.93, May 05-06, 1997
• 34: J. S. Gwertzman , M. Seltzer, The case for geographical push-caching, Proceedings of the Fifth Workshop on Hot Topics in Operating Systems (HotOS-V), p.51, May 04-05, 1995
• 35: J. Gwetzman and M. Seltzer, World Wide Web cache consistency, Proceedings of the USENIX Technical Conference, pp. 141-152, January 1996.
• 36: A. Heddaya, S. Mirdrad, and D. Yates, Diffusion based caching along routing paths (http://cswww.bu.edu/faculty/heddaya/Pepers-NonTR/webcachewkp.ps.Z).
• 37: Hypertext Transfer Protocol --- HTTP/1.0, RFC 1945.
• 38: Hypertext Transfer Protocol --- HTTP/1.1, RFC 2068.
• 39: 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).
• 40: Madhukar R. Korupolu , Michael Dahlin, Coordinated Placement and Replacement for Large-Scale Distributed Caches, Proceedings of the 1999 IEEE Workshop on Internet Applications, p.62, July 26-27, 1999
• 41: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 42: 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.
• 43: Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Placement algorithms for hierarchical cooperative caching, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.586-595, January 17-19, 1999, Baltimore, Maryland, United States
• 44: P. Krishnan , Binay Sugla, Utility of co-operating Web proxy caches, Computer Networks and ISDN Systems, v.30 n.1-7, p.195-203, April 1, 1998
• 45: 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.
• 46: Balachander Krishnamurthy , Craig E. Wills, Piggyback server invalidation for proxy cache coherency, Proceedings of the seventh international conference on World Wide Web 7, p.185-193, April 1998, Brisbane, Australia
• 47: B. Krishnamurthy and C. E. Wills, Proxy cache coherency and replacement - towards a more complete picture, ICDC99, June 1999.
• 48: I. Lovric, Internet cache protocol extension, Internet Draft <draft-lovric-icp-ext-01.txt>.
• 49: Ari Luotonen , Kevin Altis, World-Wide Web proxies, Computer Networks and ISDN Systems, v.27 n.2, p.147-154, Nov. 1994
• 50: 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.
• 51: Ulana Legedza , John Guttag, Using network-level support to improve cache routing, Computer Networks and ISDN Systems, v.30 n.22-23, p.2193-2201, Nov. 25, 1998 [doi>10.1016/S0169-7552(98)00248-7]
• 52: 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.
• 53: E. Levy-Abegnoli, A. Iyengar, J. Song, and D. Dias, Design and performance of Web server accelerator, Proceedings of Infocom'99.
• 54: P. Lorenzetti, L. Rizzo, and L. Vicisano, Replacement policies for a proxy cache (http://www.iet.unipi.it/luigi/research.html).
• 55: I. Melve, Client-cache communication, Internet Draft <draft-melve-clientcache-com-00.txt>.
• 56: E. P. Markatos and C. E. Chronaki, A TOP-10 approach to prefetching on Web, Proceedings of INET'98.
• 57: 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).
• 58: Scott Michel , Khoi Nguyen , Adam Rosenstein , Lixia Zhang , Sally Floyd , Van Jacobson, Adaptive web caching: towards a new global caching architecture, Computer Networks and ISDN Systems, v.30 n.22-23, p.2169-2177, Nov. 25, 1998 [doi>10.1016/S0169-7552(98)00246-3]
• 59: 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.
• 60: Masaaki Nabeshima, The Japan cache project: an experiment on domain cache, Computer Networks and ISDN Systems, v.29 n.8-13, p.987-995, Sep. 1997
• 61: D. Povey and J. Harrison, A distributed Internet cache, Proceedings of the 20th Australian Computer Science Conference, Sydney, Australia, Feb. 1997.
• 62: T. Palpanas and A. Mendelzon, Web prefetching using partial match prediction, Proceedings of WCW'99.
• 63: V. N. Padmanabhan and J. C. Mogul, Using predictive prefetching to improve World Wide Web latency, proceedings of Sigcomm'96.
• 64: M. Rabinovich, Issues in Web content replication.
• 65: Michael Rabinovich , Jeff Chase , Syam Gadde, Not all hits are created equal: cooperative proxy caching over a wide-area network, Computer Networks and ISDN Systems, v.30 n.22-23, p.2253-2259, Nov. 25, 1998 [doi>10.1016/S0169-7552(98)00249-9]
• 66: Relais: cooperative caches for the World Wide Web, 1998 (http://www-sor.inria.fr/projects/relais/).
• 67: Chris Roadknight , Ian Marshall, Variations in cache behavior, Computer Networks and ISDN Systems, v.30 n.1-7, p.733-735, April 1, 1998
• 68: A. Rousskov and D. Wessels, Cache Digest, Proceedings of 3rd International WWW Caching Workshop, June 1998.
• 69: P. Rodriguez, C. Spanner, and E. W. Biersack, Web caching architectures: hierarchical and distributed caching, Proceedings of WCW'99.
• 70: Peter Scheuermann , Junho Shim , Radek Vingralek, A case for delay-conscious caching of Web documents, Selected papers from the sixth international conference on World Wide Web, p.997-1005, September 1997, Santa Clara, California, United States
• 71: Renu Tewari , Michael Dahlin , Harrick Vin, Design Considerations for Distributed Caching on the Internet, University of Texas at Austin, Austin, TX, 1998
• 72: 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.
• 73: V. Valloppillil and K. W. Ross, Cache array routing protocol v1.0, Internet Draft <draft-vinod-carp-v1-03.txt>.
• 74: Z. Wang, Cachemesh: a distributed cache system for World Wide Web, Web Cache Workshop, 1997.
• 75: 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).
• 76: 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).
• 77: Roland P. Wooster , Marc Abrams, Proxy caching that estimates page load delays, Selected papers from the sixth international conference on World Wide Web, p.977-986, September 1997, Santa Clara, California, United States
• 78: Marc Abrams , Charles R. Standridge , Ghaleb Abdulla , Edward A. Fox , Stephen Williams, Removal policies in network caches for World-Wide Web documents, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.293-305, August 28-30, 1996, Palo Alto, California, United States
• 79: D. Wessels and K. Claffy, Internet cache protocol (IPC), version 2, RFC 2186.
• 80: D. Wessels and K. Claffy, Application of Internet cache protocol (IPC), version 2, RFC 2187.
• 81: J. Yin , L. Alvisi , M. Dahlin , C. Lin, Using Leases to Support Server-Driven Consistency in Large-Scale Systems, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.285, May 26-29, 1998
• 82: Philip S. Yu , Edward A. MacNair, Performance study of a collaborative method for hierarchical caching in proxy servers, Computer Networks and ISDN Systems, v.30 n.1-7, p.215-224, April 1, 1998
• 83: J. Yang, W. Wang, R. Muntz, and J. Wang, Access driven Web caching, UCLA Technical Report #990007.