大规模云计算服务器优化调度问题的最优二元交换算法研究

doi:10.11959/j.issn.1000-436x.2019105

通信学报 ›› 2019, Vol. 40 ›› Issue (5): 180-191.doi: 10.11959/j.issn.1000-436x.2019105

大规模云计算服务器优化调度问题的最优二元交换算法研究

王万良¹,臧泽林¹(),陈国棋¹,屠杭垚¹,王宇乐¹,陆琳彦²

¹ 浙江工业大学计算机科学与技术学院，浙江杭州 310027
² 伦敦大学国王学院工程科学学院，英国伦敦 WC2R 2LS

修回日期:2019-04-19 出版日期:2019-05-25 发布日期:2019-05-30
作者简介:王万良（1957-），男，江苏高邮人，博士，浙江工业大学教授，主要研究方向为人工智能、运筹优化、大数据。|臧泽林（1994-），男，河北秦皇岛人，浙江工业大学硕士生，主要研究方向为人工智能、运筹优化、深度学习。|陈国棋（1996-），男，浙江温州人，浙江工业大学硕士生，主要研究方向为深度学习、增强学习。|屠杭垚（1996- ），男，浙江杭州人，浙江工业大学硕士生，主要研究方向为智能算法、人工智能、多目标优化。|王宇乐（1990- ），男，江苏常州人，浙江工业大学博士生，主要研究方向为演化计算、多目标优化。|陆琳彦（1996- ），女，浙江杭州人，伦敦大学国王学院硕士生，主要研究方向为通信网络技术。
基金资助:
国家自然科学基金资助项目(61873240);国家自然科学基金资助项目(51875524)

Research on optimal two element exchange algorithm for large scale cloud computing server scheduling problem

Wanliang WANG¹,Zelin ZANG¹(),Guoqi CHEN¹,Hangyao TU¹,Yule WANG¹,Linyan LU²

¹ School of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310027,China
² Faculty of Natural and Mathematical Sciences,King’s College London,London WC2R 2LS,England

Revised:2019-04-19 Online:2019-05-25 Published:2019-05-30
Supported by:
The National Natural Science Foundation of China(61873240);The National Natural Science Foundation of China(51875524)

摘要/Abstract

摘要：

随着云计算产业的不断兴盛，云计算服务器的合理管理与科学调度成为了一个重要的课题。在模型方面，提出了一个新的携带亲和约束与反亲和约束的混合整数规划（MIP）模型，并将其用于描述大规模云计算服务器调度问题。考虑到求解大规模MIP问题的时间成本，在分枝定界法与局部搜索算法的基础上提出了最优二元交换算法。该算法通过不断地从完整的调度问题中提取MIP子问题，并使用分支定界法解决该子问题的思想，不断地对服务器调度方案进行优化，从而使调度方案接近最优解。实验结果表明，所提算法在测试数据集ALISS上与其他方法相比有较大优势，在完成相同任务的情况下，可以使云计算中心的资源消耗减少4%以上。

关键词: 服务器调度, 混合整数规划模型, 最优二元交换算法, 云计算

Abstract:

With the flourishing of cloud computing industry,the rational management and scientific scheduling of cloud computing servers has become an important issue.In terms of model,a new mixed integer programming (MIP) model with affinity constraints and anti-affinity constraints was proposed to describe the scheduling problem of large scale cloud computing server.Considering the time cost of solving large-scale MIP problems,an optimal two element exchange algorithm was designed with the basics of branch and bound method and local search algorithm.By constantly extracting MIP sub-problems from completing scheduling problems and using branch and bound method to solve the sub-problems,the algorithm continuously optimized the server scheduling schemes,so that the scheduling schemes approached the optimal solution.The experimental results show that the algorithm has great advantages over the other methods in testing data set ALISS,and can reduce the resource consumption of cloud computing center by more than 4% when the same task is completed.

Key words: server scheduling, mixed integer programming model, optimal two element exchange algorithm, cloud computing

中图分类号:

TP302

王万良, 臧泽林, 陈国棋, 屠杭垚, 王宇乐, 陆琳彦. 大规模云计算服务器优化调度问题的最优二元交换算法研究[J]. 通信学报, 2019, 40(5): 180-191.

