一种基于虚拟网络分割的虚拟网络改进映射方法

摘要

本发明公开了一种基于虚拟网络分割的虚拟网络改进映射方法，通过将一个大的虚拟网络分割成多个关联尽量少的子虚拟网络，各个子虚拟网络之间由若干虚拟链路连接，然后再使用现有的虚拟网络映射方法进行映射。通过本发明的改进映射策略，可以明显改善现有一些虚拟网络映射方法映射规模较大的虚拟网络所造成的映射时间长，映射代价大等问题，同时本发明为大型虚拟网络的映射提供了一个解决方法。

说明书

技术领域

本发明涉及网络技术领域，具体涉及一种基于虚拟网络分割的虚拟网络改进映射方法。

背景技术

当前网络架构僵化问题日益严重，使得难以提供差异化的网络服务，如IP网络提供尽量而为的服务模式，虽然多种技术被提出以及解决差异化服务问题如VPN，但还是有所欠缺。

随着云计算的发展，IT设备逐渐由少数设备提供商提供，服务提供商只需要根据自己的应用规模向设备提供商申请所需的IT资源，而且可以随时更改自己申请的IT资源的规模，因此云计算的发展能够为服务提供商提供方便快捷的计算服务，而且能够降低服务提供商的操作成本，提高他们的服务开发效率。虚拟化技术是目前云计算环境下实现云计算资源最大化利用的一种重要手段，然而现有的资源分配方式主要是提供虚拟机实例，缺乏对网络资源的有效管理，导致一些对网络资源敏感的应用难以获得稳定的网络资源而获得较高的运行效率。

网络虚拟化技术是对网络的一种抽象技术，以解决现有网络僵化问题，提供灵活可变的虚拟拓扑网络，使得多个用户的个人虚拟网络共存于同一物理网络。网络虚拟化技术需要解决的重大问题就是虚拟网络的映射问题，而虚拟网络的映射问题主要解决在提供可靠的网络服务的前提下如何最有效地利用底层物理网络资源。

目前很多基于整数规划的虚拟网络映射算法，如《Avirtualnetworkmappingalgorithmbasedonintegerprogramming》(JournalofZhejiangUniversitySCIENCEC,2013,14(12):899‐908)，能够得到比较好的映射结果，但是该类映射算法所需要的映射计算时间与虚拟网络的规模一般成指数增长关系，因此当虚拟网络的规模大到一定程度后，该类映射算法可能无法在要求的时间内，将用户请求的虚拟网络映射到底层物理网络；对于网络动态变化较大的底层物理网络而言，如果映射计算所需的时间较长，那么即使得到映射结果，但是底层物理已发生较大变化，因此得到的映射结果也是无效的。目前很多基于网络节点排名的启发式虚拟网络映射算法，如《TopologicalEmbeddingFeatureBasedResourceAllocationinNetworkVirtualization》(MathematicalProblemsinEngineering,2014,2014)，能够在较短的时间内完成虚拟网络的映射，但是该类映射算法中虚拟节点的映射一般是根据节点的排名确定的，没有考虑虚拟节点之间的连接特性以及相对距离，而且映射时优先选择与已映射节点距离较近的物理节点，那么很有可能将两个本来距离相距较远的虚拟网络节点映射到两个相距较近的物理节点之上，使得映射过于“拥挤”，导致较大的映射代价，甚至较低的虚拟网络请求接收率，因此为了削弱虚拟节点之间的连接特性以及相对距离对该类映射算法的影响，就需要控制虚拟网络的规模在一定范围之内。

发明内容

本发明的目的是提供一种基于虚拟网络分割的虚拟网络改进映射方法，以克服现有技术的全部或部分缺陷。

为了实现上述目的，本发明的一种基于虚拟网络分割的虚拟网络改进映射方法包括以下步骤：

1)预判阶段

如果待分割的虚拟网络的节点个数大于N，则执行步骤2)；否则，即待分割的虚拟网络的节点个数小于等于N，则执行步骤6)。

2)粗化阶段

如果待分割的虚拟网络的节点个数小于2*N，那么待分割的虚拟网络最粗化的虚拟网络为自身，此时m等于0，接下来执行步骤3)；否则，即待分割的虚拟网络的节点个数大于等于2*N，则将待分割的虚拟网络转化成一系列与其拓扑特性相似但规模递减的虚拟网络，并最终得到待分割的虚拟网络最粗化的虚拟网络具体为：

在当前虚拟网络中寻找极大匹配，并在寻找当前虚拟网络极大匹配的过程中不断合并匹配的节点对得到一个新的多重节点，该多重节点的权重等于匹配的节点对的权重之和，如果该多重节点与其任意一个邻接节点之间包含N条虚拟链路，其中N＞1，那么将这两节点之间的N条虚拟链路合并为一条多重虚拟链路，然后根据计算虚拟链路集合的分割映射代价的方法计算这N条虚拟链路的分割映射代价，设置该多重虚拟链路的权重为这N条虚拟链路的分割映代价的值；当得到当前虚拟网络的极大匹配，即当前虚拟网络中不存在未匹配的节点对时，即可得到下一级粗化的虚拟网络。

