多域虚拟网络映射算法研究

王 轩，杨龙祥

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

0 引 言

随着现阶段网络业务的不断多元化，传统的一个底层物理网络只承载一个业务需求的网络商业模式已经不再适用，不可避免地需要提出新的模式—网络虚拟化。网络虚拟化可以将一个底层物理网络实例化成虚拟网络(virtual network，VN)，优化布局达到配套服务指标。虚拟网络主要存在于底层物理网络之上，由一些有源和无源的网络单元(网络节点和网络链路)组成。虚拟节点通过虚拟链路连接，形成虚拟拓扑。资源虚拟化技术的引入可以允许网络运营商以一种高度灵活和动态的方式管理和修改网络[1]。

由于虚拟网络节点和链路必须要在满足用户需求并且最优化可用资源的情况下被映射到底层物理网络上[2]，因此出现了虚拟网络映射(virtual network embedding，VNE)问题。由于客观限制的存在(如资源位置、类型)，一个单独的InP可能并不能为虚拟网络提供足够的资源，根据在虚拟网络映射中底层网络提供商InP是否唯一，可以将虚拟网络映射问题分为单域映射和多域映射[3]。文中重点对多域虚拟网络映射问题进行研究。

1 多域虚拟网络映射

解决多域映射一种直接的思路是：服务提供商(SP)首先要与每个可能的InPs进行协商，然后决定各个InP映射整个虚拟网络的不同部分。这种方式可以在不改变传统商业模式的前提下，相对简单地完成对虚拟网络请求的映射，但是其缺陷在于会导致SP涉及与多个InPs的协商，不能满足功能分离的目标，而且会增加SP的开销[4]。针对这个问题，现有的多域映射解决方案主要采用如下两种网络商业模式。

其中一种模式的主要思路是为了避免SPs与InPs协商，扩展传统的商业模式(InPs和SPs)，引入虚拟网络提供商(VNP)这个中间角色，它的作用是收集、统计和分析底层物理网络的资源信息并且从服务提供商接收虚拟网络请求，然后将虚拟网络请求的不同部分分配给对应的InP进行域内映射[5-6]。为了确保VNP能进行有效的虚拟网络分解，许多文献都利用了一种新的信息共享方案，它需要InPs向VNP提供其物理资源的部分信息[7]，例如对等节点的位置以及对等链路的带宽成本，而不用披露InPs网络内的拓扑结构等信息，保护了InPs的机密。利用这种模式的多域虚拟网络映射算法的典型流程[8]如图1所示。

图1 多域虚拟网络映射算法典型流程

在这种模式下，由VNP代替SP，与各个底层网络提供商InPs进行映射协商，从而实现了网络功能的分离，并且减少了SP的开销。但是VNP必须知道各个InPs之间的内部细节和相互协定，才能做出一个信息全面的映射，但实际上VNP在获取资源信息时存在困难，并且可能还会出现VNP垄断虚拟网络映射的情况[9]。

针对利用VNP的网络商业模式存在的问题，一些文献提出了另一种多域映射模式，它不需要VNP作为中间商进行协调映射，而是允许各个InPs基于共同协定进行分布式映射，而且，在这种分布式的映射模式中将不再有单点的映射失败或者垄断权威(VNP)的存在[10]。

2 多域映射算法分类

基于当前多域虚拟映射的相关映射算法，文中提出一种分类方法，如图2所示。

图2 多域虚拟网络映射算法分类

首先根据是否需要VNP作为中间商进行协调映射，将多域映射算法分为集中式和分布式两类。随后，在集中式的多域映射算法中，根据分解虚拟网络请求时的方法不同，可以分为基于流量矩阵、基于拓扑结构和基于演进算法三类。基于拓扑结构研究多域映射的文章主要的研究方向有两类，一类着眼于对底层物理网络的抽象化，另一类则是通过VNP产生虚拟网络请求分段，再在每个InP上利用网络增广图分别进行映射。

在分布式多域映射算法中，根据映射算法的目标不同，可以分为基于市场的分布式映射和基于竞价的分布式映射。

2.1 集中式多域映射算法

2.1.1 基于拓扑结构

(1)抽象化映射。

有文献提出了将多域物理资源抽象化，从而使其看起来像是一个平面的网络底层结构。Vaishnavi等在文献[11]中扩展了该思想，提出了更先进的算法，从而使映射包括计算能力、存储以及网络资源的整个底层网络，将每个物理域看作是一个伪节点[12](pseudo-node)。抽象化完成后得到的伪图即可认为是一个正常的物理网络图，并且可以利用任何现存的虚拟网络映射算法对其进行映射，从而使得现存的映射算法仅需要少许改动即可重复使用。

除了文献[11]外，Baldine等[13]也提出了一种将底层网络提供商抽象化成节点的机制。基于虚拟图的min k-cut，将虚拟网络分解成子请求，尝试对每个子集使用子图同构算法，该过程如果失败则会重复进行。但其并没有给出算法实际的仿真结果，算法计算过程复杂，需要后续优化，并且没有考虑映射时间，静态的启发式算法对于动态环境也是不合适的。

