Search Advanced

Message Board

Dear readers, authors and reviewers,you can add a message on this page. We will reply to you as soon as possible!

2021 Volume 46 Issue 1
Article Contents
Previous Article Next Article

QIU Chun-hong. Optimal Allocation of Virtual Machine Clusters in Cloud Computing[J]. Journal of Southwest China Normal University(Natural Science Edition), 2021, 46(1): 44-49. doi: 10.13718/j.cnki.xsxb.2021.01.008
Citation: QIU Chun-hong. Optimal Allocation of Virtual Machine Clusters in Cloud Computing[J]. Journal of Southwest China Normal University(Natural Science Edition), 2021, 46(1): 44-49. doi: 10.13718/j.cnki.xsxb.2021.01.008
shu

Optimal Allocation of Virtual Machine Clusters in Cloud Computing

  • School of E-commerce and Logistics, Jiangsu Vocational College of Business, Nantong Jiangsu 226000, China

More Information
  • Received Date: 15/10/2019
    Available Online: 20/01/2021

  • MSC: TP311

  • In order to optimize the allocation of virtual machine resources in cloud computing, a virtual machine cluster allocation method based on energy minimization has been proposed. In the design of this method, the virtual machine cluster resources in cloud computing are abstracted by using graph cutting theory, and the allocation problem of virtual machine resources is mapped to the maximum flow minimum cutting model. In the maximum flow minimum cut model, the path is constructed to optimize the resource allocation of each virtual machine and virtual machine cluster. The experimental results show that the virtual machine cluster allocation based on this method can achieve the most efficient configuration, which makes the virtual machine resources well correspond to the physical host.
  • 加载中
  • [1] CALHEIROS R N. CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms [J]. Software: Practice and Experience, 2011, 41(1): 23-50. doi: 10.1002/spe.995

    CrossRef Google Scholar

    [2] 温少君, 陈俊杰, 郭涛.一种云平台中优化的虚拟机部署机制[J].计算机工程, 2012, 38(11): 17-19.

    Google Scholar

    [3] JAYASINGHE D, PU C, EILAM T. Improving Performance and Availability of Services Hosted on LaaS Clouds with Structural Constraint-Aware Virtual Machine Placement[C]//2011 IEEE International Conference on Services Computing. Piscataway: IEEE, 2017.

    Google Scholar

    [4] 李帅, 杨懋, 李勇.分布式镜像存储环境下的虚拟机快速部署算法[J].计算机仿真, 2014, 31(4): 131-138.

    Google Scholar

    [5] 王光波, 马自堂, 孙磊, 等.基于架构负载感知的虚拟机聚簇部署算法[J].计算机应用, 2013, 33(5): 1271-1275.

    Google Scholar

    [6] 陈彬, 肖侬, 蔡志平, 等.基于优化的COW虚拟块设备的虚拟机按需部署机制[J].计算机学报, 2009, 32(10): 1915-1925.

    Google Scholar

    [7] GUPTA R, BOSE S K, SUNDARRAJAN S. A Two Stage Heuristic Algorithm for Solving the Server Consolidation Problem with Item-Item and Bin-Item Incompatibility Constraints[C]//SCC 08: Proceedings of the 2008 IEEE International Conference on Services Computing. Piscataway: IEEE, 2008.

    Google Scholar

    [8] Muñoz A, Gonzalez J, Maña A. A Performance-Oriented Monitoring System for Security Properties in Cloud Computing Applications[J]. Computer Journal, 2018, 55(8): 979-994.

    Google Scholar

    [9] GUPTA B B, BADVE O P. Taxonomy of DoS and DDoS Attacks and Desirable Defense Mechanism in a Cloud Computing Environment[J]. Neural Computing & Applications, 2017, 28(12): 3655-3682.

    Google Scholar

  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(4)  /  Tables(2)

Export Citation
PDF
XML

Article Metrics

Article views(1424) PDF downloads(127) Cited by(0)

Access History

Other Articles By Authors

Optimal Allocation of Virtual Machine Clusters in Cloud Computing

  • Received Date: 15/10/2019
  • Available Online: 20/01/2021

