一种基于约束优化的虚拟网络映射方法  

A Constraint Optimization Based Mapping Method for Virtual Network

作　　者：李小玲[1] 郭长国[1,2] 李小勇[1] 王怀民[1] 

机构地区：[1]国防科学技术大学计算机学院并行与分步处理国家重点实验室,长沙410073 [2]中国电子设备系统工程公司,北京100039

出　　处：《计算机研究与发展》2012年第8期1601-1610,共10页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(2011CB302601);国家"八六三"高技术研究发展计划基金项目(2007AA010301;2009AA01Z142);国家自然科学基金项目(90818028)

摘　　要：虚拟网络映射问题将不同的虚拟网络应用映射到相同的基础设施网络中,这是一个极具挑战性的问题.针对该问题,提出了一种基于约束优化的虚拟网络映射方法,将映射问题分解为节点映射和链路映射两个阶段,其中,前者是将虚拟节点映射到物理节点上,后者将虚拟链路映射到物理路径上,它们都是NP难问题.针对节点映射和链路映射分别提出了node-mapping算法和link-mapping算法.node-mapping算法基于贪婪算法的思想,映射时考虑了物理节点所能提供的资源数量以及物理节点间距离两个因素,该算法能够保证基础设施网络中各节点间的负载相对均衡;同时,通过采用访问控制机制,过滤一些异常的虚拟网络请求,能够有效地提高资源的使用效率.link-mapping算法基于人工智能领域中的分布式约束优化思想,其能够保证得到的解是全局最优的,即映射链路的代价最小.最后,通过模拟实验对该方法进行验证,实验结果表明该方法在求解虚拟网络映射问题时的性能良好.Virtual network mapping problem, which attempts to map different virtual networks on the same substrate network, is an extremely challenging problem. A constraint optimization based mapping method is proposed to solve the problem. In this method, the process of solving the problem is divided into two phases, node mapping phase and link mapping phase, which are all NP-hard. The former phase maps the virtual nodes to the substrate nodes, and the latter phase maps the virtual links to the substrate paths. Node-mapping algorithm and link-mapping algorithm are proposed to solve the node mapping phase and the link mapping i^hase, respectively. Node-mapping algorithm adopts the thinking of greedy algorithm, mainly considering the available resources which are supplied by substrate nodes and distances among the nodes, in order to maintain load balancing. Meanwhile, an access control mechanism is also proposed to filter the unmoral virtual networks for the purpose of increasing the resource utilization. Link-mapping algorithm is based on the result of node mapping phase, and it adopts the thinking of distributed constraint optimization problem in artificial intelligence. The algorithm can guarantee the optimal solution, namely the minimum cost of mapping the virtual links. Finally, simulation experiments are conducted and the results show that the method performs very well.

关 键 词：虚拟网络映射问题 节点映射 链路映射 分布式约束优化 基础设施网络 虚拟网络 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]