如果得到的虚拟网络的节点个数大于等于2*N，则用上述处理当前虚拟网络的操作处理得到的虚拟网络，直到得到的虚拟网络的节点个数小于2*N；最终得到的节点个数小于2*N的虚拟网络即为待分割的虚拟网络最粗化的虚拟网络

3)初始划分阶段

步骤a)随机从虚拟网络中选取1个节点v_start作为扩展分区G_sub的扩展起点，也就是说扩展分区G_sub最初只有一个随机选取的节点v_start；

步骤b)查找虚拟网络相对于当前扩展分区G_sub的前端节点集合

步骤c)依次假设将前端节点集合中的一个节点加入到当前扩展分区G_sub，然后查找虚拟链路切割集根据计算虚拟链路集合的分割映射代价的方法计算虚拟链路切割集的分割映射代价；最后选择前端节点集合中使虚拟链路切割集的分割映射代价值最小的节点真正加入到当前扩展分区G_sub；

步骤e)如果当前扩展分区G_sub中的节点的个数小于虚拟网络的节点的个数的一半，则返回执行步骤b)；否则，即当前扩展分区G_sub中的节点的个数大于等于虚拟网络的节点的个数的一半，则执行步骤f)；

步骤f)对得到的划分进行合并调优，具体为：遍历虚拟网络中所有虚拟链路，如果被访问的虚拟链路的一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，如果该不属于当前扩展分区G_sub的端节点的度值为1的话，就将该不属于当前扩展分区G_sub的端节点加入到当前扩展分区G_sub。

4)细化阶段

将步骤3)初始划分阶段中得到的虚拟网络的两路分割映射回待分割的虚拟网络的两路分割，使用Kernighan‐Lin算法进行调优，取得划分的局部最优值。

5)递归阶段

分别对步骤4)细化阶段中得到的待分割的虚拟网络两路分割后的两个虚拟网络执行如下操作：

如果虚拟网络的节点的个数大于N，那么将该虚拟网络作为新的待分割虚拟网络，并返回步骤2)；否则，虚拟网络的节点的个数小于等于N，那么结束对该虚拟网络的分割。

6)映射阶段

使用现有的虚拟网络映射方法映射所得到的节点个数小于等于N的虚拟网络。

进一步地，本发明通过在当前虚拟网络中寻找极大匹配方法为最大亲密度匹配方法，所述的最大亲密度匹配方法包括如下步骤：

步骤i)如果当前虚拟网络的节点个数小于等于2*N，那么结束粗化阶段，当前虚拟网络即为待分割的虚拟网络最粗化的虚拟网络其中如果待分割的虚拟网络的节点小于等于2*N，那么待分割的虚拟网络最粗化的虚拟网络即为本身；否则，即当前虚拟网络的节点个数大于2*N，则执行步骤ii)；

步骤ii)以随机的顺序访问当前虚拟网络中的节点，然后对每一个被访问的节点执行步骤iii)和iv)；

步骤iii)如果被访问的节点v未匹配，而且节点v还有未匹配的邻接节点，那么计算节点v与其所有未匹配的邻接节点的亲密度，然后选择与节点v亲密度最大的未匹配的邻接节点v′作为节点v的匹配节点；合并匹配的节点对v′和v为一个多重节点v_new，多重节点v_new的权重等于匹配的节点对v′和v的权重之和；如果多重节点v_new与其任意一个邻接节点之间包含N条虚拟链路，其中N＞1，那么将这两节点之间的N条虚拟链路合并为一条多重虚拟链路，然后根据计算虚拟链路集合的分割映射代价的方法计算这N条虚拟链路的分割映射代价，设置该多重虚拟链路的权重为这N条虚拟链路的分割映代价的值；将节点对v′和v设置为匹配状态；

步骤iv)如果被访问的节点v已匹配，或者在被访问的节点v未匹配情况下，节点v没有未匹配的邻接节点，那么节点v的匹配查找过程结束。

进一步地，本发明所述的计算节点v与其所有未匹配的邻接节点的亲密度的公式为：

$>\kappa (n_1^v,n_2^v)=(2/\pi \arctan (\frac{C_{n_1^v}{C}_{n_2^v}}{{\left(Max\right(C_n^v)/\lambda )}^2})+1)*BW(n_1^v,n_2^v)---\left(2\right)$>

其中，表示虚拟网络邻接节点对的亲密度；分别表示虚拟节点请求的CPU资源，表示虚拟链路请求的带宽资源；表示由物理网络设备提供商预先设定的虚拟节点请求的CPU资源的最大值；λ为压缩常数，取值为4。

进一步地，本发明所述的计算虚拟链路集合的分割映射代价的方法为：

当虚拟链路集合只包含一条虚拟链路时，虚拟链路集合的分割映射代价等于该虚拟链路的权重；

当虚拟链路集合包含二条虚拟链路{e₁、e₂}时，虚拟链路集合的分割映射代价的计算公式为：

$>MC=w_{e_2}+\frac{1+\frac{w_{e_2}-w_{e_1}}{w_{e_1}+w_{e_2}}}{2}{w}_{e_1}=(1+\frac{w_{e_1}}{w_{e_1}+w_{e_2}})w_{e_2}---\left(1\right)$>

其中，MC表示虚拟链路集合的分割映射代价，分别表示虚拟链路e₁、e₂的权重；

