面向多链路故障的生存性虚拟网络映射算法

朱国晖,刘秀霞,张 茵

(西安邮电大学 通信与信息工程学院,西安 710121)

0 概述

随着互联网的快速发展,网络僵化成为限制互联网架构创新与发展的关键因素,而网络虚拟化的出现为解决网络僵化问题提供了有效途径[1-2]。网络虚拟化解耦了网络服务提供与基础设施提供2个功能,并允许多个异构虚拟网络(Virtual Network,VN)在同一个物理网络上共享资源[3],其核心问题是虚拟网络映射(Virtual Network Embedding,VNE)[4],而VNE被证明是NP-Hard[5-6]问题。多数VNE算法都是假设在不出现物理故障的情况下[7]提出的,它们通过优化网络模型来提高资源利用率并增加收益。然而,如果在VNE过程中出现设备故障、大规模灾害或恶意攻击等情况,将会导致VN请求服务失败,降低服务性能和可用性,若服务中断,则基础设施提供商(Infrastructure Provider,InP)必须支付服务等级协议(Service Level Agreement,SLA)中指定的罚款。因此,需要对生存性虚拟网络映射(Survivable Virtual Network Embedding,SVNE)算法进行研究,从而保证网络的正常运行。

学者们针对现有SVNE算法进行了研究,如文献[8]提出数据中心链路发生故障的概率是节点发生故障概率的10倍。对于物理链路故障,文献[9]提出一种主动链路备份生存性算法,该算法提前为虚拟链路分配好备份链路,当物理链路发生故障时将其切换至备份链路,该方法虽然提高了故障恢复率,但是过多的冗余备份会造成资源浪费。文献[10-12]提出一种被动恢复的生存性算法,该算法不预留备份资源,当链路发生故障时,利用剩余物理资源将受影响的虚拟链路进行链路重映射,该方法虽然避免了冗余备份资源的浪费,但是增加了故障恢复时延,且不能保证具有良好的故障恢复率。文献[13-15]研究了当发生单个故障时,采用链路重映射和路径分割的链路重映射方法进行故障恢复。文献[16]是在位置约束的条件下,对发生的链路故障进行重映射处理。因此,上述提出的SVNE算法均是在仅发生单一链路故障的情况下提出的。对于多链路故障,文献[17]从QoS角度提出了主动保护和被动恢复2种算法,但是这2种算法都没有考虑映射开销和物理资源碎片化问题。

针对以上问题,本文重点研究物理链路故障问题,并从多链路故障场景出发,提出一种面向多链路故障的生存性虚拟网络映射算法。利用多路径选择算法创建物理链路备份路由集,并根据目标函数求解整数线性规划,从故障链路备份路由集中选择带宽资源平衡度大的路径,为受链路故障影响的虚拟链路逐个进行重映射,从而减少物理资源碎片化概率,提高物理资源利用率。

1 网络模型建立

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

物理网络模型抽象为加权无向图,记为Gs=(Ns,Ls),其中,Ns为物理节点集合,Ls为物理链路集合,对物理节点ns∈Ns的节点需求用c(ns)表示,对物理链路ls∈Ls的带宽需求用b(ls)表示。在物理网络中,将物理资源分为主、备用资源,其中,主链路带宽资源为bp(ls)=αb(ls),备用链路带宽资源为bb(ns)=(1-α)b(ls),α为调节系数,用来调节主、备用带宽资源比例[18]。

虚拟网络模型抽象为加权无向图,记为Gv=(Nv,Lv),其中,Nv为虚拟节点集合,Lv为虚拟链路集合,对虚拟节点nv∈Nv的节点需求用c(nv)表示,对虚拟链路lv∈Lv的带宽需求用b(lv)表示。

虚拟网络映射可分为2个阶段[19]:

虚拟网络映射示意图如图1所示。

图1 虚拟网络映射示意图Fig.1 Schematic diagram of virtual network embedding

1.2 评价指标

本文采用VN请求接受率、长期平均收益开销比与平均故障恢复率对实验结果进行评价。

1)VN请求接受率的计算方法如式(1)所示:

(1)

其中,Nm(t)是t从0～T时刻映射成功的集合,N(t)是所有到达VN请求的集合,δ是趋于0的正数,用来保证分母不为0。

2)对于虚拟请求Gv=(Nv,Lv),定义在t时刻Gv的映射收益R(Gv,t)为:

(2)

其中,β是节点和链路的收益均衡因子,在本文中设置为1。

定义在t时刻Gv的映射开销C(Gv,t)为:

(3)

其中,γ是节点和链路的开销均衡因子,在本文中设置为1,hop(lv)表示虚拟链路lv映射到物理路径中的跳数。

定义长期平均收益开销比为:

(4)

