可靠性感知的服务功能链备份保护方法
技术领域
本发明涉及一种可靠性感知的服务功能链(Service Function Chain,SFC)备份保护方法，包括基于最小费用最大流的SFC部署方法以及拓扑感知的SFC备份保护方法。
背景技术
文献“汤红波,邱航,游伟等.基于联合备份的服务功能链可靠性保障的部署方法”针对服务功能链部署时的可靠性问题，提出对备份虚拟网络功能选择、备份实例放置和服务功能链部署的联合优化方法，即RG-NFV方法。该方法以提高底层网络资源利用率为目标，首先，定义一个单位开销可靠性提高值的虚拟网络功能衡量标准，改进备份虚拟网络功能选择方法。其次，采用联合备份的方式调整相邻备份实例之间的放置策略，以降低带宽资源开销。文献“Long Qu,Maurice Khabbaz,Chadi Assi.Reliability-aware servicechaining in carrier-grade softwarized networks”针对服务功能链部署时的可靠性问题，以提高底层网络资源利用率为目标，提出一种SFC请求和备份拓扑联合优化的部署方法，对SFC中的全部VNF进行备份保护，并考虑不同VNF之间备份资源共享，即RU-NFV方法。但RG-NFV方法与RU-NFV方法尚存在以下问题：
(1)RG-NFV方法在SFC部署过程中未能充分对VNF部署位置进行严格约束，易出现流量乒乓效应和SFC时延过大的问题。
(2)RG-NFV方法在对VNF进行备份保护时，对备份VNF可靠性未区分，而对可靠性低的VNF进行备份能够更快提高SFC的可靠性。
(3)RG-NFV方法未能充分考虑备份资源对邻接VNF共享保护和不同的SFC之间的备份资源共享，易出现备份资源消耗大、资源利用率不高等问题。
(4)RU-NFV方法对所有VNF进行备份保护，备份资源消耗较大，底层网络资源利用率不高。
发明内容
要解决的技术问题
为了在保证服务功能链可靠性的同时进一步提高资源利用率，本发明提出一种可靠性感知的SFC备份保护方法，在保证SFC可靠性需求的前提下尽可能降低资源消耗。首先，在SFC初步部署阶段，以可靠性为约束条件，利用基于最小费用最大流的SFC部署方法，充分考虑部署服务器节点的位置、资源约束和时延约束、可靠性需求，在未预留备份资源的情况下尽可能提高SFC部署的可靠性，形成初步部署方案。其次，在备份保护阶段，为未能达到可靠性需求的SFC通过预留备份资源的方式来提高其可靠性，并考虑备份资源可被不同的SFC共享，减少了备份资源消耗，提高了资源利用率。
技术方案
一种可靠性感知的服务功能链备份保护方法，其特征在于步骤如下：
步骤1：建立SFC部署的网络模型：
SFC请求：用一个赋权无向图Gv＝(S,T,V,Ev,dv,Dd)，V＝{v1,v2,...,vP}，业务流从一个交换机节点流入，经过给定顺序的虚拟网络功能后，从另一个交换机节点流出；其中常用符号及其含义如表1：
表1
物理网络：用一个赋权无向图Gs＝(Ns,Es,Ds)表示，其中Ns＝Nf∪Nc，
SFC部署：当SFC请求到达时，服务提供者按照既定顺序实例化服务功能链的各个虚拟网络功能；
步骤2：对SFC备份保护方法进行描述：
(1)未备份保护时SFC部署的可靠性
VNF的可靠性依赖于其部署的底层网络服务器节点的可靠性，未预留备份资源进行备份保护时SFC的可靠性AR可表示如下：
其中ri为一条SFC中各VNF部署的底层服务器节点的可靠性，如果部署过程中各VNF未进行聚合，则该条SFC请求部署的底层服务器节点数n与该SFC请求中的VNF个数相等；如果部署过程中存在VNF聚合的情况，则n为该条SFC请求部署的实际底层服务器节点数；
(2)进行备份保护的SFC可靠性
在对SFC进行备份保护时，应对SFC中已初步部署的VNF进行可靠性排序，并对可靠性最低的VNF进行备份保护；
当仅为SFC中第q个VNF预留备份资源进行备份保护，预留备份资源的服务器节点可靠性为rb，备份资源仅对第q个VNF进行备份保护，则AR可表示为：
其中，M为SFC部署的除第q个VNF部署服务器节点外底层服务器节点集合；
当为第q，q+1个VNF预留备份资源进行备份保护，预留备份资源的服务器节点可靠性为rb，预留备份资源可以共享，则AR可表示为：
其中，N为SFC部署的除第q和第q+1个VNF部署服务器节点外底层服务器节点集合；
(3)VNF备份部署节点位置选择
以选定被保护VNF的上一个VNF部署位置或是流入交换机节点位置和下一个VNF部署位置或是流出交换机节点位置为位置约束，寻找邻近满足时延和可靠性约束的服务器节点作为备份VNF部署位置；如果此时能够达到可靠性需求，则形成部署方案；否则考虑利用该备份资源对待被保护VNF与临近VNF进行共享备份保护以提高SFC可靠性，并计算其可靠性和时延，判断是否符合要求；如果满足条件，输出部署方案，否则判断为备份保护失败；
如果选择的备份节点和链路上已预留备份资源，则可考虑备份资源被不同的SFC共享，以提高底层网络资源利用率；
步骤3：建立SFC备份保护数学模型，包括目标函数和相关约束条件：
(1)选择以最小化备份资源与主用资源比例作为目标函数：
minpb
其中Reb(t)表示t时刻备份资源总量，是链路备份资源消耗、服务器节点备份资源消耗、以及备份拓扑转发资源消耗三者之和，Rez(t)表示t时刻主用资源总量，是主用链路资源消耗、主用服务器节点资源消耗、以及主用拓扑转发资源消耗三者之和，Td表示总的运行时间，δ是接近于0的常数；
(2)约束条件
约束(5)表示如果虚拟网络功能vi被部署到底层物理网络节点ncl上，xil＝1；否则，xil＝0；约束(6)表示如果虚拟链路evij被部署到底层物理网络链路eslm上，yijlm＝1；否则，yijlm＝0；
约束(7)表示每一个底层网络物理节点可承载的VNF类型为m个；约束(8)表示业务流的每一个VNF都只能部署至一台通用服务器上；约束(9)表示底层网络剩余可用CPU计算资源不能小于VNF部署的CPU资源需求；约束(10)表示底层网络链路剩余带宽资源应大于服务功能链部署的链路资源需求；约束(11)表示底层交换机节点的可用转发能力应大于即将部署于其上业务流的转发资源需求；
rrp≤ARp(17)
约束(13)表示虚拟链路应部署在底层网络的无环路径上，以防止出现网络流量的乒乓效应；约束(14)表示如果该节点上有预留的备份资源，则可以被其他SFC中的VNF备份需求共享；约束(15)表示如果该链路上有预留的备份资源，则可以被其他SFC中的备份链路需求共享；约束(16)表示部署在底层网络的服务功能链必须满足业务流的时延需求，
步骤4：采用RB-NFV方法求解步骤3建立的SFC备份保护数学模型，具体包括以下步骤：
(1)确定SFC部署的候选节点集合；
(2)利用拆点法在候选节点集合的基础上构造容量-流量-费用网络；
(3)利用最小费用最大流算法在容量-流量-费用网络中寻找SFC的最优部署路径；
步骤5：利用拓扑感知的SFC备份保护方法对未达到可靠性需求的SFC进行备份保护，具体包括以下步骤：
(1)利用控制器实时感知底层网络拓扑和资源情况；
(2)利用K-最短路径方法，为待备份虚拟网络功能vr选出从vr-1到vr+1之间除本条路径以外的K条最短路径，作为候选备份路径集合BL；
(3)利用资源、时延和可靠性约束选择最优备份路径，完成SFC备份保护。
所述的最小费用最大流算法具体步骤如下：
输入：Gs，SFC请求，Gc
输出：SFC初步部署方案
步骤1：令流量为零的最小费用流fk＝0，构造剩余网络RN(fk)；
步骤2：以Rij作为费用，利用深度优先搜索算法在RN(fk)中寻找从源点到汇点的最小费用路；
步骤3：如果最小费用路P不存在，fk为最小费用最大流，计算结束；否则，更新fk为fk+P，更新剩余网络RN(fk)，并返回步骤2；
步骤4：计算所得最小费用最大流路径即为候选最优部署路径；
步骤5：判断候选最优部署路径为是否为空集或是否不满足SFC计算资源需求，
如果是，部署失败，计算结束；否则，初步部署成功，并输出SFC初步部署方案。
所述的步骤4中的(1)具体如下：
输入：底层网络实时资源和拓扑，SFC请求长度L1和流入流出交换机间最短路径L2
输出：候选节点集合NLIST
步骤1：网络控制器实时感知底层网络拓扑和实时资源情况；
步骤2：利用约束条件为各个虚拟网络功能选择候选节点；
步骤3：将候选节点存入集合NLIST，NLIST＝{n(1)LIST；n(2)LIST；...；n(q)LIST}。
所述的步骤4中的(2)具体如下：
利用深度优先搜索算法以链路带宽为约束找出所有符合条件的底层网络有向路径，以这些底层网络有向路径构成适用于网络流的有向网络，步骤如下：
输入：底层网络实时资源和拓扑，流入流出节点位置，候选节点集合n(i)LIST
输出：候选路径集合l(i)LIST
步骤1：SDN控制器实时感知底层网络拓扑和实时资源情况；
步骤2：以流入节点为原点，以流出节点为汇点，以服务功能链时延和带宽需求为约束，利用深度优先搜索算法搜索所有从源节点到汇节点所有满足条件的路径；
步骤3：判断候选节点是否为重合节点，如果是，则该候选节点可作为VNF聚合节点使用；
步骤4：将遍历所有路径存入候选路径集合LLIST；
步骤5：将候选路径集合聚合一起在底层网络形成有向网络；
利用拆点法将有向网络转化为适用于网络流方法的容量-流量-费用网络Gc。
所述的步骤5的(3)具体如下：利用设定的约束条件判断所选择候选备份路径集合BL是否满足要求，并将满足条件的选备份路径存入最优备份路径集合BLO；选择最优备份路径集合BLO中可靠性最高的路径，计算其可靠性ARp1，并考虑邻近VNF共享保护，计算其可靠性ARp；判断所选择路径可靠性ARp1是否满足SFC可靠性需求；如果满足，则备份保护成功，该方案即为最终部署方案；否则判断考虑邻近VNF共享保护的靠性ARp是否满足SFC可靠性需求，如果满足，则备份保护成功，该方案即为最终部署方案，计算结束；否则，可靠部署失败。
有益效果
本发明提出的一种可靠性感知的服务功能链备份保护方法，首先将SFC部署问题转化为最优路径选择问题，并利用最小费用最大流算法求解，使计算结果离最优解更近，在未预留资源的情况下提高SFC部署的可靠性。其次利用拓扑感知的SFC备份保护方法对未能达到可靠性需求的SFC进行备份保护，并充分考虑备份资源共享，减小了备份资源消耗，提高了底层网络资源利用率。
附图说明
图1是本发明所给出的SFC部署示意图。
图2是本发明所给出的SFC备份保护方法描述示意图。
图3是本发明所给出的RB-NFV方法流程图。
图4是本发明所给出的基于最小费用最大流的SFC部署方法流程图。
图5是本发明方法给出的各VNF部署候选节点集合示意图。
图6是本发明方法构建的容量-流量-费用网络示意图。
图7是本发明方法给出的剩余网络示意图。
图8是本发明方法中可靠部署成功率对比结果图。
图9是本发明方法中长期收益开销比对比结果图。
图10是本发明方法中备份资源占比对比结果图。
图11是本发明方法中平均链路扩张系数对比结果图。
图12是本发明方法中瓶颈服务器节点占比对比结果图。
图13是本发明方法中闲置服务器节点占比对比结果图。
具体实施方式
现结合实施例、附图对本发明作进一步描述：
1、建立SFC部署的网络模型
SFC请求：一个SFC请求可以用一个赋权无向图Gv＝(S,T,V,Ev,dv,Dd)，V＝{v1,v2,...,vP}，如图1(a)所示。业务流从一个交换机节点流入，经过给定顺序的虚拟网络功能后，从另一个交换机节点流出，本发明常用符号及其含义如表1所示。
物理网络：本发明选择多个基础设施提供商提供硬件服务作为应用场景，这就决定了底层的通用服务器节点的可靠性和承载能力可能存在差异。物理网络可以用一个赋权无向图Gs＝(Ns,Es,Ds)表示，其中Ns＝Nf∪Nc，
表1常用符号及其含义
SFC部署：当SFC请求到达时，服务提供者按照既定顺序实例化服务功能链的各个虚拟网络功能。SFC部署需要消耗底层网络的带宽资源、计算资源和转发资源。如图1(c)所示。为防止由于流分裂带来的性能下降，本发明规定一条业务流不能被分裂成两条以上流。
2、可靠性感知的SFC备份保护方法描述
本发明首先将SFC部署问题转化为最优路径选择问题，并利用最小费用最大流算法寻找可靠性最高的部署路径，尽可能提高SFC的可靠性。其次为未达到可靠性需求的SFC通过预留备份资源的方式进行可靠性增强，并考虑不同VNF和不同SFC之间备份资源共享以提高资源利用率。
(1)未备份保护时SFC部署的可靠性
VNF的可靠性依赖于其部署的底层网络服务器节点的可靠性，未预留备份资源进行备份保护时SFC的可靠性AR可表示如下：
其中ri为一条SFC中各VNF部署的底层服务器节点的可靠性。如果部署过程中各VNF未进行聚合，则该条SFC请求部署的底层服务器节点数n与该SFC请求中的VNF个数相等。如果部署过程中存在VNF聚合的情况，则n为该条SFC请求部署的实际底层服务器节点数。由公式可以看出，VNF聚合由于减少了部署的底层节点数量，可以提高SFC部署时的可靠性，因此在部署阶段应优先考虑VNF聚合。为减少预留的备份资源量，在服务功能链主链部署时应尽可能提高其可靠性，因此应选择在满足时延约束的条件下，将VNF部署在可靠性更高的节点上。
(2)进行备份保护的SFC可靠性
在对SFC进行备份保护时，应对SFC中已初步部署的VNF进行可靠性排序，并对可靠性最低的VNF进行备份保护。
当仅为SFC中第q个VNF预留备份资源进行备份保护，预留备份资源的服务器节点可靠性为rb，备份资源仅对第q个VNF进行备份保护，则AR可表示为：
其中，M为SFC部署的除第q个VNF部署服务器节点外底层服务器节点集合。
考虑备份资源对SFC中邻近的VNF进行共享保护可以进一步提高SFC部署的可靠性。当为第q，q+1个VNF预留备份资源进行备份保护，预留备份资源的服务器节点可靠性为rb，预留备份资源可以共享，则AR可表示为：
其中，N为SFC部署的除第q和第q+1个VNF部署服务器节点外底层服务器节点集合。
(3)VNF备份部署节点位置选择
以选定被保护VNF的上一个VNF部署位置(或是流入交换机节点位置)和下一个VNF部署位置(或是流出交换机节点位置)为位置约束，寻找邻近满足时延和可靠性约束的服务器节点作为备份VNF部署位置。如果此时能够达到可靠性需求，则形成部署方案，如图2(a)所示。否则考虑利用该备份资源对待被保护VNF与临近VNF进行共享备份保护以提高SFC可靠性，如图2(b)所示，并计算其可靠性和时延，判断是否符合要求。如果满足条件，输出部署方案，否则判断为备份保护失败。
如果选择的备份节点和链路上已预留备份资源，则可考虑备份资源被不同的SFC共享，以提高底层网络资源利用率。
(4)评价指标
1)可靠部署成功率
可靠部署成功率是指在满足可靠性需求的前提下的SFC部署成功率，它是描述SFC可靠部署的重要指标之一，可以表示如下：
其中SFCsuc(t)表示t时刻成功部署的SFC请求数量，SFC(t)表示t时刻到达的SFC请求数量，Td表示总的运行时间，δ是接近于0的常数。
2)长期平均收益开销比
对服务功能链请求Gv，我们定义收益R(Gv,t)和开销C(Gv,t)分别为:
其中，参数α1,α2,α3分别为计算收益R(Gv,t)时节点计算、转发资源与链路资源的比重参数，α1+α2+α3＝1。参数β1,β2,β3分别为计算开销C(Gv,t)时节点计算、转发资源与链路资源的比重参数，β1+β2+β3＝1。cpu(vi)表示虚拟网络功能vi需要的CPU资源，rforward(vi)表示虚拟网络功能vi需要的转发资源，cforward(vi)表示虚拟网络功能vi实际消耗的转发资源，bw(evij)表示虚拟链路evij需要的带宽资源，D(evij)表示虚拟链路evij实际部署路径。hops(D(evij))表示D(evij)的跳数。
通常利用长期平均收益开销比来表征稳定状态下服务功能链部署算法的性能，表示为：
3)平均链路扩张系数
本发明将平均链路扩张系数定义为SFC部署在物理网络链路的跳数之和相较于部署成功的SFC虚拟链路跳数之和的比值。平均链路扩张系数反映了物理链路资源利用情况，可以表示如下：
其中，
4)备份资源与主用资源比例
备份资源与主用资源比例是描述备份保护方法的重要指标之一。它是指用于备份保护的资源总量与主用资源总量的比值。可表示为：
其中Reb(t)表示t时刻备份资源总量，是链路备份资源消耗、服务器节点备份资源消耗、以及备份拓扑转发资源消耗三者之和，Rez(t)表示t时刻主用资源总量，是主用链路资源消耗、主用服务器节点资源消耗、以及主用拓扑转发资源消耗三者之和，Td表示总的运行时间，δ是接近于0的常数。
3、建立SFC备份保护的整数线性规划模型
为更好地描述SFC的可靠部署问题，本发明建立SFC备份保护的整数线性规划模型，目标函数和相关约束条件如下：
(1)目标函数
minpb
备份资源与主用资源比例能够较好的反映出本发明的性能，因此选择以最小化备份资源与主用资源比例作为目标函数。
(2)约束条件
约束(11)表示如果虚拟网络功能vi被部署到底层物理网络节点ncl上，xil＝1。否则，xil＝0。约束(12)表示如果虚拟链路evij被部署到底层物理网络链路eslm上，yijlm＝1。否则，yijlm＝0。
约束(13)表示每一个底层网络物理节点可承载的VNF类型为m个。约束(14)表示业务流的每一个VNF都只能部署至一台通用服务器上。约束(15)表示底层网络剩余可用CPU计算资源不能小于VNF部署的CPU资源需求。约束(16)表示底层网络链路剩余带宽资源应大于服务功能链部署的链路资源需求。约束(17)表示底层交换机节点的可用转发能力应大于即将部署于其上业务流的转发资源需求。
rrp≤ARp(23)
约束(19)表示虚拟链路应部署在底层网络的无环路径上，以防止出现网络流量的乒乓效应。约束(20)表示如果该节点上有预留的备份资源，则可以被其他SFC中的VNF备份需求共享。约束(21)表示如果该链路上有预留的备份资源，则可以被其他SFC中的备份链路需求共享。约束(22)表示部署在底层网络的服务功能链必须满足业务流的时延需求，
4、RB-NFV方法设计
图3是本发明给出的RB-NFV方法流程图。
RB-NFV方法包括：基于最小费用最大流的SFC部署方法以及拓扑感知的SFC备份保护方法。首先，利用最小费用最大流算法综合考虑时延和可靠性进行SFC部署，尽可能提高其的可靠性，并生成SFC初步部署方案。其次，判断该方案能否达到SFC可靠性需求。如果已经达到可靠性需求，则为可行部署方案。否则利用拓扑感知的SFC备份保护方法，通过为该方案中可靠性较低的VNF预留备份资源的方式提高SFC可靠性。
5、基于最小费用最大流的SFC部署方法
为提高服务功能链部署性能，本发明所提方法首先把服务功能链部署问题转化为最优路径选择问题，然后利用最小费用最大流算法进行求解。
首先，根据业务流流入流出节点位置、各VNF节点资源需求以及业务流带宽需求确定候选节点集合和候选路径集合，并利用候选路径集合构造有向网络。其次利用拆点法将有向网络转化为容量-流量-费用网络，以底层网络链路时延为约束，以底层服务器节点可靠性作为费用，将服务功能链部署问题转化为最优路径选择问题。最后利用最小费用最大流算法寻找该底层网络源节点和汇节点之间的最小费用最大流路径，该路径即为可靠性最高的部署路径。由于在服务功能链部署过程中充分考虑底层网络资源利用情况以及VNF聚合问题，因此能够有效防止当底层资源不够充足时SFC部署路径过长的问题。
(1)拆点法构造容量-流量-费用网络
根据流入流出交换机节点位置、服务功能链中各VNF次序{v1,v2,...vn}、服务功能链请求长度L1(本发明定义服务功能链请求长度为首个虚拟网络功能到最后一个虚拟网络功能之间的跳数)以及流入流出交换机节点间的最短路径长度L2，确定各VNF候选服务器节点集合。为防止部署的SFC链路过长造成的服务质量问题，因此在服务器节点选择时应合理选择各VNF部署位置。引入单个服务器节点负载参数Nload，通过SDN控制器实时监控底层网络服务器节点负载，剔除负载超过95％的服务器节点。定义流入节点与底层候选服务器节点ncl的距离(即跳数)为I(ncl)，流出节点与底层候选节点nc距离(即跳数)为O(ncl)。
对于第i个虚拟网络功能vi，应选择满足约束条件(24-28)的服务器节点作为VNF候选部署节点。
I(ncl)≥i-1&I(ncl)≤i+3(24)
{max(L1,L2)-i-1}≤O(ncl)≤{max(L1,L2)-i+3}(25)
公式(24)(25)表示利用I(ncl)和O(ncl)对虚拟网络功能vi部署位置进行约束。
cpu(vi)≤cpu(ncl)(26)
fi∈C(ncl)(27)
Nload(ncl)≤0.95(28)
公式(26)表示候选服务器节点ncl可用计算资源应大于vi的计算资源需求，其中cpu(ncl)表示第l个服务器节点可用计算资源，cpu(vi)表示虚拟网络功能vi计算资源需求。公式(27)表示虚拟网络功能vi的服务类型需求应在候选服务器节点ncl可承载的服务类型范围内，C(ncl)表示第l个服务器节点可承载的服务类型。公式(28)候选服务器节点ncl应为非瓶颈节点，其中Nload(ncl)表示候选服务器节点ncl的实时负载。
候选节点选择具体算法步骤如下：
输入：底层网络实时资源和拓扑，SFC请求长度L1和流入流出交换机间最短路径L2
输出：候选节点集合NLIST
步骤1：网络控制器实时感知底层网络拓扑和实时资源情况
步骤2：利用约束条件(24-28)为各个虚拟网络功能选择候选节点
步骤3：将候选节点存入集合NLIST，NLIST＝{n(1)LIST；n(2)LIST；...；n(q)LIST}
根据候选节点选择算法结果，可得到各候选节点集合，如图5所示。
此时服务功能链部署问题就转化为寻找从源节点出发经过以上候选节点到达汇节点的最优路径问题，该路径必须经过所有候选节点集合，且每个候选集合中的节点只能使用一次，各候选节点集合中的重合节点可以作为VNF的聚合部署节点使用，以降低链路时延。假定底层网络节点可承载的VNF类型数为m，则相邻m个VNF可部署在同一个底层节点，除此之外则不可进行VNF聚合以防止流量的乒乓效应。例如m＝2，则第i个VNF可与第i-1个VNF部署在同一个服务器节点上，第i个VNF不可与除第i-1和第i+1个VNF以外的其它VNF聚合，否则易产生流量的乒乓效应。利用深度优先搜索算法以链路带宽为约束找出所有符合条件的底层网络有向路径，以这些底层网络有向路径构成适用于网络流的有向网络，具体算法步骤如下：
输入：底层网络实时资源和拓扑，流入流出节点位置，候选节点集合n(i)LIST
输出：候选路径集合l(i)LIST
步骤1：SDN控制器实时感知底层网络拓扑和实时资源情况。
步骤2：以流入节点为原点，以流出节点为汇点，以服务功能链时延和带宽需求为约束，利用深度优先搜索算法搜索所有从源节点到汇节点所有满足条件的路径。
步骤3：判断候选节点是否为重合节点，如果是，则该候选节点可作为VNF聚合节点使用。
步骤4：将遍历所有路径存入候选路径集合LLIST。
步骤5：将候选路径集合聚合一起在底层网络形成有向网络。
因业务流流量的有向性，为便于利用网络流理论寻找最优部署路径，需利用拆点法将有向网络转化为适用于网络流方法的容量-流量-费用网络Gc。将网络中节点进行编号，将节点Ai拆点为节点对Ai与Ai′，从Ai到Ai′连接一条边，边的容量为1(表示只能经过一次)，流量为1(表示经过次数)，一个节点对之间的流量费用为0(相当于自己到自己的费用)。如果节点Ai到Aj直接连接，则从Ai′到节点Aj连接一条边，边的容量为1，以节点Ai可靠性的倒数1/Ri作为Ai到Aj流量费用Rij，即cost＝Rij＝1/Ri，如图6所示。
(2)最小费用最大流算法
最小费用最大流问题就是在容量-流量-费用网络中求一个费用最小的最大流。利用最小费用最大流算法求解该问题，能够保证在流量最大的路径上费用最小，即可靠性最高，保证了服务功能链部署性能。为清楚地表述该问题，引入剩余网络的概念。每个网络Gc及其上的一个流都对应一个剩余网络RN(f)，其与网络Gc节点相同，剩余网络反映了节点间链路的剩余容量，如图7所示。
最小费用最大流算法具体步骤如下：
输入：Gs，SFC请求，Gc
输出：SFC初步部署方案
步骤1：令流量为零的最小费用流fk＝0，构造剩余网络RN(fk)。
步骤2：以Rij作为费用，利用深度优先搜索算法在RN(fk)中寻找从源点到汇点的最小费用路。
步骤3：如果最小费用路P不存在，fk为最小费用最大流,计算结束。否则，更新fk为fk+P，更新剩余网络RN(fk)，并返回步骤2。
步骤4：计算所得最小费用最大流路径即为候选最优部署路径。
步骤5：判断候选最优部署路径为是否为空集或是否不满足SFC计算资源需求，如果是，部署失败，计算结束。否则，初步部署成功，并输出SFC初步部署方案。
6、拓扑感知的SFC备份保护方法。
如果SFC初步部署方案能够满足SFC可靠性需求，则该方案即为最终部署方案，否则对该方案利用拓扑感知的SFC备份保护方法进行备份保护。本发明提出拓扑感知的SFC备份保护方法，仅对SFC中可靠性最低的VNF预留备份资源进行备份保护。如果可靠性仍不能满足需求，则考虑该SFC中的临近VNF共享备份资源，通过这种共享保护的方式提高其可靠性。不同SFC之间的备份资源也可以共享，尽可能提高底层网络资源利用率。
选定第r个虚拟网络功能vr作为待备份VNF，首先利用k-最短路径方法，选出从第(r-1)个虚拟网络功能vr-1部署节点S′到第(r+1)个虚拟网络功能vr+1部署节点T′之间除本条路径以外的k条最短路径作为候选备份路径集合BL。利用约束条件(22)和(26-29)在候选备份路径集合BL中选择最优备份路径：
bw(ev(r-1)r)≤bw(esS'T')&bw(evr(r+1))≤bw(esS'T')(29)
约束(23)表示备份链路选择应满足带宽需求，其中bw(ev(r-1)r)表示第(r-1)个VNF与r个VNF带宽需求，bw(evr(r+1))表示第r个VNF与(r+1)个VNF带宽需求，bw(esS’T’)表示节点S′和T′之间的可用链路带宽资源。拓扑感知的SFC备份保护方法具体步骤如下：
输入：SFC初步部署方案
输出：VNF备份节点位置及备份路径
步骤1：判断SFC初步部署方案满足SFC可靠性需求。如果是，则可靠部署成功，SFC初步部署方案即为最终部署方案。否则确定SFC可靠部署初步方案中最脆弱的虚拟网络功能。
步骤2：利用k-最短路径方法选出从S′到T′之间除本条以外的k条最短路径作为候选备份路径集合BL，并计算其时延和可靠性。
步骤3：利用(22)和(26-29)约束条件判断所选择候选备份路径集合BL是否满足要求，并将满足条件的选备份路径存入最优备份路径集合BLO。
步骤4：选择最优备份路径集合BLO中可靠性最高的路径，计算其可靠性ARp1，并考虑邻近VNF共享保护，计算其可靠性ARp。
步骤5：判断所选择路径可靠性ARp1是否满足SFC可靠性需求。如果满足，则备份保护成功，该方案即为最终部署方案。否则转步骤6。
步骤6：判断考虑邻近VNF共享保护的靠性ARp是否满足SFC可靠性需求，如果满足，则备份保护成功，该方案即为最终部署方案，计算结束。否则，可靠部署失败。
根据可靠性感知的SFC备份保护方法的最终部署方案，占用底层网络计算、转发和带宽资源，完成SFC可靠部署。
7、性能评估与分析
本发明利用MATLAB进行实验仿真，选取在较大规模的网络场景中对本发明提出方法进行性能验证，并与其它两种方法进行对比分析。
(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的平均生存时间满足参数为1000的指数分布，其可靠性需求在{0.8,0.9,0.95}中随机选择。
实验持续10000个时间单位，为减少随机因素的影响，实验进行了10次，取10次实验结果的平均值作为最终的实验结果。
(2)实验分析
本发明设置两组实验来验证提出的RB-NFV方法性能。第一组实验中，RB-NFV方法在相同的实验条件下与其他两种最新的服务功能链可靠性部署方法进行对比，如表二所示。第二组实验分析了底层网络资源使用情况，验证RB-NFV方法在资源合理利用方面的性能。
表2方法对比
实验一：方法性能对比
如图8所示，RU-NFV方法对原始SFC请求和备份拓扑联合优化，且考虑备份资源共享，取得了较好性能，但由于对所有VNF预留资源进行备份，因此底层网络资源消耗较快，稳定状态下可靠部署成功率稳定在0.48左右。RG-NFV方法对备份实例放置和服务功能链部署进行联合优化，性能较RU-NFV方法有较大提升，稳定状态下可靠部署成功率保持在0.65左右。本发明提出的RB-NFV方法由于在SFC部署阶段利用最小费用最大流进行求解，离最优解更近。在备份阶段仅对脆弱的VNF进行备份保护，且考虑邻近的VNF共享备份资源，因此预留备份资源较少，可靠部署成功率在对比三种方法中最高，稳定状态下保持在0.7左右。
如图9所示，RU-NFV方法由于对SFC中所有VNF进行备份，底层网络资源消耗较多，因此长期平均收益开销比下降较快，稳定状态下保持在0.53左右。RG-NFV方法对备份实例放置和服务功能链部署进行联合优化，性能较RU-NFV方法有较大提升，稳定状态下收益开销比保持在0.62左右。本发明提出的RB-NFV方法由于在SFC初步部署阶段利用最小费用最大流进行求解，使初步部署结果离最优解更近，在备份保护阶段仅对脆弱的VNF进行备份保护，且考虑邻近的VNF共享备份资源，因此预留备份资源较少，长期平均收益开销比在对比三种方法中最高，稳定状态下保持在0.65左右。
如图10所示，RU-NFV方法对SFC中所有VNF进行备份，且考虑备份资源共享，稳定状态下备份资源比例稳定在0.68左右。RG-NFV方法将备份实例放置和服务功能链部署进行联合优化，且能够充分考虑备份资源共享，因此备份资源消耗减少，性能较RU-NFV方法有一定提升，稳定状态下备份资源比例保持在0.54左右。本发明提出的RB-NFV方法仅对脆弱的VNF进行备份保护，且考虑邻近的VNF共享备份资源，可较大幅度减少备份资源消耗，备份资源比例在对比三种方法保持最低，稳定状态下保持在0.49左右。
平均链路扩张系数是反映SFC部署性能的重要指标。如图11所示，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方法，由于最小费用最大流算法在求解最优路径选择问题方面具有较好性能，且备份资源消耗较少，因此平均链路扩张系数在三种方法中最低，在到达率分别为0.1，0.15，0.2的情况下，平均链路扩张系数分别保持在1.31，1.34和1.38。RB-NFV方法的平均链路扩张系数在三种方法对比中始终保持最低。
实验二：分析底层网络资源使用情况
由于本发明提出的RB-NFV方法在SFC部署阶段优先选择可靠性高的节点进行部署，因此设置本组实验，主要从底层网络资源使用情况对RB-NFV方法进行性能分析，并与其他两种方法进行对比验证。
如图12所示，RU-NFV方法和RG-NFV方法由于未能充分考虑服务器节点的均衡使用问题，因此随着底层网络资源的不断消耗，底层服务器瓶颈节点较多且增长较快。RB-NFV方法在服务功能链部署阶段充分考虑服务器节点的均衡使用问题，因此瓶颈节点较少，稳定状态下低于3％，性能较为优异。
如图13所示，RU-NFV方法和RG-NFV方法在底层网络资源利用过程中未能充分考虑服务器节点的均衡使用问题，因此底层服务器节点资源使用不够均衡，出现了较多的闲置节点，稳定状态下分别为0.18和0.10。RB-NFV方法由于在SFC部署阶段和备份节点选择阶段考虑了底层服务器节点资源的均衡使用问题，因此资源使用较为均衡，闲置服务器节点比例低于0.05，相较于其他两种方法性能更好。
从以上两组实验可以看出，本发明提出方法RB-NFV相较于其它两种可靠性备份保护方法预留备份资源量更少，部署成功率更高，资源利用更加合理，整体性能较为优越。
