More Web Proxy on the site http://driver.im/

research-article

Performance models for hierarchy of caches

Authors:

Nicaise Choungmo Fofack,

Nedko NedkovAuthors Info & Claims

Performance Evaluation, Volume 97, Issue C

Pages 57 - 82

https://doi.org/10.1016/j.peva.2016.01.001

Published: 01 March 2016 Publication History

Abstract

This paper studies expiration-based caching systems in which caches assign a timer to each content they store and redraw the timer upon a cache miss. The modern Domain Name System (DNS) hierarchy is a valid application case and will be used throughout the paper. We introduce analytical models to study expiration-based caching systems based on renewal arguments. For polytree cache networks, we derive the cache performance metrics and characterize at each cache the aggregate request process, the thinning process and the miss process. A constant TTL policy is proved to maximize/minimize the hit probability if the requests' renewal function is concave/convex. We find that no distribution maximizes the hit probability anywhere in a network of caches. We validate our theoretical findings using real DNS traces (single cache and network cases) and via trace-driven simulations (network case).

References

[1]

J. Pang, A. Akella, A. Shaikh, B. Krishnamurthy, S. Seshan, On the responsiveness of DNS-based network control, in: Proc. IMC'04, Taormina, Italy, 2004.

[2]

R.J. Bayardo, R. Agrawal, D. Gruhl, A. Somani, YouServ: a web-hosting and content sharing tool for the masses, in: Proc. ACM WWW'02, New York, USA, 2002, pp. 345-354.

[3]

T. Callahan, M. Allman, M. Rabinovich, On modern DNS behavior and properties, ACM SIGCOMM Comput. Commun. Rev., 43 (2013) 7-15.

Digital Library

[4]

Y.T. Hou, J. Pan, K. Sohraby, S.X. Shen, Coping miss synchronization in hierarchical caching systems with nonlinear TTL functions, in: Proc. IEEE ICC'04, 2004, pp. 2194-2198.

[5]

N. Choungmo Fofack, Sara Alouf, Non-renewal TTL-based cache replacement policy and applications: Case of modern DNS hierarchy, Tech. Rep. RR-8414, Inria, 2013.

[6]

N. Choungmo Fofack, Sara Alouf, Modeling modern DNS caches, in: Proc. ACM ValueTools'13, Torino, Italy, 2013.

[7]

Y.T. Hou, J. Pan, B. Li, S. Panwar, On expiration-based hierarchical caching systems, IEEE J. Sel. Areas Commun., 22 (2004).

[8]

J. Jung, A.W. Berger, H. Balakrishnan, Modeling TTL-based Internet caches, in: Proc. IEEE Infocom'03, San Francisco, CA, USA, 2003.

[9]

O. Bahat, A.M. Makowski, Measuring consistency in TTL-based caches, Perform. Eval., 17 (2005) 439-455.

[10]

V. Martina, M. Garetto, E. Leonardi, A unified approach to the performance analysis of caching systems, in: Proc. IEEE Infocom'14, Toronto, Canada, 2014.

[11]

N. Choungmo Fofack, P. Nain, G. Neglia, D. Towsley, Analysis of TTL-based cache networks, in: Proc. ACM ValueTools'12, Cargèse, France, 2012.

[12]

N. Choungmo Fofack, P. Nain, G. Neglia, D. Towsley, Performance evaluation of hierarchical TTL-based cache networks, Comput. Netw., 65 (2014) 212-231.

[13]

N. Choungmo Fofack, On models for performance analysis of a core cache network and power save of a wireless access network, 2014.

[14]

D.S. Berger, P. Gland, S. Singla, F. Ciucu, Exact analysis of TTL cache networks, Perform. Eval., 79 (2014) 2-23.

[15]

J. Jung, E. Sit, H. Balakrishnan, R. Morris, DNS performance and the effectiveness of caching, in: Proc. ACM SIGCOMM Workshop on Internet Measurement, IMW'01, New York, NY, USA, 2001.

Digital Library

[16]

F. Baccelli, P. Brémaud, Elements of Queueing Theory, Palm Martingale Calculus and Stochastic Recurrences, Springer, Berlin, 2003.

[17]

W. Whitt, Approximating a point process by a renewal process, i: Two basic methods, Oper. Res., 30 (1982) 125-145.

Digital Library

[18]

A. Feldmann, W. Whitt, Fitting mixtures of exponentials to long-tail distributions to analyze network performance models, in: Proc. IEEE Infocom'97, Kobe, Japan, 1997.

[19]

