Adaptive Web Caching

The Adaptive Web Caching Home Page

• Overview of project.
• The initial proposal (postscript, PDF) for this project is from February 1997.
  An earlier version of this proposal was submitted in March 1996.
  Position Paper (postscript, PDF) submitted to the Boulder Cache Workshop '97, April 25, 1997.
  
• Lixia Zhang, Scott Michel, Khoi Nguyen, Adam Rosenstein, Sally Floyd, and Van Jacobson, "Adaptive Web Caching: Towards a New Global Caching Architecture" ( html), 3rd International WWW Caching Workshop, June 1998.
• 1997 Project Summary.
• Floyd, S., Adaptive Web Caching and Active Networking (postscript, pdf).
  This talk also addresses the relationship between Adaptive Web Caching and active networking. DARPA Active Networking PI Meeting, June 19-20, 1997.
• Floyd, S., Adaptive Web Caching (postscript, pdf). Boulder Cache Workshop '97, June 9-10, 1997.
• Jacobson, V., How to Kill the Internet (viewgraphs). (compressed postscript, pdf). SIGCOMM 95 Middleware Workshop, Cambridge MA, August 28, 1995.

General References:

• www.web-cache.com, including a list of web caching documents from the IETF.

• Brian Davison's Web Caching Pages.

• NLANR's Global Caching Hierarchy and Recomended Reading web pages, and the Hit-N-Miss Web Caching Newsletter.

• UBC's Web Caching - An Introduction, Web Caching Links, and Web Caching Bibliography web pages.

Related Papers on Web Caching Infrastructures:

• Alec Wolman, Geoffrey M. Voelker, Nitin Sharma, Neal Cardwell, Anna Karlin, Henry M. Levy, On the Scale and Performance of Cooperative Web Proxy Caching, SOSP 1999.
  "We demonstrate that cooperative caching has performance benefits only within limited population bounds."

• Bhattacharjee, S., Calvert, K., and Zegura, E., Self-Organizing Wide-Area Network Caches, Infocom 98.
  This paper considers networks in which a small cache is placed at every node in a network, and proposes algorithms for determining which caches will cache which objects. The simulations in the paper use a locally-developed network simulator for active networks.

• Abdelsalam Heddaya, Sulaiman Mirdad, and David Yates, Diffusion-based caching along routing paths, May 1997.
  This paper proposes WebWave, a diffusion-based caching protocol for distributing the caching load among the caches along a path between clients and servers, for load-balancing among the caches.

• Radhika Malpani, Jacob Lorch and David Berger, Making World Wide Web Caching Servers Cooperate Proceedings of the Fourth International World Wide Web Conference, Boston, December 1995.
  This 1995 paper proposes that web caches multicast requests to other cooperating web servers, and redirect the client to the answering web cache that has the requested object.

• Renu Tewari, Michael Dahlin, Harrick Vin and Jon Kay, Beyond Hierarchies: Design Considerations for Distributed Caching on the Internet, Technical Report TR98-04, Department of Computer Sciences, University of Texas at Austin, February 1998.
  This paper proposes several design principles for large-scale distributed caches: (1) minimizing hops to access data; (2) minimizing delay for misses; (3) sharing data among caches; and (4) caching data close to clients. The paper proposes separating data paths from the metadata paths used for determining how to forward requests; using location hints to indicate a nearby cache that has a copy of an object; and using push caching to move data near clients.

• Zheng Wang and Jon Crowcroft, Cachemesh: A Distributed Cache System For World Wide Web, Extended abstract, June 1997.
  This is a proposal for cache placement control and resolution for web caches on a well-connected underlying network.

The Current Web Caching Infrastructure:

• Michael Baentsch, L. Baum, Georg Molter, S. Rothkugel, and P. Sturm, World Wide Web Caching: The Application-Level View of the Internet. IEEE Communications, June 1997.
  An excellent introduction to the 1997 web caching infrastructure, including conclusions that the web does show locality of reference, that 50% appears to be an upper bound on cache byte hit rates, that latencies introduced by caches are negligible, and that there has not been a rise in the last year in the fraction of web traffic that is non-cachable.

