可生存性虚拟网络映射算法的研究

黄丽萍，杨龙祥

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

网络虚拟化技术被视为是构建新一代网络的重要技术，可以有效解决网络的“僵化”问题[1-4]。在网络虚拟化环境下，传统的网络服务运营商被分为两个角色[5-6]，即底层网络运营商和服务运营商。在网络虚拟化中，主要实体是虚拟网络。虚拟网络由虚拟节点和虚拟链路两部分组成，虚拟节点间通过虚拟链路相互连接，每个虚拟节点和虚拟链路拥有与物理节点和链路相同的属性。因此，如何有效地分配物理资源给不同的虚拟网络，即虚拟网络映射问题,是网络虚拟环境下必须解决的难题。该问题已被证明为NP-hard问题[7-9]。为了提高底层网络运营商的收益，很多研究主要集中于提高虚拟网络映射的成功率和底层网络资源的利用率等方面。

然而，底层网络很容易出现故障。所以，在找到一个有效的虚拟网络映射方法之后，保证虚拟网络的可生存性也是非常重要的[10]。针对虚拟网络的可靠映射问题，目前主要有两种机制，分别是保护和恢复机制[11]。故障保护机制是一种预先准备的方式，在故障发生之前就预先保留一定的备份资源。相反，恢复机制则是在故障发生之后，启动备份恢复机制。为了对可生存性虚拟网络映射问题的研究提供一个全面的视野，文中从问题定义、存在挑战、映射目标等方面对可生存性虚拟网络映射问题的不同研究算法进行综述。在按照算法不同特性进行分类和讨论的基础上，对几种典型的算法进行比较分析，并据此指出未来的研究趋势。

1 虚拟网络映射问题描述

1.1 底层网络

1.2 虚拟网络请求

1.3 虚拟网络映射

如图1(a)所示，虚拟网络请求的节点映射方案分别是{a→C,b→D,c→A}，链路方案是{(a,b)→(C,D),(a,c)→(C,A),(b,c)→(D,A)}。节点和链路的分配同时满足虚拟网络请求的约束条件。

1.4 可生存性的虚拟网络映射

当一个底层单节点失效时，其周围相连的链路也随即失效，这会导致映射到这些底层链路上的多条虚拟链路同时失效，从而使已经映射的虚拟网络不能继续工作(如图1所示)。图1(a)是一个成功的虚拟网络映射。节点和链路映射方法分别是：{a→C,b→D,c→A}和{ab→CD,ac→CA,bc→DA}。虚拟网络的节点和链路约束都满足。图1(b)表示的是当底层节点D发生故障时，一个可存活的虚拟网络映射方法。虚拟节点迁移到底层节点E上。与b相连的虚拟链路ab和bc分别重新映射到(CG)和(CH,HE,EB)上。经过节点迁移和链路重新映射，虚拟网络重新恢复正常。

图1 虚拟网络映射实例

2 可生存的虚拟网络映射算法

可生存性虚拟网络映射算法(SVNE)的主要目的就是在底层网络节点或是链路出现故障后，能够保证运行在底层网络上的虚拟网络的可生存性。图2是对现有的SVNE研究算法的分类树。文献[12]主要解决底层网络中单个节点的故障；文献[13]则集中在单条链路故障问题。文献[14-15]则分别从经济效益和地点约束进行研究。文献[16]研究了在SVNE中的资源分配效率问题。目前解决可生存性的虚拟网络映射问题主要是提供备份资源。文献[17]提出共享备份方案，允许多条虚拟链路共享分配的备份资源。本节将基于图2的分类，阐述当前为解决SVNE问题所提出的算法。

图2 可生存的虚拟网络映射算法分类

2.1 基于提供备份资源的SVNE

目前主要解决SVNE的方法是分配备份资源。文献[17]提出强生存性和弱生存性。弱生存性只能保证虚拟节点在故障出现的时候保持连接，而强生存性则可以保证原始的虚拟网络拓扑在发生故障时保持连通。

文献[17]为了从底层链路故障问题中快速恢复，使用了两种类型的恢复方法，即链路(局部)恢复和路径(端到端)恢复。该文提出一种混合策略启发式算法(hybrid policy)解决SVNE。该算法分为三个分离的阶段。第一阶段是在虚拟网络请求到来前，基础设施供应商使用路径选择算法预先为每一条底层链路计算一组可能的备份绕道。第二阶段是当虚拟网络请求到达时，使用现存的启发式算法执行节点映射和链路映射。最后一个阶段是当底层链路出现故障时，启动备份绕道优化方法，在第一阶段选择的候选备份绕道路径中为受到影响的链路重新路由。该算法降低了计算复杂性，在接受率、收益、带宽效率、执行时间等方面都比一般算法优异。

文献[18]针对多个节点故障提出了基于拓扑意识的SVNE算法。该算法分为三个阶段。第一阶段是虚拟网络请求到来前，预先分配了专用的备份定额，为每个底层节点创建了一个候选集。第二阶段是虚拟网络请求到来时，使用基于恢复性的虚拟网络映射来分配虚拟网络主要资源，虚拟网络中的重要虚拟节点要被映射到可恢复性更好的底层节点上。第三阶段是当底层节点发生故障时，启动利益驱动的再映射算法，恢复尽可能多的受影响的虚拟网络。

