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

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

Abstract

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

CLC Number:

TP302

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.

Figures/Tables 12

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

Metrics

Recommended 0

No Suggested Reading articles found!

情况	亲和/反亲和关系
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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 24

Related Articles 15

Metrics

Recommended 0

[1]	Ling MA, Qiliang FAN, Ting XU, Guanchen GUO, Shenglin ZHANG, Yongqian SUN, Yuzhi ZHANG. Scheduling framework based on reinforcement learning in online-offline colocated cloud environment [J]. Journal on Communications, 2023, 44(6): 90-102.
[2]	Huaqun WANG, Zhe LIU, Debiao HE, Jiguo LI. Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud [J]. Journal on Communications, 2021, 42(7): 52-60.
[3]	Jianhong ZHANG, Menglong WU, Jing WANG, Pei LIU, Zhengtao JIANG, Changgen PENG. Secure and verifiable multi-keyword searchable encryption scheme in cloud [J]. Journal on Communications, 2021, 42(4): 139-149.
[4]	Ruiqi LI, Chunfu JIA, Yafei WANG. Multi-key homomorphic proxy re-encryption scheme based on NTRU and its application [J]. Journal on Communications, 2021, 42(3): 11-22.
[5]	Jiawei ZHANG, Jianfeng MA, Zhuo MA, Teng LI. Time-based and privacy protection revocable and traceable data sharing scheme in cloud computing [J]. Journal on Communications, 2021, 42(10): 81-94.
[6]	Wenjuan WANG, Xuehui DU, Dibin SHAN. Construction method of attack scenario in cloud environment based on dynamic probabilistic attack graph [J]. Journal on Communications, 2021, 42(1): 1-17.
[7]	Youliang TIAN,Qin LUO. Verifiable multi-keyword search scheme based on improved Merkle-Tree authentication method [J]. Journal on Communications, 2020, 41(9): 118-129.
[8]	Na WANG,Kun ZHENG,Junsong FU,Jian LI. Method of ciphertext retrieval in mobile edge computing based on block segmentation [J]. Journal on Communications, 2020, 41(7): 95-102.
[9]	Lindong ZHAO,Wenqin ZHUANG,Jianxin CHEN,Liang ZHOU. Hierarchical task offloading in heterogeneous cellular network:modeling and optimization [J]. Journal on Communications, 2020, 41(4): 34-44.
[10]	Bing LIANG,Wen JI. Multiuser computation offloading for edge-cloud collaboration using submodular optimization [J]. Journal on Communications, 2020, 41(10): 25-36.
[11]	SU Mingfeng,WANG Guojun,LI Renfa. Multidimensional QoS cloud computing resource scheduling method based on stakeholder perspective [J]. Journal on Communications, 2019, 40(6): 102-115.
[12]	CHEN Xingshu,HUA Qiang,WANG Yitong,GE Long,ZHU Yi. Research on low-rate DDoS attack of SDN network in cloud environment [J]. Journal on Communications, 2019, 40(6): 210-222.
[13]	Tian WANG,Xuewei SHEN,Hao LUO,Baisheng CHEN,Guojun WANG,Weijia JIA. Research progress of trusted sensor-cloud based on fog computing [J]. Journal on Communications, 2019, 40(3): 170-181.
[14]	Xinfeng HE,Junfeng TIAN,Fanming LIU. Survey on trusted cloud platform technology [J]. Journal on Communications, 2019, 40(2): 154-163.
[15]	Zhiqiang ZHU,Renhao LIN,Cuiyun HU. Openstack authentication protocol based on digital certificate [J]. Journal on Communications, 2019, 40(2): 188-196.