0 引言

随着互联网技术的快速发展，互联网上新型应用层出不穷，现有的网络架构很难跟上互联网新型应用的发展，在某种程度上出现了僵化的现象。网络虚拟化是解决网络结构僵化的一项重要技术，网络虚拟化技术允许多个异构的虚拟网络共享同一个物理网络资源^[1]。它将传统意义上的互联网提供商分成了基础设施提供商(Infrastructure Provider,INP)和服务提供商(Service Provider,SP)两个部分^[2]。在网络虚拟化环境下，基础设施提供商部署和管理底层网络资源，通过可编程接口为不同的服务提供商提供资源。服务提供商租用基础设施提供商的底层网络资源并创建虚拟网络，获得个性化的端到端的网络服务^[3]。虚拟网络映射(Virtual Network Embedding,VNE)技术能有效地利用共享的物理网络资源，最大化物理网络资源的利用率，提高服务质量，降低网络运营成本^[4]。在虚拟化环境下，大多数研究仅针对虚拟网请求是固定不变的情况设计有效的虚拟网络映射算法，但是有时虚拟网络的资源请求数量甚至拓扑结构会随着时间的变化而发生变化(如：在线游戏、分布式计算等)，需要底层的物理网络动态地调整资源分配的方案及时应对虚拟网络请求的变化。底层的物理网络也会因为某些特殊情况(如：网络部件故障、自然灾害、黑客攻击等)的发生而影响到正在运行的虚拟网络，服务提供商需根据物理网络资源的变化情况及时地调整映射方案以满足虚拟网络的正常运行。

虚拟网络映射问题是一个NP-hard问题。即便已经确定了虚拟节点的位置，基于带宽约束的虚拟链路映射问题也是NP-hard问题^[5]。目前大多数研究仅针对虚拟网请求是固定不变的情况设计有效的虚拟网络映射算法，针对动态虚拟网络请求的映射算法还较少。

文献^[6]提出了一种分布式的自治虚拟资源分配算法，在该算法中物理节点能够识别某条物理链路的过载流量，并通过虚拟节点迁移尽可能地减少物理链路的跳数；但该机制没有给出迁移虚拟节点的方法。文献^[7]提出了一种根据物理节点平均负载差异度来迁移虚拟节点的方法，通过综合影响因子来选择虚拟节点适合的迁移节点以减少虚拟节点迁移对物理链路带宽和时延的影响；但该算法只是动态地调整了物理节点间的负载没有考虑物理链路的负载平衡。文献^[8]提出了一种针对动态虚拟网络请求的重配置方法；但是该算法仅考虑了当一个运行中的VN(Virtual Network)请求发生变化时，如何以最小的成本实现对该VN的重配置。文献^[9]从工作负载概率角度考虑虚拟网络映射中的动态资源分配问题，为每个虚拟网络设定一个容忍阈值，建立了一个两阶段的虚拟网络映射算法，然后以共享方式映射虚拟网络节点，物理节点/链路上的空闲资源块由所有虚拟节点/链路按需共享使用，当资源饱和时，利用贪心算法为不满足需求的虚拟节点链路寻找候选映射目标。文献^[10]针对光电混合数据中心网络的特点，针对动态到达的虚拟网络请求，利用非线性优化理论对混合数据中心的虚拟网络映射问题进行建模，然后使用改进的贪心算法对模型进行求解，获得了更好的求解速度；但没有考虑已映射虚拟网络的资源变化问题。

本文提出了面向动态虚拟网络请求的虚拟网络映射(Virtual Network Embedding based on Dynamic Virtual Network Requests,DVNR-VNE)算法，将虚拟网络请求分为三类：一类是已经映射的虚拟网络请求，它所请求的节点或链路资源因为不需要被取消；第二类是已经映射的虚拟网络请求，它的部分虚拟网络节点或链路所请求的资源增加；第三类是新到来的虚拟网络请求。以最小化映射代价和最小迁移代价为优化目标，采用多队列的方式分别对不同类型的虚拟网络请求进行预处理，优先映射需要释放资源的请求以获得更多的资源支持其他的虚拟网络，对新到来的虚拟网络请求采用优化后的WD-VNE(WinDow-Virtual Network Embedding)算法^[11]进行映射。实验表明，该算法可以降低映射成本和迁移成本并且提高虚拟网络请求的接受率。