Wanliang WANG, Zelin ZANG, Guoqi CHEN, Hangyao TU, Yule WANG, Linyan LU. Research on optimal two element exchange algorithm for large scale cloud computing server scheduling problem[J]. Journal on Communications, 2019, 40(5): 180-191.

图/表 12

图1

表1

图2

图3

图4

图5

图6

图7

表2

图8

图9

表3

参考文献 24

[1]	MARINESCU D C . Cloud computing:theory and practice[M]. Morgan Kaufmann, 2017.
[2]	HASSAN M M , SONG B , HUH E N . A market-oriented dynamic collaborative cloud services platform[J]. Annals of Telecommunications, 2010,65(11-12): 669-688.
[3]	AL-DHURAIBI Y , PARAISO F , DJARALLAH N ,et al. Elasticity in cloud computing:state of the art and research challenges[J]. IEEE Transactions on Services Computing, 2017,12(5):e0176321.
[4]	ADAN I , KLEINER I , RIGHTER R ,et al. FCFS parallel service systems and matching models[J]. arXiv Preprint,arXiv:1805.04266, 2018.
[5]	LI J , MA T , TANG M ,et al. Improved FIFO scheduling algorithm based on fuzzy clustering in cloud computing[J]. Information, 2017,8(1):25.
[6]	BURNS B , GRANT B , OPPENHEIMER D ,et al. Borg,omega,and kubernetes[J]. Queue, 2016,14(1): 70-93.
[7]	MIJUMBI R , SERRAT J , GORRICHO J ,et al. Network function virtualization:state-of-the-art and research challenges[J]. IEEE Communications Surveys ＆ Tutorials, 2015,18(c): 236-262.
[8]	VERMA A , PEDROSA L , KORUPOLU M ,et al. Large-scale cluster management at Google with Borg[C]// The Tenth European Conference on Computer Systems. ACM, 2015:18.
[9]	CHENG Y , CHAI Z , ANWAR A . Characterizing co-located datacenter workloads:an alibaba case study[J]. arXiv Preprint.arXiv:1808.02919, 2018.
[10]	TSAI W , SHAO Q , SUN X ,et al. Real-time service-oriented cloud computing[C]// 2010 6th World Congress on Services. 2010: 473-478.
[11]	ZHU X , YANG L T , CHEN H ,et al. Real-time tasks oriented energy-aware scheduling in virtualized clouds[J]. IEEE Transactions on Cloud Computing, 2014,2(2): 168-180.
[12]	王吉, 包卫东, 朱晓敏 . 虚拟化云平台中实时任务容错调度算法研究[J]. 通信学报, 2014,35(10): 171-180.
	WANG J , BAO W D , ZHU X M . Fault tolerant scheduling algorithm for real time tasks in virtualized cloud[J]. Journal on Communications, 2014,35(10): 171-180.
[13]	郭平, 宁立江, 陈海珠 ,等. 满足本地化计算的集群资源调度策略[J]. 通信学报, 2014,35(Z2): 1-8.
	GUO P , NING L J , CHEN H Z ,et al. Scheduling strategy for achiev-ing locality in cluster[J]. Journal on Communications, 2014,35(Z2): 1-8.
[14]	PENG Y , BAO Y , CHEN Y ,et al. Optimus:an efficient dynamic resource scheduler for deep learning clusters[C]// The Thirteenth EuroSys Conference on EuroSys’18. 2018: 1-14.
[15]	SINGH S , CHANA I . A survey on resource scheduling in cloud computing:issues and challenges[J]. Journal of Grid Computing, 2016,14(2): 217-264.
[16]	RIMAL B P , MAIER M . Workflow scheduling in multi-tenant cloud computing environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2017,28(1): 290-304.
[17]	PETEGHEM V V , VANHOUCKE M . A genetic algorithm for the preemptive and non preemptive multi mode resource constrained project scheduling problem[J]. European Journal of Operational Research, 2010,201(2): 409-418.
[18]	PAGNOZZI F , STUTZLE T . Speeding up local search for the insert neighborhood in the weighted tardiness permutation flowshop problem[J]. Optimization Letters, 2017,11(7): 1283-1292.
[19]	林伟伟, 刘波, 朱良昌 ,等. 基于CSP的能耗高效云计算资源调度模型与算法[J]. 通信学报, 2013,34(12): 33-41.
	LIN W W , LIU B , ZHU L C ,et al. CSP-based resource allocation model and algorithms for energy-efficient cloud computing[J]. Journal on Communications, 2013,34(12): 33-41.
