可靠性与拓扑感知的服务功能链备份保护方法

韩晓阳, 孟相如, 康巧燕, 翟 东, 刘鹏飞

(空军工程大学信息与导航学院, 陕西 西安 710077)

0 引 言

传统的功能与硬件紧耦合的网络服务提供方式存在管理复杂、升级换代成本昂贵、可扩展性差、新服务上线周期长等问题,不断发展的多样化业务需求更加剧了这些问题,互联网发展面临着瓶颈,进行技术变革势在必行[1-3]。网络功能虚拟化基于虚拟化技术和标准的商业服务器、交换机和存储器来实现网络功能,替代网络中的专用中间盒,使虚拟网络功能(virtual network function, VNF)与专用硬件设备完全解耦,能够支持新兴业务的快速上线,极大地提高业务部署的灵活性并降低运维成本[4-6]。

网络功能虚拟化以服务功能链(service function chain, SFC)的形式部署,由多个部署在网络基础设施上的VNF按一定的逻辑顺序组合成的虚拟路径来实现网络功能,为用户提供相应的网络服务[4]。SFC为网络业务提供了高度灵活、资源节约和集中编排的特性,成为当前研究热点。很多学者就SFC部署问题付出了不懈努力,取得了较为丰富的研究成果[7-9]。

当前的SFC部署研究多假设基础设施是完全可靠的,然而现实情况中问题却复杂得多。相比于高可靠的电信级专用硬件设备,“软件化”VNF的脆弱性给网络带来了一定的可靠性风险,导致VNF发生失效的因素复杂多样。任何一个服务器节点故障或是VNF失效都将导致相关SFC的故障,造成服务中断、数据丢失、资源浪费等问题。文献[10]重点研究了网络功能虚拟化相关的可靠性问题,并指出硬件或软件故障均可能导致VNF的失效,而任意VNF的失效都将影响整个SFC的工作,造成服务中断。文献[11]研究了SFC的可靠性部署问题,在未预留备份资源的情况下尽可能提高SFC的可靠性,但并未解决基础设施故障时的服务中断问题。

采用预留备份资源的方式能够提高网络业务的可靠性,但也存在物理网络资源利用率不高的问题。文献[12]采用专用备份的方式备份部署VNF实例,并实现了SFC及备份VNF的一阶段协同部署,但专用备份方式将会带来较高的资源开销,并且影响整体的部署成功率。文献[13]在满足SFC可靠性需求的基础上,以提高部署成功率和降低部署花费为目标,将SFC部署转化为马尔可夫决策过程并求解,完成SFC可靠部署。文献[14]对SFC中的所有VNF进行备份,并考虑了备份资源的共享问题,在保证服务可靠性的同时一定程度上降低了备份资源量。文献[15]设置了一个参数来衡量服务器节点可靠性和量化SFC中VNF的可靠性需求,并设计了一种鲁棒的SFC可靠部署方法以降低备份资源量并提高物理网络资源利用率。文献[16]提出了一种系统可用性评价方法,并设计了一种预留备份资源以保证服务安全性的SFC部署方法。文献[17]针对SFC部署时的可靠性问题,提出对备份VNF选择、备份实例放置和SFC部署的联合优化方法,在优先满足网络服务可靠性需求的同时,提高了SFC部署成功率。文献[18]提出一种新的备份保护方法,通过对VNF重要度进行评估,为重要的VNF预留备份资源,提高了SFC可靠性,并尽可能降低资源消耗。文献[19]为降低备份资源消耗,对SFC中可靠性较低的VNF进行备份保护来保证SFC可靠性,提高了服务器节点资源利用率,但未能充分考虑VNF备份资源共享,因此资源利用率还有提高的空间。文献[20]以最小化备份资源消耗为目标,提出一种资源感知的SFC备份保护方法,在保证SFC可靠性的同时降低了备份资源消耗,提高了资源利用率。

