一种基于优化开销收益比的虚拟网络映射方法

摘要

一种基于优化开销收益比的虚拟网络映射方法，本发明涉及虚拟网络映射方法。本发明为了解决现有技术不能在有限的物理资源内保证高的映射成功率，以及现有技术大多是从单个虚拟节点到单个物理节点的映射的问题。本发明是在现有的虚拟网络映射问题中扩大虚拟网络的规模，使其大于底层物理网络的规模，也就是虚拟网络的节点规模数大于物理网络的节点规模。本发明主要目的是在映射所有的虚拟网络请求的情况下，尽可能的减少底层物理资源的使用，提高本发明方法映射的成功率以及算法收益。比较传统Node-Opt算法，本发明在映射收益上高出将近30％，在不同的虚拟网络请求规模下普遍将映射成功率提高了50％以上。本发明用于虚拟网络映射领域。

权利要求

1.一种基于优化开销收益比的虚拟网络映射方法，其特征在于：所述基于优化开销收益比的虚拟网络映射方法包括以下步骤：步骤一：将虚拟网络和物理网络初始化，创建物理网络排序数组PGAR[]和虚拟网络排序数组VGR[]，PGAR[]和VGR[]分别表示物理网络中的物理节点数组和虚拟网络中的虚拟节点数组；

步骤二：计算PGAR[]中的物理节点的剩余资源量，并从大到小进行排序；

步骤三：计算VGR[]中的虚拟节点的资源请求量，并从大到小进行排序；

步骤四：计算虚拟中心的初始数量MergeCenterNum，并把VGR[]前MergeCenterNum个虚拟节点作为虚拟中心映射到PGAR[]的前MergeCenterNum个物理节点上；

步骤五：对于虚拟网络拓扑图中的所有非虚拟中心节点，计算当前每个非虚拟中心节点与被映射的物理节点集合的关联度值，依次把非虚拟中心节点、与非虚拟中心节点对应的最大关联度中心以及最大关联度值打包放入优先队列中，按关联度从大到小排序；非虚拟中心节点是指未映射的虚拟节点；所述当前每个非虚拟中心节点与被映射的物理节点集合的关联度值是指非虚拟中心节点与已经被映射到被映射的物理节点中的虚拟节点的链路带宽之和；最大关联度中心是指与该非虚拟中心节点有最大关联度值的物理节点；

步骤六：从优先队列中取出队首元素，即关联度最大的虚拟节点；

步骤七：若队首元素的最大关联度值为0或者最大关联度中心剩余资源量小于该虚拟节点的资源请求量，则将该虚拟节点映射到新的物理节点；否则，则将该虚拟节点映射到其最大关联度中心；

步骤八：删除优先队列中被映射的虚拟节点，并更新优先队列中剩余非虚拟中心的最大关联度中心和最大关联度值；

步骤九：迭代执行步骤六至步骤八，直至优先队列中没有剩余非虚拟中心节点。

2.根据权利要求1所述的一种基于优化开销收益比的虚拟网络映射方法，其特征在于：所述步骤二中计算PGAR[]中的物理节点的剩余资源量的具体过程为：其中ARv为PGAR[]中的物理节点的剩余资源量，FreeC(v)为物理节点v的空闲CPU资源，为与物理节点v所连接的链路的空闲带宽之和，E(v,u)为与物理节点v相连的物理节点u之间的链路，Ev为与物理节点v所连接的所有物理链路集合。

3.根据权利要求2所述的一种基于优化开销收益比的虚拟网络映射方法，其特征在于：所述步骤三中计算VGR[]中的虚拟节点的资源请求量的具体过程为：

其中Ri为VGR[]中的虚拟节点的资源请求量，C(i)为虚拟节点i的CPU资源请求量，为与虚拟节点i所连接的链路带宽之和，E(i,j)为与虚拟节点i相连的虚拟节点j之间的链路，Ei为与虚拟节点i所连接的所有虚拟链路集合。