在VNE过程中,如果一条物理链路发生故障,并且故障恢复失败,则InP需要承担SLA中指定的罚款S(Gv)[20]:

S(Gv)=ωR(Gv,t)

(5)

其中,ω是惩罚因子,在本文中设置为2。

因此,将本文中的长期平均收益开销比重新定义为:

(6)

3)平均故障恢复率的计算方法见式(7):

(7)

其中,F(lv)表示受物理链路故障影响而失效的虚拟链路总数,Re(lv)表示受物理链路故障影响而失效,但采用故障恢复算法恢复成功的虚拟链路数量。

2 多链路故障的生存性虚拟网络映射算法

2.1 备份路由集合构建

在虚拟请求到达之前,采用路径选择算法为每个物理链路构建备份路由集,缩短链路重映射时延。本文在最短路径算法[20]的基础上,提出一种多路径选择算法。它是在物理网络中构建多条可用路径集合的算法,相比于最短路径算法,该算法考虑了在规定路径跳数和链路映射过程中多种资源约束的问题,通过搜索每条物理链路,找到满足约束条件的多条路径并构成备份路由集合。

图2 备份链路图Fig.2 Backup link diagram

对物理链路定义2个变量:

(8)

ls∈x,x∈Cov(Gs,l,h)

(9)

其中,lv→l表示虚拟链路lv映射到物理链路l上,bp(lv)和bb(lv)分别表示在物理链路l上承载虚拟链路所需主用带宽和用于链路重映射的备用带宽,U(l)是两者之和,Q(x)表示在路径集合中每条路径可用于链路重映射的最小瓶颈带宽。

多路径选择算法的实现伪代码为:

输入Gs,h,h′=2,3,…,h

输出可用备份路径集合pathlist(l)

1.初始化,最大跳数h=max_hops,跳数h′=2

2.for 每条物理链路l∈Lsdo

3.使用最短路径算法计算J(Gs,l,h′),将其结果存入集合Cov(Gs,l,h)中

4.跳数增加一跳,h′++

5.if 当前跳数大于规定跳数,即h′>h then

6.return 得到h跳之内的所有链路集合Cov(Gs,l,h)

7.else 转到步骤2

8.end if

9.end for

10.for Cov(Gs,l,h) do

11.根据式(8)计算U(l)

12.根据式(9)计算Cov(Gs,l,h)中每条路径的最小瓶颈带宽Q(x)

13.if U(l)≤Q(x) then

14.将该路径存入可用路径集合pathlist(l)中

15.else pathlist(l)集合为空

16.end if

17.end for

18.return pathlist(l)

2.2 虚拟网络映射模型构建

本文将虚拟网络映射分为2个阶段进行,重点关注链路映射,将多链路故障建模为多条单一链路故障并进行逐一优化。在节点映射时,采用文献[12]中的贪婪映射算法为虚拟节点选择资源最大的物理节点,包括节点资源、链路带宽和节点映射中相邻链路的数量。虚拟链路映射采用整数线性规划模型,具体过程如下:

1)目标函数为最大化长期平均收益开销比,表示为:

max(R′/C)

(10)

2)变量定义为:

(11)

3)约束条件为:

(12)

(13)

当物理链路发生故障时,采用链路重映射算法,将受影响的虚拟链路重映射到故障链路的备份物理路径上。由于一条物理链路发生故障会造成多条虚拟链路失效,若虚拟链路恢复失败,VN请求服务中断,InP会承担SLA中规定的罚款。因此,优先重映射产生罚款较多的虚拟链路,减少InP的罚款,增加收益。

1)目标函数为:

(14)

2)约束条件为:

(15)

3)定义带宽资源平衡度为[11]:

(16)

面向多链路故障恢复的虚拟网络映射算法伪代码为:

输入输入GS,G

输出Embedding(Gv)

1.for 每个虚拟请求 do

2.for 虚拟请求的虚拟节点 do

3.采用文献[12]中的贪婪算法进行节点映射

4.end for

5.if 在进行虚拟链路映射时,物理链路未发生故障 then

6.根据本文虚拟链路映射算法,求解线性规划

7.end if

8.if 物理链路l发生故障 then

9.统计受链路l影响的虚拟链路的集合,并将虚拟链路带宽值进行降序排列,结果存入集合VL中

10.for 故障物理链路l do

11.根据多路径选择算法计算链路l的备份路由集pathlist(l)

12.for pathlist(l)集合中所有路径 do

13.根据式(16)计算带宽资源平衡度

14.根据式(14)求解线性规划,将VL集合中虚拟链路在带宽资源平衡度最大的路径上,依次进行链路重映射

15.end for

16.end for

17.end if

18.end for

19.return

3 实验仿真

3.1 实验环境配置