当虚拟链路集合包含多条虚拟链路时，虚拟链路集合的分割映射代价的计算方法如下：

按顺序从当前虚拟链路集合中取出两条虚拟链路，并利用公式(1)计算这两条虚拟链路的分割映射代价，然后将一条权重为这两条虚拟链路的分割映射代价值的虚拟链路按顺序插入到当前虚拟链路合中；重复以上过程，直到当前虚拟链路集合中只有一条虚拟链路，最后虚拟链路集合的分割映射代价等于虚拟链路集合中最后一条虚拟链路的权重。

进一步地，本发明所述的查找虚拟网络相对于当前扩展分区G_sub的前端节点集合具体为：遍历虚拟网络中所有虚拟链路，如果被访问的虚拟链路的一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，那么将该虚拟链路中不属于当前扩展分区G_sub的一端节点加入到前端节点集合

进一步地，本发明所述的依次假设将前端节点集合中的一个节点加入到当前扩展分区G_sub，然后查找虚拟链路切割集具体为：遍历虚拟网络中所有虚拟链路，如果被访问的虚拟链路的一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，那么将该虚拟链路加入到虚拟链路切割集

与现有技术相比，本发明的有益效果如下：

通过本发明的改进映射策略，可以明显改善现有一些虚拟网络映射方法映射规模较大的虚拟网络所造成的映射时间长，映射代价大等问题，同时本发明为大型虚拟网络的映射提供了一个解决方法。

附图说明

图1是本发明的虚拟网络改进映射方法的流程示意图；

图2是一个虚拟网络实例的示意图。

图3‐6是本发明使用改进的图分区贪婪式扩展划分算法对图2所示虚拟网络实例划分过程中产生的过程图；

具体实施方式

虚拟网络的分割问题类似于图的划分问题，但是又有所不同。图的划分问题最初应用于科学计算、超大规模集成电路设计、任务调度等领域，后来在图像分割、机器学习等领域也有较广泛的应用。对于无权图而言，图的划分问题主要目的在于将图中的节点分割成若干节点数目大致相同的集合，使得跨越这些集合的链路总数最小；对于有权图而言，不同的是使得跨越这些集合的链路的权重之和最小。无论是链路总数最小还是链路的权重之和，目的是为了使得划分后集合的之间的关联最小。局限于特定的应用，有权图的划分问题，仅仅是使得权重之和最小，而不必考虑分割链路的数量对应用的影响。如多核并行计算应用中涉及的图的划分问题：一个计算任务可以并行地看作由若干个子任务共同完成，每个子任务并不是完全独立地运行，可能需要相互通信，为了均衡而且高效地利用一台计算机上有限的多核资源，将一个计算任务的多个子任务分配给这些核后，各个核所接收的子任务构成不同的子任务集合，如果子任务集合之间关联越小，那么多核之间地通信量也就越少，越有利于计算任务的并行执行，那么任务的执行效率也会越高。任务划分的好与差一般取决于多核之间总的通信量，与具体子任务之间的关联基本无关。

由于虚拟网络的每条虚拟链路都需要独立映射，而且根据基于路径可分的虚拟网络映射方法的思想可知，当一条虚拟链路可被映射到多条物理路径时，不仅有利用于均衡物理网络负载而且能够明显提高虚拟网络请求的接收率《Rethinkingvirtualnetworkembedding:substratesupportforpathsplittingandmigration》(ACMSIGCOMMComputerCommunicationReview,2008,38(2):17-29)，因此虚拟网络分割的好与差不仅取决于切割集中虚拟链路的权重之和，而且还取决于切割集中虚拟链路的数量及分布，所述切割集是指所有跨越划分后得到的多个子虚拟网络之间的虚拟链路所构成的虚拟链路集合，可见虚拟网络的分割问题比图的划分问题更复杂。在切割集中的虚拟链路的权重之和相同的情况下，理应选取虚拟链路条数越多，而且虚拟链路权重分布更均匀的分割方案。由于图的划分问题是一个NP难问题，因此类似于图的划分问题的虚拟网络分割问题也是一个NP难问题。在实际分割问题中不可能计算所有的分割方案，再从中选取最优的分割方案，因此本发明也只是试图寻找一个虚拟网络的分割映射代价尽量小的分割方案。

虚拟网络的分割映射代价与虚拟网络实际映射代价是不同的，分割映射代价只是作为虚拟网络分割好与差的一个评价标准，本发明对一个由若干条虚拟链路构成的虚拟链路集合的分割映射代价作以下计算规定，其中下述虚拟节点的权重即为虚拟节点请求的CPU资源，虚拟链路的权重即为虚拟链路请求的带宽资源：

1.当虚拟链路集合只包含一条虚拟链路e时，虚拟链路集合的分割映射代价等于虚拟链路e的权重w_e；

2.当虚拟链路集合包含二条虚拟链路{e₁、e₂}时，假设其中分别表示虚拟链路e₁、e₂的权重：

在给出虚拟链路集合中包含两条虚拟链路时的分割映射代价计算公式前，请看以下四种实例的分割映射代价的计算分析：

