面向海量流媒体信道资源分配快速Nash议价算法

刘扬; 魏蔚

doi:10.16511/j.cnki.qhdxxb.2017.25.045

PDF(1427 KB)

清华大学学报（自然科学版） ›› 2017, Vol. 57 ›› Issue (10) : 1056-1062. DOI: 10.16511/j.cnki.qhdxxb.2017.25.045

计算机科学与技术

面向海量流媒体信道资源分配快速Nash议价算法

刘扬, 魏蔚

作者信息 +

Fast Nash bargaining algorithm for resource scheduling problems with a large number of media streaming channels

LIU Yang, WEI Wei

Author information +

文章历史 +

摘要

在大规模在线流媒体分发系统中，服务端需处理来自全球各区域的海量用户请求。现有混合云架构不能很好地满足日益增加的动态流媒体内容分发要求，需结合私有数据中心、云和内容分发网络3类平台，充分挖掘各平台的优势以降低费用并提高服务质量。针对基于3种平台的混合云，该文给出了多资源分配问题的描述，将其转化为Nash议价问题，从几何角度获取问题的高效求解算法，并基于实际商用环境中海量流媒体采样数据进行了模拟实验。实验结果表明：相比传统的混合云架构，该算法可显著提升服务质量，在动态和静态内容混合情况下可降低平均约40%的费用，可在包括大量动态流媒体内容场景中进行快速有效的资源分配。

Abstract

The servers in large media streaming systems need to handle a large number of requests from all around the world. However, due to the increasing dynamic media content and because existing cloud-based architectures cannot provide enough benefits, the service provider needs to utilize a hybrid architecture composed of a content delivery network with private and cloud data centers to provide sufficient quality of service while reducing costs. This paper describes a general resource scheduling problem for this scenario for a hybrid cloud, which is then transformed into a Nash bargaining problem. A fast Nash bargaining algorithm is given based on a geometrical perspective of the problem. Tests show that the algorithm improves the quality of service and reduces expenses by about 40% compared with a traditional hybrid architecture, so it can effectively handle large amounts of dynamic media content.

导出引用

刘扬, 魏蔚. 面向海量流媒体信道资源分配快速Nash议价算法[J]. 清华大学学报（自然科学版）. 2017, 57(10): 1056-1062 https://doi.org/10.16511/j.cnki.qhdxxb.2017.25.045

LIU Yang, WEI Wei. Fast Nash bargaining algorithm for resource scheduling problems with a large number of media streaming channels[J]. Journal of Tsinghua University(Science and Technology). 2017, 57(10): 1056-1062 https://doi.org/10.16511/j.cnki.qhdxxb.2017.25.045

中图分类号： TP301.6

参考文献