为了在保证SFC可靠性的同时进一步提高资源利用率,本文提出一种可靠性与拓扑感知的SFC备份保护方法,在保证SFC可靠性需求的前提下尽可能降低备份资源消耗。首先,在SFC初步部署阶段,以可靠性为约束条件,利用最小费用最大流算法形成SFC请求的初步部署方案,在未预留备份资源的情况下尽可能提高SFC部署的可靠性。其次,在备份保护阶段,利用软件定义网络(software defined network, SDN)控制器实时感知服务器节点可靠性和物理网络拓扑,为未能达到可靠性需求的SFC通过预留备份资源的方式来提高其可靠性,并考虑备份资源可被不同的SFC共享。实验结果表明,该方法能够在保证可靠性的基础上,使物理网络资源利用更加合理。

1 网络模型及方法描述

1.1 网络模型

(1) SFC请求

一个SFC请求可以用一个赋权无向图Gv=(S,T,V,Ev,dv,Dd)表示，其中V={v1,v2,…,vP}。业务流从一个交换机节点流入,经过给定顺序的VNF后,从另一个交换机节点流出,本文常用符号及其含义如表1所示。

表1 常用符号及其含义

(2) 物理网络

(3) SFC部署

当SFC请求到达时,服务提供者按照既定顺序实例化SFC的各个VNF。SFC部署需要消耗物理网络的带宽资源、计算资源和转发资源。为防止由于流分裂带来的性能下降,本文规定一条业务流不能被分裂成两条以上流。

1.2 评价指标

(1) 可靠部署成功率

可靠部署成功率是指在满足可靠性需求的前提下的SFC部署成功率,是描述SFC可靠部署的重要指标之一,可以表示为

(1)

式中:SFCsuc(t)表示t时刻成功部署的SFC请求数量;SFC(t)表示t时刻到达的SFC请求数量;Td表示总的运行时间;δ是接近于0的常数。

(2) 长期平均收益开销比

对于SFC请求Gv,定义收益R(Gv,t)和开销C(Gv,t)分别为

(2)

(3)

通常利用长期平均收益开销比来表征稳定状态下SFC部署算法的性能,可以表示为

(4)

(3) 平均链路扩张系数

本文将平均链路扩张系数定义为SFC部署在物理网络链路的跳数之和相较于部署成功的SFC虚拟链路跳数之和的比值。平均链路扩张系数反映了物理链路资源利用情况,可以表示为

(5)

(4) 备份与主用资源比例

备份与主用资源比例是描述备份保护方法的重要指标之一,是指用于备份保护的资源总量与主用资源总量的比值,可表示为

(6)

式中:Reb(t)表示t时刻备份资源总量,是链路备份资源消耗、服务器节点备份资源消耗及备份拓扑转发资源消耗三者之和;Rez(t)表示t时刻主用资源总量,是主用链路资源消耗、主用服务器节点资源消耗、以及主用转发资源消耗三者之和。

1.3 SFC备份保护方法描述

本文首先将SFC部署问题转化为最优路径选择问题,并利用最小费用最大流算法寻找可靠性最高的部署路径,尽可能提高SFC的可靠性。其次,为未达到可靠性需求的SFC通过预留备份资源的方式进行可靠性增强,并考虑不同VNF和不同SFC之间备份资源共享以提高资源利用率。

(1) 未备份保护时SFC部署的可靠性计算

VNF的可靠性依赖于其部署的服务器节点的可靠性,未预留备份资源进行备份保护时SFC的可靠性AR可表示为

(7)

式中:ri为一条SFC中各VNF部署的服务器节点的可靠性。如果部署过程中各VNF未进行聚合,则该条SFC请求部署的服务器节点数n与该SFC请求中的VNF个数相等。如果部署过程中存在VNF聚合的情况,则n为该条SFC请求部署的实际服务器节点数。由式(7)可以看出,VNF聚合由于减少了部署的服务器节点数量,可以提高SFC部署时的可靠性,因此在部署阶段应优先考虑VNF聚合。为减少预留的备份资源量,在SFC主链部署时应尽可能提高其可靠性,因此应选择在满足时延约束的条件下,将VNF部署在可靠性更高的节点上。

(2) 进行备份保护的SFC可靠性计算

在对SFC进行备份保护时,应对SFC中已初步部署的VNF进行可靠性排序,并对可靠性最低的VNF进行备份保护。

