朱国晖，刘秀霞+，张 茵，陈 刚

(1.西安邮电大学 通信与信息工程学院，陕西 西安 710121；2.中国联合网络通信有限公司东营市分公司，山东 东营 257000)

0 引 言

网络虚拟化[1]为传统的互联网提供了更大的灵活性和更好的可管理性，其关键在于虚拟网络映射(virtual network embedding，VNE)[2]。在VNE过程中若出现设备故障、大规模灾害或恶意攻击等情况，导致虚拟网络(virtual network，VN)请求服务失败，基础设施提供商(infrastructure provider，InP)[3]将会根据服务等级协议(service level agreement，SLA)的规定，为租户提供赔偿[4]。因此，保证VN请求的正常进行，变得尤为重要。

目前，相关学者针对物理网络中出现节点和链路故障问题进行了研究，并采用主动保护和被动恢复两种策略，来保证虚拟网络的生存性，将这种恢复策略方法称为生存性虚拟网络映射(survivable virtual network embedding，SVNE)算法。对于主动保护策略：文献[5-7]采用备份整个物理网络拓扑的方案，虽然这保证了节点的恢复率，但是却浪费了许多物理资源；文献[8,9]提出一种主动的基于混合策略的启发式链路备份算法。对于被动恢复策略,文献[10,11]提出一种节点迁移与重映射方法，但在物理剩余资源较少时，恢复的成功率较低。

综上，针对以上文献中存在的不足，本文从多节点故障场景出发，为解决物理节点故障问题，提出一种基于多节点故障恢复的虚拟网络映射算法。在虚拟请求到来之前，利用广度优先搜索算法，为物理节点创建备份节点集合；在虚拟请求到达时，根据目标函数，求解线性规划；当出现节点故障时，在节点备份集合中根据节点恢复度因子值，选择最佳候选节点，并逐个进行VN重映射，从而增加了InP的长期业务利润，缩短了故障恢复时延，提高了故障恢复率。

1 建立网络模型

1.1 物理网络和虚拟网络模型

本文采用文献[12]，建立网络模型。

物理网络：抽象为加权无向图Gs=(Ns,Ls)， 其中，Ns和Ls分别为物理节点集合和物理链路集合。c(ns)表示物理节点ns∈Ns的节点计算能力。b(ls)表示物理链路ls∈Ls的链路带宽。

在物理网络中，将物理节点ns主用资源需求表示为cp(ns)=αc(ns)， 备用资源需求表示为cb(ns)=(1-α)c(ns)，α为主用比例。同样，物理链路的带宽资源也分为bp(ls) 和bb(ls) 两部分。

虚拟网络与物理网络类似，详细见文献[13]，记为Gv=(Nv,Lv)。c(nv) 是虚拟节点nv∈Nv的节点资源大小。b(lv) 是虚拟链路lv∈Lv的带宽大小。

1.2 虚拟网络重映射

虚拟网络重映射定义请详见文献[4]，此处不再赘述。VN重映射过程，如图1所示，在VN映射过程中，节点A发生故障，虚拟节点a上的资源就要重映射(重新分配资源)到物理节点D上，将虚拟链路(a，b)和(a，c)分别重映射到物理链路(C，D)和(B，D)上。

图1 虚拟网络映射实例

1.3 评价指标

(1)InP的长期业务利润

映射一个虚拟网络请求获得的收益R(Gv) 是在虚拟网络Gv的生命周期内，将物理网络资源成功分配到的虚拟节点和虚拟链路上的资源能力之和。故R(Gv) 可表示为

(1)

其中，β和γ设为1，分别是虚拟节点和虚拟链路的能力的单价。

在VNE过程中，一个物理节点出现故障，并且该物理节点上承载的VN请求无法恢复工作，即节点故障恢复失败，则InP需要按照SLA中的规定支付罚款，定义为

(2)

其中，ω为惩罚因子，设为2，G′v为受节点x影响的任意一个VN

(3)

其中，D(x) 是受x节点影响而失效的VN的集合。

