Stefano Traverso
Abstract
The dimensioning of caching systems represents a difficult task in the design of infrastructures for content distribution in the current Internet. This paper addresses the problem of defining a realistic arrival process for the content requests generated by users, due its critical importance for both analytical and simulative evaluations of the performance of caching systems. First, with the aid of \youtube traces collected inside operational residential networks, we identify the characteristics of real traffic that need to be considered or can be safely neglected in order to accurately predict the performance of a cache. Second, we propose a new parsimonious traffic model, named the Shot Noise Model (SNM), that enables users to natively capture the dynamics of content popularity, whilst still being sufficiently simple to be employed effectively for both analytical and scalable simulative studies of caching systems. Finally, our results show that the SNM presents a much better solution to account for the temporal locality observed in real traffic compared to existing approaches.
- V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Briggs, and R. L. Braynard. Networking named content. In ACM CoNEXT, 2009. Google Scholar
Digital Library
- C. Fricker, P. Robert, J. Roberts, and N. Sbihi. Impact of traffic mix on caching performance in a content-centric network. In NOMEN Workshop, 2012.Google ScholarCross Ref
- J. Erman, A. Gerber, M. Hajiaghayi, D. Pei, S. Sen, and O. Spatscheck. To cache or not to cache: the 3G case. IEEE Internet Computing, 15(2), March 2011. Google ScholarDigital Library
- F. Qian, K. S. Quah, J. Huang, J. Erman, A. Gerber, Z. Mao, S. Sen, and O. Spatscheck. Web caching on smartphones: ideal vs. reality. In ACM MobiSys, 2012. Google ScholarDigital Library
- U. Lee, I. Rimac, D. Kilper, and V. Hilt. Toward energy-efficient content dissemination. IEEE Network, March 2011. Google ScholarDigital Library
- W. Jiang, S. Ioannidis, L. Massoulié, and F. Picconi. Orchestrating massively distributed CDNs. In ACM CoNEXT, 2012. Google ScholarDigital Library
- I. Poese, B. Frank, G. Smaragdakis, S. Uhlig, A. Feldmann, and B. Maggs. Enabling content-aware traffic engineering. ACM SIGCOMM CCR, Sep. 2012. Google ScholarDigital Library
- J. Erman, A. Gerber, M. T. Hajiaghayi, D. Pei, and O. Spatscheck. Network-aware forward caching. In ACM WWW, 2009. Google ScholarDigital Library
- E. Coffman and P. Denning. Operating Systems Theory. Prentice-Hall, Englewood Cliffs (NJ), 1973. Google ScholarDigital Library
- C. Fricker, P. Robert, and J. Roberts. A versatile and accurate approximation for LRU cache performance. In ITC, 2012. Google ScholarDigital Library
- B. Ager, F. Schneider, J. Kim, and A. Feldmann. Revisiting cacheability in times of user generated content. In IEEE Global Internet Symposium, March 2010.Google ScholarCross Ref
- N. Laoutaris, G. Zervas, A. Bestavros, and G. Kollios. The cache inference problem and its application to content and request routing. In IEEE INFOCOM, 2007.Google ScholarDigital Library
- S. Vanichpun and A. M. Makowski. The output of a cache under the independent reference model: where did the locality of reference go? ACM SIGMETRICS Perform. Eval. Rev., Jun. 2004. Google ScholarDigital Library
- V. Almeida, A. Bestavros, M. Crovella, and A. de Oliveira. Characterizing reference locality in the WWW. In IEEE PDIS, 1996. Google ScholarDigital Library
- S. Jin and A. Bestavros. Sources and characteristics of Web temporal locality. In IEEE/ACM Mascots, 2000. Google ScholarDigital Library
- R. Fonseca, V. Almeida, M. Crovella, and B. Abrahao. On the intrinsic locality of Web reference streams. In IEEE INFOCOM, 2003.Google ScholarCross Ref
- P. R. Jelenković and A. Radovanović. Least-recently-used caching with dependent requests. Theoretical computer science, 326(1):293--327, 2004. Google ScholarDigital Library
- E. Rosensweig, D. Menasche, and J. Kurose. On the steady-state of cache networks. In IEEE INFOCOM, 2013.Google ScholarCross Ref
- P. R. Jelenković and A. Radovanović. The persistent-access-caching algorithm. Random Struct. Algorithms, 33(2):219--251, Sept. 2008. Google ScholarDigital Library
- A. Dan and D. Towsley. An approximate analysis of the LRU and FIFO buffer replacement schemes. In ACM SIGMETRICS, 1990. Google ScholarDigital Library
- H. Che, Y. Tung, and Z. Wang. Hierarchical Web caching systems: modeling, design and experimental results. IEEE JSAC, 20(7), Sept. 2002. Google ScholarDigital Library
- E. G. Coffman and P. J. Denning. Operating systems theory, volume 973. Prentice-Hall Englewood Cliffs, NJ, 1973. Google ScholarDigital Library
- K. Kylkoski and J. Virtamo. Cache replacement algorithms for the renewal arrival model. In Fourteenth Nordic Teletraffic Seminar, NTS-14, pages 139--148, Copenhagen, Denmark, Aug. 1998.Google Scholar
- A. Finamore, M. Mellia, M. Meo, M. M. Munaf'o, and D. Rossi. Experiences of Internet traffic monitoring with Tstat. IEEE Network, 2011.Google ScholarCross Ref
- H. Abrahamsson and M. Nordmark. Program popularity and viewer behaviour in a large tv-on-demand system. In ACM IMC, 2012. Google ScholarDigital Library
- J. Yang and J. Leskovec. Patterns of temporal variation in online media. In WSDM '11, 2011. Google ScholarDigital Library
- Y. Matsubara, Y. Sakurai, B. A. Prakash, L. Li, and C. Faloutsos. Rise and fall patterns of information diffusion: model and implications. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 6--14. ACM, 2012. Google ScholarDigital Library
- M. Ahmed, S. Spagna, F. Huici, and S. Niccolini. A peek into the future: Predicting the evolution of popularity in user generated content. In ACM WSDM, Feb. 2013. Google ScholarDigital Library
- J. Møller. Shot noise Cox processes. Advances in Applied Probability, 35(3), 2003.Google Scholar
- R. Crane and D. Sornette. Robust dynamic classes revealed by measuring the response function of a social system. Proceedings of the National Academy of Sciences, 105(41):15649--15653, 2008.Google ScholarCross Ref
- M. Cha, A. Mislove, and K. P. Gummadi. A measurement-driven analysis of information propagation in the Flickr social network. In WWW '09, 2009. Google ScholarDigital Library
- M. Ahmed, S. Traverso, P. Giaccone, E. Leonardi, and S. Niccolini. Analyzing the performance of LRU caches under non-stationary traffic patterns. CoRR, abs/1301.4909, 2013.Google Scholar
- S. M. Ross. Simulation. Elsevier Academic Press, Amsterdam, 2006.Google Scholar
Index Terms
- Temporal locality in today's content caching: why it matters and how to model it
Recommendations
Analyzing Gatewaysź Impact on Caching for Micro CDNs based on CCN
ICETE 2016: Proceedings of the 13th International Joint Conference on e-Business and TelecommunicationsContent Centric Networking (CCN) is a new architecture for a future Internet. CCN is a clean-state architecture
that targets the distribution of content. As such, content is located at the heart of the architecture and CCN
includes two main features: ...
A popularity based content eviction scheme via betweenness-centrality caching approach for content-centric networking (CCN)
In distinction to today's IP-based, host-bound, Internet architecture, content-centric networking (CCN) emphasizes content by making it instantly addressable and routable. CCN has attracted attention in the research community as a means to cope with the ...
Revisiting caching in content delivery networks
SIGMETRICS '14: The 2014 ACM international conference on Measurement and modeling of computer systemsContent Delivery Networks (CDNs) differ from other caching systems in terms of both workload characteristics and performance metrics. However, there has been little prior work on large-scale measurement and characterization of content requests and ...
Comments