1 问题描述与网络模型

首先建立了物理网络模型、动态虚拟网络请求模型以及相应的虚拟网络映射问题的模型，进而定义了节点综合能力和影响因子，然后给出了系统模型和优化目标。

1.1 物理网络

物理网络资源状态及拓扑信息由一个无向图G^S=(N^S,A_N^S,L^S,A_L^S)来表示。其中：N^S是物理节点集合，A_N^S表示物理节点计算能力(如CPU、内存、存储等)参数的集合，L^S表示物理网络链路的集合，A_L^S表示物理链路参数(如带宽、延迟等)。本节后续模型的设计中，A_N^S和A_L^S表示节点计算能力参数和链路参数，本文分别使用CPU和带宽作为具体参数。另外对于物理网络来说，任意无环的路径用P^S表示，任意两个物理节点m和n之间的链路用l^s(m,n)∈L^S表示。

1.2 虚拟网络请求

虚拟网络请求由VNR=(G^V,T_a,t,η,R,κ)表示，包含拓扑信息、资源需求量等。其中：G^V是一个无向图用于描述拓扑信息；T_a表示到达时间；t表示该虚拟网络请求的在物理网络中的生存时间；二进制变量η用于区分虚拟网络请求的类型η=1表示该虚拟网络请求是新到达的，η=0表示这是一个已运行的虚拟网络，但其请求发生了动态变化，因而所需资源需要被调整；向量R=[R₁,R₂,R₃,R₄]表示虚拟网络请求的变化形式，R_i是二进制变量，R₁=1表示需要删除某些节点，R₂=1表示某些节点要减少资源，R₃=1表示请求加入新的虚拟节点，R₄=1表示某些节点要增加资源；κ是虚拟网络请求的标识。参数G^V与物理网络类似，其形式为G^V=(N^V,C_N^V,L^V,C_L^V)，其中：N^V和L^V是虚拟节点和虚拟链路的集合；C_N^V和C_L^V分别表示虚拟节点和虚拟链路的资源请求。

1.3 虚拟网络映射问题模型

虚拟网络映射问题可以被看作一个虚拟网络请求(Virtual Network Request,VNR)到底层物理网络S的映射Γ，通过下式进行描述：

$\Gamma :{{G}^{V}}\mapsto ({{N}^{S*}},{{\phi }_{N}},{{P}^{S*}},{{\phi }_{P}})$

(1)

其中N^S*⊆N^S,P^S*⊆P^S，虚拟网络请求中的每个虚拟节点到物理网络节点的映射由Γ_N表示：

${{\Gamma }_{N}}:{{N}^{V}}\mapsto {{N}^{S*}}$

(2)

进一步，对于Γ_N(n^v)∈N^S*,∀n^v∈N^V，加入资源约束条件后的映射可以被描述为：

$RCPU({{n}^{v}})\le CCPU({{\Gamma }_{N}}({{n}^{v}}))$

(3)

$CCPU({{\Gamma }_{N}}({{n}^{v}}))=CPU({{\Gamma }_{N}}({{n}^{v}}))-\sum\limits_{h\in {{N}^{V}}\mapsto {{\Gamma }_{N}}({{n}^{v}})}{RCPU(h)}$

(4)

其中：RCPU(n^v)表示虚拟节点n^v请求的CPU资源的约束，CCPU(Γ_N(n^v))表示目标物理节点空闲的CPU资源。CPU(Γ_N(n^v))表示物理节点总的CPU资源。对于物理节点来说，空闲CPU资源等于总资源减去所有已分配资源。

