面向大规模云资源调度的可扩展分布式调度方法

J4 ›› 2015, Vol. 37 ›› Issue (11): 1997-2005.

面向大规模云资源调度的可扩展分布式调度方法

林伟伟，朱朝悦

(华南理工大学计算机科学与工程学院，广东广州 510640)

收稿日期:2015-07-30 修回日期:2015-09-11 出版日期:2015-11-25 发布日期:2015-11-25
基金资助:
国家自然科学基金资助项目(61402183); 广东省科技计划资助项目(2014B010117001,2014A010103022,2014A010103008,2013B090200021,2013B010401005); 中央高校基本科研业务费专项资金资助项目(xzjsD2153930);广州开发区萝岗区科技领军人才项目(2014P176)

A scalable distributed scheduling method
for large-scale cloud resources

LIN Weiwei，ZHU Chaoyue

（School of Computer Science & Engineering,South China University of Technology,Guangzhou 510640,China）

Received:2015-07-30 Revised:2015-09-11 Online:2015-11-25 Published:2015-11-25

摘要/Abstract

摘要：

云数据中心异构物理服务器的能耗优化资源分配问题是NP难的组合优化问题，当资源分配问题规模较大时，求解的空间比较大，很难在合理时间内求得最优解。基于分而治之的思想，从调度模式方面提出可扩展分布式调度方法，即当云数据中心待调度的物理服务器的数量比较大时，将待调度的服务器划分为若干个服务器集群，然后在每个服务器集群建立能耗优化的资源分配模型，并利用约束编程框架Choco求解模型，获得能耗最优的资源分配方式。将提出的基于可扩展分布式调度方法的能耗优化云资源调度算法与非扩展调度算法进行实验比较，实验结果表明，提出的基于可扩展分布式调度方法的能耗优化云资源调度算法在大规模云资源分配上有明显的性能优势。关键词：

关键词: 云计算, 资源分配, 能耗优化, 分而治之, CSP

Abstract:

The energy consumption optimization of resources allocation in the cloud data center with heterogeneous physical servers is an NPHard combinatorial optimization problem. When the number of servers is large, the solution space is large as well. It is therefore quite difficult to get the optimal solution within reasonable time. We propose a scalable distributed scheduling method (SDSM) based on the "Divide and Conquer" idea from the aspect of scheduling model, which implements an efficient resource allocation algorithm in heterogeneous cloud environments. When the number of physical servers in cloud data centers is large, the servers will be divided into several server clusters, and then in every cluster we use Choco to model and solve the constraint satisfaction problem (CPS) of energy consumption optimization in heterogeneous cloud data centers, which can obtain the optimal resource allocation and greatly reduce its complexity. Finally, we compare the proposed SDSM and the nonscalable scheduling method through experiments, and the experimental results show that the SDSM has obvious advantage in largescale cloud resource allocation.

Key words: cloud computing;resource allocation;energy optimization;divide and conquer;constraint satisfaction problem (CPS)

林伟伟，朱朝悦. 面向大规模云资源调度的可扩展分布式调度方法[J]. J4, 2015, 37(11): 1997-2005.

LIN Weiwei，ZHU Chaoyue. A scalable distributed scheduling method
for large-scale cloud resources [J]. J4, 2015, 37(11): 1997-2005.

参考文献

