Research on Energy Efficient Virtual Machine Placement with Complicated Resources Requirements in Cloud

doi:10.12005/orms.2016.0057

Operations Research and Management Science ›› 2016, Vol. 25 ›› Issue (2): 143-150.DOI: 10.12005/orms.2016.0057

• Application Research • Previous Articles Next Articles

Research on Energy Efficient Virtual Machine Placement with Complicated Resources Requirements in Cloud

XUE Ke-lei¹, PAN Yu², PAN Fang³, QIAN Cun-hua²

1.Business School, Nankai University, Tianjin 300071, China;
2.School of Economics and Management, Nanjing University of Technology, Nanjing 211816, China;
3.School of Economics and Trade Management, Nanjing Southeast University of Chinese Medicine, Nanjing 210023, China

Received:2013-12-18 Online:2016-04-25

云环境下面向复杂资源需求的虚拟机能效部署研究

薛克雷¹,潘郁²,潘芳³,钱存华²

1.南开大学商学院,天津 300071;
2.南京工业大学经济与管理学院,江苏南京 211816;
3.南京中医药大学经贸管理学院,江苏南京 210023

作者简介:薛克雷(1988-),男,山东临沂人,博士研究生,研究方向:管理决策与商务智能;潘郁(1955-),男,江苏南通人,教授,博士,研究方向:计算管理与商务智能。
基金资助:
国家自然科学基金项目(71371097)

Abstract

Abstract: Online virtual machine placement problem in cloud which is also a bin packing problem is studied in this paper. Multi-dimensional space partition model and online energy efficient virtual machine placement algorithm are presented. The proposed model can be used to guide the placement of virtual machines and avoid the imbalanced use of multi-dimensional resources. Based on this model, the proposed OEEVMP can achieve a tradeoff between local optimum and global optimum with the number of running physical machines, so as to improve the energy efficiency of virtual machine placement. The proposed algorithm is also evaluated with MFFD algorithm via extensive simulations and experiments. The experiment results verifie the feasibility and validity of the proposed algorithm. At last, two parameters of the model are analyzed and the optimal combination of them is given.

Key words: operations research, vector bin packing, heuristic algorithm, multi-dimensional space partition, virtual machine placement

摘要： 针对云环境下在线虚拟机部署这一矢量装箱问题进行了研究,提出了多维空间划分模型和在线虚拟机能效部署算法OEEVMP。多维空间划分模型可以引导虚拟机部署,避免多维资源的不均衡利用;基于此模型,提出的OEEVMP算法在物理机运行数量局部最优和全局最优之间取得均衡,从而提高虚拟机部署能效。通过仿真实验,将OEEVMP算法与MFFD算法进行了对比,实验结果验证了所提算法的可行性和有效性。最后,对控制模型的两个参数进行了分析,给出了最佳的参数组合。

关键词: 运筹学, 矢量装箱, 启发式算法, 多维空间划分, 虚拟机部署

CLC Number:

XUE Ke-lei, PAN Yu, PAN Fang, QIAN Cun-hua. Research on Energy Efficient Virtual Machine Placement with Complicated Resources Requirements in Cloud[J]. Operations Research and Management Science, 2016, 25(2): 143-150.

薛克雷,潘郁,潘芳,钱存华. 云环境下面向复杂资源需求的虚拟机能效部署研究[J]. 运筹与管理, 2016, 25(2): 143-150.

References

[1] 林闯,田源,姚敏.绿色网络和绿色评价:节能机制、模型和评价[J].计算机学报,2011,34(4):593-612.
[2] Cook G, Horn J V. How dirty is your data: a look at the energy choices that power cloud computing[EB/OL].http://www.greenpeace.org/international/Global/international/publications/climate/2011/Cool%20IT/dirty-data-report-greenpeace.pdf, 2011-04-20.
[3] 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.
[4] 邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2005.
[5] Johnson D S, Demers A, Ullman J D, et al.. Worst-case performance bounds for simple one-dimensional packing algorithms[J]. SIAM Journal on Computing, 1974, 3(4): 299-325.
[6] Seiden S S. On the online bin packing problem[J]. Journal of the ACM(JACM), 2002, 49(5): 640-671.
[7] Bennell J A, Soon Lee L, Potts C N. A genetic algorithm for two-dimensional bin packing with due dates[J]. International Journal of Production Economics, 2013, 145(2): 547-560.
[8] Elhedhli S. Ranking lower bounds for the bin-packing problem[J]. European Journal of Operational Research, 2005, 160(1): 34-46.
[9] Baldi M M, Crainic T G, Perboli G, et al.. Asymptotic results for the generalized bin packing problem[J]. Procedia-Social and Behavioral Sciences, 2014, 111(2): 663-671.[10] Stillwell M, Schanzenbach D, Vivien F, et al.. Resource allocation algorithms for virtualized service hosting platforms[J]. Journal of Parallel and Distributed Computing, 2010, 70(9): 962-974.
[11] Panigrahy R, Talwar K, Uyeda L, et al.. Heuristics for vector bin packing[EB/OL]. http://research.microsoft.com/pubs/147927/VBPackingESA11.pdf?origin=publication_detail, 2011.
[12] 庄威,桂小林,林建材,等.云环境下基于多属性层次分析的虚拟机部署与调度策略[J].西安交通大学学报,2013,47(2):132-141.
[13] 杨星,马自堂,孙磊.云环境下基于改进蚁群算法的虚拟机批量部署研究[J].计算机科学,2012,39(9):33-37.
[14] 李强,郝沁汾,肖利民,等.云计算中虚拟机放置的自适应管理与多目标优化[J].计算机学报,2011,34(12):2253-2264.
[15] Ye D, Chen J. Non-cooperative games on multi-dimensional resource allocation[J]. Future Generation Computer Systems, 2013, 29(6): 1345-1352.
[16] Google Cluster Data[EB/OL]. http://googleresearch.blogspot.com/2010/01/google-cluster-data.html, 2013-12-10.