对于虚拟边的映射，根据其两端虚拟节点被映射的位置，在物理网络中可通过不分流的路径映射或者基于多商品流的路径分割映射，其数学描述为：

${{\Gamma }_{L}}:{{L}^{V}}\mapsto {{P}^{S*}}$

(5)

对于∀l^v(i,j)∈L^V，P^S是物理网络S上的任意路径，即Γ_L(l^v)⊆P^S(Γ_N(i),Γ_N(j))，并且虚拟链路的映射要满足带宽约束：

$Rbw({{l}^{v}})\le Cbw(p),\forall p\in {{\Gamma }_{L}}({{l}^{v}})$

(6)

$Cbw(p)=\underset{{{l}^{s}}\in p\left( q,r \right)}{\mathop{\min }}\,Cbw({{l}^{s}})$

(7)

$Cbw({{l}^{s}})=bw({{l}^{s}})-\sum\limits_{k\in {{L}^{V}}\mapsto {{l}^{s}}}{Rbw(k)}$

(8)

$DIS({{n}^{v}},{{\Gamma }_{N}}({{n}^{v}}))\le \gamma $

(9)

其中：Rbw(l^v)是虚拟链路l^v请求的带宽资源额度；Cbw(p)表示底层物理网络链路的空闲资源，取路径P上空闲带宽资源最小的链路的值；P(q,r)表示物理链路中，节点q和r之间的路径的集合；bw(l^s)表示物理网络链路总的带宽容量。

1.4 节点综合能力

为了衡量节点优劣从而判断映射目标，本文引入了节点综合能力作为判定依据，其数学描述为：

$\begin{align} & Z(n)=CPU(n)\centerdot \sum\limits_{l\in \ell (n)}{bw(l)}\oplus \\ & \sum\limits_{{{n}^{nb}}\in N}{\left[ CPU({{n}^{nb}})\centerdot \sum\limits_{h\in l({{n}_{nb}})}{bw({{n}^{nb}})}/DIS(n,{{n}^{nb}}) \right]} \\ \end{align}$

(10)

其中：n^nb是节点n的邻居节点，DIS(n,n^nb)是节点n到n^nb的路径跳数。

1.5 影响因子

鉴于动态虚拟网络的映射需要重配置机制支持，因此涉及虚拟节点的迁移，那么也就需要判断物理节点上已驻留的虚拟节点迁移代价，因此本文引入了虚拟节点的影响因子，其表达式为：

$\zeta =Z({{n}^{s}})\otimes \varphi ({{n}^{s}})/Z({{n}^{v}})$

(11)

影响因子表示物理节点上驻留的虚拟节点对该物理节点的重要程度，其中φ(n^s)是底层物理节点n^s的利用率，影响因子ζ的值越大其越重要。

1.6 映射成本和接受率

本文节点资源用CPU能力表示，链路资源用带宽表示。与文献^{[4, 12]}类似，首先给出成本和接受率的定义。

定义1 成本。底层物理网络分配给一个虚拟网络请求的CPU资源和带宽资源之和。用C(G^V)表示，形式化为：

$C({{G}^{_{V}}})=\text{ }\sum\limits_{{{l}^{v}}\in {{L}^{V}}}{Rbw({{l}^{v}})}+\sum\limits_{{{n}^{v}}\in {{N}^{V}}}{RCPU({{n}^{v}})}$

(12)

定义2 接受率。虚拟网络请求的接受率表示到t时刻虚拟网络请求被接受的概率，形式化为：

$AcceptRatio=\underset{T\to \infty }{\mathop{\lim }}\,\left( \sum\nolimits_{t=0}^{T}{VNRA} \right)/\left( \sum\nolimits_{t=0}^{T}{VNR} \right)$

(13)

其中：VNRA表示被物理网络成功映射的虚拟网络请求数量；VNR表示到t时刻到达的虚拟网络请求的总数量。