实例1：$>E_2^{s1}=\{e_1,e_2\},w_{e_1}=0,w_{e_2}=100;$>实例2：$>E_2^{s2}=\{e_1,e_2\},w_{e_1}=1,$>$>w_{e_2}=99;$>实例3：$>E_2^{s3}=\{e_1,e_2\},w_{e_1}=20,w_{e_2}=80;$>实例4：$>E_2^{s4}=\{e_1,e_2\},$>$>w_{e_1}=50,w_{e_2}=50.$>

四种实例的共同约束是二条虚拟链路的权重之和均等于100，即实例1中，虚拟链路e₂的权重为100，虚拟链路e₁的权重为0，属于两条虚拟链路的权重的差异极大的情况，可以认为虚拟链路e₁并不存在，其对虚拟链路集合的分割映射代价的贡献为0，因此此类情况下虚拟链路集合的分割映射代价理应等于虚拟链路e₂的权重即实例2中，虚拟链路e₂的权重为99，虚拟链路e₁的权重为1，属于两条虚拟链路的权重的差异很大的情况，虚拟链路e₁对虚拟链路集合的分割映射代价的贡献比虚拟链路e₂小得多，因此此类情况下虚拟链路集合的分割映射代价理应主要取决于虚拟链路e₂的权重实例3中，虚拟链路e₂的权重为80，虚拟链路e₁的权重为20，属于两条虚拟链路的权重的差异较大的情况，映射这两条虚拟网络容易使得映射后的底层物理网络负载失衡，但是相对情况1而言，相当于将一条权重为100的虚拟链路划分割成二条权重相差较大的虚拟链路，因此情况2中虚拟链路集合的分割映射代价理应小于情况1中虚拟链路集合所产生的分割映射代价即实例4中，虚拟链路e₁、e₂的权重均为50，属于两种虚拟链路的权重的差异较小的情况，此类情况最有利于均衡利用底层物理网络资源，所以实例4中虚拟链路集合的分割映射代价理应是所有两条虚拟链路的权重之和等于100的所有分割方案中分割映射代价最优的。

根据以上分析，本发明给出虚拟链路集合中包含两条虚拟链路时的分割映射代价MC_2e计算公式如式(1)所示：

$>{\mathrm{MC}}_{2e}=w_{e_2}+\frac{1+\frac{w_{e_2}-w_{e_1}}{w_{e_1}+w_{e_2}}}{2}{w}_{e_1}=(1+\frac{w_{e_1}}{w_{e_1}+w_{e_2}})w_{e_2}---\left(1\right)$>

根据公式(1)求得$>{\mathrm{MC}}_{E_2^{s1}}=100,{\mathrm{MC}}_{E_2^{s2}}=99,{\mathrm{MC}}_{E_2^{s2}}=96,{\mathrm{MC}}_{E_2^{s3}}=75.$>

3.当虚拟链路集合E_n包含多条虚拟链路{e₁、…、e_k、…、e_n}时，假如其中n表示虚拟链路集合E_n中虚拟链路的数量，n>2，表示虚拟链路e_k的权重，k＝1,…,n：

本发明按照下述方法计算虚拟链路集合中包含多条虚拟链路的分割映射代价：

按顺序从虚拟链路集合E_n中取出两条虚拟链路，并利用公式(1)计算这两条虚拟链路的分割映射代价MC_first2e，然后将一条权重的虚拟链路e_new按顺序插入到集合E_n中；重复以上过程，直到虚拟链路集合E_n中只有一条虚拟链路，最后虚拟链路集合E_n的分割映射代价等于虚拟链路集合E_n中最后一条虚拟链路的权重。

现使用上述计算虚拟链路集合中包含多条虚拟链路时的分割映射代价的方法，计算以下三种虚拟链路集合实例的分割映射代价，其中分别表示虚拟链路e₁、e₂、e₃、e₄的权重：

实例1：$>E_3^{s1}=\{e_1,e_2,e_3\},w_{e_1}=0,w_{e_2}=0,w_{e_3}=300;$>实例2：$>E_3^{s2}=$>$>\{e_1,e_2,e_3\},w_{e_1}=0,w_{e_2}=150,w_{e_3}=150;$>实例3：$>E_4^{s3}=\{e_1,e_2,e_3,e_4\},$>$>w_{e_1}=50,w_{e_2}=100,w_{e_3}=150,w_{e_4}=200.$>

实例1：由于虚拟链路e₁和e₂的权重均为0，因此它们对虚拟链路集合的分割映射代价的影响为0，所以预期得到现使用本发明中计算虚拟链路集合中包含多条虚拟链路时的分割映射代价的方法，计算虚拟链路集合的分割映射代价的过程如下：

按顺序从虚拟链路集合中取出两条虚拟链路，得到虚拟链路e₁和e₂，根据公式(1)计算这两条虚拟链路的分割映射代价MC_first2e，得MC_first2e＝0，然后将一条权重的虚拟链路e_new按顺序插入到虚拟链路集合由于所以虚拟链路e_new被插入到虚拟链路e₃的前面；此时虚拟链路集合由于虚拟链路集合中包含两条虚拟链路，因此继续按顺序从虚拟链路集合中取出两条虚拟链路，得到虚拟链路e_new和e₃，根据公式(1)计算这两条虚拟链路的分割映射代价MC_first2e，得MC_first2e＝300，然后将一条权重的虚拟链路e_new按顺序插入到虚拟链路集合此时虚拟链路集合由于虚拟链路集合中只有一条虚拟链路，所以虚拟链路集合的分割映射代价等于虚拟链路集合中最后一条虚拟链路的权重，即可见使用本发明给出的计算方法得出虚拟链路集合的分割映射代价的结果与预期的结果是一致的。