4.根据权利要求3所述的一种基于优化开销收益比的虚拟网络映射方法，其特征在于：所述步骤四中计算虚拟中心的初始数量MergeCenterNum的具体过程为：其中avg(C(vv))为虚拟网络拓扑中所有虚拟节点的CPU资源请求量的平均值，avg(FreeC(vp))为物理网络拓扑中所有物理节点的CPU资源剩余量的平均值，avg(BD(ev))为虚拟网络拓扑中所有链路的带宽请求量的平均值，avg(FreeBD(ep))为物理网络拓扑中所有链路的空闲带宽的平均值，|Vv|为虚拟网络拓扑中的虚拟节点数量。

说明书

一种基于优化开销收益比的虚拟网络映射方法

技术领域

[0001] 本发明涉及虚拟网络映射领域，具体涉及基于优化开销收益比的大规模虚拟网络映射方法。

背景技术

[0002] 随着现代互联网，存储技术以及网络规模的高速发展，计算资源变得更加廉价、强大、更无处不在的可获取性。这种潮流导致了新型计算模型云计算的高速发展，这种计算模型的计算资源(cpu，存储)分散在各个数据中心，并且直接向用户按需提供服务，主要是以VM的方式，用户使用这些资源更像一种使用一种普通的配件。网络虚拟化的定义就是提出一种潜在的解决方案，把未来的网络架构分解为独立的一个个虚拟网络，这些网络独自承担这各种客户的网络服务，这些虚拟网络又同时共享一个底层的物理网络。虚拟网络映射问题或者叫做虚拟网络嵌入问题都是在网络虚拟化中一个主要的资源分配挑战。也是网络虚拟化过程中必须解决的一个先决条件，这是之后各种工作的基础。给定一些特定的虚拟网络请求，每一个请求都是一个虚拟网络拓扑，都有着自己的节点和链路资源需求。把这些资源请求用底层物理网络中的节点和链路来满足就是虚拟网络映射问题的关键。

发明内容

[0003] 本发明的目的是为了解决现有技术不能在有限的物理资源内保证高的映射成功率，以及现有技术大多是从单个虚拟节点到单个物理节点的映射的缺点，而提出一种基于优化开销收益比的虚拟网络映射方法。

[0004] 一种基于优化开销收益比的虚拟网络映射方法包括以下步骤：

[0005] 步骤一：将虚拟网络和物理网络初始化，创建物理网络排序数组PGAR[]和虚拟网络排序数组VGR[]，PGAR[]和VGR[]分别表示物理网络中的物理节点数组和虚拟网络中的虚拟节点数组；

[0006] 步骤二：计算PGAR[]中的物理节点的剩余资源量，并从大到小进行排序；

[0007] 步骤三：计算VGR[]中的虚拟节点的资源请求量，并从大到小进行排序；

[0008] 步骤四：计算虚拟中心的初始数量MergeCenterNum，并把VGR[]前MergeCenterNum个虚拟节点作为虚拟中心映射到PGAR[]的前MergeCenterNum个物理节点上；

[0009] 步骤五：对于虚拟网络拓扑图中的所有非虚拟中心节点，计算当前每个非虚拟中心节点与被映射的物理节点集合的关联度值，依次把非虚拟中心节点、与非虚拟中心节点对应的最大关联度中心以及最大关联度值打包放入优先队列中，按关联度从大到小排序；非虚拟中心节点是指未映射的虚拟节点；所述当前每个非虚拟中心节点与被映射的物理节点集合的关联度值是指非虚拟中心节点与已经被映射到被映射的物理节点中的虚拟节点的链路带宽之和；最大关联度中心是指与该非虚拟中心节点有最大关联度值的物理节点；

[0010] 步骤六：从优先队列中取出队首元素，即关联度最大的虚拟节点；

[0011] 步骤七：若队首元素的最大关联度值为0或者最大关联度中心剩余资源量小于该虚拟节点的资源请求量，则将该虚拟节点映射到新的物理节点；否则，则将该虚拟节点映射到其最大关联度中心；

