云环境下面向跨域作业的调度方法

doi:10.3969/j.issn.0372-2112.2017.10.015

电子学报 ›› 2017, Vol. 45 ›› Issue (10): 2416-2424.DOI: 10.3969/j.issn.0372-2112.2017.10.015

云环境下面向跨域作业的调度方法

李焱¹, 郑亚松¹, 李婧², 朱春鸽¹, 刘欣然¹

1. 国家计算机网络应急技术处理协调中心, 北京 100029;
2. 中国盲文出版社, 北京 100050

收稿日期:2016-04-28 修回日期:2016-10-17 出版日期:2017-10-25
- 作者简介:
- 李焱,男,1984年2月生,湖北随州人.2016年在中国科学院计算技术研究所获工学博士学位.主要研究方向为分布式计算、云计算等.E-mail:liyan@ncic.ac.cn;郑亚松,男,1987年9月生,河南濮阳人.2014年在中国科学院计算技术研究所获工学博士学位.现在国家互联网应急中心工作,主要研究方向为大数据分析.E-mail:zys_2009@163.com
- 基金资助:
- 国家自然科学基金 (No.61402464，No.61602467）

A Scheduling Strategy for Jobs Across Geo-Distributed Datacenters in Cloud Computing

LI Yan¹, ZHENG Ya-song¹, LI Jing², ZHU Chun-ge¹, LIU Xin-ran¹

1. National Computer Network Emergency Response Technical Coordination Center, Beijing 100029, China;
2. China Braille Press, Beijing 100050, China

Received:2016-04-28 Revised:2016-10-17 Online:2017-10-25 Published:2017-10-25

摘要/Abstract

摘要： 云环境下，因数据局部性或是任务对资源的特殊偏好，一个作业所包含的任务往往需要在不同的数据中心局点上运行，此类作业称为跨域作业.跨域作业的完成时间取决于最慢任务的执行效率，即存在木桶效应.针对各域资源能力异构条件下不合理的调度策略导致跨域作业执行时间跨度过长的问题，本文提出一种面向跨域作业的启发式调度方法MIN-Max-Min，优先选择期望完成时间最短的作业执行.通过实验表明，与先来先服务的策略相比，该方法能将跨域作业平均执行时间跨度减少40%以上.

关键词: 云计算, 跨域数据中心, 跨域作业

Abstract: In cloud computing,tasks in a job often need to run on different datacenters due to the input data locality or special preference for resources,that is,the job runs across geo-distributed sites.The different tasks in a job have to be scheduled in different domain (data center) to execute for their personalization requirements,so the job completion time depends on the slowest task,which is called "barrel effect".As geo-distributed scheduling strategy without regard to heterogeneous resources leads too long execution time span,this dissertation proposes an optimization strategy for geo-distributed scheduling named MIN-Max-Min.The strategy gives priority to select the expectation shortest completion job to execute by heuristic rule.Experiments show that compared with first come first service strategy,the strategy can reduce cross domain average execution time span to less than 40% under the simulation load.

Key words: cloud computing, geo-distributed data centers, jobs across geo-distributed data centers

中图分类号:

TP393

李焱, 郑亚松, 李婧, 朱春鸽, 刘欣然. 云环境下面向跨域作业的调度方法[J]. 电子学报, 2017, 45(10): 2416-2424.

LI Yan, ZHENG Ya-song, LI Jing, ZHU Chun-ge, LIU Xin-ran. A Scheduling Strategy for Jobs Across Geo-Distributed Datacenters in Cloud Computing[J]. Acta Electronica Sinica, 2017, 45(10): 2416-2424.

参考文献

[1] ZAHARIA M,CHOWDHURY M,FRANKLIN M J,et al.Spark:Cluster computing with working sets[J].HotCloud,2010,10:10-10.
[2] ISARD M,BUDIU M,YU Y,et al.Dryad:Distributed data-parallel programs from sequential building blocks[J].ACM SIGOPS Operating Systems Review,2007,41(3):59-72.
[3] HUNG C C,GOLUBCHIK L,YU M.Scheduling jobs across geo-distributed datacenters[A].Proceedings of the Sixth ACM Symposium on Cloud Computing[C].USA:ACM,2015.111-124.
[4] VULIMIRI A,CURINO C,GODFREY P B,et al.Global analytics in the face of bandwidth and regulatory constraints[A].The 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15)[C].USA:USENIX,2015.323-336.
[5] VULIMIRI A,CURINO C,GODFREY B,et al.WANalytics:Analytics for a geo-distributed data-intensive world[A].Proceedings of CIDR[C].USA:ACM,2015.27353635.
[6] HAJJAT M,MALTZ D,RAO S,et al.Dealer:application-aware request splitting for interactive cloud applications[A].Proceedings of the 8th International Conference on Emerging Networking Experiments and Technologies[C].USA:ACM,2012.157-168.
[7] Zhou A,Wang S,Zheng Z,Hsu C,Lyu M,Yang F.On cloud service reliability enhancement with optimal resource usage[J].IEEE Transactions on Cloud Computing,DOI:10.1109/tcc.2014.2369421.
[8] 俞能海,郝卓,徐甲甲,张卫明,张驰.云安全研究进展综述[J].电子学报,2013,41(2):371-381. YU Neng-hai,HAO Zhuo,XU Jia-jia,ZHANG Wei-ming,ZHANG Chi.Review of cloud computing security[J].Acta Electronica Sinica,2013,41(2):371-381.(in Chinese)
[9] LI Y,ZHANG H,WANG Y,et al.A Scheduling framework for periodic tasks in geo-distributed data centers[A].IEEE Symposium on Service-Oriented System Engineering (SOSE)[C].USA:IEEE,2015.247-252.
[10] 童钊,肖正,李肯立.分布式系统中多用户网络应用的概率型调度算法研究[J].电子学报,2016,44(7):1679-1688. TONG Zhao,XIAO Zheng,LI Ken-li.A queueing model and probabilistic scheduling for multi-user network applications[J].Acta Electronica Sinica,2016,44(7):1679-1688.(in Chinese)
[11] SCHWARZKOPF M,KONWINSKI A,ABD-EL-MALEK M,et al.Omega:flexible,scalable schedulers for large compute clusters[A].Proceedings of the 8th ACM European Conference on Computer Systems[C].USA:ACM,2013.351-364.
[12] OUSTERHOUT K,WENDELL P,ZAHARIA M,et al.Sparrow:distributed,low latency scheduling[A].Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles[C].USA:ACM,2013.69-84.
[13] 谭一鸣,曾国荪,王伟.随机任务在云计算平台中能耗的优化管理方法[J].软件学报,2012,23(2):266-278. TAN YM,ZENG GS,WANG W.Policy of energy optimal management for cloud computing platform with stochastic tasks[J].Journal of Software,2012,23(2):266-278.(in Chinese)
[14] JOE-WONG C,SEN S,LAN T,et al.Multiresource allocation:Fairness-efficiency tradeoffs in a unifying framework[J].IEEE/ACM Transactions on Networking (TON),2013,21(6):1785-1798.
[15] KIM K H,BELOGLAZOV A,BUYYA R.Power-aware provisioning of cloud resources for real-time services[A].Proceedings of the 7th International Workshop on Middleware for Grids,Clouds and e-Science[C].USA:ACM,2009.1.
[16] 陶晓玲,韦毅,王勇.一种基于分层多代理的云计算负载均衡方法[J].电子学报,2016,44(9):2106-2113. TAO Xiao-ling,WEI Yi,WANG Yong.A load balancing method based on hierarchy and multi-agent for cloud computing platform[J].Acta Electronica Sinica,2016,44(9):2106-2113.(in Chinese)
[17] MAHESWARAN M,ALI S,SIEGAL H J,et al.Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems[A].Proceedings of Heterogeneous Computing Workshop(HCW'99)(Eighth)[C].USA:IEEE,1999.30-44.
[18] CALHEIROS R N,RANJAN R,BELOGLAZOV A,et al.CloudSim:A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software:Practice and Experience,2011,41(1):23-50.

云环境下面向跨域作业的调度方法

A Scheduling Strategy for Jobs Across Geo-Distributed Datacenters in Cloud Computing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	罗智勇, 朱梓豪, 谢志强, 孙广路. 面向云计算的花朵差分授粉工作流多目标优化算法研究[J]. 电子学报, 2021, 49(3): 470-476.
[2]	李航, 冯朝胜, 刘帅南, 刘彬, 赵开强. 支持离线/在线加密及可验证外包解密的CP-WABE方案[J]. 电子学报, 2020, 48(11): 2146-2153.
[3]	卢晶, 段勇, 刘海波. 基于z值的分布式密度峰值聚类算法[J]. 电子学报, 2018, 46(3): 730-738.
[4]	王于丁, 杨家海. DACPCC:一种包含访问权限的云计算数据访问控制方案[J]. 电子学报, 2018, 46(1): 236-244.
[5]	丁嘉宁, 张鹏, 杨嵘, 刘俊朋, 刘庆云, 熊刚. 支持多租户的网络测试床模拟流量标记和溯源模型[J]. 电子学报, 2017, 45(8): 1947-1956.
[6]	杜思军, 徐尚书, 刘俊南, 张俊伟, 马建峰. 云计算中抗共谋攻击的数据位置验证协议[J]. 电子学报, 2017, 45(6): 1321-1326.
[7]	陈振华, 李顺东, 王道顺, 黄琼, 张卫国. 集合成员关系的安全多方计算及其应用[J]. 电子学报, 2017, 45(5): 1109-1116.
[8]	陶晓玲, 韦毅, 王勇. 一种基于分层多代理的云计算负载均衡方法[J]. 电子学报, 2016, 44(9): 2106-2113.
[9]	陈凯, 许海铭, 徐震, 林东岱, 刘勇. 适用于移动云计算的抗中间人攻击的SSP方案[J]. 电子学报, 2016, 44(8): 1806-1813.
[10]	梁俊杰, 李凤华, 刘琼妮, 尹利. MapReduce框架下的优化高维索引与KNN查询[J]. 电子学报, 2016, 44(8): 1873-1880.
[11]	肖鹏, 刘洞波, 屈喜龙. 云计算中基于能耗比例模型的虚拟机调度算法[J]. 电子学报, 2015, 43(2): 305-311.
[12]	冯朝胜, 秦志光, 袁丁, 卿昱. 云计算环境下访问控制关键技术[J]. 电子学报, 2015, 43(2): 312-319.
[13]	匡桂娟, 曾国荪, 曹洁, 熊焕亮. 基于图匹配理论的云任务与云资源满意“婚配”方法[J]. 电子学报, 2014, 42(8): 1582-1586.
[14]	李德毅, 张天雷, 黄立威. 位置服务：接地气的云计算[J]. 电子学报, 2014, 42(4): 786-790.
[15]	陈丹伟, 邵菊, 樊晓唯, 陈林铃, 何利文. 基于MAH-ABE的云计算隐私保护访问控制[J]. 电子学报, 2014, 42(4): 821-827.