Abstract: In order to optimize the allocation of virtual machine resources in cloud computing, a virtual machine cluster allocation method based on energy minimization has been proposed. In the design of this method, the virtual machine cluster resources in cloud computing are abstracted by using graph cutting theory, and the allocation problem of virtual machine resources is mapped to the maximum flow minimum cutting model. In the maximum flow minimum cut model, the path is constructed to optimize the resource allocation of each virtual machine and virtual machine cluster. The experimental results show that the virtual machine cluster allocation based on this method can achieve the most efficient configuration, which makes the virtual machine resources well correspond to the physical host.

    HTML

  • 云计算是一种新兴的计算模式和计算方法, 充分利用网络上的计算资源完成用户无法个体完成的复杂计算任务[1].在云计算的实现过程中, 网络间的资源如何合理地分配给不同用户的计算任务, 是决定云端总体计算效率高低的关键问题[2].为了提升资源到任务间的合理匹配, 将发送到云端的任务所需求的资源进行虚拟化, 进而将其所需的虚拟机与网络间可以调配的实际物理主机相配合, 可以实现云计算资源的最佳配置.

    通过虚拟化技术运用, 云计算充分解决了用户需求和网络间实际资源耦合的问题, 使得云计算的计算效率、服务效率和经营收益大为提高[3].近年来, 学者们仍然致力于进一步提升虚拟机资源到实际物理主机的优化分配, 其实质还是进一步提升用户需求和网络资源的更高效配置.最终完成数据存储和算法执行的硬件是磁盘, 因此以磁盘、磁盘存储模式、磁盘读取模式为视角的优化分配成为云计算资源调度的一类重要方法[4].云计算资源的最佳配置, 应该是使参与任务的各个物理主机的CPU都充分地运行起来, 即每台参与任务的计算机都高负荷地工作, 以充分发挥每个计算资源的效率.所以, 基于CPU利用率的考核方法经常用于虚拟机资源调度的评价之中[5].虚拟机资源进行合理的分割后, 如何以更快的速度和实际物理主机进行对应配置也是非常重要的问题, 因此有基于镜像配置的方法被设计出来以提升虚拟机到物理主机的配置效率[6].对于一个具体而庞大的计算任务, 如果参与任务的各个虚拟机资源能够彼此建立联系, 就构成了一个虚拟机资源集合, 也称为虚拟机簇.当前, 云计算中的虚拟机资源调度正在逐步向虚拟机簇调度演变, 其难度和复杂度也不断增加[7].考虑到蚁群之间的信息交流类似于虚拟机簇中各虚拟机资源的交流, 因此蚁群算法被应用于虚拟机资源集合的调度之中并取得了初步成效[8].虚拟机簇作为一个庞大的虚拟机资源集合, 向物理主机进行分配时如果也能有对应成簇的物理主机资源承接, 将在很大程度上提升优化分配的效率[9].

    从现有的研究成果来看, 虚拟机部署正在从单个虚拟机部署逐步演变为多虚拟机部署, 也就是虚拟机簇的部署问题.虚拟机簇内部各个虚拟机之间往往有着比较密切的联系, 当向物理主机进行配置时, 如何根据匹配程度进行合理分割成为虚拟机簇部署算法必须妥善解决的核心问题.据此, 本文构建了一种基于能量最小化图割理论的虚拟机簇部署方法.

