一种基于云存储的CDN视频副本部署策略

doi:10.3969/j.issn.0253-2778.2014.07.003

中国科学技术大学学报 ›› 2014, Vol. 44 ›› Issue (7): 554-562.DOI: 10.3969/j.issn.0253-2778.2014.07.003

一种基于云存储的CDN视频副本部署策略

姚士佳，朱明，崔昊旻

中国科学技术大学自动化系，安徽合肥 230027

收稿日期:2013-10-11 修回日期:2014-04-29 接受日期:2014-04-29 出版日期:2023-05-11 发布日期:2014-04-29
通讯作者: 朱明
作者简介:姚士佳，男，1985年生，博士生. 研究方向：云存储. E-mail: yaosj@mail.ustc.edu.cn
基金资助:
中国科学院先导专项(XDA06030900),国家科技支撑计划(2012BAH73F01)资助.

A novel video replica placement strategy for storage cloud-based CDN

YAO Shijia, ZHU Ming, CUI Haoming

Department of Automation, University of Science and Technology of China, Hefei 230027, China

Received:2013-10-11 Revised:2014-04-29 Accepted:2014-04-29 Online:2023-05-11 Published:2014-04-29

摘要/Abstract

摘要： 在线视频服务无法离开CDN（content delivery network）的支持.与传统CDN相比，使用云存储节点作为CDN的节点对视频内容进行分发可以节省大量运营费用.在线视频服务的内容文件要尽量预先部署到离用户较近的边缘节点上，以保证用户的QoS（quality of service）.现有的GS (greedy site)内容预部署算法在有历史记录的前提下，有着较小的货币开销，且能满足QoS需求.然而，GS算法会导致云存储节点的负载均衡情况较差.为此，提出了一种称为GUCP（greedy user core preallocation）的部署算法，该算法利用k-means算法将负载过重节点上的用户分配到负载较轻的节点以平衡负载，解决GS算法在负载均衡方面存在的不足.实验表明，GUCP算法在系统使用费用、QoS性能方面与GS算法十分接近，在负载均衡性能上远远优于GS算法.

关键词: 云存储, CDN, 副本部署, 负载均衡

Abstract: Online video service needs the support of CDN (content delivery network) which can be costly. Using cloud storage nodes to deliver video content can help solve the problem. To guarantee the users QoS, CDN should pre-deploy the content files of online video service to the edge nodes which are close to the users. The existing GS (greedy site) placement algorithm can satisfy the QoS requirements at a relatively smaller cost when the historical log is provided. However, the GS algorithm will result in bad load balance among cloud storage nodes. A novel replica placement algorithm named GUCP (greedy user core preallocation) was proposed to solve this problem. The algorithm assigned users on overloaded nodes to lightly-loaded ones using the k-means algorithm, in order to balance the load. The numerical experimental results show that the cost and QoS performance of GUCP are very close to those of GS, while its performance of load balance is much better than that of GS.

Key words: cloud storage, CDN, replica placement, load balance

中图分类号:

TP39

姚士佳，朱明，崔昊旻. 一种基于云存储的CDN视频副本部署策略[J]. 中国科学技术大学学报, 2014, 44(7): 554-562.

YAO Shijia, ZHU Ming, CUI Haoming. A novel video replica placement strategy for storage cloud-based CDN[J]. Journal of University of Science and Technology of China, 2014, 44(7): 554-562.

参考文献