2 系统模型和优化目标

对于动态虚拟网络映射问题，本文利用混合线性规划(Mixed Linear Programming,MLP)理论，建立以最小开销为优化目标的模型。需要注意的是，在模型及后续算法的设计中利用了可重用特性，即允许同一虚拟网络的不同虚拟节点可以被映射到同一物理网络节点上，这样可以节省分配的带宽资源^[13]。

映射开销指为了承载虚拟网络，物理网络所分配的所有资源，包括节点计算资源和链路带宽资源以及由于映射方案调整所需要的迁移虚拟节点及链路的开销，即：

$COST(V)=cost({{n}^{v}})+cost({{l}^{v}})\text{+}cos{{t}_{mig}}$

(14)

虚拟网络的节点映射开销为其计算资源，即所占用CPU资源的总和：

$cost({{n}^{v}})=RCPU({{n}^{v}})$

(15)

虚拟网络的链路映射开销为所有物理路径上所占用的带宽资源的总和：

$cost({{l}^{v}})=\sum\limits_{(i,j)\in {{P}^{s}}}{\varphi _{ij}^{w}}\times Rbw({{l}^{_{w}}})\text{ }$

(16)

其中φ_ij^w是一个二进制变量，由于可重用机制而被引入，其定义为：

$\forall w\in {{L}^{v}}\text{,}\forall i,j\in {{N}^{s}}\text{,}\varphi _{ij}^{w}=\left\{ \begin{align} & 0,\text{ }i=j \\ & 1,\text{ }i\ne j \\ \end{align} \right.$

当i=j时，表示虚拟链路w利用可重用机制被映射到内存中，即虚拟链路ij并没有占用实际物理链路带宽；i≠j时该虚拟链路才被映射到实际物理链路上并被分配了相应带宽资源。

对于虚拟网络来说，迁移开销表示为：

$\text{cos}{{\text{t}}_{mig}}=MCPU({{n}^{v}})+Mbw({{l}^{t}})$

(17)

其中MCPU(n^v)和Mbw(l^w)分别表示迁移节点和迁移链路的代价。对于物理网络来说，无论虚拟网络的节点被映射到哪个物理节点，其计算资源即CPU资源是必须分配且额度不变的，因此在考虑最小映射开销时，CPU资源的开销可以被省略，那么动态虚拟网络映射问题的优化目标可以被定义为：

$\min (cost({{l}^{v}})\text{+}cos{{t}_{mig}})$

(18)

即系统的总体目标为最小化映射该虚拟网络的链路开销与为了映射该虚拟网络产生的虚拟节点和虚拟链路的迁移代价之和。

3 DVNR-VNE算法

针对虚拟网络请求是动态的这一特点，首先建立请求提交的等待队列模型。在请求到达执行映射算法寻找可行的资源分配方案前明确虚拟网络请求的分类并加入相应的队列。本文提出的DVNR-VNE算法使用了三个队列：r_new、r_increase和r_decrease。根据1.2节中参数η和R设置，本文将动态虚拟网络请求分为三类，分别对应算法中的三个队列。当η=1时，说明虚拟网络请求是新的队列，将被加入队列r_new。当η=0时，进一步判断R的值，如果该虚拟网络请求增加节点或者资源，则将其加入队列r_increase；如果该虚拟网络请求减少节点或者资源时，将其加入队列r_decrease。

在三个队列的处理顺序上，为了尽可能充分地利用资源，应当首先处理队列r_decrease中的请求，使其释放不需要的资源。然后处理r_increase中的请求，因为要尽可能地响应已运行的虚拟网络请求对于资源增加或节点增加的需求，以尽量缩短其生命周期并保证用户的服务质量(Quality of Service,QoS)需求。最后才尝试处理队列r_new中的新增虚拟网络请求，因为让未被映射的虚拟网络请求继续等待要强于拒绝已运行虚拟网络请求的资源增加请求。

具体的DVNR-VNE算法的详细描述如算法1所示。

算法1 DVNR-VNE算法。

输入：物理网络G^S=(N^S,A_N^S,L^S,A_L^S);虚拟网络请求VNR=(G^V,T_a,t,η,R,κ)。

1)   根据虚拟网络请求参数将其加入到请求提交的等待队列中；

