Heuristic Replica Placement Algorithms in Content Distribution Networks

doi:10.4304/jnw.6.3.416-423

Journal of Networks, Vol 6, No 3 (2011), 416-423, Mar 2011

doi:10.4304/jnw.6.3.416-423

Heuristic Replica Placement Algorithms in Content Distribution Networks

Jing Sun, Suixiang Gao, Wenguo Yang, Zhipeng Jiang

Abstract

Content Distribution Networks have been attracted a great deal of attraction in recent years. Replica placement problems (RPPs) as one of the key technologies in the Content Distribution Networks have been widely studied. In this paper, we propose an optimization model with server storage capacity constraints for the RPPs. Furthermore, part of the objective function is represented as a Multiple Minimum Cost Flow Model for the first time. Efficient algorithms are designed to minimize the total network cost. The algorithms include three parts: replication algorithm preprocess, constraint P-median model and algorithm of solving constraint P-median models. Correctness of the algorithms is proved by two theorems. In the simulation, we compare our algorithms to other heuristic methods numerically. The results show that our algorithms perform better with less cost. Future work should be concentrated on the more meticulous models with other resources constraints of the RPPs.

Keywords

Content Distribution Networks;Replica Placement Algorithm; P-median Model

References

[1] Akamai, http://www.akamai.com.

[2] Digital Island, http://www.digitalisland.com.

[3] Mengkun Yang and Zongming Fei, “A Model for Replica Placement in Content Distribution Networks for Multimedia Applications”, IEEE International Conference on Communications (ICC’03), vol. 1, pp. 557-561, May 2003.

[4] Lili Qiu and V. N. Padmanabhan, “On the Placement of Web Server Replicas”, in Proceedings of INFOCOM’01, vol. 3, pp. 1587-1596, April 2001.

[5] Zhiyong Xu and Laxmi Bhuyan, “Qos-Aware Object Replica Placement in CDNs”, in Proceedings of IEEE GLOBECOM’05, vol. 2, pp. 862-866, Dec. 2005.

[6] J. Kangasharjum, James Roberts, “Object Replication Strategies in Content Distribution Networks”, Computer Communications, vol. 25, Issue 4, pp. 376-383, March 2002.
doi:10.1016/S0140-3664(01)00409-1

[7] F. L. Presti and N. Bartolini, “Dynamic Replica Placement and User Request Redirection in Content Delivery Networks”, IEEE International Conference on Communications (ICC’05), vol. 3, pp. 1495-1501, May 2005.

[8] F. L. Presti and C. Petrioli, “Distributed Dynamic Replica Placement and Request Redirection in Content Delivery Networks”, 15th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS ’07), pp. 366-373, Oct. 2007.
doi:10.1109/MASCOTS.2007.19

[9] S. U. Khan, “Robust CDN Replica Placement Techniques”, IEEE International Symposium on Parallel and Distributed Processing, pp. 1-8, May 2009.
doi:10.1109/IPDPS.2009.5160908
PMCid:2691805

[10] I. Cidon, S. Kutten, “Optimal Allocation of Electronic Content”, in Proceedings of IEEE INFOCOM’01, pp. 1773-1780, April 2001.

[11] Xueyan Tang and Jianliang Xu, “On Replica Placement for QoS-Aware Content Distribution”, INFOCOM’04, vol. 2, pp. 806-815, March 2004.

[12] Limin Wang, V. Pai and L. Peterson, “The Effectiveness of Request Redirection on CDN Robustness”, ACM SIGOPS Operating Systems Review, Volume 36, Issue SI, 2002.

[13] Zhiruo Cao, Zheng Wang and Ellen Zegura, “Performance of Hashing-Based Schemes for Internet Load Balancing”, in Proceeding of IEEE INFOCOM'00, 2000.

[14] V. Cardellini, M. Colajanni, and P. Yu, “Redirection Algorithms for Load Sharing in Distributed Web Server Systems”, in Proceeding of IEEE 19th International Conference on Distributed Computing Systems, 1999.

[15] P. Yu and D. M. Dias, “Analysis of Task Assignment Policies in Scalable Distributed Web-server Systems”, IEEE Transaction on Parallel and Distributed Systems, June, 1998.

Full Text: PDF

Journal of Networks (JNW, ISSN 1796-2056)

Username
Password
Remember me