保持节点相邻的虚拟网络映射算法

彭红姣，潘子辉

（1.南京邮电大学 工程训练中心，江苏 南京 210023；2.南京邮电大学 计算机学院，江苏 南京 210046）

全球互联网持续高速发展，远超出互联网原设计初衷，使现有网络体系架构不具备可控可管性、服务质量难以保障、可扩展性较差、移动性支持较差等问题越为突出。随着网络规模进一步增长，这些问题暴露更为明显。云计算、物联网、大数据、人工智能、大流量视频等新应用和新技术的不断涌现，也对现有互联网提出了更高要求。为从根本上解决现有网络面临的问题，打破互联网僵局，研究者们经过不懈努力，认为网络虚拟化（Network Visualization，NV）[1-5]是一个很有前景的方法，其包括新型网络更便捷的迁移方案，更易与现有网络共存。本文研究了其虚拟网络映射问题并提出一种新算法，与经典的两步式映射算法进行了比较，并分析其优势和适用环境，验证了其可行性。

1 虚拟网络映射算法研究

1.1 现状和问题

虚网映射问题是网络虚拟化最核心的问题之一，也是一个充满挑战性的问题[6]。在虚网映射中，虚拟网络请求各自对应的网络拓扑往往不尽相同，因此要适应这些不同的拓扑请求。在分配资源时，节点和链路需求要同时满足要求。一般情况下，虚网请求都是动态的，在分配当前物理资源时，不能预知将要到达的虚网请求信息。即使是静态请求，或所有请求信息也能预知，虚网映射问题仍是一个NP-hard问题，可转化为多路分离器问题[7-10]。另外，即便已确定节点映射，在流不可分割情况下，即在一个单一路径上最佳地分配一个虚拟链路集，虚拟链路的映射仍是一个NP-hard问题，但可转化为不可分割流问题[11-12]。

至今，研究人员已提出不少提高物理资源利用率的虚网映射算法，可得出某种网络环境下较为适合的映射结果。由于虚网映射是一个NP-hard问题，需考虑的影响因素非常多，有些算法[13-15]以物理链路资源无限大为前提，从而实现更合理的节点映射。另一部分算法[1,16-17]侧重于链路映射，以寻找最优链路映射为目的，而相对的节点映射则采取简单处理。这两个偏向都会存在一些问题[18-19]。

假设链路资源无限大，节点映射算法通常能取得非常好的效果，这些算法可有效提高物理节点资源的利用率，同时可保证节点相对紧凑（即节点间距离相对较小）。而实际上，链路资源不可能为无限大，这种理想情况并不存在。故此类节点映射算法通常会在链路映射上遇到困难，最典型的两个虚拟节点所映射到的物理节点之间的物理链路资源，无法满足其虚网请求中虚拟链路的需求。其次，如果优先选择带宽资源较多的节点进行映射，确实能很好地满足对物理链路及物理节点资源的需求。但由于总是优先占用带宽资源最为充裕的节点，可能会对后来的虚拟网络请求造成一定影响。另外，如将节点和链路映射分别执行，对于虚网请求中相邻或相近的节点，在映射后其对应的物理节点在物理网络中距离可能会非常远。这种分布分散的情况常常会导致虚拟链路过多占用网络资源，致使物理资源利用率降低。本文给出了一种保持节点相邻的虚拟网络映射算法，可有效避免上述问题，或减少其所带来的不利影响。

1.2 经典的两步式虚拟网络映射算法

文献[20]介绍了最为经典的虚拟网络映射算法——两步式虚拟网络映射算法，该算法既简洁又通用，映射简化为虚拟节点映射和虚拟链路映射。在虚拟节点映射中先使用贪婪算法进行求解，再在虚拟链路映射中使用k最短路径算法进行求解。

定义1映射收益是指映射到物理网络成功后，虚网请求的收益，由映射的带宽和CPU资源定义：

其中，B(eν)是映射成功的虚拟网络带宽，C(nν)是映射成功的虚拟网络节点CPU资源，α和β是用于调节带宽和CPU的权重系数，在本文研究中均设为1。