[0012] 步骤八：删除优先队列中被映射的虚拟节点，并更新优先队列中剩余非虚拟中心的最大关联度中心和最大关联度值；

[0013] 步骤九：迭代执行步骤六至步骤八，直至优先队列中没有剩余非虚拟中心节点。

[0014] 本发明的有益效果为：

[0015] 本发明是在现有的虚拟网络映射问题中扩大虚拟网络的规模，使其大于底层物理网络的规模，也就是虚拟网络的节点规模数大于物理网络的节点规模。这也越来越符合现在的互联网模型，用户提出的网络规模需求变大，如果一味的增大底层的物理网络规模是不现实的。在大规模虚拟网络映射问题中研究一种映射合理的算法，主要目的是在映射所有的虚拟网络请求的情况下，尽可能的减少底层物理资源的使用，提高本发明方法映射的成功率以及算法收益。我们提出了开销收益比这个概念，及利用带宽映射开销与映射收益的比值来考量算法性能，该指标越低，性能越好。

[0016] 通过比较传统Node-Opt算法，图3中Node-Opt比Node-Merge在带宽映射开销方面高出将近200％；图4中显示Node-Merge比Node-Opt在映射收益上高出将近30％；从图5中看出Node-Opt比Node-Merge在开销收益比上普遍高出300％以上；图6显示Node-Merge比Node-Opt在不同的虚拟网络请求规模下普遍将映射成功率提高了50％以上，有的甚至高达120％。

附图说明

[0017] 图1为虚拟节点聚合图；

[0018] 图2为优化后链路映射算法处理图；

[0019] 图3为链路映射开销随虚拟网络请求规模的变化规律比较图，图中CoBM为链路映射开销，是虚拟链路映射到物理链路后产生的网络开销，计算过程为：其中Ev表示虚拟网络拓扑中的虚拟链路集合，BD(ev)表
示虚拟链路ev的链路带宽请求量， 表示虚拟链路ev所连接的虚拟节点i和m映射到物理节点j和n后所占用的物理链路的长度。

[0020] 图4为映射收益随虚拟网络请求规模的变化规律比较图，图中MR为映射收益，计算过程为： 其中β是一个根据虚拟网络请求中CPU资源请求和链路带宽需求情况而人工设定的调节参数，Vv表示虚拟网络拓扑中的虚拟节点集合，Ev表示虚拟网络拓扑中的虚拟链路集合， 表示虚拟网络拓扑中的所有虚拟节点的CPU资源请求量之和， 表示虚拟网络拓扑中的所有虚拟节点的链路带宽资源请求量之和。

[0021] 图5为开销收益比随虚拟网络请求规模的变化规律比较图，图中Ratio of Cost to Revenue表示开销收益比，计算过程为： 其中α是一个根据开销和收益情况而人工设定的调节参数。

[0022] 图6为虚拟拓扑映射成功率随虚拟网络请求规模的变化规律比较图，图中Mapped Successed ratio表示映射成功率。

具体实施方式

[0023] 具体实施方式一：一种基于优化开销收益比的虚拟网络映射方法包括以下步骤：

[0024] 步骤一：将虚拟网络和物理网络初始化，创建物理网络排序数组PGAR[]和虚拟网络排序数组VGR[]，PGAR[]和VGR[]分别表示物理网络中的物理节点数组和虚拟网络中的虚拟节点数组；

[0025] 步骤二：计算PGAR[]中的物理节点的剩余资源量，并从大到小进行排序；

[0026] 步骤三：计算VGR[]中的虚拟节点的资源请求量，并从大到小进行排序；

[0027] 步骤四：计算虚拟中心(指的是虚拟节点)的初始数量MergeCenterNum，并把VGR[]前MergeCenterNum个虚拟节点作为虚拟中心映射到PGAR[]的前MergeCenterNum个物理节点上；