定义InP在时间T内的长期业务利润profit(T)

(4)

其中，Nm(T) 映射成功的VN的集合，B(T) 是故障物理节点组成的集合。

(2)VN请求接受率

(5)

其中，Nm(t) 是t=0到T时刻映射成功的集合，N(t) 是所有到达的VN请求的集合。δ是趋于零的正数。

2 基于恢复度因子的生存性虚拟网络映射算法

2.1 基于节点恢复度因子的候选节点选择策略

2.1.1 构建物理节点候选集合

图2 物理网络资源配置

关于物理节点候选集合的构建算法，其伪代码如下。

算法1： 物理节点候选集合的构建算法

输入：Gs,x∈Ns，h′=1,2,…,h

输出：Cov(Gs,x,h)

(1)初始化跳数h′=1

(2)for 物理节点x∈Nsdo

(3) 使用广度优先搜索算法， 计算距离节点的最短路径为h′ 跳的节点集合J(Gs,x,h′)

(4)h′++， 增加一跳

(5) if 当前跳数大于预定跳数即h′>hthen

(6) return 得到h跳之内的所有节点集合Cov(Gs,x,h)

(7) else 转到步骤(4)

(8) end if

(9) end for

2.1.2 定义节点恢复度因子

(1)物理节点的生存性概率

当一个物理节点x发生故障时，若候选节点上实时剩余的备份资源较多，则重映射成功的概率较高，反之，则重映射成功的概率较低，在本文中定义节点生存概率为P(ri)， 表示当一个节点发生故障时，在它的候选节点ri进行重映射，并且使得VN请求正常工作的概率。

对于物理节点ns定义两个变量

(6)

(7)

在物理节点x发生故障时，若节点x的一个候选节点ri∈Cov(Gs,x,h) 上的剩余可用资源Q(ri) 大于节点x已使用的资源A(ri) 时，在节点ri上进行重映射成功的概率就会较高，当Q(ri) 小于A(ri) 时在节点ri上进行重映射成功的概率就会较低。根据上述特点，定义一个归一化的节点生存概率P(ri) 来表示这个关系

(8)

其中，δ为趋于零的正数。

(2)接近中心度：节点与物理网络中可到达该节点最短跳数之和的倒数[14]

(9)

(3)节点资源度：节点计算资源与所有相邻链路带宽资源的和

(10)

(4)由式(9)和式(10)得到节点重要度

M(ri)=D(ri)U(ri)

(11)

(5)由式(11)和式(8)可得到节点恢复度因子

(12)

在图2中，矩形框中的内容表示节点的资源需求，例如节点B旁边的矩形框中“P∶5/7”表示节点主用资源共7个单位，目前已经使用了5个单位，而“B∶3/6”表示节点备份资源共6个单位，已经使用了3个单位，物理链路和节点表示类似。由此可以计算出物理节点A上的A(A)=23， 对于节点A在一跳范围内的候选节点B、C、D，根据式(8)可得，P(B)=0.456，P(C)=0.432，P(D)=0.691， 由此可知当节点A发生故障时，节点D作为备份节点进行重映射成功概率较高。

但是，物理网络的资源是有限的，在保证恢复率的同时，也必须考虑整个物理网络资源的有效利用，故提出了节点重要度。节点重要度越大，则该节点在物理网络拓扑中越重要，则它成为其它故障节点的备份节点的可能性就越大，因此若优先使用重要度小的候选节点，将重要度大的节点用于恢复那些重要的虚拟节点，则有利于优化剩余备份资源的连通性。

于是考虑到节点重映射成功的概率和剩余备份资源的连通性，提出了节点恢复度因子，它将两种因素进行了折中处理，在故障节点x的候选集中，优先使用恢复度因子值最大的节点进行重映射。如图2中节点A的3个候选节点的恢复度因子分别为ε(B)=0.064，ε(C)=0.042,ε(D)=0.038， 由此可得在节点A发生故障时，在节点B上进行节点重映射的综合质量最佳。

2.2 虚拟网络重映射的混合整数规划