2)   for 每个r_decrease中的虚拟网络请求 do

3)   释放其请求释放的节点和链路资源；

4)   end for

5)   for 每个r_increase 中的虚拟网络请求 do

6)   if 如果该VNR请求增加资源 then

7)   if 如果需要增加节点资源 then

8)   for 每个要增加资源的节点 do

9)   if 目标物理节点满足 RCPU(n^v)≤CCPU(Γ_N(n^v)) then

10)   为该节点资源增加请求的资源；

11)   else调用vnmig1()函数找到可迁移节点，释放需迁移节点已占用的资源并对其进行重新映射；

12)   end if

13)   end for

14)   end if

15)   if 需要增加链路资源 then

16)   for 每个需要增加资源的虚拟链路 do

17)   if 目标物理链路满足 Rbw(l^v)≤Cbw(p) then

18)   为该虚拟链路分配增加请求的资源；

19)   else 尝试路径分割映射，即利用其他物理路径满足该资源增加请求并使得cost(l^v)最小；

20)   end if

21)   end for

22)   end if

23)   end if

24)   if 该虚拟网络请求申请增加节点 then

25)   for 每个需要被增加的虚拟节点 do

26)   从物理网络节点中找到空闲资源大于该虚拟节点请求的资源综合能力Z(n)最大，并且与相应虚拟节点的距离满足式(9) 的约束的物理网络节点加入集合F；

27)   if F非空 then

28)   找到cost(l^v)最小的映射方案并映射该节点使用k-shortest path 算法对相应的虚拟链路进行路径分割映射；

29)   else 调用vnmig2()重新映射节点，尝试对虚拟链路进行迁移并释放其所占资源；

30)   end if

31)   end for

32)   end if

33)   end for

34)   if r_increase已经为空或队列中所有的虚拟网络请求已被尝试分配5次 then

35)   for 队列r_new中的前processcount 个虚拟网络请求 do

36)   利用文献^[11]中WD-VNE映射算法映射虚拟网络请求；

37)   if 映射成功 then

38)   将其从r_new中移除；

39)   end if

40)   end for

41)   end if

在算法1中，参数processcount是WD-VNE映射算法中的滑动窗口值，即先处理若干个虚拟网络请求，目的是将滑动窗口中虚拟网络请求收益较大的优先处理。另外需要注意的是，r_increase队列中的虚拟网络请求根据类型不同被区别对待，当虚拟网络请求增加某个或某些虚拟节点的计算资源或者链路资源时，只需要考虑该节点或者链路的映射目标对应的物理节点或者物理路径上是否有满足需求的空闲资源，如果有则简单增加即可；当空闲资源不满足条件时，如果是增加节点资源，则需要对目标物理节点上的其他虚拟节点进行迁移以获得更多的资源，即调用vnmig1()函数进行迁移；如果是增加虚拟链路资源，则需要利用其他物理网络路径，对增加资源的虚拟链路作多路径分割映射，即将该虚拟链路映射到多条底层物理网络路径之上，在算法中直接采用k-shortest path算法进行多路径映射。

当虚拟网络请求增加虚拟节点时，必然涉及到虚拟链路的增加，因此需要同时对虚拟节点和虚拟链路进行调整，如果能够在物理网络中找到符合资源约束的目标物理节点和物理链路，则进行直接映射；否则意味着当前物理网络的资源状态无法直接满足要求，因此需要对部分已运行虚拟节点及其相关链路进行适当迁移，本文使用vnmig2()函数对这种情况进行处理。下面是对两个函数的具体算法说明。