当仅为SFC中VNFvq预留备份资源进行备份保护时,预留备份资源的服务器节点可靠性为rb,备份资源仅对vq进行备份保护,则AR可表示为

(8)

式中:M为SFC中VNF(除vq外)部署的服务器节点集合。

考虑备份资源对SFC中邻近的VNF进行共享保护可以进一步提高SFC部署的可靠性。当为vq和vq+1预留备份资源进行备份保护时,预留备份资源的服务器节点可靠性为rb,预留备份资源可以共享,则AR可表示为

(9)

式中:N为SFC中VNF(除vq和vq+1外)部署的服务器节点集合。

(3) VNF备份部署节点位置选择

以选定被保护VNF的上一个VNF部署位置(或是流入交换机节点位置)和下一个VNF部署位置(或是流出交换机节点位置)为位置约束,寻找邻近满足时延和可靠性约束的服务器节点作为备份VNF部署位置。如果此时能够达到可靠性需求,则形成部署方案,如图1(a)所示,其中绿色节点为备份VNF部署服务器节点。否则考虑利用该备份资源对待被保护VNF与邻近VNF进行共享备份保护以提高SFC可靠性,如图1(b)所示,并计算其可靠性和时延,判断是否符合要求。如果满足条件,输出部署方案,否则判断为备份保护失败。

图1 SFC备份保护示例Fig.1 Example of SFC backup protection

如果选择的备份节点和链路上已预留备份资源,则可考虑备份资源被不同的SFC共享,以提高物理网络资源利用率。

2 整数线性规划模型

为更好地描述SFC的可靠部署问题,本文建立SFC可靠部署的整数线性规划模型,目标函数和相关约束条件如下。

2.1 目标函数

备份资源与主用资源比例能够较好地反映出本文提出方法的性能,因此本文以最小化备份资源与主用资源比例作为目标函数minpb：

(10)

2.2 约束条件

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

rrp≤ARp

(23)

3 可靠性与拓扑感知的SFC备份保护方法

可靠性与拓扑感知的SFC部署方法包括:基于最小费用最大流的SFC部署方法以及拓扑感知的VNF备份保护方法,其流程如图2所示。首先,利用最小费用最大流算法综合考虑时延和可靠性进行SFC部署,尽可能提高其可靠性,并生成SFC初步部署方案。其次,判断该方案能否达到SFC可靠性需求。如果已经达到可靠性需求,则为可行部署方案。否则利用拓扑感知的VNF备份保护方法,通过为该方案中可靠性较低的VNF预留备份资源的方式提高SFC可靠性。

图2 SFC备份保护方法流程Fig.2 Process of SFC backup protection method

3.1 基于最小费用最大流的SFC部署方法

为提高SFC部署性能,本文所提算法首先把SFC部署问题转化为最优路径选择问题,然后利用最小费用最大流算法进行求解,其流程如图3所示。

图3 SFC部署方法流程Fig.3 Process of SFC deployment method

首先,根据业务流流入流出节点位置、各VNF节点资源需求以及业务流带宽需求确定候选节点集合和候选路径集合,并利用候选路径集合构造有向网络。其次,利用拆点法将有向网络转化为容量-流量-费用网络,以物理链路时延为约束,以服务器节点可靠性作为费用,将SFC部署问题转化为最优路径选择问题。最后,利用最小费用最大流算法在物理网络上寻找从源节点和汇节点之间的最小费用最大流路径,该路径即为可靠性最高的部署路径。

3.1.1 拆点法构造容量-流量-费用网络

(1)确定候选节点集合

为防止SFC部署链路过长的问题,对于第i个VNFvi,其候选部署节点应满足如下位置约束:

(24)

(25)

确定候选节点集合具体算法如下。

(2)确定候选路径集合

根据第2节算法结果,可得到各候选节点集合,如图4所示。

图4 各候选节点集合示例Fig.4 Example of candidate node sets