• Ingrid Melve, Lars Slettjord, Ton Verschuren and Henny Bekker, Building a web caching system - architectural considerations.
  This web page addresses considerations in constructing web caching meshes today, and includes other references on web caching architecture.

• Mirror Image Internet's ICP-compliant caching product for ISPs and large corporations includes large centrally-located caches and a Cache Management Service.

• D. Wessels and K. Claffy, ICP and the Squid Web Cache, IEEE JSAC, April 1998, pp. 345-357.
  This article describes ICP, caching-related features of HTTP, and the development of the Squid cache. Some of the scaling issues with ICP are described. In the Recent Work section, the paper describes an approach for Squid to acquire topology information, building up a local table, based on IP names, of round-trip times to server hosts. Squid caches would use these tables to learn which peers are likely sources for which caches.

Caching and Replicated Servers:

• Mark Russell, Tim Hopkins, CFTP - A Caching FTP Server, 3rd International WWW Caching Workshop, June 1998.
  This paper shows that providing caches with knowledge of local (e.g., national) mirror sites can significantly reduce the amount of data that needs to be transferred across overused networks.

Hash Routing and other approaches for clusters of web servers

Content-based Web Caches:

• Masaaki Nabeshima, The Japan Cache Project: An Experiment on Domain Cache, WWW6 proceedings.

Other information about the contents of other caches:

• Li Fan, Pei Cao, Jussara Almeida, and Andrei Broder, Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol , Technical Report 1361, Computer Sciences Department, University of Wisconsin-Madison.
  This paper proposes the "Summary Cache" protocol, where caches keep a summary of the cache directories of other caches.

• Dean Povey and John Harrison, Distributed Internet Cache, 20th Australasian Computer Science Conference, February 1997.
  This paper nicely describes the limitations of the existing hierarchical structure of web caches. The paper proposes a distributed cache where leaf caches would cache and retrieve objects, and upper level caches in the hierarchy would only be used to maintain information about the contents of the leaf caches.

• Micheal Rabinovich, Jeff Chase, and Syam Gadde, Not All Hits Are Created Equal: Cooperative Proxy Caching Over a Wide-Area Network. 3rd International WWW Caching Workshop, June 1998.
  This paper proposes a model for a cache to share information with other caches in its "vicinity" about cache contents.

• Alex Rousskov and Duane Wessels, Cache Digests, 3rd International WWW Caching Workshop, June 1998.
  This paper uses Bloom filters to allow proxies to make information about their cache contents available to their peers in a compact form.

Web caching, multicast, and continuous media:

• Large-Scale Active Middleware, ISI.
  The goal of this project is to support multicast-based distributed information services for hot-spot web traffic.

• Pablo Rodriguez, Ernst W Biersack, Keith W Ross, Improving the WWW: Caching or Multicast (postscript). An earlier version appeared in the 3rd International WWW Caching Workshop, June 1998.
  This paper finds that caching is preferable to multicast except for popular documents that change very fast, which are better served by a multicast distribution.

• Renu Tewari, Harrick Vin, Asit Dan and Dinkar Sitaram, Resource Based Caching for Web Servers, Proceedings of SPIE/ACM Conference on Multimedia Computing and Networking (MMCN), San Jose, January 1998.
  This paper proposes characterizing objects by their resource requirements and caching gain, and dynamically selecting the granularity of the object to be cached. For continuous media data, the web cache might cache distinct subsets of the data, for delivery to multiple clients.

Measuring response times:

• Zongming Fei, Samrat Bhattacharjee, Ellen Zegura, and Mostafa Ammar, A Novel Server Selection Technique for Improving the Response Time of a Replicated Service, Infocom '98.
  This paper proposes a method for a client to estimate the response time metric to a server, defined as the time from sending a query to that server until a complete response is received.

The Backlash - the Dangers of Web Caching:

• Russell Tewksbury, Is the Internet Heading for a Cache Crunch?, OnTheInternet, January/February 1998.
  "Both proxy caching and impending implementation of an international hierarchical cache system set the stage for abuses such as individual monitoring and surveillance, tampering, identity theft, censorship, intellectual property or copyright infringement, invasion of privacy, and taxation by government." A little one-sided, perhaps?