• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 高性能计算 • 上一篇    下一篇

基于节点连通性排序的虚拟网络映射算法

刘少楠,李玲,苑迎,蒋国佳,王聪,吕艳霞   

  1. (东北大学秦皇岛分校计算机与通信工程学院,河北 秦皇岛 066004)
  • 收稿日期:2019-07-13 修回日期:2019-11-15 出版日期:2019-12-25 发布日期:2019-12-25
  • 基金资助:

    国家自然科学基金(61702089);中央高校基本科研业务费(N182304021);河北省高等学校科学研究计划(ZD2019306)

A virtual network mapping algorithm
based on node connectivity ranking

LIU Shao-nan,LI Ling,YUAN Ying,JIANG Guo-jia,WANG Cong,L Yan-xia   

  1. (School of Computer and Communication Engineering,Northeastern University at Qinhuangdao,Qinhuangdao 066004,China)
     
  • Received:2019-07-13 Revised:2019-11-15 Online:2019-12-25 Published:2019-12-25

摘要:

对当今云环境下的数据中心来说,以虚拟资源租赁的运营方式具有极大的灵活性,尤其是以虚拟网络为粒度的资源租赁能够为用户提供更好的个性化需求支持。虚拟网络映射问题是指依据用户资源需求,合理分配底层主机和网络资源。现有的虚拟网络映射算法大多是针对随机拓扑设计的通用算法,未针对数据中心拓扑结构进行优化,映射效率有很大提升空间。针对数据中心的结构特点,提出了一种基于节点连通性排序的虚拟网络映射算法BS-VNE算法。首先,设计了一种最大生成算法来对虚拟节点重要程度进行求解和排序。该算法不仅基于虚拟节点的带宽和连通度,还基于虚拟节点在整个虚拟网络中的连通性来进行节点连通性的计算,以获得更加合理的排序结果。然后,根据虚拟节点连通性排序结果利用离散粒子群优化算法求解虚拟网络的映射解。在求解过程中,引入了针对数据中心结构的物理网络拓扑启发式规则,并将其组合到粒子搜索过程中,以提高映射算法的收敛速度。仿真实验结果表明,与现有算法相比,本文提出的算法可以提高物理网络的收益/成本比和资源利用率。
 

关键词: 云资源分配, 数据中心, 虚拟网络映射, 离散粒子群优化, 节点排序

Abstract:

In today’s cloud environment, the on-demand leasing of virtual resources can provide great flexibility for data centers, especially the resource leasing with the granularity of virtual network can provide much better personalized demand support for users. To allocate reasonable physical host and network resources for user’s requirement including nodes and links is called Virtual Network Embedding (VNE) problem. Most of the existing VNE algorithms are general algorithms on random topology, and are not optimized for the topological structure of data centers. Therefore, the efficiency and optimization extent need be improved in dealing the VNE problem in data centers. According to the characteristics of data center topology, a virtual network embedding algorithm based on node connectivity ranking named BS-VNE is proposed. Firstly, a maximum spanning tree algorithm is designed to sort the virtual nodes. The sorting algorithm calculates the node connectivity according to both the bandwidth and connectivity of virtual nodes and the connectivity of virtual nodes in the whole network, so as to obtain more reasonable ranking results. Then, a discrete particle swarm optimization algorithm is used to solve the mapping solution of virtual networks according to the results of virtual node ranking result. In the process of solution searching, the heuristic rules for physical network topology of data center are introduced and combined into particles search process to improve the solution efficiency. Simulation results show that the proposed algorithm can improve the benefit/cost ratio and resource utilization ratio of physical network.
 

Key words: cloud resource allocation, data center, virtual network embedding, discrete particle swarm optimization, node ranking