本文通过MATLAB进行仿真实验评估。使用GT-ITM[21]拓扑生成工具创建实验所需的虚拟网络和物理网络拓扑,具体参数如表1所示。物理链路故障的到达服从参数为0.05的泊松分布,候选集合跳数h为4。每次实验运行50 000个时间单元,约有5 000个VN请求到达,每2 000个时间单元进行一次数据统计,取10次实验的平均值为最终结果。

表1 实验参数配置Table 1 Experimental parameters configuration

3.2 对比方案与性能选取

将本文提出的M-SVNE算法与文献[17]中的P-SVNE算法、文献[22]中的N-SVNE算法进行对比,从VN请求接受率、长期平均收益开销比、平均故障恢复率和平均故障恢复时延4个方面验证本文算法的性能,上述3种算法的具体描述如表2所示。

表2 3种SVNE算法描述Table 2 Description of three SVNE algorithms

3.3 仿真结果与分析

3.3.1 VN请求接受率

3种算法的VN请求接受率随时间的变化情况如图3所示。从图3可以看出,3种算法的VN请求接受率均随着时间的推移呈现逐渐降低的趋势,当VN的到达与离开达到平衡时,VN请求接受率趋于稳定。N-SVNE算法的VN请求接受率最高,这是因为它使用被动恢复策略,无任何资源备份,具有充足的物理资源用于虚拟网络映射。而M-SVNE算法和P-SVNE算法虽然也使用了被动恢复策略,但是这2种算法都为物理链路预留了备份资源,VN请求接受率相对N-SVNE算法较低。其中,M-SVNE算法能够动态感知物理网络剩余资源,并根据链路发生故障的数量动态调整链路的主、备份资源比例,使得更多的物理资源用于VNE,与P-SVNE算法相比,M-SVNE算法的VN请求接受率较高。

图3 VN请求接受率变化曲线Fig.3 Curves of VN request acceptance rate change

3.3.2 长期平均收益开销比

3种算法在长期平均收益开销比方面的性能比较如图4所示。从图4可以看出,M-SVNE算法的长期平均收益比最终稳定在0.59左右,高于其他2种算法。这是因为当物理链路发生故障时,M-SVNE算法优先使用带宽资源平衡度大的备份路径,重映射罚款高的虚拟链路,在减少资源碎片化,优化剩余备份资源的同时,减少了因故障恢复失败而导致的罚款,提高了长期平均收益开销比。

图4 长期平均收益开销比变化曲线Fig.4 Curves of long-term average revenue-to-expense ratio change

3.3.3 平均故障恢复率

图5是3种算法的平均故障恢复率的性能比较。从图5可以看出,N-SVNE算法的平均故障恢复率最低,因为它无任何备份资源,当发生链路故障时,使用剩余物理资源进行链路重映射,而当VN请求数量逐渐增多,导致没有足够的物理资源用于链路重映射,平均故障恢复率会较低。而其他2种算法为物理链路预留了备份资源,有更多的资源用于链路重映射,其中,M-SVNE算法使用多路径选择算法创建备份路由集合,集合中的备份路径均满足资源约束条件,并且优先使用带宽资源平衡度大的备份路径,在减少资源碎片化,优化剩余备份资源的同时,提高了平均故障恢复率。

图5 平均故障恢复率变化曲线Fig.5 Curves of average failure recovery rate change

3.3.4 平均故障恢复时延

图6是3种算法的平均故障恢复时延性能比较。从图6可以看出,N-SVNE算法的平均故障恢复时延最长,这是因为N-SVNE算法无任何备份,当链路发生故障时,根据剩余物理资源进行路由选择,实现链路重映射,花费时间较长。而M-SVNE算法和P-SVNE算法都为物理链路创建了备份路由集合,为链路重映射节省了时间。其中,M-SVNE算法使用带宽资源平衡度大的备份路径用于虚拟链路重映射,进一步缩短了路径选择的时间。因此,M-SVNE算法的平均故障恢复时延最短。

图6 平均故障恢复时延变化曲线Fig.6 Curves of average failure recovery delay change

4 结束语

本文对在多链路故障场景下的生存性虚拟网络映射问题进行研究,提出一种面向多链路故障的生存性虚拟网络映射算法。通过使用多路径选择算法为物理链路创建备份路由集,并优先选择带宽资源平衡度大的路径用于链路重映射,降低了物理资源碎片化的可能性,且提升了物理资源利用率。仿真结果表明,该算法提高了长期平均收益开销比和平均故障恢复率,缩短了故障恢复时延。此外,本文仅涉及的是单域VNE,而当涉及多域VNE时将会产生域内和域间的链路故障问题。因此,探索多域链路故障的SVNE算法将是下一步的研究方向。