Collaborative Web caching based on proxy affinities

ABSTRACT

With the exponential growth of hosts and traffic workloads on the Internet, collaborative web caching has been recognized as an efficient solution to alleviate web page server bottlenecks and reduce traffic. However, cache discovery, i.e., locating where a page is cached, is a challenging problem, especially in the fast growing World Wide Web environment, where the number of participating proxies can be very large. In this paper, we propose a new scheme which employs proxy affinities to maintain a dynamic distributed collaborative caching infrastructure. Web pages are partitioned into clusters according to proxy reference patterns. All proxies which frequently access some page(s) in the same web page cluster form an “information group”. When web pages belonging to a web page cluster are deleted from or added into a proxy's cache, only proxies in the associated information group are notified. This scheme can be shown to greatly reduce the number of messages and other overhead on individual proxies while maintaining a high cache hit rate. Finally, we employ trace driven simulation to evaluate our web caching scheme using three web access trace logs to verify that our caching structure can provide significant benefits on real workloads.

REFERENCES

• 1: Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266275]
• 2: 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]
• 3: 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]
• 4: L. Breslau, P. Cao, L. Fan, G. Phillips and S. Shenker. Web caching and zipf-like distributions: evidence and implications. Prec. of 18th Annual Joint Conf. of the IEEB Computer and Communications Societies. (INFOCOM), 126-134, 1999.
• 5: Redirection Algorithms for Load Sharing in Distributed Web-server Systems, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.528, May 31-June 04, 1999
• 6: A. Chankhunthod, P. Danzig, C. Neerdaels, M. Schwartz, and K. Worrell. A hierarchical Internet object cache, available htt p://cataxina.usc.edu/danzig/cache, ps
• 7: ClarkNet traces, available at :'http://www.acm.org/sigcomm/ITA/index.html"
• 8: 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
• 9: Peter B. Danzig , Richard S. Hall , Michael F. Schwartz, A case for caching file objects inside internetworks, Conference proceedings on Communications architectures, protocols and applications, p.239-248, September 13-17, 1993, San Francisco, California, United States
• 10: Digital's web traces, available at "ftp://ftp.digital.com/pub/D EC / tr aces/proxy / webtraces.html"
• 11: 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
• 12: 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
• 13: S. Ramaswamy. Personal communication, 1998.
• 14: T. S. Loon and V. Bharghavan. Alleviating the latency and bandwidth problem in WWW browsing. Prec. of USENIX Syrup. on Internct Technologies and Systems (USITS), 1997.
• 15: Hannes Marais , Krishna Bharat, Supporting cooperative and personal surfing with a desktop assistant, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.129-138, October 14-17, 1997, Banff, Alberta, Canada [doi>10.1145/263407.263531]
• 16: S.B. Moon, P. Skelly, and D. Towsley. Estimation and removal of clock skew from network delay measurements. Prec. of 18th Annual Joint Conf. of the IEEE Computer and Communications Societies. (INFOCOM), 227-234, 1999.
• 17: Vern Paxson, On calibrating measurements of packet transit times, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.11-21, June 22-26, 1998, Madison, Wisconsin, United States
• 18: J. Pitkow and M. Recker. A simple yet robust caching algorithm based on dynamic access patterns~ available http ://www.vuw. ac.nz/mimi/www/wwwcaching/caching.html
• 19: L. Zhang, S. Michel, K. Nguyen, A. Roseastern, S. Floyd, and V. Jocobson. Adaptive web caching: towards a new global caching architecture. Prec. of 3rd International Caching Workshop, 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Collaborative computing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Measurement, Performance, Theory