此时SFC部署问题就转化为寻找从源节点出发经过候选节点到达汇节点的最优路径问题,该路径必须经过所有候选节点集合,且每个候选集合中的节点只能使用一次,各候选节点集合中的重合节点可以作为VNF的聚合部署节点使用,以降低链路时延。假定物理网络节点可承载的VNF类型数为m,则相邻m个VNF可部署在同一个服务器节点,除此之外则不可进行VNF聚合以防止流量的乒乓效应。例如m=2,则vi可与相邻的vi-1部署在同一个服务器节点上,vi不可与除vi-1和vi+1以外的其他VNF聚合,否则易产生流量的乒乓效应。利用深度优先搜索算法以链路带宽为约束在物理网络上找出所有符合条件的有向路径,以这些有向路径构成适用于网络流的有向网络。

(3) 拆点法构造网络

因业务流量的有向性,为便于利用网络流理论寻找最优部署路径,需利用拆点法将有向网络转化为适用于网络流方法的容量-流量-费用网络Gc。将网络中节点进行编号,将节点Ai拆点为节点对Ai与Ai′,从Ai到Ai′连接一条边,边的容量为1(表示只能经过一次),流量为1(表示经过次数),一个节点对之间的流量费用为0(相当于自己到自己的费用)。如果节点Ai到Aj直接连接,则从Ai′到节点Aj连接一条边,边的容量为1,以节点Ai可靠性的倒数1/Ri作为Ai到Aj流量费用Rij,即cost=Rij=1/Ri,如图5所示。

图5 容量-流量-费用网络构造Fig.5 Construction of capacity-flow-cost network

3.1.2 最小费用最大流算法

最小费用最大流问题就是在容量-流量-费用网络中求一个费用最小的最大流。利用最小费用最大流算法求解该问题,能够保证在流量最大的路径上费用最小,即可靠性最高,保证了SFC部署性能。为清楚地表述该问题,引入剩余网络RN(f),其与网络Gc节点相同,剩余网络反映了节点间链路的剩余容量。最小费用最大流算法具体步骤如下。

算法2 最小费用最大流算法输入 Gc,Gs,SFC请求输出 SFC初步部署方案1. 令流量为0的最小费用流fk=02. for i=1: k3. 构造剩余网络RN(fk)4. 以Rij作为费用,利用深度优先搜索算法在RN(fk)中寻找从源点到汇点的最小费用路5. if 最小费用路P不存在6. fk为最小费用最大流,计算结束7. else8. 更新fk为fk+P,更新剩余网络RN(fk)9. end if10. end for11. return 最小费用最大流路径即为候选最优部署路径12. if 候选最优部署路径为空集或不满足SFC计算资源需求13. 部署失败14. else 初步部署成功15. return SFC初步部署方案16. end if

3.2 拓扑感知的VNF备份保护方法

如果SFC初步部署方案能够满足SFC可靠性需求,则为最终部署方案。否则,对该初步部署方案利用拓扑感知的VNF备份保护方法,对SFC中可靠性最低的VNF预留备份资源进行备份保护。如果可靠性仍不能满足需求,则考虑该SFC中的邻近VNF共享备份资源,通过这种共享保护的方式提高其可靠性。不同SFC之间的备份资源也可以共享,尽可能提高物理网络资源利用率。选定VNFvr作为待备份VNF,首先利用k-最短路径方法,选出从vr-1部署节点S′(或流入交换机节点)到vr+1部署节点T′ (或流出交换机节点)之间除本条路径以外的k条最短路径作为候选备份路径集合BL,并选择BL中满足时延约束且可靠性最高的路径作为最优备份路径,拓扑感知的VNF备份保护方法具体步骤如下。

输入 SFC初步部署方案输出 VNF备份节点位置及备份路径1. if SFC初步部署方案满足SFC可靠性需求2. 可靠部署成功3. return SFC初步部署方案即为最终部署方案4. else 5. 选择SFC可靠部署初步方案中最脆弱VNF部署位置Locr6. 利用k-最短路径方法选出从S'到T'之间除本条以外的k条最短路径作为候选备份路径集合BL,并计算其时延和可靠性7. for j=1: k8. if 方案j满足资源和时延约束条件9. 方案j为备份候选方案10. return 最优备份路径集合BLO11. end if12. end for13. 选择最优备份路径集合BLO中可靠性最高的路径,计算其可靠性ARp1,并考虑邻近VNF共享保护,计算其可靠性ARp14. if rrp≤ARp115. 备份保护成功16. return 最终部署方案17. else if rrp≤ARp 18. 备份保护成功19. return 最终部署方案20. else 备份保护失败21. end if22. end if23. end if