[0028] 步骤五：对于虚拟网络拓扑图(VGragh)中的所有非虚拟中心节点，计算当前每个非虚拟中心节点与被映射的物理节点集合的关联度值，依次把非虚拟中心节点、与非虚拟中心节点对应的最大关联度中心以及最大关联度值打包放入优先队列(queue)中，按关联度从大到小排序；非虚拟中心节点是指未映射的虚拟节点；所述当前每个非虚拟中心节点与被映射的物理节点集合的关联度值是指非虚拟中心节点与已经被映射到被映射的物理节点中的虚拟节点的链路带宽之和；最大关联度中心是指与该非虚拟中心节点有最大关联度值的物理节点；

[0029] 步骤六：从优先队列中取出队首元素，即关联度最大的虚拟节点；

[0030] 步骤七：若队首元素的最大关联度值为0或者最大关联度中心剩余资源量小于该虚拟节点的资源请求量，则将该虚拟节点映射到新的物理节点；否则，则将该虚拟节点映射到其最大关联度中心；

[0031] 步骤八：删除优先队列中被映射的虚拟节点，并更新优先队列中剩余非虚拟中心的最大关联度中心和最大关联度值；

[0032] 步骤九：迭代执行步骤六至步骤八，直至优先队列中没有剩余非虚拟中心节点。

[0033] 本发明主要是在新的大规模虚拟网络映射的问题背景下，通过对传统的Node-Opt算法进行分析，发现其中的不足。运用节点合并的思想，提出了优化后的一个Two-Stage算法：Node-Merge算法。从而提高算法映射成功率，提高算法收益。

[0034] Node-Opt算法是一种优先映射虚拟节点Two-Stage算法，我们把它实现主要是作为我们后续算法的一个比较基准以及优化基准。

[0035] 本发明方法在虚拟节点部署的时候，主要考虑的是物理节点的是物理节点的剩余资源(Available Resource)情况，包括空闲计算能力以及对外连接的空闲总带宽情况：

[0036]

[0037] 对于虚拟节点则计算它的资源请求情况：

[0038]

[0039] 计算出物理节点的剩余资源和虚拟节点的资源请求情况之后，资源请求大的虚拟节点可能会连接很多的虚拟链路，在以后的映射中将会占用更多的物理节点向外带宽，所以利用一种贪心的策略把资源请求大的虚拟节点尽量放到剩余资源大的物理节点中。节点映射成功之后，对于链路映射过程用K-Shortest算法寻找最短路径，只要保证所有物理边的剩余带宽大于虚拟链路所需的带宽。

[0040] Node-Opt算法在一般场景下能够表现的很好。但是没有突出在大规模网络映射中优势，而本专利提出的Node-Merge算法是一种基于减少链路带宽开销的合并节点算法。

[0041] 在大规模虚拟网络拓扑映射提出之前，一般的虚拟网络拓扑的规模是小于底层物理网络。所以出现的许多算法都是把同一虚拟网络中的不同节点映射到不同的物理节点上，甚至是映射问题中的一条严格要求。但是在大规模网络映射中，这显然是不可能实现的，总有许多虚拟节点共享一个物理节点。换一种思路，把带宽需求较大的虚拟链路上的虚拟节点映射到同一个物理节点上，这对于减少网络带宽开销巨大问题是有这明显的改观。因为在物理节点内部，我们可以认为这里面通信的空闲带宽能力是无穷大的，几乎不会产生任何开销。

[0042] 所以基于上面的思路。我们直观的减少虚拟链路带宽开销的方法就是进行把有通信的节点放在同一个物理节点上，如图1所示。这样选择虚拟节点对以及对物理节点筛选成为关键。

[0043] 本发明提出一种虚拟中心的概念，虚拟中心是指某些与外部通信带宽较多的一些节点，在网络拓扑图中的只管感受就是虚拟中心像一个一个小型的辐射中心，辐射出许多边。图1中就是虚拟方框中就是一个虚拟中心。我们选出虚拟中心后，然后对于某个虚拟中心，选择一些与之相邻的虚拟节点加入虚拟中心，形成一个一个虚拟映射集，映射虚拟节点的问题就变成了直接把这些映射集映射到物理节点上。除了虚拟集内部的虚拟链路，剩余处理的就只有虚拟集外部的链路。