定义2剩余资源（Available Resource,AR）是指某节点剩余物理资源与连接该节点的链路资源总和的乘积：

其中，nP为物理节点，lP为物理链路，L(nP)为与物理节点nP直接相连的物理链路的集合。

在两步式虚拟网络映射算法中，先以时间窗为单位接收虚网请求。再根据映射收益R(GV)对一个时间窗内的虚网请求由高到低排序，收益高优先映射。若映射成功，则更新物理网络状态；若映射失败，则将其列入等待队列；若失败次数超过预先设定的值，则放弃该虚拟网络请求。

在每个虚网映射请求时，先进行节点映射环节。对于请求中的每个虚拟节点(nV)，通过贪婪算法找出能够满足其节点CPU需求，以及剩余资源最大物理节点(nP)。若能找到满足nV条件的nP，则将nV映射到nP上，节点映射成功；否则，节点映射失败，虚网请求映射失败。若每个节点映射成功，则虚网请求节点映射成功。寻找物理节点过程考虑了与之相连接的物理链路资源，链路映射率得到提高。在完成节点映射后，执行链路映射。对于虚网请求中的每条虚拟链路(lV)，首先确定其两端点，之后找到其映射的物理节点，通过k最短路径算法，找到物理节点间的1至k条最短路径，若其中有任意一条路径满足lV的带宽需求，则将lV映射到该路径上；若物理路径均不满足条件，则不能完成虚拟链路映射，无法实现虚网请求映射。只有全部完成每个虚拟链路映射，才能完成虚拟链路映射环节。两个环节全部成功后，即可完成整个虚网请求映射。

1.3 虚网请求接收算法改进思路

一旦虚网请求在短时间内涌入，则会出现先到请求阻塞，或低收益请求长时间得不到满足而产生饥渴现象等问题。为了保证算法高效运行，并取得较高的映射收益，同时避免低收益请求长时间得不到处理，本节提出了一种算法来应对这些困难。

虚拟网络请求将实时到达，并将它们按照时间窗进行划分。每个时间窗收到的虚拟网络请求按收益进行排序，且按收益由高到低设立优先级（优先级数值越大则优先级越低），映射失败时设其优先级为当前最低优先级加1，从而加入队列末尾，并设置其count参数加1，count参数达到一定数值后（数值大小视具体情况而定），放弃该请求。当新的时间窗到达时，释放已完成或者失效的资源，对于新到时间窗内的请求，在计算其优先级后，对其优先级加上[x/2（]x为上一时间窗的请求总数），对于优先级相同的请求，优先处理较早到达的。这样可在有效确保较高收益的同时，保证低收益请求不会长时间得不到处理。

具体算法，步骤1：令x=0，c=0；步骤2：检测是否有新的时间窗到达，若没有，则跳至步骤5；步骤3：释放已完成或者失效的资源，对时间窗内虚拟网络请求进行统计，令y为该时间窗内虚拟网络请求的数量，令c=c+1；步骤4：将该时间窗内虚拟网络请求按收益从高到低进行排序，分别设其优先级为(1+[x/2])到(y+[x/2])β，且分别设其count[z]为0（z为序号），W[z]=c，令x=y；步骤5：寻找当前优先级最高的虚拟网络请求（优先级数值最小），若结果唯一，跳至步骤7；步骤6：寻找结果中W[z]最小的虚拟网络请求；步骤7：将该虚拟网络请求进行映射，若不成功，count[z]=count[z]+1，若count[z]=3，放弃该请求，优先级设为当前最低优先级+1，并跳至步骤2。

例如，第一个时间窗中共有20个虚网请求，按请求收益由高到底给出优先级1至20。若优先级为5的虚拟网络请求失败，则将其优先级设为21，从而加入队列末尾。若在一个时间窗内只能处理10个请求，而第二个时间窗又涌入10个虚拟网络请求，则将第二个时间窗中的虚拟网络请求按其受益从大到小优先级分别设为11至20。然后优先处理第一个时间窗中优先级为11的虚拟网络请求，再处理第二个时间窗中优先级为11的请求，之后再处理第一个时间窗中优先级为12的请求，依此类推。

