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

计算机工程与科学

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

张耀国1，武继刚2，高任飞1

（1.天津工业大学计算机科学与软件学院,天津 300387;2.广东工业大学计算机科学与技术学院,广东广州 510006)

收稿日期:2015-12-28 修回日期:2016-05-27 出版日期:2017-09-25 发布日期:2017-09-25
基金资助:
教育部博士点基金（20131201110002）;国家自然科学基金（11501411）

A fault-tolerant allocation algorithm for virtual

machine with controllable redundancy

ZHANG Yao-guo1,WU Ji-gang2,GAO Ren-fei1

(1.School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387;

2.School of Computer Science and Technology,Guangdong University of Technology,Guangzhou 510006,China)

Received:2015-12-28 Revised:2016-05-27 Online:2017-09-25 Published:2017-09-25

摘要/Abstract

摘要：

在现代基于虚拟化的数据中心中，虚拟机分配是实现云中资源有效调度的首要考虑。已经证明对数据结点分配虚拟机并考虑虚拟机之间的通信延迟，使得最大通信延迟最小的问题是NP-hard问题。目前鲜有在数据中心网络虚拟机分配问题上考虑其安全性和可靠性的研究。针对虚拟机分配中的容错技术，提出了一种具有可控虚拟机冗余度的启发式分配算法。算法以最大通信延迟最小化为优化目标，在可利用的虚拟机集合中通过构造可控冗余度的团来分配处理数据结点。实验结果表明，在Tree、VL2、Fat-tree和BCube四种常用的网络结构中，提出的启发式算法能提供0-200%之间任意冗余度。同时，在冗余度介于0~40%时，虚拟机与数据结点的匹配时间平均降低了67.1%，并且算法运行时间平均降低了12.8%。

关键词: 数据中心网络, 容错, 虚拟机分配, 启发式算法

Abstract:

In modern data centers based on virtualization, virtual machine (VM) allocation is the primary consideration for efficient resources scheduling in the cloud. It has been proved that the VM allocation (VMA) problem to minimize the maximum access latency is of NP-hard. But few works on fault tolerant algorithms for the VMA problem are reported, which is very important for the security and reliability of the data center network. We present a heuristic algorithm focusing on minimizing the maximum data access latency. The proposed fault tolerant algorithm constructs the group with controllable redundancy in the set of available VMs, and then selects the VMs from the group and assigns them to the data nodes in the data center network. Extensive experiments on the Tree, VL2, Fat-Tree and BCube, the four commonly used network structures, show that the proposed algorithm can provide between 0 and 200% redundancy, the assignment time of virtual machines for the data nodes is reduced by 67.1% on average when redundancy is between 0 and 40%, and the running time of the algorithm is generally reduced by 12.8%.

Key words: data center network, fault tolerance, virtual machine assignment, heuristic algorithm

张耀国1，武继刚2，高任飞1. 具有可控冗余度的虚拟机容错分配算法[J]. 计算机工程与科学.

ZHANG Yao-guo1,WU Ji-gang2,GAO Ren-fei1.

A fault-tolerant allocation algorithm for virtual

machine with controllable redundancy

[J]. Computer Engineering & Science.

[1]	张贝, 闵华松, 张新明. 差分变异和领地搜索的平衡优化算法及其机器人路径规划[J]. 计算机工程与科学, 2023, 45(11): 2078-2090.
[2]	段晨, 彭伟, 王宝生. 数据中心网络路由研究进展[J]. 计算机工程与科学, 2022, 44(04): 631-644.
[3]	李腾, 程哲, 贾东立, 贾耀清. 基于角色管理的实用拜占庭容错共识算法[J]. 计算机工程与科学, 2022, 44(02): 237-243.
[4]	张玲. MEDA芯片菊花链的自动容错设计[J]. 计算机工程与科学, 2021, 43(07): 1192-1199.
[5]	韩彪, 王韬, 王宝生. 无线数据中心网络：进展、挑战和展望[J]. 计算机工程与科学, 2021, 43(01): 70-81.
[6]	包敏泽, 胡秀婷, 谢玉莹, 蒋波. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(06): 1127-1133.
[7]	陈秀兰，刘婷. 基于动态奖惩的CDCL SAT求解器分支启发式算法[J]. 计算机工程与科学, 2019, 41(03): 490-497.
[8]	李永伟1,2，刘树安3，郭晋秦1. 普通立体仓库的货位优化模型与算法研究[J]. 计算机工程与科学, 2019, 41(02): 321-327.
[9]	王洁，康俊杰，周宽久. 基于FPGA的故障修复演化技术研究[J]. 计算机工程与科学, 2018, 40(12): 2120-2125.
[10]	黄洪涛1，武继刚1，郑露露1，缪裕青2. 面向无线内容分发网络的树形拓扑生成算法[J]. 计算机工程与科学, 2018, 40(12): 2133-2140.
[11]	罗裕春,武继刚,史雯隽,贺子楠. 移动云计算中的任务调度与计算迁移算法[J]. 计算机工程与科学, 2018, 40(11): 1915-1924.
[12]	郑露露,武继刚,陈辉. 网络可存活生成树的快速恢复算法[J]. 计算机工程与科学, 2018, 40(11): 1967-1973.
[13]	李树楠1,2,3，詹男杰1,2,3，章玥1,2. 面向数据中心租户带宽特征的虚拟拥塞控制方法性能分析[J]. 计算机工程与科学, 2018, 40(09): 1562-1571.
[14]	王余伟1，曹东2,施书成1. 实时操作系统CPU使用率监测的软件容错研究[J]. 计算机工程与科学, 2018, 40(08): 1337-1343.
[15]	骆伟忠，蔡昭权. 基于核心化技术的点覆盖改进算法[J]. 计算机工程与科学, 2018, 40(08): 1405-1411.