1.   基于能量最小化图割理论的虚拟机部署方法

    1.1.   虚拟机簇分割部署的能量最小化问题

  • 在虚拟机资源分配的早期研究中, 都是针对物理主机进行的单虚拟机配置, 也不考虑各个虚拟机之间的关联关系.现在的一个主要方向就是, 将为某个用户任务服务的关联虚拟机先聚集成簇, 进而以簇的形式向物理主机配置.当然, 因为虚拟机簇本身的资源需求会大于单个虚拟机的资源需求, 往往一台物理主机无法承接整个虚拟机簇的配置, 这就涉及到了虚拟机簇的分割问题.

    一个已经聚簇好的虚拟机簇如图 1所示.

    在图 1中, 这个虚拟机簇中一共有9个相互关联的虚拟机.当这个虚拟机簇向物理主机配置时, 一个物理主机无法承载, 需要2个物理主机时就要将已经关联在一起的虚拟机簇分割为2个部分, 图 1中的虚线就是一种可能的分割方法.

    对上述虚拟机簇进行分割的方法很多, 本文试图用能量最小化模型来解决这个最佳分割判断的问题.我们用VC来表示一个虚拟机簇, 用Vi来表示簇中的第i个虚拟机, 那么这个虚拟机簇的能量表达为

    式(1)中, E()表示能量函数, Ei()表示第i个虚拟机的能量, Ei, j()表示第i个虚拟机和第j个虚拟机产生关联时所需的能量, λ是调节比重因子.

    进一步明确这个能量最小化模型在虚拟机簇部署中的某些问题, Ei()所代表的能量可以具体为第i个虚拟机所需的物理主机资源配置, 如CPU, RAM、硬盘、带宽等; Ei, j()所代表的能量可以具体为第i个虚拟机和第j个虚拟机产生关联时所需的带宽等.我们要实现理想的虚拟机簇分割, 就是保证分割后的式(1)具有最小化的能量.

    • 1.2.   基于图割理论的虚拟机簇分割

  • 当多个虚拟机聚集成簇后, 其结构上相当于一个网络形状, 符合图割理论中的最大流最小割.实现虚拟机簇网络的最小割, 也就相当于使其能量最小化.

    对能量最小化的网络建模时, 可以为网络构建一个源点和一个汇点.这样原有的网络结构变成了如图 2所示的结构.

    在图 2中, 用PS表示源点, 用PT表示汇点, 这个网络可以表示为这样一个集合N={Pv, L}.这说明集合中含有两种元素, 一种是以虚拟机构成的节点Pv, 一种是连接L.集合中的连接又分为两种形式, 一种是各个虚拟机节点之间的连接用LP表示, 另一种是源点、汇点和虚拟机节点之间的连接, 用LS和LT表示.各种连接又配置权重, 用w(i, j)表示.

    在图 2b中, 虚线实现了对网络的一个分割, 分割之后形成一个割集GC={GS, GT}.在GS中包含源点PS和一部分虚拟机节点, 在GT中包含汇点PT和一部分虚拟机节点.并且, 这两个集合没有交集.这个割集的形成, 需要同时考虑两个问题: ①如何尽可能地保证割集的总能量最小, ②如何尽可能地避免形成割集所付出的代价过大.

    对于第1个问题, 因为各个虚拟机节点能量的确定性, 可以主要考虑簇中各个虚拟机通信的问题, 尤其是形成新割集时要保证这个通信带宽需求尽可能小.对应于式(1), 可以将这个问题进一步具体化为

    对于第2个问题, 要考虑如何尽可能地保证最小割的形成, 即满足式(3).

    式(3)的含义就是如何能使切割的虚拟机之间的连接通信量之和尽可能小, 即保证割后的两个(或多个)虚拟机簇的通信量尽可能多地保留, 不转嫁这个任务给承载它们的物理主机.

    最小割问题可以转化为最大流问题来解决, 设图 2中各个连接的流量用f(i, j)来表示.则这个流量要符合的关系为

    之所以会形成流量总和为0, 是因为我们考察了流量的方向, 即有从甲虚拟机流向乙虚拟机的流量, 也有从乙虚拟机流向甲虚拟机的流量, 这两个流量可以相抵.当我们对原有虚拟机簇进行一个切割之后, 在形成的包含源点和包含汇点的子簇中流量之和大于等于0.

    在执行最小割时, 要保证割后的最大流.最大流的实现依赖于从源点出发的流能够寻找到下一个活动节点, 如果不能再找到活动节点, 则这个路径搜索终止.

    为此, 我们按照4个步骤来执行本文的最小割算法.

    1) 设定一个流高度函数h().随着流推进一个单位, 流高度函数执行加1的处理.即h(i+1)=h(i)+1.

    2) 寻找活动节点.活动节点要同时满足两个条件: ①h(i)>0; ②该节点处∑f(i, j)>0.

    3) 在网络内各条路径上, 从源点方向向汇点执行寻找活动节点的处理, 当下一个节点不是活动节点时标记此节点.

    4) 连接各个路径上的不活动节点, 形成切割.

    本文的最小割处理应用于虚拟机簇分割, 这个前提确保了分割后的能量最小化问题, 也就是物理主机列表中, 必须存在足够承担分割后各个子簇的物理主机.