2 设计保持节点相邻的虚拟网络映射算法

本节针对完成映射后相邻虚拟节点所对应的物理节点过于分散的情况，提出了一种既考虑节点映射又考虑链路需求的保持节点相邻的虚拟网络映射算法。

如图1所示，在虚网请求到达时，大多算法会将虚拟节点a、b、c分别映射到物理节点A、F、B。这样，在虚拟网络请求中相邻的两对节点（a与b，b与c）之间的距离就相对较远。但如果将虚拟节点a、b、c分别映射到物理节点A、D、E，则既能满足节点需求，又能满足链路需求，同时在虚拟网络请求中相邻的两对节点在实际物理网络中仍旧保持相邻，大大减少了物理链路资源的耗费，同时保持节点相邻可以提高实际工作效率，从而提高了服务质量。

图1 节点资源优先节点映射。（a）虚拟网络请求；（b）物理网络

2.1 物理资源与虚拟网络请求的描述

物理资源和虚拟网络请求可用无向加权图表述。物理资源GP，GP=，其中，NP为物理结点集合，EP为物理链路集合，权(nP)指结点nP∈NP的属性（如计算能力），权(eP)指链路eP∈EP的属性（如带宽大小）。同理，虚网请求GV，GV=其中，权为虚拟结点的资源需求为虚拟链路的资源需求（如请求分配的计算能力和网络带宽等）。将GV部署到GP上的虚网映射记为M:GV→GP，其中，节点映射记为MN:NV→NP，链路映射记为ME:EV→EP。

2.2 割与k-割检验

定义3（割）[21]N，网络G=(N,E,AN,AE)的结点集合，对N的一个划分称为G的一个割。

其中MN(S)={nP|nP=MN(nV),nV∈S}。

定理1（可行性检验定理）[22]当且仅当MN通过所有的k-割检验，MN有可行的链路映射与之对应，其中k∈[1,[|NV|/2]]。

文献[30]表明，当节点映射MN通过k-割检验时，对应存在可行链路映射的概率为93.9%，故可排除掉绝大部分不具备相应可行链路映射的节点映射。本文所提算法需要k-割检验时，都只进行1-割检验，1-割检验的实例如图2所示。

图2 节点资源优先节点映射

2.3 保持节点相邻的虚拟网络映射算法

本节提出的算法在略微降低映射效率的情况下，提升了映射成功率和物理资源，特别是物理链路得到高效利用，并使虚网请求中相邻的节点在实际映射后的物理网路中尽可能保持相邻，从而提升映射后虚拟网络的运行效率，提高了服务质量并改善了映射效果。具体算法描述如下文。

图3 给出了虚拟网络请求和供映射的物理网络，虚拟网络请求a，b，c 三个节点的节点需求分别为20，15，10，其间的链路需求分别为10，15，20，供映射的物理网络A，B，C，D，E 五个节点的节点资源分别为40，30，5，10，20，其间的链路资源分别为10，30，20，30，15。根据上述算法，首先寻找虚拟网络请求中节点需求资源最大的节点，即为a 节点，然后寻找物理网络中节点资源最多的节点，即为A 节点。经过判断，A节点的节点资源满足需求，但是不能通过1-割检验，所以去除A节点，再在剩余节点中寻找资源最多的节点，即B节点，其能够满足a节点的需求，又能通过1-割检验，因此将虚拟节点a映射到物理节点B上，并更新B节点剩余资源为10。之后寻找与a节点相邻的需求资源最多的虚拟节点，即为b节点，a，b节点间的虚拟链路需求为10。之后寻找与物理节点B相邻且之间链路能够满足链路需求的节点，即为A和C，其中节点资源最多的是A节点。经过判断，A节点既能满足b节点需求，又能通过1-割检验，因此将b节点映射到A节点上，并更新A节点剩余资源为25。之后寻找虚拟网络请求中与a节点相邻的、除b节点外的，且节点资源需求最多的节点，即c节点，a，c节点间的虚拟链路需求为20。之后寻找物理资源中与B节点相邻的、能够满足链路需求的节点中，节点剩余资源最大的节点，即C节点。经过判断，C节点不能满足虚拟节点c的节点需求，而有没有其他与A相邻的节点，因此将已映射的虚拟节点a，b，物理节点B，A排除，将剩下的节点继续回到算法最初开始进行。寻找虚拟请求中需求资源最多的虚拟节点，即c节点。之后寻找物理网络中节点资源最多的节点，即E 节点。经过判断，物理节点E 能够满足虚拟节点c 的节点资源需求，并且能够通过1-割检验，因此将c节点映射到物理节点E上，从而完成映射。算法具体步骤如