Research on Energy Efficient Virtual Machine Placement with Complicated Resources Requirements in Cloud

云环境下面向复杂资源需求的虚拟机能效部署研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	MA Yong, HE Zheng-wen, JIANG Bo, WANG Neng-min. A Heuristic Algorithm for Solving Flexible Resource Constrained Proactive Project Scheduling Problem [J]. Operations Research and Management Science, 2021, 30(8): 14-20.
[2]	PANG Nan-sheng, YE Bo-tong. Research on Resource Allocation Heuristic Algorithm for Robust Project Scheduling [J]. Operations Research and Management Science, 2021, 30(8): 21-27.
[3]	CHEN Wei, ZHANG Yu-lin. Integrated Order Picking and Delivery Scheduling under “Warehouse and Store Integration” Mode [J]. Operations Research and Management Science, 2021, 30(7): 16-22.
[4]	DONG Ji-yang, HE Wan-li. Minimizing Costs Model and Algorithm of Centralized Commute [J]. Operations Research and Management Science, 2021, 30(12): 28-34.
[5]	ZHANG Wen-si, LI Jin-lin, RAN Lun, WANG Wei. Appointment Scheduling of Heterogeneous Outpatients under Random Service Time [J]. Operations Research and Management Science, 2020, 29(5): 26-36.
[6]	JIAO Xiao-gang, ZHENG Fei-feng, XU Yin-feng, LIU Ming. Integrated Continuous Berth Allocation and Time-variant Quay Crane Assignment under Berth Dredging in Container Terminal [J]. Operations Research and Management Science, 2020, 29(2): 47-57.
[7]	BIAN Zhan, ZHANG Qian, XU Qi, JIN Zhi-hong. Hybrid Algorithms for the Pickup and Delivery Problem with Time Windows [J]. Operations Research and Management Science, 2020, 29(2): 99-115.
[8]	Hong-tao WANG Hong-tao, ZHANG Xiang, WANG Ke. Operations Research 1996~2017: A Retrospective Statistical Analysis [J]. Operations Research and Management Science, 2020, 29(2): 229-239.
[9]	CHEN Gang, FU Jiang-yue, HE Mei-ling. Emergency Shelter Location Problem Considering Residents’ Choice Behavior [J]. Operations Research and Management Science, 2019, 28(9): 6-14.
[10]	CAO Ping, ZHANG Jian, XIONG Yan. Research onPayment Scheduling Problems with Different Quality ——Take a Software Project as Example [J]. Operations Research and Management Science, 2019, 28(9): 192-199.
[11]	WANG Nuo, DING Kai, WU Di, WU Nuan. Bidirectional Logistics Network Planning of Remote Islands and Reefs [J]. Operations Research and Management Science, 2019, 28(6): 118-128.
[12]	ZHANG Yuan-kai, SUN Li-jun, HU Xiang-pei. Multi-compartment Vehicle Dispatching and Routing for Product Oil Distribution [J]. Operations Research and Management Science, 2017, 26(7): 1-9.
[13]	BAO Xiao-guang, LIU Zhao-hui, YU Wei. Single Vehicle Scheduling Problems with Cluster and Release Time Constraints on a Line [J]. Operations Research and Management Science, 2017, 26(5): 125-129.
[14]	HAN Wei-yi. Perfection and Extension of a Ranking Method Based on the Virtual Decision-making Unit [J]. Operations Research and Management Science, 2017, 26(11): 65-69.
[15]	LI Kai, ZHOU Chao, MA Ying. Single Machine JIT Scheduling Problem Considering the Release Time [J]. Operations Research and Management Science, 2016, 25(3): 71-77.