Top

OR Spectrum

Published in:

01-01-2015 | Regular Article

The dynamic replica placement problem with service levels in content delivery networks: a model and a simulated annealing heuristic

Authors: Rainer Kolisch, André Dahlmann

Published in: OR Spectrum | Issue 1/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Dynamically assigning copies (replicas) of internet files to regionally placed servers is a crucial planning problem for content delivery network providers. Their goal is to minimize placement, storage and delivery costs while fulfilling service-level agreements. Although there is considerable work on simplified versions of this problem such as the static case, the dynamic problem with all three cost types and service-level constraints has yet not been considered in the literature. This paper provides a mixed integer programming (MIP) formulation for the problem as well as a simulated annealing metaheuristic. A computational study is employed to assess the simulated annealing heuristic and the MIP employing a state-of-the-art solver.

previous article Urban public transit network optimization with flexible demand

next article Clustering clinical departments for wards to achieve a prespecified blocking probability

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Aarts E, Korst J,Wil M (2005) Simulated annealing. In Burke EK, Kendall G (eds) Search methodologies. Springer, New York

Aggarwal A, Rabinovich M (1998) Performance of dynamic replication schemes for an internet hosting service. In: Technical report, AT &T Labs. http://www.research.att.com/~misha/radar/tm-perf.ps.gz

Ahrens J (1977) A code for the transportation problem. In: Technical report, Universität Kiel, Kiel

Aikens CH (1985) Facility location models for distribution planning. Eur J Oper Res 22(3):263–279CrossRef

Aioffi WM, Mateus GR, Almeida JM, Melo RC (2004) Dynamic content placement for mobile content distribution networks. In: Chi C-H , van Steen M, Wills C (eds) Web content caching and distribution, vol 3293. Lecture notes in computer science. Springer, Berlin, pp 19–33

Akamai Technologies Inc. (2010) http://wwwnui.akamai.com/datavis/visitors_feed.xml. Accessed 4 February 2010

Baentsch M, Baum L, Molter G, Rothkugel S, Sturm P (1997) Enhancing the web’s infrastructure: from caching to replication. IEEE Internet Comput 1(2):18–27CrossRef

Bartolini N, Presti F, Petrioli C (2003) Optimal dynamic replica placement in content delivery networks. In: The 11th IEEE international conference on networks, ICON 2003, pp 125–130

Chen Y, Katz R, Kubiatowicz J (2002) Dynamic replica placement for scalable content delivery. In: Druschel P, Kaashoek F, Rowstron A (eds) Peer-to-peer systems, vol 2429. Lecture notes in computer science. Springer, New York, pp 306–318

Chen Y, Qiu L, Chen W, Nguyen L, Katz R (2003) Efficient and adaptive web replication using content clustering. IEEE J Sel Areas Commun 21(6):979–994CrossRef

Chu W (1969) Optimal file allocation in a multiple computer system. IEEE Trans Comput C-18(10):885–889

Cidon I, Kutten S, Soffer R (2002) Optimal allocation of electronic content. Comput Netw 40(2):205–218CrossRef

De Reyck B, Herroelen W (1996) On the use of the complexity index as a measure of complexity in activity networks. Eur J Oper Res 91(2):347–366CrossRef

Dilley J, Maggs B, Parikh J, Prokop H, Sitaraman R, Weihl B (2002) Globally distributed content delivery. IEEE Internet Comput 6(5):50–58CrossRef

Dowdy LW, Foster DV (1982) Comparative models of the file assignment problem. ACM Comput Surv 14(2):287–313CrossRef

Frank A, Wittie L, Bernstein A (1985) Multicast communication on network computers. IEEE Softw 2(3):49–61CrossRef

Henderson D, Jacobson S, Johnson A (2003) The theory and practice of simulated annealing. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics (international series in operations research and management science). Springer, New York

Jamin S, Jin C, Jin Y, Raz D, Shavitt Y, Zhang L (2000) On the placement of internet instrumentation. In: 19th annual joint conference of the IEEE computer and communications societies, INFOCOM 2000. Proceedings of the IEEE, vol 1, pp 295–304

Jamin S, Jin C, Kurc A, Raz D, Shavitt Y (2001) Constrained mirror placement on the internet. In: 20th annual joint conference of the IEEE computer and communications societies, INFOCOM 2001. Proceedings of the IEEE, vol 1, pp 31–40

Jeon WJ, Gupta I, Nahrstedt K (2006) Mmc01-6: Qos-aware object replication in overlay networks. In: Global telecommunications conference, GLOBECOM ’06. IEEE, pp 1–5

Jia X, Li D, Hu X, Wu W, Du D (2003) Placement of web-server proxies with consideration of read and update operations on the internet. Comput J 46(4):378–390CrossRef

Kalpakis K, Dasgupta K, Wolfson O (2001) Optimal placement of replicas in trees with read, write, and storage costs. IEEE Trans Parallel Distrib Syst 12(6):628–637CrossRef

Kangasharju J, Roberts J, Ross KW (2002) Object replication strategies in content distribution networks. Comput Commun 25(4):376–383CrossRef

Karlsson M, Karamanolis C (2003) Bounds on the replication cost for QoS. In: Technical report, Hewlett Packard Labs, USA

Karlsson M, Karamanolis C (2004) Choosing replica placement heuristics for wide-area systems. In: Proceedings of the 24th international conference on distributed computing systems, pp 350–359