图3 保持节点相邻的虚拟网络映射算法实例

步骤1：记虚拟节点集合为N(nV)，物理节点集合为N(nP)；

步骤2：若集合N(nV)为空，则映射成功，结束算法；若集合N(nV)不为空，则寻找集合N(nV)中节点资源要求最高的虚拟节点，记为节点

步骤3：寻找集合N(nP)中剩余节点资源最多的物理节点，若其能够满足节点的需求，并且能够通过1-割检验，则将其记为节点若其能够满足节点的需求，但不能够通过1-割检验，则将其排除出集合N(nP)，返回步骤3重新执行；若其不能满足节点的需求，则映射失败；

步骤6：在N()中寻找需求最大的虚拟节点，记为节点，且节点与节点之间的虚拟链路为；

步骤8：寻找集合N中节点资源最多的节点，若其不能满足节点的需求，则将节点排除出集合N，跳至步骤6；若是能够满足节点的需求但不能够通过1-割检验，则将其排除出集合N，返回步骤8重新执行；若最终未能找到可行的节点或已不存在满足链路需求的链路，则将虚拟节点排除出集合N，跳至步骤6；若寻找到的节点能够满足节点的需求且通过1-割检验，则将其记为节点若是集合N中所有虚拟节点都已经通过步骤8 但没有成功映射，则更新集合N(nV)为还未被映射的虚拟节点集合，跳至步骤2；若是集合N中所有虚拟节点都已经通过步骤8且成功映射，则跳至步骤11；

3 实验分析

3.1 实验环境

本文采用自主设计的虚拟网络映射仿真器进行仿真实验。其中，网络拓扑情况（包括虚拟网络请求虚拟节点个数、虚拟节点的节点资源、链路状况、物理节点、链路资源等）由GT-ITM[23]随机生成。仿真器通过设置不同的参数（如虚拟网络请求虚拟节点个数取值范围、虚拟节点的节点资源取值范围等）来模拟不同的虚拟网络请求与物理网络环境。在各种情况下，对保持节点相邻的虚拟网络映射算法（以下称本算法）进行仿真，并将其与经典的两步式虚拟网络映射算法（以下称两步式算法）进行比较。

3.2 仿真实验结果与分析

（1）虚拟网络请求与物理网络环境情况A

根据表1设置，得到仿真结果如图4～6所示。从映射结果看，在物理资源充足的网络环境下，两种算法都有很高的映射成功率，而在保持节点相邻、提高物理链路利用率、优化映射效果的目标来看，本算法虽然会随虚拟链路存在概率的升高（即虚拟网络请求的拓扑复杂度升高）而降低效果，但始终比两步式算法高很多，也就是说映射效果要好很多。可以看出，两种算法都比较好地做到了节点压力的均衡，其中两步式算法表现更为出色一些。

表1 虚拟网络请求与底层物理网络的生成相关参数

图4 映射成功率随虚拟链路存在概率变化

图5 虚拟网络请求仍旧相邻的比率随虚拟链路存在概率变化

图6 物理节点利用率的方差随虚拟链路存在概率变化

（2）虚拟网络请求与物理网络环境情况B