[0044] 虚拟映射集的映射不光映射了虚拟节点，连带着这些映射集内部的链路也相当于被映射到了同一个节点上。所以Node-Merge算法总体相当于一种Two-Stage算法。之后虚拟映射集之间的虚拟链路再通过优化后的最短路径算法来计算。这时候对虚拟链路的映射变得大幅度减少。

[0045] 虚拟映射集映射完成之后，需要考虑的是对映射集之间的虚拟链路映射。长度为1的虚拟链路映射到物理路径上，物理路径的长度可以大于1，物理路径上的剩余带宽必须满足虚拟链路的带宽需求。采用优化后的Dijkstra算法。

[0046] 算法Node-Opt算法对于链路映射常用K-Shortest最短路径算法。但是这种启发式算法有时的算法效率是非常差的。一般是在已经找出的一条最短路径的基础上，经过修改获取其他的最短路径，但是对于虚拟网络映射问题中，每一条路径都有一个剩余带宽能力。很有可能很多衍生出来的最短路径都包含一条带宽资源不符合的边，从而也是失败的。

[0047] 我们结合大规模虚拟网络映射问题的特性，充分利用底层物理边的剩余带宽资源能力。对Dijkstra算法进行优化形成OptimumSP算法。主要的做法是对每条边进行了处理，如果是不符合带宽资源能力的边，提前就舍弃这条边。而不是等到求出最短路径之后，进行带宽资源的检查，然后舍弃整个路径。

[0048] 处理过程如图2所示，利用贪心思想维护两个集合，左侧都是有最短路径的节点集合S，右侧都是未选择的节点集合N。每次从N中选出最短路径节点，如图中椭圆之外的节点，只保留其剩余带宽能力大于虚拟链路带宽的路径，即加粗路径，带宽能力不足的物理链路则被舍弃。这样保证本算法每次一旦找到最短路径，都是符合条件的，如果找不到路径，则都是不存在最短路径的。

[0049] Node-Merge算法充分利用了大规模虚拟网络映射中的大规模特点和节点映射优化特点，把联系紧密的虚拟节点“抱团”，充分降低虚拟网络的复杂度，使虚拟网络拓扑变得简单化，真正的通信联系变得清晰，变成了大的虚拟映射集之间的通信。

[0050] 本发明方法的主要伪代码如下：

[0051]

[0052]

[0053] Node-Merge算法的主要点在于4和12步，4是初始化，对于已经分配的虚拟映射集，计算所有虚拟节点(除虚拟中心外)与虚拟映射集的关联度，关联度其实就是一个节点和虚拟映射集中所有虚拟节点的通信带宽之和。并选择最大的开始映射到映射集里(虚拟节点所在的物理节点)。12是在一旦完成虚拟节点的映射，开始更新queue中的所有虚拟节点的关联度。总体上保持动态上永远使得每个虚拟映射集的紧密程度。

[0054] Node-Merge算法的主要优势就是虚拟中心的建立，减少了许多虚拟链路映射带来的带宽开销，所以算法对于总体的开销是会降低很多，尤其是在带宽映射开销方面。其次，在节约了许多虚拟链路的映射之后，总体映射的拥塞会减少，链路映射会更容易找到最短路径来映射，能调高映射的接受率，从而提高映射总收益。

[0055] 由于虚拟中心节点的选取映射之后，所有虚拟映射集的建立都会减少链路映射工作和节点的选取映射工作。但是对于虚拟映射集的形成，由于是一个动态的过程，而且对于所有虚拟节点都要考虑这又是一个大规模的映射问题，映射时间可能会比一般的算法较长。所有节点都围绕虚拟中心映射，物理节点利用效率高。映射的结果会给人一种底层被映射物理节点都被充分的利用，映射很紧凑。

[0056] 具体实施方式二：本实施方式与具体实施方式一不同的是：所述步骤二中计算PGAR[]中的物理节点的剩余资源量的具体过程为：