实例2：由于虚拟链路e₁的权重为0，所以其对虚拟链路集合的分割映射代价的影响为0，所以预期得到的值等于虚拟链路集合中只包含两条权重均为150的分割映射代价的值，根据公式(1)计算得的预期值为225；现使用本发明中计算虚拟链路集合中包含多条虚拟链路时的分割映射代价的方法，计算虚拟链路集合的分割映射代价的过程如下：

按顺序从虚拟链路集合中取出两条虚拟链路，得到虚拟链路e₁和e₂，根据公式(1)计算这两条虚拟链路的分割映射代价MC_first2e，得MC_first2e＝150，然后将一条权重的虚拟链路e_new按顺序插入到虚拟链路集合由于所以虚拟链路e_new被插入到虚拟链路e₃的前面；此时虚拟链路集合由于虚拟链路集合包含两条虚拟链路，因此继续按顺序从虚拟链路集合中取出两条虚拟链路，得到虚拟链路e_new和e₃，根据公式(1)计算这两条虚拟链路的分割映射代价MC_first2e，得MC_first2e＝225，然后将一条权重的虚拟链路e_new按顺序插入到虚拟链路集合，此时虚拟链路集合由于虚拟链路集合中只有一条虚拟链路，所以虚拟链路集合的分割映射代价等于虚拟链路集合中最后一条虚拟链路的权重，即可见使用本发明给出的计算方法得出虚拟链路集合的分割映射代价的结果与预期的结果是一致的。

实例3：直接使用本发明中计算虚拟链路集合中包含多条虚拟链路时的分割映射代价的方法，计算虚拟链路集合的分割映射代价的过程如下：

按顺序从虚拟链路集合中取出两条虚拟链路，得到虚拟链路e₁和e₂，根据公式(1)计算这两条虚拟链路的分割映射代价MC_first2e，得MC_first2e＝133，然后将一条权重的虚拟链路e_new按顺序插入到虚拟链路集合由于所以虚拟链路e_new被插入到虚拟链路e₃的前面；此时虚拟链路集合由于虚拟链路集合中包含三条虚拟链路，因此继续按顺序从虚拟链路集合中取出两条虚拟链路，得到虚拟链路e_new和e₃，根据公式(1)计算得这两条虚拟链路的分割映射代价为MC_first2e＝220，然后将一条权重的虚拟链路e_new按顺序插入到虚拟链路集合由于所以虚拟链路e_new被插入到虚拟链路e₄的后面；此时虚拟链路集合由于虚拟链路集合中包含两条虚拟链路，因此继续按顺序从虚拟链路集合中取出两条虚拟链路，得到虚拟链路e₄和e_new，根据公式(1)计算这两条虚拟链路的分割映射代价为MC_first2e＝325，然后将一条权重的虚拟链路e_new按顺序插入到虚拟链路集合此时虚拟链路集合由于虚拟链路集合中只有一条虚拟链路，所以虚拟链路集合的分割映射代价等于虚拟链路集合中最后一条虚拟链路的权重，即$>{\mathrm{MC}}_{E_4^{s3}}=w_{e_{new}}=325.$>

正如前面所述，目前很多虚拟网络映射方法受制于虚拟网络的规模，因此本发明设定常数N为直接使用现有的虚拟网络映射方法映射的虚拟网络的节点个数最大值，N的取值受到所使用现有的虚拟网络映射方法可接受的虚拟网络节点个数限制。当然从小的虚拟网络更容易匹配到底层物理网络那些相互隔离的低密度的区域中这个角度考虑的话，那么N的值可以适当设置得小点。

本发明的虚拟网络改进映射方法的流程示意图如图1所示。本发明根据接收的虚拟网络请求的节点个数规模，决定是否需要对其进行分割后再进行利用现有的虚拟网络映射方法映射接收到的虚拟网络请求，本发明只是提供一种虚拟网络分割解决方案，并不会描述如何将分割后的虚拟网络映射到底层物理网络。对于需要分割的虚拟网络请求，本发明采用改进的多级递归二分法(MultilevelRecursiveBisection，MLRB)解决虚拟网络的分割问题，具体过程如下：

当接收的虚拟网络的节点个数大于N，则使用本发明中的多级递归二分法将该虚拟网络分割成多个节点个数小于等于N的子虚拟网络，然后再使用现有的虚拟网络映射方法进行映射；否则，即接收的虚拟网络的节点小于等于N，那么直接使用现有的虚拟网络映射方法映射该虚拟网络。

本发明接下来对上述多级递归二分法的具体实现过程进行详细描述：

递归二分法(Recursivebisection，RB)就是首先对原虚拟网络进行两路分割，得到两个子虚拟网络，然后递归地对得到的两个子虚拟网络进行两路分割，经过logk步后，最终得到原虚拟网络的k路分割。由于不能提前知道需要将原虚拟网络做多少路分割，因此在本发明中只要得到的虚拟网络的节点个数大于N，那么继续对该虚拟网络进行两路分割，直到所有得到的虚拟网络的节点个数小于等于N。