根据最终部署方案,占用物理网络计算、转发和带宽资源,完成SFC可靠部署。

4 实验仿真

本文利用Matlab进行实验仿真,选取在较大规模的网络场景中对本文提出方法进行性能验证,并与其他两种方法进行对比分析。

4.1 实验环境设置

实验所用的物理网络拓扑和SFC拓扑由改进的Salam网络拓扑随机生成算法生成。本文假定物理网络的交换机节点和服务器节点处于同一位置,数量均为100,节点间的连接度为0.5。服务器节点和交换机节点的资源都服从参数为(50,60)的平均分布,交换机间的链路带宽资源服从参数为(20,25)的平均分布。物理网络的链路传输时延服从参数为(1, 2)的平均分布。本文假定每一个服务器节点可承载VNF类型为{v1,v2,v3,v4}中的两种,即m=2。服务器节点的可靠性在{0.7, 0.8, 0.9}中随机选择。

随机选择SFC请求的流入流出节点且不能重复,每个SFC请求中的VNF数量满足参数为[2, 4]的平均分布,且分属于不同类型。各VNF计算资源需求满足参数为[7, 10]的平均分布,各虚拟链路带宽资源需求满足参数为[5, 8]的平均分布。每条SFC请求允许的最大传输时延满足参数为[6, 8]的平均分布。SFC请求到达率满足参数为0.1的泊松分布,每个SFC的平均生存时间满足参数为1 000的指数分布,其可靠性需求在{0.8, 0.9, 0.95}中随机选择。

实验持续10 000个时间单位,为减少随机因素的影响,实验进行了10次,取10次实验结果的平均值作为最终的实验结果。

4.2 实验分析

本文设置两组实验来验证可靠性与拓扑感知的SFC备份保护方法(简称为RB-NFV)性能。第一组实验中,RB-NFV方法在相同的实验条件下与其他两种SFC可靠性部署方法进行对比,即可靠性保证的SFC备份保护方法(简称为RG-NFV)[11]和完全备份的SFC可靠性部署方法(简称为RU-NFV)[14]，具体如表2所示。第二组实验分析了物理网络资源使用情况,验证RB-NFV方法在资源合理利用方面的性能。

表2 方法对比

4.2.1 实验1:方法性能对比

(1) 可靠部署成功率

如图6所示,RU-NFV方法对原始SFC请求和备份拓扑联合优化,且考虑备份资源共享,取得了较好性能,但由于对所有VNF预留资源进行备份,因此物理网络资源消耗较快,稳定状态下可靠部署成功率稳定在0.48左右。RG -NFV方法对备份实例放置和SFC部署进行联合优化,性能较RU-NFV方法有较大提升,稳定状态下可靠部署成功率保持在0.65左右。本文提出的RB -NFV方法由于在SFC部署阶段利用最小费用最大流进行求解,离最优解更近。在备份阶段仅对脆弱的VNF进行备份保护,且考虑邻近的VNF共享备份资源,因此预留备份资源较少,可靠部署成功率在对比3种算法中最高,稳定状态下保持在0.7左右。

图6 可靠部署成功率变化情况Fig.6 Change of reliable deploying success ratio

(2) 长期平均收益开销比

如图7所示,RU-NFV方法由于对SFC中所有VNF进行备份,物理网络资源消耗较多,因此长期平均收益开销比下降较快,稳定状态下保持在0.53左右。RG-NFV方法对备份实例放置和SFC部署进行联合优化,性能较RU-NFV方法有较大提升,稳定状态下收益开销比保持在0.62左右。本文提出的RB-NFV方法由于在SFC初步部署阶段利用最小费用最大流进行求解,使初步部署结果离最优解更近,在备份保护阶段仅对脆弱的VNF进行备份保护,且考虑邻近的VNF共享备份资源,因此预留备份资源较少,长期平均收益开销比在对比3种算法中最高,稳定状态下保持在0.65左右。