文献[19]提出一种基于底层资源的负载平衡的分配资源的方法和重新配置备份资源的策略。为了确保从底层链路故障中的成功恢复，对于任意一条虚拟链路，一条带宽等于主要链路的备份链路也被映射到底层链路中，和主要路径不重叠。不同的备份路径可以在同一条底层链路上共享相同的备份带宽资源。在故障发生前，备份路径上是没有数据传输的，所以可以尝试用备份流去接受第一次未被接受的VN。该算法的本质是重新配置备份资源从而提高接受率。通过这种方式，可以根据自己的需求重新配置，删除和添加备份资源。相比于主要资源的迁移，备份资源的重新配置更加简单且风险低，同时也提高了资源的利用率。

2.2 基于无备份资源的SVNE

为了保证虚拟网络的可生存性，之前的很多研究工作都是通过给虚拟网络分配备份资源。这种方式虽然保护了虚拟网络，但是会增加基础设施提供商的成本。以降低基础设施提供商的成本为目标，许多研究提出在不预备备份资源的前提下解决可生存的虚拟网络问题。

文献[20]提出一种两步策略。第一步是预防策略，第二步是恢复策略。在第一步中，通过将每一条虚拟链路映射到多条路径上，减轻由底层故障产生的损害，防止虚拟链路失去全部的容量。这一步需要解决VNE问题，通过使用模拟退火法，可以找到全局最优解。该算法通过迭代产生可能的映射，直到达到最大的迭代次数K。在每次迭代中，通过将它和几个相似的方法进行比较，从而改善当前的方法。在第二步中，提出容量恢复策略。该策略代替分配备份资源，而是将受到损害的虚拟网络链路重新分配到未受到影响的路径上。该路径必须是在第一步中被选来用于分配虚拟链路或是在运行过程中未受到影响的路径。该算法与提供备份资源相比，降低了基础设施提供商的成本，同时还提高了虚拟网络的接受率。

文献[21]提出一种基于节点迁移和链路再映射的启发式可生存虚拟网络映射算法(SVNE-NOLR)。该算法不会预先为虚拟网络分配备份资源，而是采用具有全局寻优能力的人工蜂群算法求取近似最优解[22]。如果底层节点发生故障，则使用贪婪算法将受到影响的节点迁移到正常节点上，然后使用Dijkstra最短路径算法重新映射受到故障影响的虚拟链路。该算法没有预留备份资源，不会产生资源的冗余，并且提高了虚拟网络请求的接受率和虚拟网络的恢复率，同时改善了底层网络的负载强度。

2.3 典型可生存虚拟映射算法的比较总结

综上所述，SVNE算法目前主要是从两个方向进行研究，一个方向是提供备份资源，在故障发生时立即调度该备份资源，从而恢复受到影响的虚拟网络。提供备份资源也有两种方式：第一种是主动式的。在故障发生前，准备好足够的备份资源；第二种是反应式的。当故障发生时，根据其需要提供备份资源。另一个方向是不提供备份资源，而是通过节点迁移和链路再映射或是路径映射等方式恢复受到影响的虚拟网络。表1为不同分类下典型算法的比较总结。

表1 典型算法比较总结

3 总结与展望

主要讨论了虚拟网络映射的可生存性问题，即如何使虚拟网络从底层节点或链路故障中快速恢复，并且对现有的一些解决算法进行总结分类。目前，一大部分研究主要是基于提供备份资源来保证虚拟网络的可生存性。当故障发生时，启动备份恢复机制，为受到影响的虚拟节点或是链路提供备份资源，保证虚拟网络的连通性。还有一些研究是基于无备份资源的前提下保证虚拟网络的可生存性。但是在现有的研究中，依然存在一定的局限性。

(1)大部分研究只考虑单个底层节点故障或是单条链路故障的情况。目前提出的一些算法能够很好地解决底层网络单点故障的问题，完全恢复受到影响的虚拟网络，但是如果发生了底层网络多点故障，则只能恢复一部分受到影响的虚拟网络，算法的性能大大下降。

(2)资源利用率不高。提供备份资源一般有两种方式，一种是在映射前预备足够的备份资源，一种是在发生故障时提供相应需求的备份资源。第一种方法易造成资源闲置，产生浪费。第二种易造成备份资源不足，影响虚拟网络的恢复。这两种方法都使得资源利用效率不高。

未来的研究方向可以关注两个方面：

(1)多个节点故障和多条链路故障问题。大部分研究的前提还是针对底层网络中单点故障提出的。现有方案虽然可以保证在底层单条链路故障的情况下完全恢复受到影响的虚拟网络，但是当出现多条链路故障时，恢复率会下降，不能保证提供完全的可生存性。

(2)无线虚拟网络映射[23-24]的可生存性问题。无线网络和有线网络的区别主要在于无线链路的广播特性，因此无线链路之间存在干扰。无线网络中的节点还存在移动性，影响已成功映射的虚拟网络的服务质量。所以，当无线底层网络中出现故障时，如何保证虚拟网络的可生存性是未来研究的方向之一。

4 结束语

虚拟网络映射的可生存性问题作为网络虚拟化环境下的重要问题已经受到研究者的广泛关注，找到一种可靠的算法能够在底层网络发生故障时保护受到影响的虚拟网络存在许多挑战。例如针对底层节点故障提出的预留备份资源方案和节点迁移方案，这些方案的目的都是为了保证底层网络发生故障时虚拟网络能够快速恢复。但从整体上讲，目前该领域的发展还未成熟，从理论到具体应用还有很大的差距。

文中对已有的SVNE算法进行研究，提出一种全新的分类方法，详细介绍了每一类算法的典型方案，并进行对比总结，最后指出SVNE问题未来的研究方向。