[0057]

[0058] 其中ARv为PGAR[]中的物理节点的剩余资源量，FreeC(v)为物理节点v的空闲CPU资源， 为与物理节点v所连接的链路带宽之和，E(v,u)为与物理节点v相连的物理节点u之间的链路，Ev为与物理节点v所连接的所有物理链路集合。

[0059] 其它步骤及参数与具体实施方式一相同。

[0060] 具体实施方式三：本实施方式与具体实施方式一或二不同的是：所述步骤三中计算VGR[]中的虚拟节点的资源请求量的具体过程为：

[0061]

[0062] 其中Ri为VGR[]中的虚拟节点的资源请求量，C(i)为虚拟节点i的CPU资源请求量，为与虚拟节点i所连接的链路带宽之和，E(i,j)为与虚拟节点i相连的虚拟节点j之间的链路，Ei为与虚拟节点i所连接的所有虚拟链路集合。

[0063] 其它步骤及参数与具体实施方式一或二相同。

[0064] 具体实施方式四：本实施方式与具体实施方式一至三之一不同的是：所述步骤四中计算虚拟中心的初始数量MergeCenterNum的具体过程为：

[0065]

[0066] 其中avg(C(vv))为虚拟网络拓扑中所有虚拟节点的CPU资源请求量的平均值，[0067] avg(FreeC(vp))为物理网络拓扑中所有物理节点的CPU资源剩余量的平均值，[0068] avg(BD(ev))为虚拟网络拓扑中所有链路的带宽请求量的平均值，avg(FreeBD(ep))为物理网络拓扑中所有链路的空闲带宽的平均值，|Vv|为虚拟网络拓扑中的虚拟节点数量。

[0069] 其它步骤及参数与具体实施方式一至三之一相同。

[0070] 采用以下实施例验证本发明的有益效果：

[0071] 实施例一：

[0072] 因为网络虚拟化这个领域的开放性，对于物理和虚拟网络真正的特点尚且都是不明确的，所以采用了人工合成网络来模拟的做法。对于底层物理网络采用网络生成工具GT-ITM来生成。虚拟网络采用BRITE来生成链路依赖关系。实验的主要模拟参数如下：

[0073] 表1映射算法模拟参数值

[0074]

[0075]

[0076] 主要的对比算法就是Node-Opt算法。通过大规模多次的实验模拟，我们从多方面对提出的优化算法进行性能比较和分析，主要是比较方面有带宽映射开销(COBM)，算法收益(MR)，开销收益比，算法映射成功率。

[0077] 图3-图6是关于大规模映射算法Node-Merge(本发明方法)和传统算法Node-Opt算法之间的性能比较。通过比较相比传统Node-Opt算法，图3中Node-Opt比Node-Merge在带宽映射开销方面高出将近200％；图4中显示Node-Merge比Node-Opt在映射收益上高出将近30％；从图5中看出Node-Opt比Node-Merge在开销收益比上普遍高出300％以上；图6显示Node-Merge比Node-Opt在不同的虚拟网络请求规模下普遍将映射成功率提高了50％以上，有的甚至高达120％。因此，可以明显看出Node-Merge在大规模虚拟网络映射问题中有着更好的效果。

[0078] Node-Merge算法主要思想就是节点合并策略。把大规模问题简单化，形成一个个虚拟中心，然后通过虚拟中心的动态计算建立一个个的虚拟映射集，在优化映射开销的时候非常直观，直接少了很多虚拟链路的映射，它们变成了物理节点内部的信息交互。而且围绕虚拟中心形成的虚拟映射集其实在虚拟网络拓扑中是一个“团”，其中的通信交互是比较频繁的，所以这样就省略了一大部分的虚拟链路的映射。所以它的带宽映射开销优化最好。而且有效缓解了底层物理网络紧缺的带宽资源，如图6，它有着更好的成功接受率，接受率越高，算法所获得的收益也就越大。

[0079] 本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，本领域技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。