基于多层图划分的云环境软件部署管理算法

Hybrid software deployment management algorithm based on multilevel graph partitioning in cloud environment

针对在云服务器上软件构件分配时需要最大限度地减少所需带宽的问题,提出一种基于多层图划分算法的混合算法,来解决云计算环境中的软件部署问题。该算法对重边匹配(HEM)算法进行改进,同时添加1个新的约束条件来进行粗化,且使用类似KL的算法进行细分,最后结合退火算法从而实现对图划分算法的重新设计和评估。与传统的图划分相比,本文提出的算法考虑到基础设施的异构性,因此不局限于平衡划分。实验仿真结果表明:相比传统的KL图划分算法,提出的混合算法在执行时间和求解质量之间取得很好的平衡,综合性能优于传统算法。

To allocate the software components to the appropriate cloud servers at the same time of minimizing the required bandwidth, a hybrid algorithm based on multi-layer graph partitioning algorithm was proposed for solving the software deployment issues in cloud computing environment. This algorithm improves the heavy-edge matching（HEM） algorithm, adds a new constraint for coarsening, conducts segmentation using the algorithm similar to KL, and finally achieves the re-design and assessment for graph partitioning algorithm in combination with annealing algorithm. Compared with traditional graph partitioning, the proposed algorithm takes into account the heterogeneity of the infrastructure, and so it is not limited to the balance partitioning. The simulation results of test show that compared with the traditional KL graph partitioning algorithm, the proposed hybrid algorithm can achieve a good balance between execution time and solution quality, and so its overall performance is better than that of the traditional algorithms.