Value-based web caching

ABSTRACT

Despite traditional web caching techniques, redundant data is often transferred over HTTP links. These redundant transfers result from both resource modification and aliasing. Resource modification causes the data represented by a single URI to change; often, in transferring the new data, some old data is retransmitted. Aliasing, in contrast, occurs when the same data is named by multiple URIs, often in the context of dynamic or advertising content. Traditional web caching techniques index data by its name and thus often fail to recognize and take advantage of aliasing.Despite traditional web caching techniques, redundant data is often transferred over HTTP links. These redundant transfers result from both resource modification and aliasing. Resource modification causes the data represented by a single URI to change; often, in transferring the new data, some old data is retransmitted. Aliasing, in contrast, occurs when the same data is named by multiple URIs, often in the context of dynamic or advertising content. Traditional web caching techniques index data by its name and thus often fail to recognize and take advantage of aliasing.

REFERENCES

• 1: Hyokyung Bahn, Hyunsook Lee, Sam H. Noh, Sang Lyul Min, and Kern Koh. Replica-aware caching for web proxies. Computer Communications, 25(3):183--188, February 2002.
• 2: Gaurav Banga, Fred Douglis, and Michael Rabinovich. Optimistic deltas for WWW latency reduction. In Proc. of the USENIX Annual Technical Conf., 1997.
• 3: Brian E. Brewington , George Cybenko, How dynamic is the Web?, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.257-276, June 2000, Amsterdam, The Netherlands
• 4: Mun Choon Chan and Thomas Y. C. Woo. Cache-based compaction: A new technique for optimizing web transfer. In Proc. of IEEE INFOCOM, March 1999.
• 5: Fred Douglis, Anja Feldmann, Balachander Krishnamurthy, and Jeffrey C. Mogul. Rate of change and other metrics: a live study of the World Wide Web. In Proc. of the USENIX Symp. on Internet Technologies and Systems, 1997.
• 6: Fred Douglis and Arun Iyengar. Application-specific delta-encoding via resemblance detection. To appear in Proc. of USENIX Annual Technical Conference, June 2003.
• 7: Fred Douglis, Arun Iyengar, and Kiem-Phong Vo. Dynamic suppression of similarity in the web: a case for deployable detection mechanisms. Technical Report RC22514, IBM Research, July 2002.
• 8: Barron C. Housel , David B. Lindquist, WebExpress: a system for optimizing Web browsing in a wireless environment, Proceedings of the 2nd annual international conference on Mobile computing and networking, p.108-116, November 1996, Rye, New York, United States [doi>10.1145/236387.236416]
• 9: Mihut D. Ionescu. xProxy: A transparent caching and delta transfer system for web objects. Master's thesis, University of California at Berkeley, December 2000.
• 10: Terence Kelly , Jeffrey Mogul, Aliasing on the world wide web: prevalence and performance implications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511484]
• 11: U. Manber. Finding similar files in a large file system. In Proc. of the USENIX Winter Technical Conf., 1994.
• 12: P. Mattis, J. Plevyak, M. Haines, A. Beguelin, B. Totty, and D. Gourley. U.S. Patent #6,292,880: "Alias-free content-indexed object cache", September 2001.
• 13: J. Mogul, B. Krishnamurthy, F. Douglis, A. Feldmann, Y. Goland, A. van Hoff, and D. Hellerstein. Delta encoding in HTTP. The Internet Society, RFC 3229, January 2002.
• 14: Jeffrey C. Mogul , Fred Douglis , Anja Feldmann , Balachander Krishnamurthy, Potential benefits of delta encoding and data compression for HTTP, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.181-194, September 14-18, 1997, Cannes, France
• 15: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 16: Henrik Frystyk Nielsen , James Gettys , Anselm Baird-Smith , Eric Prud'hommeaux , Håkon Wium Lie , Chris Lilley, Network performance effects of HTTP/1.1, CSS1, and PNG, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.155-166, September 14-18, 1997, Cannes, France
• 17: Venkata N. Padmanabhan , Lili Qiu, The content and access dynamics of a busy Web site: findings and implications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.111-123, August 28-September 01, 2000, Stockholm, Sweden
• 18: M. O. Rabin. Fingerprinting by random polynomials. Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981.
• 19: R.L. Rivest. The MD5 message digest algorithm. April 1992.
• 20: Luigi Rizzo, Dummynet: a simple approach to the evaluation of network protocols, ACM SIGCOMM Computer Communication Review, v.27 n.1, p.31-41, Jan. 1997 [doi>10.1145/251007.251012]
• 21: R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon. Design and implementation of the Sun network filesystem. In Proc. of USENIX Summer Technical Conf., 1985.
• 22: Jonathan Santos and David Wetherall. Increasing effective link bandwidth by suppressing replicated data. In Proc. of USENIX Annual Technical Conference, June 1998.
• 23: Neil T. Spring , David Wetherall, A protocol-independent technique for eliminating redundant network traffic, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.87-95, August 28-September 01, 2000, Stockholm, Sweden
• 24: Andrew Tridgell. Efficient Algorithms for Sorting and Synchronization. PhD thesis, Australian National University, April 2000.
• 25: Arthur van Hoff, John Giannandrea, Mark Hapner, Steve Carter, and Milo Medin. The HTTP distribution and replication protocol. Technical Report NOTE-DRP, World Wide Web Consortium, August 1997.
• 26: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 27: Craig E. Wills and Mikhail Mikhailov. Examining the cacheability of user-requested web resources. In Proc. of the 4th Intl. Web Caching Workshop, 1999.
• 28: Craig E. Wills and Mikhail Mikhailov. Studying the impact of more complete server information on web caching. In Proc. of the 5th Web Caching and Content Delivery Workshop, 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

General Terms:
Algorithms, Design, Experimentation, Performance, Security

Keywords:
HTTP, WWW, aliasing, caching, duplicate suppression, dynamic content, hypertext transfer protocol, privacy, proxy, redundant transfers, resource modification, scalability, world wide web