[20]	LI J , SU S , CHENG X ,et al. Cost-efficient coordinated scheduling for leasing cloud resources on hybrid workloads[J]. Parallel Computing, 2015,44: 1-17.
[21]	DONG Z , LIU N,ROJAS-CESSA R . Greedy scheduling of tasks with time constraints for energy-efficient cloud-computing data centers[J]. Journal of Cloud Computing, 2015,4(1):5.
[22]	KRAMER O . Briefs in applied sciences and technology[M]. London: SpringerPress, 2014.
[23]	糜培培 . 基于云计算的改进差分进化算法的研究与实现[D]. 成都:电子科技大学, 2018.
	MI P P . Research and implementation of improved differential evolu-tion evolution algorithm based on cloud computing[D]. Chengdu:University of Electronic Science and Technology of China, 2018.
[24]	DAS S , MULLICK S S , SUGANTHAN P N . Recent advances in differential evolution – an updated survey[J]. Swarm and Evolutionary Computation, 2016,11(9): 30-45.

情况	亲和/反亲和关系
2个应用间有功能上的依赖关系	2个应用亲和
2个应用的某一维度的资源存在强烈的竞争	2个应用反亲和
2个应用都是重要的应用，如果将2个应用布置到同一服务器会增大故障风险	2个应用反亲和
应用需要用到部分宿主机服务器的计算资源（如GPU、HDFS模块）	宿主机服务器与应用亲和
应用由于资源问题不适合某一宿主机服务器（如GPU、HDFS模块）	宿主机服务器与应用反亲和

不同规模	实例数	OTECA			C-MSDE			CT-DE			GA			LS
不同规模	实例数	N_m	Score	CPU	N_m	Score	CPU	N_m	Score	CPU	N_m	Score	CPU	N_m	Score	CPU
SSP₁	100	9	9.01	49%	10	10.00	46%	9	9.01	49%	11	11.01	44%	9	9.01	49%
SSP₂	500	41	48.70	48%	41	48.57	47%	41	48.84	48%	41	48.48	48%	41	48.46	48%
SSP₃	1 000	95	102.04	45%	97	109.62	44%	102	100.52	44%	105	102.88	45%	105	107.56	45%
SSP₄	7 000	480	607.76	45%	482	613.26	47%	481	626.15	47%	480	608.95	47%	480	619.58	47%
SSP₅	14 000	1 413	1 709.48	45%	1 433	1 756.14	43%	1 426	1 716.54	45%	1 452	1 786.51	42%	1422	1 712.15	45%
SSP₆	70 000	4 731	5 544.98	47%	5 098	6 034.26	44%	4 969	6 167.03	45%	5 260	5 989.14	44%	4816	5 861.35	45%
平均	—	1 128.17	1 337.00	47%	1 193.50	1 428.64	45%	1 171.33	1 444.68	46%	1 224.83	1 424.50	45%	1 145.50	1 393.02	47%

算法	指标	ALISS-1	ALISS-2	ALISS-3	ALISS-4	ALISS-5	ALISS-6	ALISS-7	平均
	Score	5 534.3	6 214.5	5 234.9	5 240.2	6 894.6	6 825.1	9 584.9	6 665.70
	CPU	0.34	0.49	0.51	0.5	0.49	0.51	0.51	0.50
OTECA	MEM	0.42	0.63	0.62	0.61	0.65	0.63	0.72	0.64
	DISK	0.99	0.44	0.5	0.49	0.46	0.45	0.39	0.46
	STD	0.128	0.083	0.042	0.052	0.153	0.146	0.126	0.10
	Score	5 668.8	6 715.6	5 214.6	5 244.9	7 015.9	7 163.4	10 125.6	6 913.33
	CPU	0.32	0.44	0.49	0.49	0.42	0.44	0.38	0.44
C-MSDE	MEM	0.40	0.57	0.60	0.60	0.56	0.54	0.54	0.57
	DISK	0.93	0.40	0.48	0.48	0.39	0.39	0.29	0.40
	STD	0.15	0.106	0.042	0.052	0.154	0.142	0.121	0.10
	Score	5 679.6	7 832.5	5 235.7	5 247.3	7 948.1	7 216.4	11 244.8	7 454.02
	CPU	0.32	0.44	0.50	0.50	0.40	0.40	0.39	0.44