D.R. Cox, Théorie du Renouvellement, Monographies, Dunod, Paris, 1966.

[20]

M. Tortorella, Numerical solutions of renewal-type integral equations, INFORMS J. Comput., 17 (2005) 73-96.

[21]

S. Karlin, Total Positivity, Vol. 1, Stanford University Press, 1968.

[22]

M. Brown, Bounds, inequalities, and monotonicity properties for some specialized renewal processes, Ann. Probab., 8 (1980) 227-240.

[23]

A. Dan, D. Towsley, An approximate analysis of the LRU and FIFO buffer replacement schemes, in: Proc. ACM Sigmetrics'90, Boulder, CO, USA, 1990, pp. 143-152.

[24]

E.J. Rosensweig, J. Kurose, D. Towsley, Approximate models for general cache networks, in: Proc. IEEE Infocom'10, San Diego, USA, 2010.

[25]

A. Simonian, M. Gallo, B. Kauffmann, L. Muscariello, C. Tanguy, Performance of the random replacement policy for networks of caches, in: Proc. ACM Sigmetrics/Performance'12, London, UK, 2012, pp. 395-396.

[26]

J.A. Fill, L. Holst, On the distribution of search cost for the move-to-front rule, Random Structures Algorithms, 8 (1996) 179-186.

Digital Library

[27]

S. Karlin, H.M. Taylor, A First Course in Stochastic Processes, Elsevier, 1975.

[28]

A.T. Lawrance, Dependency of intervals between events in superposition processes, J. R. Stat. Soc. Ser. B Stat. Methodol., 35 (1973) 306-315.

[29]

V. Isham, Dependent thinning of point processes, J. Appl. Probab., 17 (1980) 987-995.

[30]

A.D. Polyanin, A.V. Manzhirov, Handbook of Integral Equations, CRC Press, 1998.

[31]

G. Casale, E. Zhang, E. Smirni, KPC-Toolbox: Simple yet effective trace fitting using Markovian arrival processes, in: Proc. QEST'08, 2008.

Cited By

Ben Mazziane YAlouf SNeglia GMenasche D(2024)TTL model for an LRU-based similarity caching policyComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110206241:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.comnet.2024.110206
Si Salem TNeglia GIoannidis S(2023)No-regret Caching via Online Mirror DescentACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36052098:4(1-32)Online publication date: 11-Aug-2023
https://dl.acm.org/doi/10.1145/3605209
Li YSi Salem TNeglia GIoannidis S(2021)Online Caching Networks with Adversarial GuaranteesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34910475:3(1-39)Online publication date: 15-Dec-2021
https://dl.acm.org/doi/10.1145/3491047
Show More Cited By

Performance models for hierarchy of caches
1. General and reference
  1. Cross-computing tools and techniques

Recommendations

Hierarchical cache performance analysis under TTL-based consistency

This paper introduces an analytical model for characterizing the instantaneous hit ratio and instantaneous average hit distance of a traditional least recently used (LRU) cache hierarchy. The analysis accounts for the use of two variants of the Time-to-...
On the performance of general cache networks
VALUETOOLS '14: Proceedings of the 8th International Conference on Performance Evaluation Methodologies and Tools

The performance evaluation of cache networks has gain a huge attention due to content-oriented delivery technologies. If general network topologies are more realistic than hierarchical networks widely studied in the literature, their analysis is ...
Performance of One's Complement Caches

On-chip caches to reduce average memory access latency are commonplace in today's commercial microprocessors. These on-chip caches generally have low associativity and small cache sizes. Cache line conflicts are the main source of cache misses, which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Performance Evaluation

Performance Evaluation Volume 97, Issue C

March 2016

104 pages

ISSN:0166-5316

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 March 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ben Mazziane YAlouf SNeglia GMenasche D(2024)TTL model for an LRU-based similarity caching policyComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110206241:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.comnet.2024.110206
Si Salem TNeglia GIoannidis S(2023)No-regret Caching via Online Mirror DescentACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36052098:4(1-32)Online publication date: 11-Aug-2023
https://dl.acm.org/doi/10.1145/3605209
Li YSi Salem TNeglia GIoannidis S(2021)Online Caching Networks with Adversarial GuaranteesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34910475:3(1-39)Online publication date: 15-Dec-2021
https://dl.acm.org/doi/10.1145/3491047
Detti ABracciale LLoreti PMelazzi N(2019)Modeling LRU cache with invalidationComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2018.01.029134:C(55-65)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.comnet.2018.01.029

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents