Joint Placement of Virtual Machine and Routing Path Based on Virtual Extended Network

doi:10.19678/j.issn.1000-3428.0065731

Computer Engineering ›› 2023, Vol. 49 ›› Issue (8): 154-162. doi: 10.19678/j.issn.1000-3428.0065731

• Mobile Internet and Communication Technology • Previous Articles Next Articles

Joint Placement of Virtual Machine and Routing Path Based on Virtual Extended Network

Xuyan ZHAO¹^,²^,³, Yunhe CUI¹^,²^,³^,*, Qing QIAN⁴, Chun GUO¹^,²^,³, Guowei SHEN¹^,²^,³

1. College of Computer Science and Technology, Guizhou University, Guiyang 550025, China
2. State Key Laboratory of Public Big Data Co-built by Provincial and Ministry, Guizhou University, Guiyang 550025, China
3. Engineering Research Center of Text Computing and Cognitive Intelligence, Ministry of Education, Guizhou University, Guiyang 550025, China
4. College of Information, Guizhou University of Finance and Economics, Guiyang 550025, China

Received:2022-09-13 Online:2023-08-15 Published:2023-01-03
Contact: Yunhe CUI

基于虚拟扩展网络的虚拟机及路由路径联合部署

赵徐炎¹^,²^,³, 崔允贺¹^,²^,³^,*, 钱清⁴, 郭春¹^,²^,³, 申国伟¹^,²^,³

1. 贵州大学计算机科学与技术学院, 贵阳 550025
2. 贵州大学省部共建公共大数据国家重点实验室, 贵阳 550025
3. 贵州大学文本计算与认知智能教育部工程研究中心, 贵阳 550025
4. 贵州财经大学信息学院, 贵阳 550025

通讯作者: 崔允贺
作者简介:
赵徐炎（1998—），男，硕士研究生，主研方向为软件定义网络、边缘计算
钱清，副教授、博士
郭春，副教授、博士
申国伟，教授、博士
基金资助:
国家自然科学基金(62102111); 贵州省科技计划项目(黔科合基金[2020]1Y267); 贵州省普通高等学校青年科技人才成长项目(黔教合KY字[2021]136); 贵州大学引进人才科研项目(贵大人基合字(2019)52号)

Abstract

Abstract:

In response to a tenant's request for virtual machine usage, cloud data centers typically select a physical server for virtual machine placement and calculate the routing path between the tenant and the selected virtual machine placement server to carry traffic between them. However, it is hard to predict the impact of virtual machine placement on the network, and this sequential virtual machine placement can result in the inefficient use of network resource and congestion.To address this problem, a virtual machine and routing path joint placement algorithm, VENet, is proposed. VENet expands the original network topology into a virtual network topology by adding virtual switches and links. Based on this virtual extended network topology, the joint placement problem is approximated as a commodity flow problem, where virtual machines requests are represented as a commodity flow between the corresponding access point switch and the virtual destination switch.The commodity flow problem is modeled and solved through linear programming, obtaining the virtual machine placement location and corresponding routing path simultaneously. Experimental results show that VENet can improve the upper limit of the number of virtual machine requests that can be accepted by the data center, shorten the routing path length between the tenant and the virtual machine placement location, and reduce the network load rate of the data center.Compared to the Weighted Least Connection-Genetic Algorithm(WLC-GA), VENet reduces the routing path length and network load rate by 42% and 30%, respectively.

Key words: virtual machine placement, routing path, extended network topology, commodity flow, Software Defined Network(SDN)

摘要：

为响应租户的虚拟机使用请求，云数据中心通常从物理服务器中选择虚拟机放置服务器，随后计算租户与所选择的虚拟机放置服务器之间的路由路径以承载两者之间的流量。但是这种顺序的处理方式使得虚拟机放置服务器的计算过程难以考虑其对网络造成的影响，可能导致网络利用率降低甚至出现网络拥塞。为解决该问题，提出一种虚拟机及路由路径联合部署算法VENet。VENet通过添加虚拟交换机及虚拟链路将原网络拓扑扩展为虚拟网络拓扑，基于该虚拟扩展网络拓扑，将虚拟机及路由路径联合部署问题近似为商品流问题，即将虚拟机请求近似为从相应接入起点交换机到虚拟目的交换机之间的商品流，对该商品流问题进行建模，通过线性规划的方式求解该模型，即可同时获得虚拟机放置位置及相应的路由路径。实验结果表明，VENet算法能够提高数据中心可接受的虚拟机请求数上限，缩短租户与虚拟机部署位置之间的路由路径长度同时降低数据中心的网络负载率，路由路径长度和网络负载率相比WLC-GA算法分别降低42%和30%。

关键词: 虚拟机放置, 路由路径, 拓展网络拓扑, 商品流, 软件定义网络

Xuyan ZHAO, Yunhe CUI, Qing QIAN, Chun GUO, Guowei SHEN. Joint Placement of Virtual Machine and Routing Path Based on Virtual Extended Network[J]. Computer Engineering, 2023, 49(8): 154-162.

赵徐炎, 崔允贺, 钱清, 郭春, 申国伟. 基于虚拟扩展网络的虚拟机及路由路径联合部署[J]. 计算机工程, 2023, 49(8): 154-162.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0065731

http://www.ecice06.com/EN/Y2023/V49/I8/154

Figures/Tables 9

Fig.1 Schematic diagram of virtual machine request placement problem

Fig.2 Principle of data center network topology extension

Fig.3 Example of joint placement algorithm of virtual machine and routing path

Fig.4 Comparison of the maximum number of virtual machine requests acceptable by three algorithms

Fig.5 Comparison of mean routing path length of three algorithms

Fig.6 Comparison of network load rates of three algorithms

Fig.7 Comparison of server load rates of three algorithms

Fig.8 Comparison of server load balance degree of three algorithms

Fig.9 Comparison of calculation time of three algorithms

References 29

1	PENG J, CUI Y H, QIAN Q, et al. ADVICE: towards adaptive scheduling for data collection and DDoS detection in SDN. Journal of Information Security and Applications, 2021, 63, 103017. doi: 10.1016/j.jisa.2021.103017
2	CUI Y H, QIAN Q, GUO C, et al. Towards DDoS detection mechanisms in software-defined networking. Journal of Network and Computer Applications, 2021, 190, 103156. doi: 10.1016/j.jnca.2021.103156
3	CUI Y H, QIAN Q, XING H L, et al. LNAD: towards lightweight network anomaly detection in software-defined networking[C]//Proceedings of IEEE International Conference on High Performance Computing and Communications. Washington D. C., USA: IEEE Press, 2021: 855-860.
4	GHETAS M. A multi-objective Monarch Butterfly algorithm for virtual machine placement in cloud computing. Neural Computing and Applications, 2021, 33(17): 11011- 11025. doi: 10.1007/s00521-020-05559-2
5	ABOHAMAMA A S, HAMOUDA E. A hybrid energy-aware virtual machine placement algorithm for cloud environments. Expert Systems with Applications, 2020, 150, 113306. doi: 10.1016/j.eswa.2020.113306
6	卢海峰, 顾春华, 罗飞, 等. 强化学习下能耗优化的虚拟机放置策略. 计算机科学, 2019, 46(9): 291- 297. URL
	LU H F, GU C H, LUO F, et al. Virtual machine placement strategy with energy consumption optimization under reinforcement learning. Computer Science, 2019, 46(9): 291- 297. URL
7	XU M X, TIAN W H, BUYYA R. A survey on load balancing algorithms for virtual machines placement in cloud computing. Concurrency and Computation: Practice and Experience, 2017, 29(12): e4123. doi: 10.1002/cpe.4123
8	GHASEMI A, HAGHIGHAT A T. A multi-objective load balancing algorithm for virtual machine placement in cloud data centers based on machine learning. Computing, 2020, 102(9): 2049- 2072. doi: 10.1007/s00607-020-00813-w
9	ZHAO H, WANG Q, WANG J, et al. VM performance maximization and PM load balancing virtual machine placement in cloud[C]//Proceedings of the 20th IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing. Washington D. C., USA: IEEE Press, 2020: 857-864.
10	RAWAS S. Energy, network, and application-aware virtual machine placement model in SDN-enabled large scale cloud data centers. Multimedia Tools and Applications, 2021, 80(10): 15541- 15562. doi: 10.1007/s11042-021-10616-6
11	汪晓洁, 徐明伟, 王思秀, 等. 基于网络感知的两阶段虚拟机放置算法. 计算机工程, 2017, 43(8): 32- 37. URL
	WANG X J, XU M W, WANG S X, et al. Two-phase virtual machine placement algorithm based on network awareness. Computer Engineering, 2017, 43(8): 32- 37. URL
