On filter effects in web caching hierarchies

ABSTRACT

This article studies the "filter effects" that occur in Web proxy caching hierarchies due to the presence of multiple levels of caches. That is, the presence of one level of cache changes the structural characteristics of the workload presented to the next level of cache, since only the requests that miss in one cache are forwarded to the next cache.Trace-driven simulations, with empirical and synthetic traces, are used to demonstrate the presence and magnitude of the filter effects in a multilevel Web proxy caching hierarchy. Experiments focus on the effects of cache size, cache replacement policy, Zipf slope, and the depth of the Web proxy caching hierarchy.Finally, the article considers novel cache management techniques that can better exploit the changing workload characteristics across a multilevel Web proxy caching hierarchy. Trace-driven simulations are used to evaluate the performance of these approaches. The simulation results demonstrate that size-based partitioning and heterogeneous cache replacement policies each offer improvements in overall caching performance. The sensitivity of the results to the degree of workload overlap among child-level proxy caches is also studied.

REFERENCES

• 1: Abdulla Ghaleb , Fox Edward A. , Abrams Marc , Williams Stephen, WWW Proxy Traffic Characterization with Application to Caching, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1997
• 2: ALMEIDA, V., CESARIO, M., FONSECA, R., MEIRA, W., JR., AND MURTA, C. 1998. Analysing the behavior of a proxy server in light of regional and cultural issues. In Proceedings of the Third International WWW Caching Workshop (Manchester, England, June).
• 3: Virgílio Almeida , Azer Bestavros , Mark Crovella , Adriana de Oliveira, Characterizing reference locality in the WWW, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.92-107, December 18-20, 1996, Miami Beach, Florida, United States
• 4: ARLITT, M., CHERKASOVA, L., DILLEY, J., FRIEDRICH, R., AND JIN, T. 1999. Evaluating content management techniques for Web proxy caches. In Proceedings of the Second Workshop on Internet Server Performance (Atlanta, GA, May).
• 5: RLITT,M.AND JIN, T. 2000. A workload characterization study of the 1998 World Cup Web site. IEEE Network 14, 3 (May/June), 30-37.
• 6: ARLITT,M.AND WILLIAMSON, C. 1997a. Trace-driven simulation of document caching strategies for internet Web servers. Simulation J. 68, 1 (Jan.), 23-33.
• 7: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 8: BAENTSCH, M., BAUM, L., MOLTER, G., ROTHKUGEL,S.,AND STURM, P. 1997a. World-Wide Web caching: The application level view of the Internet. IEEE Commun. (June), 170-178.
• 9: Michael Baentsch , Lothar Baum , Georg Molter , Steffen Rothkugel , Peter Sturm, Enhancing the Web's Infrastructure: From Caching to Replication, IEEE Internet Computing, v.1 n.2, p.18-27, March 1997 [doi>10.1109/4236.601083]
• 10: A. Bestavros , R. L. Carter , M. E. Crovella , C. R. Cunha , A. Heddaya , S. A. Mirdad, Application-level document caching in the Internet, Proceedings of the 2nd International Workshop on Services in Distributed and Networked Environments, p.166, June 05-08, 1995
• 11: 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
• 12: BRESLAU, L., CAO, P., FAN, L., PHILLIPS,G.,AND SHENKER, S. 1999. Web caching and Zipf-like distributions: Evidence and implications. In Proceedings of the IEEE INFOCOM Conference (New York, March), 126-134.
• 13: BUSARI, M. 2000. Simulation evaluation of Web caching hierarchies. M.Sc. thesis, Dept. Computer Science, Univer. of Saskatchewan, June.
• 14: BUSARI,M.AND WILLIAMSON, C. 2001a. On the sensitivity of Web proxy cache performance to workload characteristics. In Proceedings of the IEEE INFOCOMM (Anchorage, AL, April), 1225-1234.
• 15: Mudashiru Busari , Carey Williamson, Simulation Evaluation of a Heterogeneous Web Proxy Caching Hierarchy, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.379, August 15-18, 2001
• 16: CAO,P.AND IRANI, S. 1997. Cost-aware WWW proxy caching algorithms. In Proceedings of the USENIX Symp. on Internet Technologies and Systems (Dec.), 193--206.
• 17: CHE, H., WANG, Z., TUNG, Y. 2001. Analysis and design of hierarchical Web caching systems. In Proceedings of IEEE INFOCOMM (Anchorage, AL, April), 1416-1424.
• 18: CHANKHUNTHOD, A., DANZIG, P., NEERDAELS, C., SCHWARTZ, M., AND WORRELL, K. 1996. A hierarchical Internet object cache. In Proceedings of the 1996 USENIX Technical Conference (San Diego, CA, Jan.), 153-163.
• 19: CHERKASOVA,L.AND CIARDO, G. 2000. Characterizing temporal locality and its impact on Web server performance. Proceedings of ICCCN'2000, Las Vegas, NV, October.
• 20: 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
• 21: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 22: Carlos Cunha , Azer Bestavros , Mark Crovella, Characteristics of WWW Client-based Traces, Boston University, Boston, MA, 1995
• 23: DOYLE, R., CHASE, J., GADDE,S.,AND VAHDAT, A. 2001. The trickle-down effect: Web caching and server request distribution. In Proceedings of the Web Caching and Content Delivery Workshop (Boston, MA, June).
• 24: DUSKA, B., MARWOOD,D.,AND FEELEY, M. 1997. The measured access characteristics of World-Wide Web client proxy caches. In Proceedings of the USENIX Symposium on Internet Technologies and Systems (Dec.), 23-35.
• 25: 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
• 26: FELDMANN, A., CACERES, R., DOUGLIS, F., GLASS,G.,AND RABINOVICH, M. 1999. Performance of Web proxy caching in heterogeneous bandwidth environments. In Proceedings of IEEE INFOCOMM (April), 107-116.
• 27: Michael J. Franklin , Michael J. Carey , Miron Livny, Global Memory Management in Client-Server Database Architectures, Proceedings of the 18th International Conference on Very Large Data Bases, p.596-609, August 23-27, 1992
• 28: 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
• 29: John Heidemann , Katia Obraczka , Joe Touch, Modeling the performance of HTTP over several transport protocols, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.616-630, Oct. 1997 [doi>10.1109/90.649564]
• 30: JIN,S.AND BESTAVROS, A. 2000. Greedy-Dual Web caching algorithms: Exploiting the two sources of temporal locality in Web request streams. In Proceedings of the Fifth Web Caching Workshop (Lisbon, Portugal, May).
• 31: Shudong Jin , Azer Bestavros, Sources and Characteristics of Web Temporal Locality, Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.28, August 29-September 01, 2000
• 32: MAHANTI, A. 1999. Web proxy workload characterization and modeling. M.Sc. thesis, Dept. of Computer Science, University of Saskatchewan, Sept.
• 33: Anirban Mahanti , Derek Eager , Carey Williamson, Temporal locality and its impact on Web proxy cache performance, Performance Evaluation, v.42 n.2-3, p.187-203, Oct. 2000 [doi>10.1016/S0166-5316(00)00032-8]
• 34: MAHANTI, A., WILLIAMSON,C.,AND EAGER, D. 2000b. Traffic analysis of a Web proxy caching hierarchy. IEEE Network, 14, 3 (May/June), 16-23.
• 35: MAHANTI,A.AND WILLIAMSON, C. 2001. Web proxy workload characterization. Tech. Rep. http://www.cs.usask.ca/faculty/carey/papers/workloadstudy.ps
• 36: POVEY,D.AND HARRISON, J. 1997. A distributed Internet cache. In Proceedings of the 20th Australian Computer Science Conference (Sydney, Australia, Feb.).
• 37: ROADKNIGHT, C., MARSHALL, I., AND VEARER, D. 1999. File popularity characterization. In Proceedings of the Second Workshop on Internet Server Performance (WISP'99, Atlanta, GA, May).
• 38: RODRIGUEZ, P., SPANNER,C.,AND BIERSACK, E. 1999. Web caching architectures: Hierarchical and distributed caching. In Proceedings of the Fourth Web Caching Workshop (San Diego, CA, March), 37-48.
• 39: Design Considerations for Distributed Caching on the Internet, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.273, May 31-June 04, 1999
• 40: VALLOPPILLIL,V.AND ROSS, K. 1988. Cache array routing protocol v1.1. Internet draft, Feb.
• 41: D. Weikle , S. McKee , W. Wulf, Caches as Filters: A New Approach to Cache Analysis, Proceedings of the 6th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.2, July 19-24, 1998
• 42: WESSELS,D.AND CLAFFY, K. 1998. ICP and the squid Web cache. IEEE J. Selected Areas Commun. 16, 3 (April), 345-357.
• 43: WILLICK, D., EAGER,D.,AND BUNT, R. 1993. Disk cache replacement policies for network fileservers. In Proceedings of ICDCS (Pittsburgh, PA).
• 44: Alec Wolman , M. Voelker , Nitin Sharma , Neal Cardwell , Anna Karlin , Henry M. Levy, On the scale and performance of cooperative Web proxy caching, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.16-31, December 12-15, 1999, Charleston, South Carolina, United States
• 45: Philip S. Yu , Edward A. MacNair, Performance study of a collaborative method for hierarchical caching in proxy servers, Proceedings of the seventh international conference on World Wide Web 7, p.215-224, April 1998, Brisbane, Australia
• 46: ZHANG, L., FLOYD,S.AND JACOBSON, V. 1997. Adaptive Web caching. In Proceedings of the NLANR Web Caching Workshop (Boulder, CO, June).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
Performance evaluation, Web performance, Web proxy caching hierarchies, World-Wide-Web