算法2 vnmig1( )。

输入：物理网络G^S=(N^S,A_N^S,L^S,A_L^S);目前的虚拟网络映射方案和需要调整的节点编号。

1)   找到需增加资源的虚拟节点n_v驻留的物理节点n_s；

2)   读取n_s上映射的其他虚拟节点集合A；

3)   for each节点 in A do

4)   if 该虚拟节点请求的资源大于n_v需要增加的资源 then

5)   计算该虚拟节点的ζ值；

6)   end if

7)   取最小的ζ值对应的虚拟节点n_v′；

8)   找到n_s的能满足式(9) 的距离约束γ且空闲资源能力大于n_v′占用资源的邻居节点集合B；

9)   if B非空 then

10)   依次遍历B中的所有节点，找到n_v′的迁移目标物理节点，且满足以下要求：根据式(18) 使得迁移n_v′代价最小的目标节点n_s′；

11)   迁移n_v′到n_s′并迁移相应的虚拟链路；

12)   else 将整个n_v看成需要被新映射的节点，调用vnmig2( )函数映射；

13)   If 映射成功 then

14)   释放n_v在n_s上占用的资源；

15)   end if

16)   end if

算法2的思路是，尽量迁移待调整虚拟节点的宿主主机上的能空闲足够资源且影响力最小的其他虚拟网络的节点，将其迁移到宿主主机邻居节点上，并使得迁移代价最小。如果迁移某一个虚拟节点无法满足要求，那意味着要迁移两个或两个以上节点才能满足该虚拟节点的增加资源需求，那么与其进行多个节点的迁移，不如直接将该虚拟节点作为新的虚拟节点重映射到其他物理节点之上，因此调用了vnmig2( )函数，如果成功，则释放原来宿主主机上的资源，这样的好处是使被迁移虚拟节点的个数尽量少，从而减少迁移代价。vnmig2( )函数的具体描述如下：

算法3 vnmig2( )。

输入：物理网络G^S=(N^S,A_N^S,L^S,A_L^S);目前的虚拟网络映射方案和重映射的虚拟节点编号。

1)   找到与需重映射虚拟节点n_v连接的邻接节点集合C；

2)   for each节点in C do

3)   找到与n_v相连的链路所需带宽最大的节点n_v^a；

4)   end for

5)   找到n_v^a所映射的物理节点n_s^a；

6)   for n_s^a节点 do

7)   找到与n_s^a节点满足距离约束γ且剩余节点资源大于n_v节点所需总资源的节点集合D；

8)   将D中的所有节点降序排序，取具有最大空闲资源的物理节点n_s^b；

9)   end for

10)   for 节点n_s^b do

11)   将n_v映射到n_s^b，并利用k-shortest path算法映射相应的虚拟边；

12)   end for

算法3是节点的重新映射算法，主要思路是首先找到与需要重映射节点直接相连的虚拟节点中所需虚拟链路资源最大的节点并找到该节点映射的物理节点。通过此物理节点找到满足距离约束和资源请求约束的候选集合，选择剩余节点资源最大的节点作为迁移节点进行映射，并采用k-shortest path算法迁移相应的虚拟链路。

4 仿真与分析 4.1 仿真环境和参数设置

在CloudSim 3.0.1 上测试了本文所提出的DVNR-VNE算法，硬件平台为配备Intel Core i7- 3770 CPU和20 GB内存的PC。在CloudSim中用Java为底层物理网络和虚拟网络编写了一个拓扑生成器，以连通概率、资源需求边界、节点数量范围作为输入参数生成随机物理网络和虚拟网络拓扑。算法1中的processcount设置为8，三类虚拟网络请求随机分布，实验中涉及到的具体参数如表 1所示。虚拟网络请求增加请求、增加节点资源和新到达的虚拟网络请求服从随机均匀分布。

4.2 仿真结果与分析