12	张从越, 付雄, 乔磊. 云计算环境下基于多目标优化的虚拟机放置研究. 计算机应用与软件, 2021, 38(3): 32- 38. URL
	ZHANG C Y, FU X, QIAO L. Virtual machine placement based on multi-objective optimization in cloud computing environment. Computer Applications and Software, 2021, 38(3): 32- 38. URL
13	郭良敏, 高俊杰, 胡桂银. 一种基于机器学习的虚拟机放置方法. 计算机工程, 2019, 45(5): 135- 142. doi: 10.19678/j.issn.1000-3428.0052354
	GUO L M, GAO J J, HU G Y. A method for virtual machine placement based on machine learning. Computer Engineering, 2019, 45(5): 135- 142. doi: 10.19678/j.issn.1000-3428.0052354
14	ALBOANEEN D, TIANFIELD H, ZHANG Y, et al. A metaheuristic method for joint task scheduling and virtual machine placement in cloud data centers. Future Generation Computer Systems, 2021, 115, 201- 212. doi: 10.1016/j.future.2020.08.036
15	OMER S, AZIZI S, SHOJAFAR M, et al. A priority, power and traffic-aware virtual machine placement of IoT applications in cloud data centers. Journal of Systems Architecture, 2021, 115, 101996. doi: 10.1016/j.sysarc.2021.101996
16	BALAJI K, SAI KIRAN P, SUNIL KUMAR M. Power aware virtual machine placement in IaaS cloud using discrete firefly algorithm. Applied Nanoscience, 2023, 13(3): 2003- 2011. doi: 10.1007/s13204-021-02337-x
17	LIAQAT M, NAVEED A, ALI R L, et al. Characterizing dynamic load balancing in cloud environments using virtual machine deployment models. IEEE Access, 2019, 7, 145767- 145776. doi: 10.1109/ACCESS.2019.2945499
18	CHEN T, ZHU Y M, GAO X F, et al. Improving resource utilization via virtual machine placement in data center networks. Mobile Networks and Applications, 2018, 23(2): 227- 238. doi: 10.1007/s11036-017-0925-7
19	陶晓玲, 韦毅, 王勇. 一种基于分层多代理的云计算负载均衡方法. 电子学报, 2016, 44(9): 2106- 2113. URL
	TAO X L, WEI Y, WANG Y. A load balancing method based on hierarchy and multi-agent for cloud computing platform. Acta Electronica Sinica, 2016, 44(9): 2106- 2113. URL
20	FENG H, DENG Y, LI J. A global-energy-aware virtual machine placement strategy for cloud data centers. Journal of Systems Architecture, 2021, 116, 102048. doi: 10.1016/j.sysarc.2021.102048
21	HORMOZI E, HU S, DING Z, et al. Energy-efficient virtual machine placement in data centres via an accelerated genetic algorithm with improved fitness computation. Energy, 2022, 252, 123884. doi: 10.1016/j.energy.2022.123884
22	KIANI M, KHAYYAMBASHI M R. A network-aware and power-efficient virtual machine placement scheme in cloud datacenters based on chemical reaction optimization. Computer Networks, 2021, 196, 108270. doi: 10.1016/j.comnet.2021.108270
23	YANG S, WIEDER P, YAHYAPOUR R, et al. Reliable virtual machine placement and routing in clouds. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(10): 2965- 2978. doi: 10.1109/TPDS.2017.2693273
24	GANDHI S, VINIOTIS Y. Joint virtual machine placement and path selection in a virtualized datacenter environment[C]//Proceedings of the 19th International Conference on Distributed Computing and Networking. New York, USA: ACM Press, 2018: 1-10.
25	ZHANG X, PAPACHRISTODOULOU A. Improving the performance of network congestion control algorithms. IEEE Transactions on Automatic Control, 2015, 60(2): 522- 527. doi: 10.1109/TAC.2014.2336338
26	LANTZ B, HELLER B, MCKEOWN N. A network in a Laptop: rapid prototyping for software-defined networks[C]//Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. New York, USA: ACM Press, 2010: 1-6.
27	RYU SDN framework[EB/OL]. [2022-08-05]. http://osrg.github.io/ryu/.
28	SINGLA A, HONG C Y, POPA L, et al. Jellyfish: networking data centers randomly[C]//Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. San Diego, USA: USENIX Association, 2012: 17.
29	WHITLEY D. A genetic algorithm tutorial. Statistics and Computing, 1994, 4(2): 65- 85.