本文采用对单一节点故障恢复的逐一优化策略，来提高在多节点故障场景下，整体的长期业务利润。

(1)目标函数

(13)

目标函数由两部分组成，第一部分表示最小化由于物理节点故障，导致VN失效，所支付的罚款；第二部分表示最小化虚拟链路重映射占用的带宽资源，ξ为权重因子，设为1。

(2)定义变量

myr：若虚拟节点y∈G′v∈D(x) 重映射到物理节点r∈Cov(Gs,x,h) 上时myr=1， 否则，myr=0。D(x)是受节点x影响而失效的VN组成的集合。

θnvr：若虚拟节点nv∈G′v映射到物理节点r∈Cov(Gs,x,h) 上时θnvr=1， 否则，θnvr=0。nv∈G′v表示节点nv和节点y在同一个虚拟请求中。

fuw：物理链路 (u,w) 用于链路重映射占用的带宽资源。

(3)约束条件

备份资源约束

(14)

(15)

式(14)和式(15)表示任意用于重映射的节点，它的实际可用备份资源要大于等于被替代节点的计算资源；用于重映射的物理链路，它的实际可用备份带宽也要大于或等于被替代链路的带宽。

节点重映射约束

(16)

myr=0,θnvr=1,y∈N′v(x),
r∈Cov(Gs,x,h),nv∈G′v

(17)

式(16)表示一个物理节点发生故障，至多有一个候选节点进行重映射，式(17)表示在相同VN中的虚拟节点不能同时重映射在相同的物理节点上。

变量约束

myr∈{0,1}, ∀y∈N′v(x),r∈Cov(Gs,x,h)

(18)

对于基于恢复度因子的生存性虚拟网络映射算法(RE-SVNE)的伪代码描述如下。

算法2： RE-SVNE算法

输入：Gs，Gv

输出：Embedding(Gv)

(1) forx∈Nsdo

(2) 根据算法1计算候选节点集Cov(Gs,x,h)

(3) end for

(4) forri∈Cov(Gs,x,h) do

(5) 根据式(8)计算Cov(Gs,x,h) 集合中每个节点生存概率

(6) 根据式(11)计算Cov(Gs,x,h) 集合中每个节点重要度

(7) 根据式(12)计算Cov(Gs,x,h) 集合中每个节点的恢复度因子值

(8) 将节点x的候选集合中的节点按恢复度因子值降序排列,并将结果存入Nodeslist

(9) end for

(10) for 每个VN请求 do

(11) if VN请求到达时， 未发生物理节点故障 then

(12) 采用文献[15]的VN映射算法进行映射

(13) end if

(14) if 物理节点x发生故障 then

(15) 统计受x影响而失效的虚拟节点和虚拟链路构成的集合

(16) for 每个失效虚拟节点 do

(17) 根据式(13)目标函数求解线性规划，在Nodeslist中ε(ri) 值最大的候选节点上，逐个进行虚拟节点重映射处理

(18) end for

(19) for 每个失效虚拟链路 do

(20) 使用K最短路径算法进行链路重映射[17]

(21) end for

(22) end if

(23) forri∈Cov(Gs,x,h) do

(24) 更新ε(ri) 的值和结果集Nodeslist

(25) end for

(26) returnEmbedding(Gv)

3 实验仿真

3.1 实验环境

本文的实验环境为：内存是4 GB，操作系统是64位的Win7系统，处理器是Intel i5。其中，采用MATLAB软件进行实验评估，在实验中用到的网络拓扑均由GT-ITM[17]生成，设置物理节点故障的到达服从参数为0.03的泊松分布，故障持续时间服从参数为d的指数分布,h的值为3，具体的参数见表1[18]。本实验运行50 000个时间单元，为体现实验结果的稳定性，结果均采用10次实验的平均值。

表1 实验参数配置

3.2 对比方案和性能选取

将文献[19]中TA-SVNE算法和文献[4]Blind-SVNE算法与本文所提RE-SVNE算法在长期业务利润、VN接受率、VN恢复率、重映射平均计算时间和主用比例α对算法的影响程度进行算法性能比较。

