Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We consider a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). We characterize the popularity pmf of the stream of misses from the cache, the so-called output of the cache, for a large class of demand-driven cache replacement policies. We measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution. Using the notion of majorization to capture this degree of skewness, we show that for the policy A0 and the random policy, the output always has less locality of reference than the input. However, we show by counterexamples that this is not always the case under the LRU and CLIMB policies when the input is selected according to a Zipf-like pmf. In that case, conjectures are offered (and supported by simulations) as to when LRU or CLIMB caching indeed reduces locality of reference.

REFERENCES

• 1: 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
• 2: Oleg Ivanovich Aven , E. G. Coffman, Jr. , Y. A. Kogan, Stochastic Analysis of Computer Storage, Kluwer Academic Publishers, Norwell, MA, 1987
• 3: G. Barish and K. Obraczka, "World Wide Web caching: Trends and techniques," IEEE Communications Magazine, Internet Technology Series. May 2000.
• 4: L.A. Belady, "A study of replacement algorithms for a virtual-storage computer," IBM Systems Journal 5 (1966), pp. 78--101.
• 5: L. Breslau, P. Cao, L. Fan, G. Phillips and S. Shenker, "Web caching and Zipf-like distributions: Evidence and implications," in Proceedings of IEEE INFOCOM 1999, New York (NY), March 1999.
• 6: A. Chankhunthod, P.B. Dantzig, C. Neerdaels, E.J. Schwartz and K. Worrell, "A hierarchical Internet object cache," in Proceedings of the USENIX 1995 Technical Conference, New Orleans (LA), 1995.
• 7: H. Che, Z. Wang and Y. Tung, "Analysis and design of hierarchical Web caching systems," in Proceedings of IEEE INFOCOM 2001, Anchorage (AL), April 2001.
• 8: K.L. Chung, "A Course in Probability Theory, Second. Edition, Academic Press, New York (NY), 1974.
• 9: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 10: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• 11: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 12: S.G. Dykes and K.A. Robbins, "A viability analysis of cooperative proxy caching," in Proceedings of IEEE INFOCOM 2001, Anchorage (AL), April 2001.
• 13: Sandra G. Dykes , Clinton L. Jeffery , Samir Das, Taxonomy and Design Analysis for Distributed Web Caching, Proceedings of the Thirty-second Annual Hawaii International Conference on System Sciences-Volume 8, p.8010, January 05-08, 1999
• 14: J. Escorcia, D. Dipak and D. Sarkar, "A novel cache distribution heuristic algorithm for a mesh of caches and its performance evaluation," Computer Communications 25 (2002), pp. 329--340.
• 15: R. Fonseca, V. Almeida, M. Crovella and B. Abrahao, "On the intrinsic locality of Web reference streams," in Proceedings of IEEE INFOCOM 2003, San Francisco (CA), April 2003.
• 16: Shudong Jin , Azer Bestavros, Temporal locality in Web request streams (poster session) (extended abstract): sources, characteristics, and caching implications, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.110-111, June 18-21, 2000, Santa Clara, California, United States
• 17: 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
• 18: A. Mahanti, C. Williamson and D. Eager, "Traffic Analysis of a Web proxy caching hierarchy," IEEE Network 14, May/June 2000, pp. 16--23.
• 19: 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]
• 20: A.W. Marshall and I. Olkin, "Inequalities: Theory of Majorization and Its Applications, Academic Press, New York (NY), 1979.
• 21: S. Vanichpun and A.M. Makowski, "Comparing strength of locality of reference -- Popularity, majorization, and some folk theorems," in Proceedings of IEEE INFOCOM 2004, New York (NY), March 2004.
• 22: J. Wang, "A survey of Web caching schemes for the Internet," ACM Computer Communication Review 25 (1999), pp. 36--46.
• 23: Carey Williamson, On filter effects in web caching hierarchies, ACM Transactions on Internet Technology (TOIT), v.2 n.1, p.47-77, February 2002 [doi>10.1145/503334.503337]
• 24: Alec Wolman , M. Voelker , Nitin Sharma , Neal Cardwell , Anna Karlin , Henry M. Levy, On the scale and performance of cooperative Web proxy caching, ACM SIGOPS Operating Systems Review, v.33 n.5, p.16-31, Dec. 1999
• 25: P. C. Yue , C. K. Wong, On the Optimality of the Probability Ranking Scheme in Storage Applications, Journal of the ACM (JACM), v.20 n.4, p.624-633, Oct. 1973 [doi>10.1145/321784.321790]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

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)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Performance attributes

General Terms:
Algorithms, Performance

Keywords:
locality of reference, majorization, output of a cache, popularity