Abstract
One popular approach to overcome the expected congestions due to the spectacular development of various multimedia applications consists in installing transparent caches at strategically chosen places inside telecommunication networks. The problem of locating caches is a difficult optimization problem, closely related to the p-median problem. In the case where the network is a tree, some cache location problems have already been investigated. In this paper, we propose to refine these models by taking into account a dynamic effect due to cache replacement policies. In our model, only the most popular contents are stored in the caches. The hierarchical effect of several successive caches is also captured by the model. A Mixed Integer Programming model and a Dynamic Programming algorithm are proposed and compared on a preliminary set of numerical experiments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asit, D., Towsley, D.: An approximate analysis of the lru and fifo buffer replacement schemes. SIGMETRICS Perform. Eval. Rev. 18(1), 143–152 (1990)
Avella, P., Boccia, M., Canonico, R., Emma, D., Sforza, A., Ventre, G.: Web cache location and network design in vpns (2003), http://citeseer.ist.psu.edu/639771.html
Cronin, E., Jamin, S., Danny, C., Yuval, R.: Constrained mirror placement on the internet (2002), http://citeseer.ist.psu.edu/cronin02constrained.html
Dantzig, P., Hall, R., Schwartz, M.: A case for caching file objects inside internetworks. In: SIGCOMM 1993, pp. 239–243 (1993)
Flajolet, P., Gardy, D., Thimonier, L.: Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Appl. Math. 39(3), 207–229 (1992)
Gelenbe, E.: A unified approach to the evaluation of a class of replacement algorithms. IEEE Trans. Comput. 22(6), 611–618 (1973)
Hakimi, S., Schmeichel, E.: Locating replicas of a database on a network. Networks 30(1), 31–36 (1997)
Jelenkovic, P.R.: Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities. Annals of Applied Probability 9(2), 430–464 (1999)
Kariv, O., Hakimi, L.: An algorithmic approach to network location problems. ii: The p-median. SIAM J. Appl. Math. 37(3), 539–560 (1979)
Krishnan, P., Raz, D., Shavitt, Y.: The cache location problem. IEEE/ACM Transactions on Networking 8(5), 568–582 (2000), citeseer.ist.psu.edu/635591.html
Luss, H.: Optimal content distribution in video-on-demand tree networks. IEEE Transactions on systems, man, and cybernetics - part A: systems and humans 40(1) (2010)
Pathan, A.M.K., Buyya, R.: A taxonomy and survey of cdns. Tech. rep., The University of Melbourne (2007)
Podlipnig, S., Böszömenyi, L.: A survey of web cache replacement strategies. ACM Computing Surveys (CSUR) 35(4), 374–398 (2003)
Reese, J.: Solution methods for the p-median problem: An annotated bibliography. Networks 19, 125–142 (2006)
Tamir, A.: An \(\mathcal{O}(pn^{2})\) algorithm for the p-median and other related problems on tree graphs. Operations Research Letters 19, 59–64 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pierre, B., Walid, B.A., Eric, G. (2011). Cache Location in Tree Networks: Preliminary Results. In: Pahl, J., Reiners, T., Voß, S. (eds) Network Optimization. INOC 2011. Lecture Notes in Computer Science, vol 6701. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21527-8_56
Download citation
DOI: https://doi.org/10.1007/978-3-642-21527-8_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21526-1
Online ISBN: 978-3-642-21527-8
eBook Packages: Computer ScienceComputer Science (R0)