面向底层单节点失效的轻量级可靠虚拟网络映射算法  

Less Stringent Reliable Virtual Network Mapping Algorithm for Substrate Single Node Failure

作　　者：刘光远[1] 苏森[1] 

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室,北京100876

出　　处：《电子与信息学报》2013年第11期2644-2649,共6页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61170274);国家973计划项目(2011CB302506);工业和信息化部国家科技重大专项(2011ZX03002-001-01);国家自然科学基金委创新研究群体项目(60821001);河北省自然科学基金(F2011402028)资助课题

摘　　要：网络可靠性是虚拟网络设计的一个重要指标,目前得到了越来越多的关注。该文对轻量级可靠的虚拟网络映射问题进行研究。目标是不预留底层网络保护资源,当底层物理网络单节点失效时,虚拟网络拓扑除失效虚拟节点外仍保持连通,将损失降到最小。文章首先给出了存在轻量级可靠虚拟网络映射可能的必要条件并加以证明,然后基于此条件对面向底层单节点失效的轻量级可靠虚拟网络映射问题进行整数线性规划建模,最后设计了一种新的启发式算法对其进行求解。该算法包括拓扑感知的虚拟节点映射策略和一种基于禁忌搜索(tabu search)算法的虚拟链路映射策略。模拟实验结果表明,该文提出的算法在得到轻量级可靠虚拟网络映射的同时,仍能获得较高的底层网络长期运行平均收益和底层网络资源利用率。Network reliability is one of the most important performance in the design of Virtual Network （VN） and gaining more and more attention currently. This paper focuses on the issue of less stringent reliable virtual network mapping. The VN topology remains connected except failed virtual node in the event of single substrate node failure without reserving backup resources. The necessary conditions for mapping VN to be reliable are researched at first, and then the issue is formulated as an Integer Linear Program （ILP） based on it. Finally a novel heuristic algorithm is proposed to solve it. The policy consists of a topology-aware node mapping strategy and a link mapping strategy based on tabu search. Evaluation results show that the proposed heuristic algorithm can obtain the reliable VN mapping with higher substrate long-term average revenue and efficient resource utilization.

关 键 词：虚拟网络映射 轻量级可靠 单节点失效 整数线性规划 启发式算法 

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