3.3 仿真结果与分析

(1)长期业务利润

图3是发生多个物理节点故障时，使用InP的长期业务利润来比较3种算法的性能，其中主用比例α为0.7。如图3(a)和图3(b)所示，RE-SVNE算法的长期业务利润要都高于其它两种算法，并且当节点故障平均持续时间从25增大到50时，RE-SVNE算法的长期业务利润的影响并不大，而对于TA-SVNE算法和Blind-SVNE算法的性能显著下降。这是因为随着发生多节点故障概率增加，用于恢复故障的物理剩余备份资源会被过度占用，而RE-SVNE算法，在提高恢复率的同时还优化了备份资源的连通性，确保那些连通性好的节点不会被过度占用，将其用于恢复受其节点故障影响的VN中罚款较高的，减少InP必须支付的罚款，来提高长期业务利润，由此验证当发生多节点故障的概率增大时，RE-SVNE算法有更好的稳定性。

图3 长期业务利润

(2)VN请求接受率

图4是关于3种算法的VN请求接受率的比较，RE-SVNE算法的请求接受率介于其它两种算法之间。因为Blind-SVNE算法没有任何的备份资源，将物理网络资源全都用来进行VN映射，故接受率最高，RE-SVNE和TA-SVNE算法要将一定比例的物理资源用于VN重映射，故接受率稍低，但RE-SVNE算法重映射时采用的节点选择策略，会使得剩余资源的连通性比较好，使其VN接受率相比TA-SVNE较高。

图4 VN请求接受率

(3)VN恢复率

图5中是关于3种算法的VN恢复率的比较，如图5所示，文中所提算法RE-SVNE的恢复率都高于其它两种算法。因为随着到达VN的增多，物理资源不断被占用，故障节点的个数增多，用于重映射资源被过度占用，因此VN恢复率会快速降低，而RE-SVNE算法优先选择恢复度因子值最大的候选节点，使得剩余备份资源的连通性得到优化，随着剩余备份资源的不断减少，VN恢复率也会出现一定程度的降低，但较为缓慢，最终保持在0.826左右，优于其它3种对比算法。

图5 VN恢复率

(4)重映射平均计算时间

图6是3种算法重映射平均计算时间的对比，重映射平均计算时间即故障恢复时延是衡量被动恢复机制算法的有效性指标，重映射时间短，则故障恢复时延较小，可能造成的数据丢失情况较少。由图6所示TA-SVNE算法和RE-SVNE算法两种算法的重映射程序运行时间相比较Blind-SVNE算法较短，这是因为TA-SVNE算法和RE-SVNE算法两种算法都采用了节点备份策略减少了节点选择的时间，但是在重映射过程中TA-SVNE算法要在节点候选集中再找到合适的节点进行重映射，而RE-SVNE算法在重映射之前就为每一个节点计算好了最佳备份节点，更近一步缩短了重映射的时间。

图6 重映射平均计算时间

(5)主用比例α对算法的影响程度

图7是在节点故障平均持续时间d=25的情况下，主用比例α对TA-SVNE算法和RE-SVNE算法性能的影响，因为Blind-SVNE算法并没有将物理资源进行主备用分配，故它的长期业务利润不随α的增大而改变。其它两种算法在主用比例为0.7时长期业务利润均达到最大值，当大于0.7时长期业务利润又开始减少。因此在多节点故障场景下，应适当减小α， 来保障充足的资源进行故障恢复。

图7 主用比例对算法的影响

4 结束语

本文主要分析了网络虚拟化环境中VNE的生存性问题。对于发生多个物理节点故障时，使用节点恢复度因子的候选节点选择策略，提出RE-SVNE算法。仿真实验结果分析表明本文所提算法在故障恢复时延、InP的长期业务利润和VN恢复率方面均有较好的性能，也有效提高了虚拟网络的生存性。本文对节点故障的研究仅仅是在单域的VNE过程中进行的，对于多域的节点故障恢复可作为下一步的研究方向。