Open Access Open Access  Restricted Access Subscription or Fee Access

A Survey on Data Replication Methods in Content Delivery Networks

Shahram Jamali, Hadi Zare Fatin

Abstract


The Content Delivery Networks (CDN) host the rich and bandwidth consuming content of an organization and process the requests of clients and deliver the content for them. With the extension of these networks and also distributive nature of the resources on them, it is necessary to ensure the desired quality of service for users of these networks. One of the important requirements of maintaining quality of access over the content delivery networks is to utilize an efficient data replication algorithm. This brief review, first explains the necessity of using data replication over the CDN networks and then discusses the challenges exist in this process. The paper then describes the popular replication methods in Content Delivery Networks. The heuristic method as an effective algorithm for data replication is also presented.

Keywords


Content Delivery Network, Data Replication, Heuristic Algorithm

Full Text:

PDF

References


Akamai, http://www.akamai.com.

Digital Island, http://www.digitalisland.com.

P.B. Mirchandani, R.L. Francis, “Discrete Location Theory”, Wiley, 1990.

Y. Bartal, “Probabilistic approximation of metric spaces and its algorithmic applications”, in: FOCS ’96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC,USA, 1996, p. 184.

M. Karlsson, C. Karamanolis, “Choosing replica placement heuristics for wide-area systems”, in: ICDCS ’04: Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS’04), IEEE Computer Society,Washington, DC, USA, 2004, pp. 350–359.

V. Vazirani, “Approximation Algorithms, Springer”-Verlag, 2001.

S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, L. Zhang, “On the placement of internet instrumentation”, vol. 1, 2000, pp. 295–304, doi:10.1109/INFCOM.2000.832199.

P. Krishnan, D. Raz, Y. Shavitt,The cache location problem”, IEEE/ACM Transactions on Networking 8 (5) (2000) 568–582, doi:10.1109/90.879344.

L. Qiu, V. Padmanabhan, G. Voelker, “On the placement of web server replicas” 3 (2001) 1587–1596, doi:10.1109/INFCOM.2001.916655.

E. Cronin, S. Jamin, C. Jin, A. Kurc, D. Raz, Y. Shavitt, ‘Constrained mirror placement on the internet, selected areas in communications”, IEEE Journal 20 (7) (2002) 1369–1382, doi:10.1109/JSAC.2002.802066.

Y. Chen, R.H. Katz, J. Kubiatowicz, “Dynamic replica placement for scalable content delivery”, in: IPTPS ’01: Revised Papers from the First International Workshop on Peer-to-Peer Systems, Springer-Verlag, London, UK, 2002, pp.306–318.

M. Szymaniak, G. Pierre, M. van Steen, “Latency-driven replica placement”, in: 2005. Proceedings of the Symposium on Applications and the Internet, 2005, pp. 399–405. doi:10.1109/SAINT.2005.37.

P. Radoslavov, R. Govindan, D. Estrin, “Topology-informed internet replica placement”, Computer Communications 25 (4) (2002) 384–392.

Y. Chen, L. Qiu, W. Chen, L. Nguyen, R. Katz, “Efficient and adaptive web replication using content clustering”, IEEE Journal on Selected Areas in Communications 21 (6) (2003) 979–994, doi:10.1109/JSAC.2003.814608.

N. Fujita, Y. Ishikawa, A. Iwata, R. Izmailov, “Coarse-grain replica management strategies for dynamic replication of web contents”, Computer Networks 45 (1) (2004) 19–34. http://dx.doi.org/10.1016/j.comnet.2004.02.006.

A. Sidiropoulos, G. Pallis, D. Katsaros, K. Stamos, A. Vakali, Y. Manolopoulos, “Prefetching in content distribution networks via web communities identification and outsourcing”, World Wide Web 11 (1) (2008) 39–70. http://dx.doi.org/10.1007/s11280-007-0027-8.

G. Pallis, A. Vakali, “Insight and perspectives for content delivery networks”, Communications of the ACM 49 (1) (2006) 101–106. http://doi.acm.org/10.1145/1107458.1107462.

M. Pathan, R. Buyya, “A Taxonomy of CDNs, First ed.”, Springer-Verlag, R. Buyya,M. Pathan, A. Vakali (Eds.), 2008, (Chapter 2), .

A. Leff, J. Wolf, P. Yu, “Replication algorithms in a remote caching architecture”, IEEE Transactions on Parallel and Distributed Systems 4 (11) (1993) 1185–1204, doi:10.1109/71.250099.

I. Cidon, S. Kutten, R. Soffer, “Optimal allocation of electronic content”, INFOCOM 2001, Proceedings of Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, IEEE, 2001, pp. 1773–1780, doi:10.1109/INFCOM.2001.916675.

K. Kalpakis, K. Dasgupta, O. Wolfson, “Optimal placement of replicas in trees with read, write, and storage costs”, IEEE Transactions on Parallel and Distributed Computing. 12 (6) (2001) 628–637. http://dx.doi.org/10.1109/71.932716.

S.S.H. Tse, “Approximate algorithms for document placement in distributed web servers”, IEEE Transactions on Parallel and Distributed Computing. 16 (6) (2005) 489–496. http://dx.doi.org/10.1109/TPDS.2005.63.

M.R. Korupolu, C.G. Plaxton, R. Rajaraman, “Placement algorithms for hierarchical cooperative caching, in”: SODA ’99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999, pp. 586–595.

I.D. Baev, R. Rajaraman, “Approximation algorithms for data placement inarbitrary networks”, in: SODA ’01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001, pp. 661–670.