Karlsson M, Mahalingam M (2002) Do we need replica placement algorithms in content delivery networks. In: 7th international workshop on web content caching and distribution (WCW)

Karp R (1972) Reducibility among combinatorial problems. In: Miller R, Thatcher J (eds) Complexity of computer computations. Plenum Press, London

Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220:671–680CrossRef

Korupolu MR, Plaxton CG, Rajaraman R (2001) Placement algorithms for hierarchical cooperative caching. J Algorithms 38(1):260–302CrossRef

Kou L, Markowsky G, Berman L (1981) A fast algorithm for steiner trees. Acta Informatica 15(2):141–145CrossRef

Krarup J, Pruzan PM (1983) The simple plant location problem: survey and synthesis. Eur J Oper Res 12(1):36–81CrossRef

Krishnan P, Raz D, Shavitt Y (2000) The cache location problem. IEEE/ACM Trans Netw 8(5):568–582CrossRef

Li B, Golin M, Italiano G, Deng X, Sohraby K (1999) On the optimal placement of web proxies in the internet. In: 18th annual joint conference of the IEEE computer and communications societies, INFOCOM ’99. Proceedings of the IEEE, vol 3, pp 1282–1290

Medina A, Lakhina A, Matta I, Byers J (2001) Brite: universal topology generation from a user’s perspective. In: Technical report, Boston University, Boston

Nguyen TV, Safaei F, Boustead P, Tung C (2005) Provisioning overlay distribution networks. Comput Netw 49(1):103–118

Oliveira CA, Pardalos PM, Resende MG (2006) Optimization problems in multicast tree construction. In: Resende MG, Pardalos PM (eds) Handbook of optimization in telecommunications. Springer, New York

Oliveira CAS, Pardalos PM (2005) A survey of combinatorial optimization problems in multicast routing. Comput Oper Res 32(8):1953–1981CrossRef

Pallis G, Vakali A (2006) Insight and perspectives for content delivery networks. Commun ACM 49(1):101–106CrossRef

Pathan M, Buyya R, Vakali A (2008) Content delivery networks: state of the art, insights, and imperatives. In: Buyya R, Pathan M, Vakali A (eds) Content delivery networks. Springer, New York, pp 3–32

Paul S (1998) Multicasting on the internet and its applications. Kluwer Academic Publishers, Norwell

Qiu L, Padmanabhan V, Voelker G (2001) On the placement of web server replicas. In: 20th annual joint conference of the IEEE computer and communications societies, INFOCOM 2001. Proceedings of the IEEE, vol 3, pp 1587–1596

Rabinovich M, Spatschek O (2002) Web caching and replication. Addison-Wesley Longman Publishing Co. Inc., Boston

Radoslavov P, Govindan R, Estrin D (2002) Topology-informed internet replica placement. Comput Commun 25(4):384–392CrossRef

Rahul HS, Kasbekar M, Sitaraman RK, Berger AW (2008) Performance and availability benefits of global overlay routing. In: Buyya R, Pathan M, Vakali A (eds) Content delivery networks. Springer, New York, pp 251–274

Shi S, Turner J (2002) Placing servers in overlay networks. In: Symposium on performance evaluation of computer and telecommunication systems (SPETS)

Tang X, Xu J (2005) QoS-aware replica placement for content distribution. IEEE Trans Parallel Distrib Syst 16(10):921–932CrossRef

Unger O, Cidon I (2004) Optimal content location in multicast based overlay networks with content updates. World Wide Web 7(3):315–336CrossRef

Vakali A, Pallis G (2003) Content delivery networks: status and trends. IEEE Internet Comput 7(6):68–74CrossRef

Verma DC (2002) Content distribution networks: an engineering approach. John Wiley , New York

Voss S (1990) Steiner-Probleme in Graphen. Anton Hain, Germany

Voss S (2006) Steiner tree problems in telecommunications. In: Resende MG, Pardalos PM (eds) Handbook of optimization in telecommunications. Springer, New York, pp 459–492

Waxman B (1988) Routing of multipoint connections. IEEE J Sel Areas Commun 6(9):1617–1622CrossRef

Wittmann R, Zitterbart M (1999) Multicast communication: protocols and applications. Morgan Kaufmann Publishers Inc., Burlington

Wolfson O, Milo A (1991) The multicast policy and its relationship to replicated data placement. ACM Trans Database Syst 16(1):181–205CrossRef

Xu J, Li B, Lee DL (2002) Placement problems for transparent data replication proxy services. IEEE J Sel Areas Commun 20(7):1383–1398CrossRef

Zhang X, Wang W, Tan X, Zhu Y (2003) Data replication at web proxies in content distribution network. In: Zhou X, Orlowska ME, Zhang Y (eds) Web technologies and applications, vol 2642. Lecture notes in computer science. Springer, New York, pp 560–569

Title: The dynamic replica placement problem with service levels in content delivery networks: a model and a simulated annealing heuristic
Authors: Rainer Kolisch
André Dahlmann
Publication date: 01-01-2015
Publisher: Springer Berlin Heidelberg
Published in: OR Spectrum / Issue 1/2015
Print ISSN: 0171-6468
Electronic ISSN: 1436-6304
DOI: https://doi.org/10.1007/s00291-013-0358-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 1/2015

Clustering clinical departments for wards to achieve a prespecified blocking probability

Duality in fuzzy linear programming: a survey

Acknowledgement to Referees

A graph partitioning strategy for solving large-scale crew scheduling problems

Timetabling with passenger routing

Urban public transit network optimization with flexible demand