(2)机制化映射。

与抽象化映射不同，机制化映射在完成虚拟网络请求分解后，需要利用每个InP的域内拓扑信息，一般会在虚拟网络请求分段映射中利用增广图以获取映射最优解，代表性的算法如下：

Shen Meng等[7]针对多域映射问题，提出采用一种估算方案来处理未知的域内拓扑，生成增广的网络图来协调节点映射和链路映射的方案,可以在多项式时间内解决虚拟网络请求。

Leivadeas等[14]为了解决多域资源映射固有的复杂性及可扩展性等问题，提出了一种请求分解方案—基于迭代本地搜索的元启发式算法，以一种能促进下一步虚拟链路映射到底层路径的方式，将虚拟节点映射到底层物理节点，进而实现成本的有效性，并且有助于在线分解网络云环境中云服务提供商之间的用户请求。

之后，Li Shuopeng等[15-16]着重考虑域内链路与域间对等链路的联合关系，协调并最优化域内和域间链路的映射。文中提出的算法在VN请求接受率、网络资源利用率以及收益方面都优于文献[7]中提出的方法，在现存的网络结构上更容易部署。

2.1.2 基于流量矩阵

现有的集中式多域映射算法都将所处理的虚拟网络拓扑请求假设为无相加权图[17]，虚拟网络拓扑会在虚拟网络映射中引入不必要的限制，利用虚拟网络拓扑的方式缺乏现实性[18]。从另一方面来说，服务提供商SPs也更希望将虚拟网络请求以一个较为抽象的形态进行分发，从而排除对任何虚拟网络拓扑特性的依赖。

因此，在文献[19]中，主要研究方向为有限信息披露下的多域VNE问题。文章讨论了VNP对底层物理网络资源的可见性，提出了基于流量矩阵的虚拟网络映射架构，从而能够利用线性整数规划解决虚拟网络请求分解问题。

为了克服文献[19]中虚拟网络请求分解和域内资源分配问题所耗费的大量时间复杂度的不足，Dietrich等[8]虽然也是采用流量矩阵来描述虚拟网络，但是放宽了在虚拟网络请求分解中的整数限制，从而降低了时间复杂度；放宽了域内资源分配中的整数限制，从而减少了运行时间。

然而上述算法缺乏对多域映射的有效性的考虑，于是Guo Kailing等[20]对此进行改进。在虚拟网络请求分解阶段，他们继承了Dietrich利用流量矩阵描述虚拟网络的思想，随后采用一种基于粒子群优化算法的启发式虚拟网络请求分解方法。与Dietrich提出的算法相比，该算法可以增加虚拟网络请求分解的有效性，其运行时间随虚拟请求节点的增加呈线性增加。

2.1.3 基于演进算法

近年来，研究者利用蚁群优化、颗粒群优化[21-23]、遗传算法[24]等演进算法，有效地解决了计算复杂的问题，这些问题包括调度问题、最小重量三角测量问题、二次阻塞分派问题等。因此针对虚拟网络映射问题，也可以利用演进算法进行解决。例如，文献[25]使用颗粒群优化算法，在平均收益、虚拟网络请求接收率的性能上优于Chowdhury等[26]提出的协调节点链路映射算法。文献[27]通过引入基于蚁群优化的元启发式算法，在服务质量QoS的性能上达到了最优化。文献[28]根据节点排序方法产生基于成本-带宽和基于马尔可夫随机游走的两类遗传算法，与文献[25]中的颗粒群优化算法相比，它们在底层网络提供商InPs的平均收益、请求接收率及收益成本比率等参数上具有更好的性能。

Isha等[29]提出利用遗传算法来解决多域虚拟网络映射问题，是当前应用演进算法解决多域映射问题的首次尝试。该算法与文献[30]中Houidi等提出的动态适应性映射算法相比，通过最大化底层网络的剩余资源，从而允许InPs具有更大的能力承载其他的虚拟网络请求，最终增加底层网络的利用率及InPs的收入。

在上一节基于流量矩阵进行多域映射中，Guo Kailing等[21]也利用了基于粒子群优化的演进算法对虚拟网络请求进行分解，从而增加虚拟网络请求分解的有效性。因此，也可以将其归为基于演进算法进行多域虚拟网络映射一类。

2.2 分布式多域映射算法

2.2.1 基于市场的分布式多域映射算法

Chowdhury等在文献[9]中引入了PolyViNE，是一个基于策略的端到端虚拟网络映射架构，可以用一个全局分布式的方式对跨越多个InPs的虚拟网络进行映射，同时能允许每个相关InP在各自的映射域内执行自己的映射策略。PolyViNE中很重要的一步就是转发(forwarding)，如果一个InP只能部分映射一个VN请求，那么它会在控制网络中，将剩余的请求转发给别的InPs，以完成整个VN请求。该方案通过运用经济学的market-based机制，在映射过程中的每一步都进行重复投标，以保证每个InP都能提供具有竞争性的价格，从而最小化SP的成本。