当原虚拟网络的规模较大时，直接对原虚拟网络进行两路分割，一些方法，如谱二分法，虽然能得到不错的划分结果，却带来很高的计算代价。一种多级技术被应用到递归二分法中，得到应用更广的多级递归二分法，该方法在得到较优的分割结果的前提下，能够明显缩短计算时间。与递归二分法不同的是，多级递归二分法不是直接对原虚拟网络进行两路分割，而是对原虚拟网络进行粗化处理后得到一系列与原虚拟网络拓扑特性相似但规模递减的虚拟网络，接着对得到的原虚拟网络最粗化的虚拟网络进行两路分割，然后通过细化阶段将最粗化的虚拟网络的二路分割映射回原虚拟网络的二路分割，从而得到原虚拟网络两路分割后的两个虚拟网络，细化阶段一般使用某种局部调优算法，如Kernighan‐Lin算法，对得到的上一级虚拟网络的两路分割进行优化处理。多级递归二分法总共包含四个阶段：粗化阶段、初始划分阶段、细化阶段、递归阶段。本发明在多级递归二分法的四个阶段的基础上作改进，以适用于虚拟网络的分割问题，具体改进过程如下：

步骤一：粗化阶段

粗化阶段的目的是将待分割的虚拟网络转化成一系列与其拓扑特性相似，但规模递减的虚拟网络满足|V₀|＞|V₁|＞...＞|V_k|＞...＞|V_m|，其中|V_k|表示虚拟网络的节点个数，虚拟网络为待分割的虚拟网络最粗化的虚拟网络，k＝1,2,…,m；如果待分割的虚拟网络的节点个数小于等于2*N，那么虚拟网络最粗化的虚拟网络为自身，即m＝0。本发明通过下述方法得到虚拟网络

对于一个虚拟网络其中V_k表示虚拟网络中所有节点构成的集合，E_k表示虚拟网络中所有链路构成的集合，表示节点集合V_k中节点对应的权重集合，表示链路集合E_k中链路对应的权重集合，k＝0,1,2,..m。

如果虚拟网络的节点个数小于2*N，那么虚拟网络为待分割的虚拟网络最粗化的虚拟网络，m等于此时的k值；否则，即虚拟网络的节点个数大于等于2*N，那么在虚拟网络中寻找极大匹配，并在寻找极大匹配的过程中不断合并匹配的节点对得到一个新的多重节点，该多重节点的权重等于匹配的节点对的权重之和，如果该多重节点与其任意一个邻接节点之间包含N条虚拟链路，其中N>1，那么本发明都会将这两节点之间的N条虚拟链路合并为一条多重虚拟链路，然后根据本发明中计算虚拟链路集合的分割映射代价的方法计算这N条虚拟链路的分割映射代价MC_Ne，然后设置该多重虚拟链路的权重为MC_Ne。当遍历完虚拟网络中所有节点之后，此时虚拟网络中不存在未匹配的节点对，即可得到下一级粗化的虚拟网络通过寻找极大匹配的方式得到的粗化的虚拟网络保留了上一级虚拟网络的许多特性，因此对虚拟网络的划分，即使直接映射回也能得到分割映射成本与接近的划分。

目前有多种寻找极大匹配的方法：随机匹配(Randommatching，RM)、重边匹配(Heavyedgematching，HEM)、轻边匹配(Lightedgematching，LEM)、重群匹配(Heavycliquematching，HCM)等。本发明提出一种新的寻找极大匹配的方法：最大亲密度匹配(Mostclosenessmatching，MCM)。

虚拟网络邻接节点对的亲密度是一种根据网络连接特性提出的概念，用以度量两个邻接节点之间潜在的数据交换量，潜在的数据交换量越大则这两个节点越亲密，亲密度反映了节点对的关联特性。一般可以认为，邻接节点对的亲密度主要由这两个邻接节点之间的直连链路带宽决定。两个邻接节点之间的直连链路带宽越大，邻接节点对的亲密度越大。特别地，当直连链路带宽趋于0时，即使两个邻接节点的处理能力再高，可以认为这两个节点几乎不会进行数据交换，是两个相对独立的节点，亲密度极低。但是，在直连链路带宽相同的情况下，两个邻接节点的处理能力越强，那么这两个节点潜在的数据交换量也会有所增加。亲密度越小的虚拟网络邻接节点对，潜在数据交换量越小，对映射距离越不敏感，那么节点对之间的虚拟链路更适合作为切割链路。其中，虚拟网络邻接节点对的亲密度的计算公式如式(2)所示。

$>\kappa (n_1^v,n_2^v)=(2/\pi \arctan (\frac{C_{n_1^v}{C}_{n_2^v}}{{\left(Max\right(C_n^v)/\lambda )}^2})+1)*BW(n_1^v,n_2^v)---\left(2\right)$>

其中，表示虚拟网络邻接节点对的亲密度；分别表示虚拟节点请求的CPU资源，表示虚拟链路请求的带宽资源；表示由物理网络设备提供商(InP)预先设定的虚拟节点请求的CPU资源的最大值；λ为压缩常数，一般取值为4。

对虚拟网络采用最大亲密度匹配(MCM)方法得到下一级粗化的虚拟网络具体执行过程如下：