在实验一中，假设虚拟网络请求的到达服从泊松分布，平均每100个时间单位有4个虚拟网络请求，物理网络节点数设为100。虚拟网络请求的节点数分别设为4，8，12，16和20。运行100个虚拟网络请求，每种情况运行20次取平均值实验结果如图 1所示。分别将DVNR-VNE算法与文献^[8]中算法的链路映射代价和迁移代价进行比较。从图 1中可以看出DVNR-VNE算法链路映射代价和迁移代价均低于DVNMA(Dynamic Virtual Network Mapping Algorithm)，这是因为DVNR-VNE算法使用了多队列来存储不同类型的虚拟网络请求。如果r_decrease队列中有虚拟网络请求对其进行优先处理，这样能预留出更多的资源为后续的虚拟网络请求服务。随着虚拟网络请求节点个数的增多，链路映射代价和迁移代价逐渐增大，且链路映射代价的差距增大。这是因为本文的算法采用了可重用机制，随着虚拟网络请求节点个数的增多，可重用机制的优势越来越明显。

在实验二中，假设虚拟网络请求的到达服从泊松分布，平均每100个时间单位有4个虚拟网络请求，物理网络节点数分别设为60，70，80，90和100。运行200个虚拟网络请求，每种情况运行20次取平均值，实验结果如图 2所示。从图中可以看出DVNR-VNE算法的成本低于DVNMA，这是因为DVNR-VNE算法采用了可重用技术且优先处理减少资源的虚拟网络请求，这样后续的虚拟网络请求映射的可选资源更充足。随着物理网络节点的个数的增加，在处理相同虚拟网络请求的情况下，DVNMA的成本减少比DVNR-VNE算法明显，这是因为在物理节点增多的请求下，采用DVNMA映射虚拟网络请求可选择资源增多，且DVNR-VNE算法因采用了节点可重用技术，而使新增节点对采用DVNR-VNE算法的映射结果影响不大。

在实验三中，物理网络节点数设定为80。运行1 000个虚拟网络请求，运行20次取平均值，实验结果如图 3所示。从图 3可以看出在前2 000 s内两种算法的接受率都急剧下降，这是由于随着虚拟网络请求的不断到来物理网络逐渐趋于饱和状态，能承载的新到来的虚拟网络请求能力减弱。随着时间增长，算法的接受率趋于稳定且DVNR-VNE算法的接受率比DVNMA的接受率高大约5%，原因在于算法采用了可重用技术，这样可以节约部分链路的映射开销，能使物理网络承载更多的虚拟网络请求，算法采用的多队列和滑动窗口技术首先映射的是已运行着的虚拟网络请求，使占用资源的虚拟网络请求能尽早地满足变化的请求完成任务，且并不是映射不成功就直接加入到队列后面而是在滑动窗口内等待一段时间再重新映射，这样提高了虚拟网络完成工作的效率，使得已运行的虚拟网络请求的运行时间缩短从而能接受新的请求任务。在映射调整的过程中是映射到满足要求的且剩余资源最多的节点上，这样虽然在一定程度上增加了映射成本，但是负载趋于均衡，为后续到来的虚拟网络请求提供了更多的映射成功机会。

5 结语

本文针对多租赁模式下的动态虚拟网络请求映射问题，提出了一种物理节点可重用多队列存储虚拟网络请求的DVNR-VNE算法，该算法首先对到来的虚拟网络请求进行分类，并建立虚拟网络请求存储队列模型，优先映射需要释放资源和已运行的虚拟网络请求，使得被占用资源尽早完成任务；采用了节点可重用的方法，以内存交换代替虚拟链路从而减少了物理链路资源的使用。仿真实验表明，该算法降低了链路映射成本和迁移成本并提高了虚拟网络请求接受率。此外DVNR-VNE算法仅用了最短路径算法来作路径的迁移，因此在路径迁移的优化方面还有一定的改进和发展空间。