CT-DE	MEM	0.40	0.57	0.61	0.61	0.53	0.49	0.55	0.56
	DISK	0.93	0.40	0.49	0.49	0.38	0.35	0.30	0.40
	STD	0.14	0.098	0.043	0.053	0.133	0.142	0.134	0.10
	Score	5 683.9	7 816.5	5 247.6	5 256.3	7 365.2	7 201.6	10 165.6	7 175.37
	CPU	0.33	0.42	0.50	0.50	0.40	0.43	0.36	0.44
GA	MEM	0.41	0.54	0.61	0.61	0.53	0.53	0.51	0.55
	DISK	0.96	0.38	0.49	0.49	0.38	0.38	0.28	0.40
	STD	0.15	0.106	0.043	0.052	0.157	0.142	0.146	0.11
	Score	5 630.6	7 834.4	5 235	5 247.3	7 952.5	7 265.2	12 033.9	7 594.72
	CPU	0.33	0.44	0.5	0.5	0.42	0.41	0.35	0.44
LS	MEM	0.41	0.57	0.61	0.61	0.56	0.51	0.49	0.56
	DISK	0.96	0.40	0.49	0.49	0.39	0.36	0.27	0.40
	STD	0.14	0.098	0.043	0.053	0.134	0.142	0.136	0.10

大规模云计算服务器优化调度问题的最优二元交换算法研究

Research on optimal two element exchange algorithm for large scale cloud computing server scheduling problem

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 24

相关文章 15

Metrics

推荐阅读 0

[1]	马玲, 樊漆亮, 许婷, 郭冠琛, 张圣林, 孙永谦, 张玉志. 基于强化学习的在线离线混部云环境下的调度框架[J]. 通信学报, 2023, 44(6): 90-102.
[2]	王化群, 刘哲, 何德彪, 李继国. 公有云中身份基多源IoT终端数据PDP方案[J]. 通信学报, 2021, 42(7): 52-60.
[3]	张键红, 武梦龙, 王晶, 刘沛, 姜正涛, 彭长根. 云环境下安全的可验证多关键词搜索加密方案[J]. 通信学报, 2021, 42(4): 139-149.
[4]	李瑞琪, 贾春福, 王雅飞. 基于NTRU的多密钥同态代理重加密方案及其应用[J]. 通信学报, 2021, 42(3): 11-22.
[5]	张嘉伟, 马建峰, 马卓, 李腾. 云计算中基于时间和隐私保护的可撤销可追踪的数据共享方案[J]. 通信学报, 2021, 42(10): 81-94.
[6]	王文娟, 杜学绘, 单棣斌. 基于动态概率攻击图的云环境攻击场景构建方法[J]. 通信学报, 2021, 42(1): 1-17.
[7]	田有亮,骆琴. 基于改进Merkle-Tree认证方法的可验证多关键词搜索方案[J]. 通信学报, 2020, 41(9): 118-129.
[8]	王娜,郑坤,付俊松,李剑. 基于分块的移动边缘计算密文检索方法[J]. 通信学报, 2020, 41(7): 95-102.
[9]	赵临东,庄文芹,陈建新,周亮. 异构蜂窝网络中分层任务卸载：建模与优化[J]. 通信学报, 2020, 41(4): 34-44.
[10]	梁冰,纪雯. 基于次模优化的边云协同多用户计算任务迁移方法[J]. 通信学报, 2020, 41(10): 25-36.
[11]	苏命峰,王国军,李仁发. 基于利益相关视角的多维QoS云资源调度方法[J]. 通信学报, 2019, 40(6): 102-115.
[12]	陈兴蜀,滑强,王毅桐,葛龙,朱毅. 云环境下SDN网络低速率DDoS攻击的研究[J]. 通信学报, 2019, 40(6): 210-222.
[13]	王田,沈雪微,罗皓,陈柏生,王国军,贾维嘉. 基于雾计算的可信传感云研究进展[J]. 通信学报, 2019, 40(3): 170-181.
[14]	何欣枫,田俊峰,刘凡鸣. 可信云平台技术综述[J]. 通信学报, 2019, 40(2): 154-163.
[15]	朱智强,林韧昊,胡翠云. 基于数字证书的openstack身份认证协议[J]. 通信学报, 2019, 40(2): 188-196.