虚拟网络映射算法与机制研究

现今互联网表面的繁荣之下暗藏着日趋严重的网络僵化危机,阻碍了网络服务和应用的进一步发展创新,因此全新的下一代网络体系架构已成为近年来全球学术界研究的热点。作为下一代网络体系架构的核心技术和关键属性,网络虚拟化通过将物理网络资源抽象为虚拟网络资源切片的方式,为多个相互隔离且异构的虚拟网络同时运行在一个共享的底层网络上提供了一个有效的解决办法。网络虚拟化中一个长期存在的核心问题和关键挑战是虚拟网络映射问题,即如何有效且高效地将异构虚拟网络的节点和链路分别映射到共享底层网络的特定节点和链路上。本文主要围绕网络虚拟化中的虚拟网络映射问题,在算法和机制等方面做出了以下一些工作:(1)对虚拟网络映射问题的商业角色与模型、问题建模和研究现状进行了综述研究。水平维度上业务逐渐融合的下一代网络将在垂直维度上进行更加深入的角色解耦,因此本文提出了一个针对网络虚拟化环境以及虚拟网络映射问题的改进的五层商业模型,用以指导问题研究与算法设计。同时对虚拟网络映射问题从虚拟网络、底层网络、映射函数、求解目标等各方面进行了完整建模。对国内外学术界关于虚拟网络映射问题的研究现状,特别是近年来已有的虚拟网络映射算法则按照多种分类方式进行了较为深入的分析归纳总结。通过研究已有算法和机制的不同类型、特点与优势,及其存在的问题和瓶颈,从中寻找提高虚拟网络映射算法性能的研究方向,指导新算法的设计。(2)针对已有虚拟网络映射算法只考虑单一拓扑属性、对网络拓扑属性利用不足而导致映射性能降低的弊端,提出了一种基于多个拓扑特征值的拓扑感知的虚拟网络映射算法。七个互补的反映不同网络拓扑属性的拓扑特征值被引入虚拟网络映射问题,包括“度”、“强度”、“远离中心性”、“接近中心性”、“中间中心性”、“特征向量中心性”和“卡茨中心性”。不同的拓扑特征值从各自不同的角度衡量了底层或虚拟节点的相对重要程度和影响力,多种基于多个特征值的节点排序算法进而被相应地设计提出,以充分发挥不同特征值各自的特点和优势。基于度与强度这两个拓扑特征值的改进的K核分解算法则从另一个角度被提出,以利用多拓扑特征值更好地解开虚拟网络拓扑的层次化结构,优化映射过程。由于全面考虑了底层网络和虚拟网络的拓扑属性,基于多拓扑特征值的拓扑感知的虚拟网络映射算法更好地协调了节点映射和链路映射,实验仿真也证明了其相比先前算法明显提高了长期的平均收益、接受率和成本收益率。(3)针对传统虚拟网络映射算法没有考虑到先前虚拟网络请求与待映射虚拟网络请求的相互联系,以及已映射节点与待映射节点之间的拓扑关系的弊端,提出一种基于学习与依赖度的虚拟网络映射算法。新算法通过收集、处理、分析虚拟网络成功以及失败映射的历史数据,生成依赖矩阵表征每个底层节点自身的重要程度和它们两两间的拓扑关系,即底层网络的“依赖度”,以此取代经典的资源评价指标,实现对底层网络资源能力的拓扑感知的评价。通过充分考虑已映射节点与待映射节点之间的拓扑关系,该算法同时利用了贝叶斯推理为每个虚拟节点判决选择合适的底层节点进行映射,以此替代传统的贪婪匹配策略。这种基于学习与依赖度的虚拟网络映射算法实现了拓扑感知的节点映射,能够减少不必要的带宽消耗,减轻网络的碎片化程度,实现节点映射和链路映射的优化选择。实验仿真也证明了该算法的有效性,显示出其相比先前算法具有更好的映射性能。(4)针对现有集中式虚拟网络映射算法与分布式虚拟网络映射算法各自固有的优势和弊端,提出了一个协同的虚拟网络映射算法与机制。新的协同算法保留了集中式算法中拥有全局视野的中心控制器,负责整体管理和控制,同时将具体映射方案的计算过程交给底层网络节点以分布式的方式自主实现。该算法在实现拓扑感知的资源评价机制和基于布隆过滤器的映射信息传递机制的同时,设计了协同的映射管理策略。负载减轻的中心控制器与承担一部分映射任务的各底层节点相互配合紧密协作,共同完成虚拟网络映射的整个过程。协同算法同时继承了集中式算法和分布式算法各自的相对优势,其可行性、有效性和优于已有算法的性能也在实验仿真中得到了验证。