根据表2设置，得到仿真结果如图7～9所示。从映射结果看，随着虚拟网络请求虚拟节点个数取值范围的增加（即虚拟网络请求扩大），尤其是虚拟节点个数超过物理节点个数一半时，两种算法的映射成功率都有明显下降。当虚拟网络请求中虚拟链路的需求相对于物理链路资源较高时，本算法的映射成功率明显高于两步式算法。同时，通过图8 也可得出，当虚拟网络请求中虚拟链路的需求相对于物理链路资源较高时，本算法相对于两步式算法仍可达到一个较好的虚拟网络请求中相邻节点映射后仍旧相邻的比率，也就是能提高虚拟链路的利用率，从而达到一个较好的映射效果。由物理节点利用率的方差均较低可以看出，两种算法都较好地做到了节点压力的均衡，而其中两步式算法表现更为出色一些。

表2 虚拟网络请求与底层物理网络的生成相关参数

图7 映射成功率随虚拟节点个数取值变化

图8 虚拟网络请求中仍旧相邻的比率随虚拟节点个数取值变化

图9 物理节点利用率的方差随虚拟节点个数取值变化

（3）虚拟网络请求与物理网络环境情况C

根据表3设置，仿真结果如图10～12所示。从映射结果看，虚拟网络请求中虚拟节点资源的取值变化对这两种算法各方面影响都不是很大。但是，从图10 可以明显地反映出在这种情况下本算法映射成功率普遍高于两步式算法。同时，由图11可知，本算法映射在提高物理链路利用率、提高服务质量、优化映射结果方面要明显优于两步式算法。由图12 可知，虚拟网络请求中虚拟节点资源的取值范围的提高会降低节点压力的均衡程度，虽然上升幅度很大，但绝对数值却很小，因此可以说两种算法在节点压力均衡上都表现良好。

表3 虚拟网络请求与底层物理网络的生成相关参数

图11 虚拟网络请求中仍旧相邻的比率随虚拟节点资源的取值变化

图12 物理节点利用率的方差随虚拟节点资源的取值变化

（4）虚拟网络请求与物理网络环境情况D

根据表4设置，仿真结果如图13～15所示。从映射结果看，在虚拟网络请求中虚拟链路资源需求相对于物理链路资源较低时，两种算法都能保证比较高的映射成功率。而当虚拟链路资源相对于物理链路资源变得较大时，两种算法的映射成功率都有明显下降。由图13可知，本算法的映射成功率在苛刻的链路条件下会高于两步式算法。而作为本算法的主要目标，由图14可知，虚拟网络请求中相邻节点映射后仍旧相邻的比率在各种虚拟链路条件下都比两步式算法高得多，可见其在提高物理链路资源利用率、优化映射结果、提高服务质量方面做得很好。由图15反映出的较低物理节点利用率的方差可知，两种算法在节点压力均衡方面都表现优良，而本算法只是略微逊色一些。

表4 虚拟网络请求与底层物理网络的生成相关参数

图13 映射成功率随虚拟网络请求中虚拟链路资源的取值变化

图14 虚拟网络请求中仍旧相邻的比率随虚拟链路资源的取值变化

图15 物理节点利用率的方差随虚拟链路资源的取值变化

4 结束语

相比于经典两步式算法，本算法在相对物理资源充足、虚拟网络请求节点资源需求较大、虚拟网络请求链路资源需求较大等几种情况下都有不错的映射成功率。在虚拟网络请求中，只有虚拟链路资源需求相对于实际物理链路资源要求苛刻时，才会存在比较低的映射成功率。因此，在绝大多数虚拟网络映射中，本算法可行性比较高，且在虚拟网络请求中相邻节点映射后仍旧相邻的比率在虚拟网络请求与物理网络环境情况中都表现出色，同时在提高物理链路资源利用率、优化虚拟网络映射效果、提高映射后的服务质量方面非常好。在对虚拟网络映射结果要求较高情况下的适用性很高，并且在保持节点压力均衡方面也较出色，达到了现今对于网络负载均衡方面的需求。