步骤i)如果虚拟网络的节点个数小于等于2*N，那么结束粗化阶段，虚拟网络即为待分割的虚拟网络最粗化的虚拟网络，m等于此时的k值；否则，即虚拟网络的节点个数大于2*N，则执行步骤ii)；

步骤ii)以随机的顺序访问虚拟网络中的节点，然后对每一个被访问的节点执行步骤iii)和iv)；

步骤iii)如果被访问的节点v未匹配，而且节点v还有未匹配的邻接节点，那么使用公式(2)计算节点v与其所有未匹配的邻接节点的亲密度，然后选择与节点v亲密度最大的未匹配的邻接节点v′作为节点v的匹配节点；合并匹配的节点对v′和v为一个多重节点v_new，多重节点v_new的权重等于匹配的节点对v′和v的权重之和，即其中为多重节点v_new的权重，w_v为节点v的权重，w_v′为节点v′的权重；如果多重节点v_new与其任意一个邻接节点之间包含两条虚拟链路，那么将这两节点之间的两条虚拟链路合并为一条多重虚拟链路，然后根据公式(1)计算两虚拟链路的分割映射代价MC_2e，最后设置多重虚拟链路的权重为MC_2e；如果多重节点v_new与其任意一个邻接节点之间包含多条虚拟链路，那么将这两节点之间的多条虚拟链路合并为一条多重虚拟链路，然后根据本发明中计算虚拟链路集合中包含多条虚拟链路时的分割映射代价的方法，计算这多条虚拟链路的分割映射代价MC_{Multi_e}，最后设置多重虚拟链路的权重为MC_{Multi_e}；将节点对v′和v设置为匹配状态；

步骤iv)如果被访问的节点v已匹配，或者在被访问的节点v未匹配情况下，节点v没有未匹配的邻接节点，那么节点v的匹配查找过程结束。

步骤二：初始划分阶段

初始划分阶段的目的是将步骤一粗化阶段得到的待分割的虚拟网络最粗化的虚拟网络分割成二个节点个数相当的子虚拟网络。目前有多种分割方法：谱二分法(Spectralbisection，SB)、组合方法、Kernighan‐Lin算法、图分区扩展划分算法(Graphgrowingpartitioningalgorithm，GGP)、图分区贪婪式扩展划分算法(Graphgrowingpartitioningalgorithm，GGGP)等，但是这些方法均没有考虑切割链路总数对虚拟网络的分割代价的影响。

本发明对图分区贪婪式扩展划分算法(Greedygraphgrowingpartitioningalgorithm，GGGP)《KarypisG,KumarV.Afastandhighqualitymultilevelschemeforpartitioningirregulargraphs》(SIAMJournalonscientificComputing,1998,20(1):359-392)进行改进，以适用于虚拟网络的分割，改进的部分主要是结合切割集中虚拟链路的权重分布以及数量来定量切割集的切割代价，这里的切割集具体是指所有跨越划分后得到的两个子虚拟网络的虚拟链路构成的集合，具体改进的执行过程如下:

步骤a)随机从虚拟网络中选取1个节点v_start作为扩展分区G_sub的扩展起点，也就是说扩展分区G_sub最初只有一个本发明随机选取的节点v_start；

步骤b)查找虚拟网络相对于当前扩展分区G_sub的前端节点集合具体可以遍历虚拟网络中所有虚拟链路，如果被访问的虚拟链路的一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，那么将该虚拟链路中不属于当前扩展分区G_sub的一端节点加入到前端节点集合

步骤c)依次假设将前端节点集合中的一个节点加入到当前扩展分区G_sub，然后查找虚拟链路切割集具体可以遍历虚拟网络中所有虚拟链路，如果被访问的虚拟链路的一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，那么将该虚拟链路加入到虚拟链路切割集最后根据本发明中计算虚拟链路集合的分割映射代价的方法计算虚拟链路切割集的分割映射代价最后选择前端节点集合中使值最小的节点真正加入到当前扩展分区G_sub；

步骤e)如果当前扩展分区G_sub中的节点的个数小于虚拟网络的节点的个数的一半，则返回执行步骤b)；否则，即当前扩展分区G_sub中的节点的个数大于等于虚拟网络的节点的个数的一半，则执行步骤f)；

步骤f)对得到的划分进行合并调优，具体就是遍历虚拟网络中所有虚拟链路，如果被访问的虚拟链路的一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，如果该不属于当前扩展分区G_sub的端节点的度值为1的话，就将该不属于当前扩展分区G_sub的端节点加入到当前扩展分区G_sub。至此，虚拟网络的划分过程结束。

为了更直观地阐述本发明使用上述改进的图分区贪婪式扩展划分算法解决初始划分阶段虚拟网络的分割问题，现结合图2，以一个具体的虚拟网络实例进行详细的划分说明。

1)随机从图2所示虚拟网络实例中选取一个节点作为扩展分区G_sub的扩展起点，这里假设随机选中的节点为节点b，所以扩展分区G_sub＝{b}；

2)查找虚拟网络实例相对于当前扩展分区G_sub的前端节点集合遍历虚拟网络实例中所有虚拟链路后可知只有虚拟链路(b，a)、(b，c)、(b，e)满足其一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，所以前端节点集合$>F_{G_{sub}}\left(G^v\right)=\{a,c,e\};$>