［1］Qusay H F. Demystifying cloud computing［J］. The Journal of Defense Software Engineering (CrossTalk),2011,(Jan/Feb):1621.
［2］Mell P, Grance T, Mell P, et al. The NIST Definition of Cloud Computing(draft). National Institute of Standards and Technology［J］. Appl Opt, 2011,145(16):17.
［3］Srikantaiah S,Kansal A,Zhao F. Energy aware consolidation for cloud computing［C］∥Proc of HotPower’08,2008:115.
［4］Berl A,Gelenbe E,Girolamo M,et al. Energyefficient cloud computing［J］. The Computer Journal,2010,53(7):10451051.
［5］Beloglazoy A,Buyya R,Lee C Y,et al. A taxonomy and survey of energyefficient data centers and cloud computing systems ［J］. Advances in Computers,2011,82(2):47111.
［6］Liu L,Wang H,Liu X,et al. Greencloud:A new architecture for green data center［C］∥Proc of ICACINDST’09,2009:2938.
［7］Jinquan Z,Lina N,Changjun J. A heuristic scheduling strategy for independent tasks on grid［C］∥Proc of International Conference on HighPerformance Computing in AsiaPacific Region,2005:588593.
［8］Shi Xuelin,Xu Ke. Utility maximization model of virtual machine scheduling in cloud environment ［J］. Chinese Journal of Computers,2013,36(2):252261.(in Chinese)
［9］Lin Weiwei,Qi Deyu. Survey of resource scheduling in cloud computing ［J］. Computer Science,2012,39(10):16.(in Chinese)
［10］Beloglazov A,Abawajy J,Buyya R. Energyaware resource allocation heuristics for efficient management of data centers for cloud computing［J］. Future Generation Computer Systems,2012,28(5):755768.
［11］Garg S K,Yeo C S,Anandsivam A,et al. Environment conscious scheduling of HPC applications on distributed cloudoriented data centers［J］. Journal of Parallel and Distributed Computing,2011,71(6):732749.
［12］Cheng Chunling,Pan Yu,Zhang Dengyin, et al. Energy saving resource scheduling algorithm in cloud environment ［J］. Systems Engineering and Electronics,2013,35(11):24162423.
［13］Mi Haibo,Wang Huaimin,Yin Gang,et al. Resource ondemand reconfiguration method for virtualized data centers ［J］. Journal of Software,2011,22(9):21932205.(in Chinese)
［14］Addis B,Ardagna D,Panicucci B,et al. A hierarchical approach for the resource management of very large cloud platforms［J］. IEEE Transactions on Dependable & Secure Computing,2013,10(5):253272.
［15］Lin Weiwei,Qi Deyu. Cloud computing resource scheduling method based on dynamic reconfiguration of virtual resources:China,patent number:ZL2010102681057［P］. 20110105.(in Chinese)
［16］Vignesh V, Sendhil Kumar K S, Jaisankar N. Resource management and scheduling in cloud environment［J］. International Journal of Scientific and Research Publications,2013,3(6):1.
［17］Zemin Z,Qing Z. Resource scheduling with load balance based on multidimensional QoS and cloud computing［J］. Computer Measurement & Control,2013(1):087.
［18］Lin Weiwei,Liu Bo,Zhu Liangchang,et al. CSPbased resource allocation model and algorithms for energyefficient cloud computing ［J］. Journal of Communication,2013,34(12):3341.(in Chinese)
［19］Rivin I,Zabih R. An algebraic approach to constraint satisfaction problem［C］∥Proc of IJCAI’89,1989:284289.
［20］Rodero I,Jaramillo J,Quiroz A. Energyefficient applicationaware online provisioning for virtualized clouds and data centers［C］∥Proc of 2010 International Green Computing Conference,2010:3145.
附中文参考文献：
［8］师雪霖,徐恪. 云虚拟机资源分配的效用最大化模型［J］. 计算机学报,2013,36(2):252261.
［9］林伟伟,齐德昱. 云计算资源调度研究综述［J］. 计算机科学,2012,39(10):16.
［12］程春玲,潘钰,张登银. 云环境下一种节能的资源调度算法［J］. 系统工程与电子技术,2013,35(11):24162423.
［13］米海波,王怀民,尹刚,等. 一种面向虚拟化数字中心资源按需重配置方法［J］. 软件学报,2011,22(9):21932205.
［15］林伟伟，齐德昱.一种基于动态重配置虚拟资源的云计算资源调度方法:中国，专利号：ZL2010102681057［P］.20110105.
［18］林伟伟，刘波，朱良昌，等. 基于CSP的能耗高效云计算资源调度模型与算法［J］. 通信学报,2013,34(12):3341.

[1]	李卫平1,2，武海燕2，杨杰1. 基于效益博弈的云计算资源动态可协调分配策略研究[J]. J4, 20160101, 38(01): 57-61.
[2]	王冠博, 赵一帆, 李波, 杨俊东, 丁洪伟. 改进YOLO v4-tiny的火焰实时检测[J]. 计算机工程与科学, 2022, 44(12): 2196-2205.
[3]	方海, 赵扬, 高媛, 杨旭. 考虑任务依赖的卫星边缘计算资源分配与卸载决策算法[J]. 计算机工程与科学, 2022, 44(11): 1951-1958.
[4]	任小康, 刘行行. 基于改进的YOLOv3口罩佩戴检测和识别[J]. 计算机工程与科学, 2022, 44(10): 1812-1821.
[5]	杨柏蔼, 赵山, 刘芳. 无服务器计算技术研究综述[J]. 计算机工程与科学, 2022, 44(04): 611-619.
[6]	池来新, 杨旭涛, 谢宁, 张学杰. 边缘计算系统中资源分配防策略拍卖机制设计[J]. 计算机工程与科学, 2021, 43(10): 1720-1729.
[7]	肖卓宇, 何锫, 徐运标, 陈果, 郭杰, 黄俊. 引入线索约束的设计模式变体挖掘研究[J]. 计算机工程与科学, 2021, 43(06): 1014-1023.
[8]	李波, 侯鹏, 牛力, 武浩, 丁洪伟. 基于软件定义网络的云边协同架构研究综述[J]. 计算机工程与科学, 2021, 43(02): 242-257.
[9]	廖建锦, 孙庆骁, 杨海龙, 栾钟治, 钱德沛. 满足工作流执行时限的可抢占虚拟机实例配置和调度方法研究[J]. 计算机工程与科学, 2020, 42(11): 1956-1964.
[10]	吴俊斌, 吴晟, 吴兴蛟. 一种用于求解TSP问题的随机最佳插入烟花算法[J]. 计算机工程与科学, 2020, 42(11): 2080-2087.
[11]	童钊, 叶锋, 刘碧篮, 邓小妹, 梅晶, 刘宏. 移动边缘计算中多约束下的任务卸载和资源分配算法[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1869-1879.
[12]	林涛, 冯竞凯, 郝章肖, 黄少群. 基于组合预测模型的云计算资源负载预测研究[J]. 计算机工程与科学, 2020, 42(07): 1168-1173.
[13]	刘少楠，李玲，苑迎，蒋国佳，王聪，吕艳霞. 基于节点连通性排序的虚拟网络映射算法[J]. 计算机工程与科学, 2019, 41(12): 2101-2109.
[14]	史文杰，詹雨奇，李奎. 一种面向多平台航电资源建模及其调度算法[J]. 计算机工程与科学, 2019, 41(11): 1976-1984.
[15]	刘梓璇，周建涛. 负载均衡的主导资源公平分配算法[J]. 计算机工程与科学, 2019, 41(09): 1574-1580.