图7 长期平均收益开销比变化情况Fig.7 Change of long-term average revenue to cost ratio

(3) 备份与主用资源比例

如图8所示,RU-NFV方法对SFC中所有VNF进行备份,且考虑备份资源共享,稳定状态下备份资源与主用资源比例稳定在0.68左右。RG -NFV方法将备份实例放置和SFC部署进行联合优化,且能够充分考虑备份资源共享,因此备份资源消耗减少,性能较RU-NFV方法有一定提升,稳定状态下备份资源与主用资源比例保持在0.54左右。本文提出的RB -NFV方法仅对脆弱的VNF进行备份保护,且考虑邻近的VNF共享备份资源,可较大幅度减少备份资源消耗,备份资源与主用资源比例在对比3种算法保持最低,稳定状态下保持在0.49左右。

图8 备份与主用资源比例变化情况Fig.8 Change of backup to primary resource ratio

(4) 平均链路扩张系数

如图9所示,RU-NFV方法对所有VNF进行备份,资源消耗速度较快,平均链路扩张系数较高,在到达率分别为0.1、0.15和0.2的情况下分别为1.44、1.53和1.78。RG-NFV方法充分考虑VNF备份资源共享,预留备份资源量减少,因此平均链路扩张系数有所降低,在到达率分别为0.1,0.15和0.2的情况下,平均链路扩张系数分别保持在1.34、1.39和1.43。本文提出的RB-NFV方法,由于最小费用最大流算法在求解最优路径选择问题方面具有较好性能,且备份资源能够共享,因此平均链路扩张系数在3种算法中最低,在到达率分别为0.1、0.15和0.2的情况下,平均链路扩张系数分别保持在1.31、1.34和1.38,性能在3种算法中最优。

图9 平均链路扩张系数变化情况Fig.9 Change of average link expansion coefficient

4.2.2 实验2:物理网络资源使用情况分析

本组实验主要从物理网络资源使用情况对本文所提算法进行性能分析,并与其他两种方法进行对比验证。

(1) 瓶颈服务器节点占比

如图10所示,RU-NFV和RG -NFV方法由于未能充分考虑服务器节点的均衡使用问题,因此随着物理网络资源的不断消耗,瓶颈服务器节点较多且增长较快。本文提出的RB -NFV方法在SFC部署阶段充分考虑服务器节点的均衡使用问题,因此瓶颈节点较少,稳定状态下低于3%,性能较为优异。

图10 瓶颈服务器节点占比变化情况Fig.10 Change of bottleneck server nodes proportion

(2) 闲置服务器节点占比

如图11所示,RU-NFV和RG -NFV方法在物理网络资源利用过程中未能充分考虑服务器节点的均衡使用问题,因此服务器节点资源使用不够均衡,出现了较多的闲置服务器节点,稳定状态下分别为0.18和0.10。本文提出的RB -NFV方法由于在SFC部署阶段和备份节点选择阶段考虑了服务器节点资源的均衡使用问题,因此资源使用较为均衡,闲置服务器节点比例低于0.05,相较于其他两种方法性能更好。

图11 闲置服务器节点占比变化情况Fig.11 Change of idle server nodes proportion

从以上两组实验可以看出,本文提出的RB -NFV方法相较于其他两种可靠性备份保护方法预留备份资源量更少,部署成功率更高,资源利用更加合理,整体性能较为优越。

5 结 论

本文针对SFC可靠部署中存在资源利率较低的问题,提出了一种可靠性与拓扑感知的SFC备份保护方法。首先,将SFC部署问题转化为最优路径选择问题,并利用最小费用最大流算法求解。其次,利用SDN控制器实时感知物理网络拓扑和服务器节点可靠性,对未达到可靠性需求的SFC通过预留冗余资源进行备份保护,并通过SFC间资源共享,尽可能降低备份资源消耗。实验表明,该方法在保证SFC可靠性的同时,提高了物理网络资源利用率。