[1]	Xiangju LIU, Ben ZHAO, Xianjin FANG, Yangyang XU. Dynamic Load Balancing Strategy Based on Process Optimization in SDN [J]. Computer Engineering, 2023, 49(8): 137-145.
[2]	YE Heyuan, HAN Li, SUN Shimin. Network Measurement Node Selection Algorithm Based on Ant Colony Optimization in SDN [J]. Computer Engineering, 2022, 48(5): 191-199.
[3]	ZUO Pan, SHU Yongan. Dynamic Multi-Path Load Balancing Method Based on Feedforward Neural Network in DCN [J]. Computer Engineering, 2021, 47(9): 113-119.
[4]	XU Xiao, GU Lingli, CHEN Jianping, FU Qiming, LU You. An Intelligent Cooperative Algorithm for Multi-Path Routing and Subflow Allocation [J]. Computer Engineering, 2021, 47(9): 136-144,152.
[5]	YANG Xueting, LI Zhong. Identity Authentication Scheme Based on Vehicle Behavior Prediction for IoV [J]. Computer Engineering, 2021, 47(1): 129-138.
[6]	LI Weiyong, WU Que, ZHANG Wei, CHEN Yunfang. A Fast Protocol-Oblivious Source Routing Forwarding Scheme for SD-WAN [J]. Computer Engineering, 2020, 46(7): 206-215.
[7]	GENG Haijun, ZHANG Wei, YIN Xia. Routing Protection Algorithm Based on Hybrid Software Defined Network [J]. Computer Engineering, 2020, 46(6): 209-215.
[8]	GAO Hanghang, WANG Xiang, ZHAO Shanghong, PENG Cong. Controller Reliability Deployment Method for Aeronautical Information Network [J]. Computer Engineering, 2020, 46(6): 221-229.
[9]	ZHU Jing, WU Zhongdong, DING Longbin, WANG Yang. DDoS Attack Detection Based on DBN in SDN Environment [J]. Computer Engineering, 2020, 46(4): 157-161,182.
[10]	ZHAO Jihong, SUN Tianao, QU Hua, ZHANG Yin, ZHAI Fanni. An SDN Controller Deployment Strategy for Improved Community Detection Algorithm [J]. Computer Engineering, 2020, 46(11): 207-213.
[11]	CAO Yongyi, JIN Weizheng, WU Jing, LUO Wei, ZHU Bo. A DDoS Detection and Defense Method Based on Cross Plane Cooperation for SDN [J]. Computer Engineering, 2020, 46(11): 148-156.
[12]	LIU Jiamei, XU Qiaozhi. Network Traffic Prediction and Deployment Strategy Based on Machine Learning for SDN [J]. Computer Engineering, 2020, 46(10): 223-230.
[13]	DING Wei, ZHANG Qianfeng, ZHOU Wenfeng. UDP Reflection Attack Response Scheme Based on SDN [J]. Computer Engineering, 2020, 46(1): 121-128.
[14]	ZOU Xinqing, Lü Na, CHEN Kefan, LIU Chuang, CAO Fangbo. A Content-driven Routing Protocol for a New Airborne Tactical Network [J]. Computer Engineering, 2019, 45(8): 113-119.
[15]	ZANG Weifei,LAN Julong,HU Yuxiang,CHEN Wentao. Network-aware virtual machine placement algorithm based on multi-objective discrete differential evolution [J]. Computer Engineering, 2019, 45(6): 96-102.

Please choose a citation manager

Content to export