T. Loukopoulos, I. Ahmad, “Static and adaptive distributed data replication using genetic algorithms”, Journal of Parallel and Distributed Computing 64 (11) (2004) 1270–1285. http://dx.doi.org/10.1016/j.jpdc.2004.04.005.

M. Yang, Z. Fei, “A model for replica placement in content distribution networks for multimedia applications”, in: IEEE International Conference on Communications, 2003. ICC ’03, vol. 1, 2003, pp. 557–561, doi:10.1109/ICC.2003.1204238.

H. Yu, A. Vahdat, “Minimal replication cost for availability”, in: PODC ’02: Proceedings of the twenty-first annual symposium on Principles of distributed computing, ACM, New York, NY, USA, 2002, pp. 98–107. http://doi.acm.org/10.1145/571825.571839.

L. Zhuo, C.-L. Wang, F.C.M. Lau, “Load balancing in distributed web server systems with partial document replication”, in: ICPP ’02: Proceedings of the 2002 International Conference on Parallel Processing, IEEE Computer Society, Washington, DC, USA, 2002, p. 305.

B.-J. Ko, D. Rubenstein, “Distributed self-stabilizing placement of replicated resources in emerging networks”, IEEE/ACM Transactions on Networking 13 (3) (2005) 476–487. http://dx.doi.org/10.1109/TNET.2005.850196.

J. Kangasharju, K.W. Ross, J.W. Roberts, “Performance evaluation of redirection schemes in content distribution networks”, Computer Communications 24 (2) (2001) 207–214.

G. Pallis, A. Vakali, K. Stamos, A. Sidiropoulos, D. Katsaros, Y. Manolopoulos, “A latency-based object placement approach in content distribution networks”, 2005, p. 8, doi:10.1109/LAWEB.2005.3.

G. Pallis, K. Stamos, A. Vakali, D. Katsaros, A. Sidiropoulos, “Replication based on objects load under a content distribution network”, in: ICDEW ’06:Proceedings of the 22nd International Conference on Data Engineering Workshops, IEEE Computer Society, Washington, DC, USA, 2006, p. 53.http://dx.doi.org/10.1109/ICDEW.2006.127.

X. Tang, J. Xu, “Qos-aware replica placement for content distribution”, IEEE Transactions on Parallel and Distributed Systems 16 (10) (2005) 921–932, doi:10.1109/TPDS.2005.126.

N. Laoutaris, V. Zissimopoulos, I. Stavrakakis, “On the optimization of storage capacity allocation for content distribution”, Computer Networks 47 (2005) 409–428.

J. Xu, B. Li, D.L. Lee, “Placement problems for transparent data replication proxy services”, IEEE Journal on Selected Areas in Communications 20 (7) (2002) 1383–1398, doi:10.1109/JSAC.2002.802068.

X. Zhang, W. Wang, X. Tan, Y. Zhu, “Data replication at web proxies in content distribution network”, in: LNCS 2642: Web Technologies and Applications, Springer-Verlag, 2003.

T. Bektas, O. Oguz, I. Ouveysi, “Designing cost-effective content distribution networks”, Computers and Operations Research 34 (8) (2007) 2436–2449. http://dx.doi.org/10.1016/j.cor.2005.09.013.

T. Bektas , J.-F. Cordeau, E. Erkut, G. Laporte, “Exact algorithms for the joint object placement and request routing problem in content distribution networks”, Computers and Operations Research 35 (12) (2008) 3860–3884. http://dx.doi.org/10.1016/j.cor.2007.02.005.

N. Laoutaris, V. Zissimopoulos, I. Stavrakakis, “Joint object placement and node dimensioning for internet content distribution”, Information Processing Letters 89 (6) (2004) 273–279. http://dx.doi.org/10.1016/j.ipl.2003.12.002.

T. Bektas, J.-F. Cordeau, E. Erkut, G. Laporte, “A two-level simulated annealing algorithm for efficient dissemination of electronic content”, Journal of the Operational Research Society 59 (2008) 1557–1567.

P. Venkatesh, S.N. Sivanandam, R. Venkatesan, “A review of consistency mechanisms for qos aware content distribution networks”, Academic Open Internet Journal 14 (2005).

X. Tang, H. Chi, S.T. Chanson, “Optimal replica placement under ttl-based consistency”, IEEE Transactions on Parallel and Distributed Computing 18 (3) (2007) 351–363. http://dx.doi.org/10.1109/TPDS.2007.47.

Peng L, Debin G, Michael K. “Replica Placement for Availability in the Worst Case”. 35th International Conference on Distributed Computing Systems, IEEE. pp 597-608(2015).

Keiichi Endo, Ryosuke Hamabe, Dai Okano, Kaname Amano. “An Effective Replication Technique Using Rateless Codes for Unstructured P2P Networks”; Journal of Communications, VOL. 7, NO. 4(2012).

Jan Schaffner, Dean Jacobs, Tim Kraska, Hasso Plattner. “The Multi-Tenant Data Placement Problem”; DBKDA: The Fourth International Conference on Advances in Databases, Knowledge, and Data Applications (2012)

X. Tang, S.T. Chanson, “Analysis of replica placement under expiration-based consistency management”, IEEE Transactions on Parallel and Distributed Computing. 17 (11) (2006) 1253–1263. http://dx.doi.org/10.1109/TPDS.2006.147.

X. Jia, D. Li, H. Du, J. Cao, “On optimal replication of data object at hierarchical and transparent web proxies”, IEEE Transactions on Parallel and Distributed Computing. 16 (8) (2005) 673–685. http://dx.doi.org/10.1109/TPDS.2005.94.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.