Yahaya等在文献[31]中也运用经济学基于市场的market-based机制，通过在参与的InPs之间进行协商自动地执行QoS策略，也允许域内策略的执行，这与PolyViNE类似。但是两者的区别在于，前者只关注映射简单的路径，而PolyViNE则致力于映射更复杂的虚拟网路请求。

基于对底层网络提供商InPs的隐私信息保护，Toru Mano等借鉴文献[32]中安全多方计算(multi-party computation，MPC)的思想，在文献[33]中使用一个MPC排序算法得到各个InP映射价格的排序，SP通过价格顺序选择能够映射整个虚拟网络的价格最优的映射方案。该方案是在运行时间和解的准确性之间的折中，因此得到的映射解是近似最优解，但是它有效地解决了大规模虚拟网络请求下进行快速、有效映射的实际问题，同时保护了各个InPs的机密信息。

2.2.2 基于竞价的分布式多域映射算法

Esposito等[10]针对虚拟网络映射分配问题，借鉴了有关一致性资源分配的文献，提出一种一般性的分布式一致性竞价机制(consensus-based auction mechanism for distributed slice embedding，CAD)。该算法的一般性在于通过调节策略，可以根据对应的分布式模型，支持广泛的应用和提供商的目标。算法过程如图3所示。

图3 CAD算法过程

文章通过将CAD映射方案与两个现存的分布式解决方案进行对比(PolyViNE[9]和分布式VNE算法[34])，发现一致性竞价机制具有更好的收敛特性和资源利用率。并且，作者证实了通过合理的策略设计，CAD算法可以适应不同SP和InPs的映射目标，从而为多域网络虚拟化提供了灵活的资源分配方案。

Esposito以CAD算法为基础，在文献中又补充了分布式路径竞价机制(path auction for distributed embedding，PAD)。在CAD的基础上要求物理节点尽可能承载邻近的虚拟节点，从而使得每条虚拟链路能够在单独的物理链路上分配资源，而不是被分配在任意一条无回路的物理路径上。这样做的好处在于，可以避免在无回路的物理路径上映射虚拟链路时引入中介物理节点。与文献[10]中的CAD算法相比，当需要映射的虚拟链路数量较大时，PAD具有更高的虚拟网络请求接收率。

Zaheer等在文献[35]中，依靠虚拟资源竞价(auction)的真实性，提出了V-Mart架构，利用两步Vickrey竞价模型，为VNP和InPs提供一个开放的市场模型以及一个公平的竞争环境。通过在参与的InPs之间进行竞价和协商，进行虚拟网络请求分解，解决多域虚拟网络映射问题。但是与文献[10]相比，V-Mart不能保证本地和InP之间的策略执行以及整体的资源利用率。Hausheer等在文献[36]中也运用基于竞价的机制，在网络虚拟化环境中进行资源交易，但只是基本解决了虚拟链路竞价问题。

Flavio Esposito等在文献[37]中，提出一种基于策略的(policy-based)虚拟网络映射架构VINEA。该算法的主要优点是将策略(高层目标)与底层映射机制(资源发现、虚拟网络映射、在物理网络上的分配)分离开，可以包含现存的映射方法，并且仅通过实例化不同的策略就可以将其用于设计适用于不同场景的虚拟网络映射解决方案。由于VINEA算法也是在一致性协商的基础上，以最大化底层物理网络的使用率为目标，从而最大化InPs的收入，这与作者和Zaheer等在文献[35-36]中提出的算法是一致的，因此文中也将VINEA算法归类为基于竞价的分布式多域映射。

表1为不同分类下典型算法的总结。

表1 典型算法总结

3 结束语

文中对当前多域虚拟网络映射算法进行了重点研究，从不同角度对现有几种主要的多域虚拟网络映射算法进行了系统分类，然后详细介绍了每种分类下的典型算法，并深入分析了各类算法的优缺点。

当前多域虚拟网络映射算法在虚拟网络请求接收率、网络资源利用率以及映射成本及收益等性能指标上都可以达到最优或者次优的映射结果，通过对底层网络的抽象化以及演进算法等方案也可以在解的准确性和运算时间上达到折中，但多域映射的研究仍旧有很大的发展空间，未来的研究方向可以关注以下两个方面：

(1)集中式多域映射：VNP从InPs获取的信息量越多，映射求解时间则越长，但是解的准确性也会随之增加，这需要映射算法进行平衡；在有限信息披露下的多域映射问题处理的是静态资源信息，而在实际的虚拟网络映射中，需要能根据当前网络资源的变化动态调整参数的自适应映射算法，对虚拟网络请求进行重映射，从而提高底层物理网络的利用率以及虚拟网络请求接收率。

(2)分布式多域映射：映射算法中的价格模型、各个InPs之间的交互、信誉管理以及如何对参与的InPs给予一定的激励策略等问题仍旧有很大的研究空间；映射算法的扩展性、稳定性需要在具有不同域内虚拟网络映射算法的InPs之间，通过更大的仿真和分布式实验进行探究。