一种启发式网络虚拟化资源分配算法  

A heuristic resource allocation algorithm for virtual network embedding

作　　者：罗娟[1] 陈磊[1] 李仁发[1] 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082

出　　处：《中国科学：信息科学》2012年第8期960-973,共14页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:60903019);湖南省自然科学基金(批准号:11JJ5039);广东省部产学研结合项目(批准号:2011B-090400060);湖南大学"青年教师成长计划"资助项目

摘　　要：网络虚拟化是克服当前Internet僵化问题的一种重要方法,而资源分配是网络虚拟化技术的核心.为了平衡负载,本文提出了一种启发式资源分配算法HVNE.该算法充分利用虚拟节点和虚拟链路间的关联因素(虚拟网络拓扑),将节点映射和链路映射两个过程合并为一个统一的过程,改善了传统映射算法在拓扑稀疏时,算法性能不理想的问题.此外,HVNE允许同一个虚拟请求中的多个虚拟节点映射到同一个物理节点,节约了物理链路资源.HVNE将无向图的"k-区域划分优化"理论与传统的拓扑分割理论相结合,定义了虚拟拓扑间节点的关联因子,改进了传统的星形分割方法,使之能适用于大规模网络.仿真实验表明,HVNE在保证网络负载的情况下,获得了较好的虚拟请求接受率,较高的资源利用率和网络收益.Currently network virtualization has been taken as an important role to overcome the problem of Internet ossification. Resource allocation is the core technology for network virtualization. A heuristic resource allocation algorithm named HVNE is proposed in order to balancing network load. By fully utilize the virtual network topology, the process of node mapping and link mapping can be merged together into a single process. In this case, even if in a sparse topology the algorithm can still achieve good performance. Besides, to conserve physical link resource, HVNE allows multiple virtual nodes mapped into a single physical node. HVNE made up a connection between the theory of k-regional divided optimization and traditional topology division theory. The proposed virtual network topology, as a correlation factor among the virtual topology, greatly improved the traditional star-division method which can be applied to the network of large scale. Simulation results show the better acceptance rate and higher resource utility can be acquired with a balanced network load.

关 键 词：网络虚拟化 资源分配 启发式算法 关联因子 负载均衡 拓扑 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]