具有可控冗余度的虚拟机容错分配算法

发布时间：2018-03-14 01:36

本文选题：数据中心网络　切入点：容错　出处：《天津工业大学》2017年硕士论文　论文类型：学位论文

【摘要】：近年来,数据中心(Data Center)的高速发展和和Mapreduce/Hadoop框架的日益重要,云提供商把越来越多的大数据放到云系统中处理。在现代基于虚拟化的数据中心上,虚拟机分配是实现云中资源有效调度的首要考虑。在云系统中,大数据被划分成多个数据存储在数据中心的数据结点上等待虚拟机处理。已经证明对数据结点分配虚拟机并考虑虚拟机之间的通讯延迟,使得最大通讯延迟最小的问题是NP-hard问题。目前鲜有在数据中心网络虚拟机分配问题上考虑其安全性和可靠性的研究。针对虚拟机分配中的容错技术,本文提出了两种新的虚拟机容错分配算法,可满足任意大小的容错需求。从从降低解空间、提高解的质量角度考虑我们提出了一种具有可控冗余度的虚拟机容错分配算法,该算法先利用图兰定理判断某一阈值内是否存在满足冗余需求的虚拟机机群。如果存在则运用分支界限和回溯法在该阈值下寻找满足冗余需求并互相通信的虚拟机完全子图,然后进行预处理满足冗余需求,删除多余的虚拟机结点。再采用Hopcroft-Karp算法为数据结点分配冗余团中的虚拟机资源。实验结果表明,本文提出的虚拟机容错分配算法在在Tree,VL2,Fat-Tree和BCube四种网络拓扑中,与当前最新的近似算法相比平均情况下最大通讯延迟分别降低了 9.09%,4.5%,9.09%,4.5%。第二种算法从降低算法复杂度角度出发,遍历当前阈值下每一个虚拟机节点,在每个节点处根据三角不等式原则加入,先加入与该虚拟机节点阈值小于等于t/2的虚拟机节点,再运用贪心法把剩下的虚拟机与目前团中虚拟机之间阈值都小于t的虚拟机加入团中。然后将规模大于或等于冗余需求的团进行预处理删除多余节点。最后将完全子图中的虚拟机节点根据Hopcroft-Karp算法分配给数据结点。实验结果表明,本文提出的算法能够找到满足需求的可控冗余度的虚拟机团,与当前最新的启发式算法相比,平均情况下运行时间减少了 12.8%。
[Abstract]:In recent years, with the rapid development of data center and the increasing importance of Mapreduce/Hadoop framework, cloud providers put more and more big data into cloud system. Virtual machine allocation is the primary consideration for efficient resource scheduling in the cloud. Big data has been divided into data stored on data nodes in data centers waiting for virtual machines to be processed. It has been shown that virtual machines are assigned to data nodes and that communication delays between virtual machines are considered. The problem that makes the maximum communication delay minimum is the NP-hard problem. At present, there are few researches on the security and reliability of virtual machine allocation in data center network. In this paper, two new fault-tolerant allocation algorithms for virtual machines are proposed, which can satisfy the fault-tolerant requirements of any size. From the point of view of reducing the solution space and improving the quality of the solution, we propose a fault tolerant allocation algorithm for virtual machines with controllable redundancy. The algorithm first uses Turan theorem to determine whether there is a cluster of virtual machines satisfying redundant requirements within a threshold. If there is a cluster of virtual machines that satisfy redundant requirements, the branch bounds and backtracking methods are used to find complete subgraphs of virtual machines that satisfy redundant requirements and communicate with each other under the threshold. Then preprocessing is carried out to meet the redundant requirements, and the redundant virtual machine nodes are deleted. Then the Hopcroft-Karp algorithm is used to allocate the virtual machine resources in the redundant cluster for the data nodes. The experimental results show that, The fault-tolerant allocation algorithm for virtual machine proposed in this paper has reduced the maximum communication delay by 9.09 and 4.09 respectively in four network topologies, TreeLv VL2Fat-Tree and BCube, compared with the latest approximate algorithms. The second algorithm is based on reducing the complexity of the algorithm. Traversing each virtual machine node under the current threshold, adding the virtual machine node at each node according to the triangular inequality principle, adding the virtual machine node with the virtual machine node threshold less than t / 2. Then the greedy method is used to add the virtual machines which have a threshold of less than t between the remaining virtual machines and the virtual machines in the current group. Then the clusters with a size greater than or equal to the redundant requirements are pre-processed to remove the redundant nodes. The virtual machine nodes in the whole subgraph are assigned to the data nodes according to the Hopcroft-Karp algorithm. The experimental results show that, The algorithm proposed in this paper can find a cluster of virtual machines with controllable redundancy to meet the requirements. Compared with the latest heuristic algorithm, the average running time is reduced by 12. 8%.
【学位授予单位】：天津工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP302

【相似文献】