［1］ Rayburn D. Content delivery networking pricing, costs for outsourced video delivery［EB/OL］. http://www.scribemedia.org/2007/12/12/cdn-pricing-video/.
［2］ Elson J, Howell J. Handling flash crowds from your garage［C］// Proceedings of the USENIX Annual Technical Conference. Santa Clara, USA: USENIX Association, 2008: 171-184.
［3］ Gottfrid D. Self-service, prorated super computing fun!［EB/OL］. http://open.blogs.nytimes.com/2007/11/01/self-service-prorated-super-com-putting-fun(0).
［4］ MacAskill D. Scalability: Set Amazons servers on fire, not yours［EB/OL］. hhttp:// blogs.smugmug.com/don/files/ETech-SmugMug-Amazon-2007.pdfi (0).
［5］ Broberg J, Buyya R, Tari Z. MetaCDN: Harnessing storage clouds for high performance content delivery［J］. Journal of Network and Computer Applications, 2009, 32(5): 1 012-1 022.
［6］ Li B, Golin M J, Italiano G F, et al. On the optimal placement of web proxies in the internet［C］// Proceedings of the 8th Annual Joint Conference of the IEEE Computer and Communications Societies. IEEEPress, 1999, 3: 1 282-1 290.
［7］ Krishnan P, Raz D, Shavitt Y. The cache location problem［J］. IEEE/ACM Transactions on Networking, 2000, 8(5): 568-582.
［8］ Qiu L, Padmanabhan V N, Voelker G M. On the placement of web server replicas［C］// Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies. Anchorage, USA: IEEE Press, 2001: 1 587-1 596.
［9］ Radoslavov P, Govindan R, Estrin D. Topology-informed internet replica placement［J］. Computer Communications, 2002, 25(4): 384-392.
［10］ Cronin E, Jamin S, Cheng J, et al. Constrained mirror placement on the internet［J］. IEEE Journal on Selected Areas in Communications, 2002, 20(7): 1 369-1 382.
［11］ Xu J, Li B, Lee D L. Placement problems for transparent data replication proxy services［J］. IEEE Journal on Selected Areas in Communications, 2002, 20(7): 1 383-1 398.
［12］ Jia X, Li D, Hu X, et al. Placement of web-server proxies with consideration of read and update operations on the internet［J］. The Computer Journal, 2003, 46(4): 378-390.
［13］ Cidon I, Kutten S, Soffer R. Optimal allocation of electronic content［C］// Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies. Anchorage, USA: IEEE Press, 2001, 3: 1 773-1 780.
［14］ Kalpakis K, Dasgupta K, Wolfson O. Optimal placement of replicas in trees with read, write, and storage costs［J］. IEEE Transactions on Parallel and Distributed Systems, 2001, 12(6): 628-637.
［15］ Tang X Y, Xu J L. QoS-aware replica placement for content distribution［J］. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(10): 921-932.
［16］ Wang H, Liu P, Wu J J. A QoS-aware heuristic algorithm for replica placement［C］// Proceedings of the 7th IEEE/ACM International Conference on Grid Computing. Bacelona, Spain: IEEE Computer Society, 2006: 96-103.
［17］ Rodolakis G, Siachalou S, Georgiadis L. Replicated server placement with QoS constraints［J］. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(10): 1 151-1 162.
［18］ He J, Wu D, Zeng Y P, et al. Towards optimal deployment of cloud-assisted video distribution services［J］. IEEE Transactions on Circuit and System for Video Technologies, 2013, 23(10): 1 717-1 728.
［19］ Zhu W, Luo C, Wang J, et al. Multimedia cloud computing: Directions and applications［J］. Signal Processing Magazine, 2011, 28(3): 59-69.
［20］ Wu Y, Wu C, Li B, et al. CloudMedia: When cloud on demand meets video on demand［C］// Proceedings of the 31st International Conference on Distributed Computing Systems. Minneapolis, USA: IEEE Press, 2011: 268-277.
［21］ Li H T, Zhong L L, Liu J C, et al. Cost-effective partial migration of VoD services to content clouds［C］// Proceedings of the International Conference on Cloud Computing. Washington, USA: IEEE Press, 2011: 203-210.
［22］ Wang F, Liu J C, Chen M H. CALMS: Cloud-assisted live media streaming for globalized demands with time/region diversities［C］// Proceedings IEEE INFOCOM. Orlando, USA: IEEE Press, 2012: 199-207.
［23］ Chen F F, Guo K, Lin J, et al. Intra-cloud lightning: Building CDNs in the cloud［C］// Proceedings IEEE INFOCOM. Orlando, USA: IEEE Press, 2012: 433-441.
［24］郭成城, 晏蒲柳. 一种异构 Web 服务器集群动态负载均衡算法［J］. 计算机学报, 2005, 28(2): 179-184.
［25］ Godfrey B, Lakshminarayanan K, Surana S, et al. Load balancing in dynamic structured P2P systems［C］// Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kang, China: IEEE Press, 2004, 4: 2 253-2 262.