[1] QIU Xuanjia, LI Hongxing, WU Chuan, et al. Dynamic scaling of VoD services into hybrid clouds with cost minimization and QoS guarantee[C]//Proceedings of the IEEE International Conference on Packet Video Workshop. Piscataway, NJ, USA:IEEE, 2012:137-142.[2] YOU Kun, TANG Bin, QIAN Zhuzhong, et al. QoS-aware placement of stream processing service[J]. The Journal of Supercomputing, 2013, 64(3):919-941.[3] WANG Feng, LIU Jiangchuan, CHEN Minghua. Calms:Cloud assisted live media streaming for globalized demands with time/region diversities[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2012:199-207.[4] WU Yu, WU Chuan, LI Bo, et al. Cloudmedia:When cloud on demand meets video on demand[C]//Proceedings of the IEEE Conference on Distributed Computing Systems. Piscataway, NJ, USA:IEEE, 2011:268-277.[5] DENG Da, LU Zhihui, FANG Wei, et al. Cloud stream media:A cloud assistant global video on demand leasing scheme[C]//Proceedings of the IEEE Conference on Services Computing. Piscataway, NJ, USA:IEEE, 2013:486-493.[6] LI Haitao, ZHONG Lili, LIU Jiangchuan, et al. Cost effective partial migration of VoD services to content clouds[C]//Proceedings of the IEEE Conference on Cloud Computing. Piscataway, NJ, USA:IEEE, 2011:203-210.[7] 黄永锋, 董永强, 张三峰, 等. 数据中心间空闲带宽感知的内容分发算法[J]. 通信学报, 2013, 34(7):24-33. HUANG Yongfeng, DONG Yongqiang, ZHANG Sanfeng, et al. Leftover bandwidth-aware peer selection algorithm for inter-datacenter content distribution[J]. Journal on Communications, 2013, 34(7):24-33. (in Chinese)[8] 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):1012-1022.[9] QIU Xuanjia, LI Hongxing, WU Chuan, et al. Cost-minimizing dynamic migration of content distribution services into hybrid clouds[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2012:2571-2575.[10] CHEN Fangfei, GUO Katherine, LIN John, et al. Intra-cloud lightning:Building CDNs in the cloud[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2012:433-441.[11] 何智聪, 谷光昭, 王新, 等. 基于可重构路由器上缓存的流媒体协作分发策略[J]. 通信学报, 2012, 33(6):82-90. HE Zhicong, GU Guangzhao, WANG Xin, et al. Novel cooperative caching strategies for video streaming distribution based on reconfiguration routers[J]. Journal on Communications, 2012, 33(6):82-90. (in Chinese)[12] 周景才, 张沪寅, 查文亮, 等. 云计算环境下基于用户行为特征的资源分配策略[J]. 计算机研究与发展, 2014, 51(5):1108-1119. ZHOU Jingcai, ZHANG Huyin, CHA Wenliang, et al. User-aware resource provision policy for cloud computing[J]. Journal of Computer Research and Development, 2014, 51(5):1108-1119. (in Chinese)[13] 唐卓, 朱敏, 杨黎, 等. 云环境中面向随机任务的用户效用优化模型[J]. 计算机研究与发展, 2014, 51(5):1120-1128. TANG Zhuo, ZHU Min, YANG Li, et al. Random task-oriented user utility optimization model in the cloud environment[J]. Journal of Computer Research and Development, 2014, 51(5):1120-1128. (in Chinese)[14] TAN B, Massoulie L. Optimal content placement for peer-to-peer video-on-demand systems[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2012:694-702.[15] Nicolas L S, Christoph N, Gilles S T. Cache policies for cloud-based systems:To keep or not to keep[C]//Proceedings of the IEEE Conference on Cloud Computing. Piscataway, NJ, USA:IEEE, 2014:1-8.[16] HUANG Zixia, MEI Cao, LI Li Erran, et al. Cloudstream:Delivering high-quality streaming videos through a cloud-based svc proxy[C]//Proceedings of the IEEE International Conference on Computer Communications. Piscataway, NJ, USA:IEEE, 2011:201-205.[17] Meeyoung C, Haewoon K, Pablo R, et al. I tube, you tube, everybody tubes:Analyzing the world's largest user generated content video system[C]//Proceedings of the ACM Sepecial Interest Group on Data Communication Conference on Internet Measurement. New York, NY, USA:ACM, 2007:1-14.[18] Karlof J K. Integer Programming:Theory and Practice[M]. Boca Raton:CRC Press, 2005.[19] 黄丽亚, 刘臣, 王锁萍. 改进的认知无线电频谱共享博弈模型[J]. 通信学报, 2010, 31(2):136-140. HUANG Liya, LIU Chen, WANG Suoping. Improved spectrum sharing model in cognitive radios based on game theory[J]. Journal on Communications, 2010, 31(2):136-140. (in Chinese)[20] 饶翔, 张顺颐, 孙雁飞, 等. 基于预判与合作博弈的下一代网络资源优化分配方法[J]. 通信学报, 2009, 30(4):60-65. RAO Xiang, ZHANG Shunyi, SUN Yanfei, et al. Next generation network resource allocation method based on cooperative game and decision-making in advance[J]. Journal on Communications, 2009, 30(4):60-65. (in Chinese)[21] Baron R, Durieu J, Haller H, et al. Finding a Nash equilibrium in spatial games is an NP-complete problem[J]. Economic Theory, 2004, 23(2):445-454.[22] Wong K K L. A geometrical perspective for the bargaining problem[J]. Plos One, 2010, 5(4):1-11.

PDF(1427 KB)

Accesses

Citation

Detail

段落导航

收稿日期	出版日期
2016-10-24	2017-10-15
发布日期
2017-10-15

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

访问统计

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

访问统计