3)依次假设将前端节点集合中的一个节点加入到当前扩展分区G_sub＝{b}，然后根据本发明中计算虚拟链路集合的分割映射代价的方法计算虚拟链路切割集的分割映射代价具体执行过程如下：

假设将节点a加入到当前扩展分区G_sub＝{b}，得到如图3(1)所示划分，当前扩展分区G_sub＝{a，b}，遍历虚拟网络实例中所有虚拟链路后可知只有虚拟链路(b，c)、(b，e)、(b，f)，满足其一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，所以虚拟链路切割集(b，e)，(b，f)}，根据本发明中计算虚拟链路集合的分割映射代价的方法计算虚拟链路切割集的分割映射代价得

假设将节点c加入到当前扩展分区G_sub＝{b}，得到如图3(2)所示划分，当前扩展分区G_sub＝{a，c}，遍历虚拟网络实例中所有虚拟链路后可知只有虚拟链路(b，a)、(b，e)、(b，f)，满足其一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，所以虚拟链路切割集(b，e)，(b，f)}，根据本发明中计算虚拟链路集合的分割映射代价的方法计算虚拟链路切割集的分割映射代价得

假设将节点e加入到当前扩展分区G_sub＝{b}，得到如图3(3)所示划分，当前扩展分区G_sub＝{b，e}，遍历虚拟网络实例中所有虚拟链路后可知只有虚拟链路(b，a)、(b，c)、(b，f)、(e，d)、(e，f)，满足其一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，所以虚拟链路切割集$>E_{cut}\left(G_m^v\right)=\{(b,a),(b,c),(b,f),(e,d),(e,f)\},$>根据本发明中计算虚拟链路集合的分割映射代价的方法计算虚拟链路切割集的分割映射代价得$>{\mathrm{MC}}_{E_{cut}}=44;$>

由于将节点a加入到当前扩展分区G_sub＝{a}后得到的值最小，所以本发明最后将节点a真正加入到当前扩展分区G_sub＝{a}，即可得到如图3(1)所示的划分，此时当前扩展分区G_sub＝{b，a}；

3)当前扩展分区G_sub＝{b，a}，其节点的个数为2，小于虚拟网络实例的节点的个数的一半(4)，所以返回执行上述改进的图分区贪婪式扩展划分算法中的步骤b)，这里不再详细说明，最终得到如图4所示的划分，G_sub＝{b，a，c}；

4)当前扩展分区G_sub＝{b，a，c}，其节点的个数为3，小于虚拟网络实例的节点的个数的一半(4)，所以返回执行上述改进的图分区贪婪式扩展划分算法中的步骤b)，这里不再详细说明，最终得到如图5所示的划分，G_sub＝{b，a，c，e}；

5)当前扩展分区G_sub＝{b，a，c，e}，其节点的个数为4，等于虚拟网络实例的节点的个数的一半(4)，所以不再返回执行上述改进的图分区贪婪式扩展划分算法中的步骤b)，而是执行步骤f)；

6)对得到的划分进行合并调优，即对如图5所示的划分进行合并调优，遍历虚拟网络实例中所有虚拟链路后可知只有虚拟链路(e，d)，满足其一端节点属于当前扩展分区G_sub，而其另一端节点不属于当前扩展分区G_sub，而且该不属于当前扩展分区G_sub的节点d的度值为1，所以将节点d加入到当前扩展分区G_sub，得到如图6所示的划分。至此，虚拟网络实例的划分过程结束。

由于本发明对图分区贪婪式扩展划分算法所作的改进并没有改变原算法贪婪地扩展方式，所以改进的图分区贪婪式扩展划分算法最终得到虚拟网络的二路划分一定程度上取决于扩展分区起点v_start的选取，因此实际实现时可以随机选择多个扩展起点，并独立运行上述算法，最后再选择分割映射代价最小的划分方案。

步骤三：细化阶段

细化阶段的目的是将步骤二初始划分阶段中虚拟网络的两路分割映射回待分割的虚拟网络的两路分割，该阶段一般使用Kernighan‐Lin算法进行调优，以取得划分的局部最优值。虽然Kernighan‐Lin算法也仅仅是将切割链路集合的权重之和作为划分的评价指标，也没有考虑切割集中链路数量及权重分布对划分的影响，但是只要初始划分阶段能得到比较好的分割的话，Kernighan‐Lin划分算法也只是作局部交换，相对于整个切割链路集合而言，被交换的链路条数对分割代价的影响被削弱，因此本发明在细化阶段直接使用Kernighan‐Lin算法进行调优。

本发明没有对传统的多级递归二分法的细化阶段作任何修改，因此这里不再详细描述细化阶段的操作过程。

步骤四：递归阶段

递归阶段的目的是检测是否需要继续调用多级递归二分法，对步骤三细化阶段中得到的待分割的虚拟网络的两个子虚拟网络进行分割，分别对这两个子虚拟网络执行如下操作：

如果虚拟网络的节点的个数大于N，那么将该虚拟网络作为新的待分割虚拟网络，并返回步骤一粗化阶段，即递归调用多级递归二分法对该虚拟网络作进一步地分割；否则，即虚拟网络的节点个数小于N，那么结束对该虚拟网络的分割。