（上接第553页）

［11］ Gkoulalas-Divanis A, Verykios V S, Mokbel M F. Identifying unsafe routes for network-based trajectory privacy［C］// Proceedings of the SIAM International Conference on Data Mining. Sparks, USA: SIAM Press, 2009: 942-953.
［12］ Chow C Y, Mokbel M F, Liu X. A peer-to-peer spatial cloaking algorithm for anonymous location-based service［C］// Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems. New York: ACM Press, 2006: 171-178.
［13］ Chow C Y, Mokbel M F. Enabling private continuous queries for revealed user locations［C］// Proceedings of the 10th International Symposium on Advances in Spatial and Temporal Databases. Boston, USA: Springer, 2007: 258-273.
［14］ Ghinita G, Kalnis P, Skiadopoulos S. MobiHide: A mobile peer-to-peer system for location-based queries［C］// Proceedings of the 10th International Symposium on Advances in Spatial and Temporal Databases. Boston, USA: Springer, 2007, 221-238.
［15］ Gkoulalas-Divanis A, Verykios V S. A free terrain model for trajectory k-anonymity［C］// Proceedings of the 19th International Conference on Database and Expert Systems Applications. Turin, Italy: Springer, 2008: 49-56.
［16］ Mokbel M F, Chow C Y, Aref W G. The new Casper: Query processing for location services without compromising privacy［C］// Proceedings of the 32nd International Conference on Very Large Data Bases. Seoul, Korea: ACM Press, 2006: 763-774.
［17］ Gedik B, Liu L. Location privacy in mobile systems: A personalized anonymization model［C］// Proceedings of the 25th International Conference on Distributed Computing Systems. Columbus, USA: IEEE Press, 2005, 620-629.
［18］ Pan X, Xu Ji L, Meng X F. Protecting location privacy against location-dependent attacks in mobile services［J］. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(8): 1 506-1 519.
［19］潘晓，郝兴，孟小峰.基于位置服务中的连续查询隐私保护研究［J］.计算机研究与发展,2010,47(1): 121-129.
［20］杨晓春,王雅哲,王斌,等.数据发布中面向多敏感属性的隐私保护方法［J］.计算机学报,2008,31(4): 574-586.

[1]	凌华泽, 薛开平, Wei David S.L., 李睿栋. 多用户场景支持多关键词模糊搜索的可搜索加密方案[J]. 中国科学技术大学学报, 2021, 51(7): 562-576.
[2]	李华康，刘盼，杨一涛，孙国梓. 一种基于节点映射关系的云数据安全代理访问机制[J]. 中国科学技术大学学报, 2017, 47(4): 304-310.
[3]	殷超，王健宗，吕海涛，崔宗敏，程良伦，李同芳，刘妍. BDCode: 一种面向大数据存储系统的纠删码算法[J]. 中国科学技术大学学报, 2016, 46(3): 188-199.
[4]	徐爱萍，吴笛，徐武平，陈军. 实时多任务异构云计算平台负载均衡算法[J]. 中国科学技术大学学报, 2016, 46(3): 215-221.
[5]	张旭东，邵晓丽，张远旭，张华堂，何有文. 树鼩PD-1基因的分离、鉴定及表达分析[J]. 中国科学技术大学学报, 2009, 39(7): 714-721.

一种基于云存储的CDN视频副本部署策略

A novel video replica placement strategy for storage cloud-based CDN

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价