2.   实验结果与分析

  • 为了验证本文构建的基于最小化图割理论的虚拟机簇部署方法的有效性, 开展了如下的实验研究.在实验中, 可供选择的物理主机共有6台, 其硬件配置情况如表 1所示.

    根据用户需求, 一个包含12个虚拟机的虚拟机簇聚合完毕.这个虚拟机簇的结构如图 3所示.

    在这个虚拟机簇中, 12台虚拟机形成了并行交错的网状结构.各个虚拟机与相邻的其他虚拟机形成比较规律的通信关系. 12台虚拟机的硬件资源需求情况, 如表 2中的数据所示.

    每个虚拟机预留20 MB/s的带宽, 之所以要预留20 MB/s, 是考虑除本次虚拟机配置任务以外, 还可能面临其他的任务, 为了避免带宽超限, 所以预留20 MB/s.

    虚拟机两两交互时设定带宽为10 MB/s.据此, 1号虚拟机除了自身预留的20 MB/s以外, 还要分别和2号虚拟机、5号虚拟机完成通信, 所以带宽需求共计40 MB/s.从这个网状结构可以看出, 6号虚拟机和7号虚拟机的带宽需求最大, 因为他们同时和4个虚拟机交互.

    由于表 1中单个物理主机, 没有一台能够完整地配置这个虚拟机簇, 所以需要对这个虚拟机簇执行分割.同时结合物理主机的硬件资源情况, 以及图割理论的分割方法, 最终形成了图 3中虚线所示的分割结果.

    从图 3中可以看出, 3号虚拟机、7号虚拟机、10号虚拟机分别是各自路径上的最后一个活动结点.最终的分割结果就是1, 2, 3, 5, 6, 7, 9, 10这8台虚拟机形成一个子簇, 4, 8, 11, 12这4台虚拟机形成了另外一个子簇.这两个子簇分别可以找到5号物理主机和2号物理主机进行配置.当然, 我们可以看到6号物理主机也可以适用于这两个子簇的配置, 但是资源利用率不高, 故此没有选择6号物理主机进行配置.

    为了进一步检验本文虚拟机部署方法的效率, 以基于负载的单虚拟机部署方法为对照, 考察二者在配置相等数量的物理主机时, 系统的总体带宽需求情况, 比较结果如图 4所示.

    从图 4的比较结果可以看出, 单虚拟机部署方法对虚拟机进行部属时, 随着配置物理主机数量的增多, 系统的总体带宽需求会显著增长.基于本文的方法进行虚拟机部属, 随着配置物理主机数量增多, 带宽总体需求增长幅度缓慢, 这是因为多个虚拟机以簇的形式进行部属, 虚拟机簇内的联系降低了总体带宽的消耗.

3.   结语

  • 从云计算对虚拟机部属算法的需求来看, 单虚拟机部署算法的效率低、部署后的总体带宽需求大, 加之用户任务需求日益复杂, 单虚拟机部署算法越来越表现出弊端.结合能量最小化和图割理论, 本文构建了一种全新的虚拟机簇部署方法. ①根据用户任务需求构筑虚拟机簇, 并按照图论的思想对簇中节点和各个节点之间的联系进行虚拟机属性映射. ②将虚拟机簇的分割问题转化为图论中的最大流-最小割问题, 通过辅助源点、汇点以及源点-汇点各个路径上的活动节点搜索, 确定分割的具体位置. ③连接各个路径上的最后一个活动节点, 获得虚拟机簇的分割.实验结果表明, 本文的分割方法有效地实现了虚拟机簇部署, 可以降低部署后的总体带宽需求.

Figure (4)  Table (2) Reference (9)

Catalog

    Copyright Journal of Southwest China Normal University(Natural Science Edition)

    Address： Tel：023-68252540，68254576，68254478 E-mail：xbbjb@swu.edu.cn

    Supported by:Beijing Renhe Information Technology Co. Ltd

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return