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

LIU Yang; WEI Wei

doi:10.16511/j.cnki.qhdxxb.2017.25.045

PDF(1427 KB)

Journal of Tsinghua University(Science and Technology) ›› 2017, Vol. 57 ›› Issue (10) : 1056-1062. DOI: 10.16511/j.cnki.qhdxxb.2017.25.045

COMPUTER SCIENCE AND TECHNOLOGY

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

{{article.zuoZhe_EN}}

Author information +

History +

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.

Key words

streaming media / cloud computing / hybrid cloud / resource scheduling / Nash bargaining

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

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

References

[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.