计算机应用   2017, Vol. 37 Issue (4): 948-953  DOI: 10.11772/j.issn.1001-9081.2017.04.0948
0

引用本文 

周桥, 伊鹏, 门浩崧. 基于资源效用最大化的虚拟网络功能备份方法[J]. 计算机应用, 2017, 37(4): 948-953.DOI: 10.11772/j.issn.1001-9081.2017.04.0948.
ZHOU Qiao, YI Peng, MEN Haosong. Virtual network function backup method based on resource utility maximization[J]. Journal of Computer Applications, 2017, 37(4): 948-953. DOI: 10.11772/j.issn.1001-9081.2017.04.0948.

基金项目

国家973计划项目(2012CB315901);国家863计划项目(2015AA016102)

通讯作者

周桥 (1993-), 男, 湖北钟祥人, 硕士研究生, 主要研究方向:网络功能虚拟化、服务功能链。E-mail: zhouqiao_ndsc@163.com

作者简介

伊鹏 (1977-), 男, 河南郑州人, 研究员, 博士, 主要研究方向:宽带信息网络、网络安全;
门浩崧 (1978-), 男, 北京人, 工程师, 硕士, 主要研究方向:复杂网络

文章历史

收稿日期:2016-09-05
修回日期:2016-12-24
基于资源效用最大化的虚拟网络功能备份方法
周桥1, 伊鹏1, 门浩崧2    
1. 国家数字交换系统工程技术研究中心 第三研究部, 郑州 450002;
2. 中华人民共和国科学技术部 信息中心, 北京 100000
摘要: 针对网络功能虚拟化环境下组成服务功能链的虚拟网络功能故障所引起的网络服务故障问题,提出一种最大化资源效用的虚拟服务功能备份方法来提高网络可靠性。首先,对虚拟服务功能备份问题进行详细分析并建立了可靠性评估模型,提出了改进的备份机制,并证明了该机制与其他机制相比的优势;其次,对全网络设计了全局备份算法和备份选择策略来对相应的虚拟网络功能选取备份直到满足可靠性需求。仿真实验结果表明,与GREP方法、联合备份机制加上随机选择策略(JP+random selection)及双重共享式备份机制加上随机选择策略(DSP+random selection)相比,该方法在可靠性和资源利用率上取得了优异的性能,特别是服务功能链请求接受率提高18.8%~25%,资源效用利用率提高15%~20%。实验结果表明该方法能较为有效地利用资源来提升网络可靠性。
关键词: 网络功能虚拟化    服务功能链    虚拟服务功能    可靠性    备份    
Virtual network function backup method based on resource utility maximization
ZHOU Qiao1, YI Peng1, MEN Haosong2     
1. The Third Research Department, National Digital Switching System Engineering & Technological R & D Center, Zhengzhou Henan 450002, China;
2. Information Center, Ministry of Science and Technology of the People's Republic of China, Beijing 100000, China
Abstract: Concerning the network service failure caused by the virtual network function failure of the service function chain in the network function virtualization environment, a resource utility maximization backup method of virtual network function was put forward to improve the network reliability. First, the backup problem of virtual network functions was analyzed in detail and a reliability evaluation model was established; then a corresponding backup mechanism was put forward, and the advantages of the proposed mechanism over other mechanisms were proved. Secondly, a global backup method and a backup selection strategy were designed to select the corresponding virtual network functions until the reliability requirement was satisfied. Finally, simulation and experimental results showed that compared with GREP, JP+random selection and DSP+random selection, the proposed method achieved excellent performance in terms of reliability and resource utilization, especially improved the rate of request acceptance by 18.8%-25% and the resource utilization ratio by 15%-20%. The experimental results demonstrate that the proposed method can effectively utilize the resources to improve the network reliability.
Key words: network function virtualization    service function chain    virtual network function    reliability    backup    
0 引言

计算机网络由一系列丰富的网络功能 (Network Function, NF) 组成, 如负载均衡、冲突检测以及防火墙等[1]。传统的网络功能通常由基于硬件的中间件盒子 (Middlebox) 所提供, 但其扩展性不强, 难以灵活配置及开销巨大等缺点一直备受诟病[2]。随着网络功能虚拟化 (Network Function Virtualization, NFV)[3]的演进, 部署在商用x86服务器上的虚拟网络功能 (Virtual NF, VNF) 逐渐代替了传统的中间件盒子[4]。这些基于软件的网络功能根据需求按一定的逻辑顺序组合构成服务功能链 (Service Function Chain, SFC)[5]来向用户提供相应的网络服务。网络服务的可靠性受网络功能的影响, 网络功能故障导致网络服务失效甚至网络瘫痪的事件时有发生, 例如2012年12月, 谷歌公司因负载均衡器的配置不当而导致包括Gmail和Chrome在内的多个谷歌服务受到影响[6]。如何提高服务功能链的可靠性成为近年来研究的热点。

文献曾对中间件盒子故障进行了一个长达两年的调研, 得出如下结论:传统基于硬件的网络功能故障发生大部分是因为链路故障, 其次是设备故障, 最后是配置不当。网络功能虚拟化技术将在硬件中间件盒子上的流量包处理转移到了软件上, 成为了虚拟化的网络功能。NFV带来革命性变化的同时却对网络功能的可靠性带来了新的挑战:首先, 发生在某物理设备上的单个虚拟服务功能故障可能影响多个服务功能链; 另外, 根据需求动态部署服务功能链的特性使虚拟机的分布变得更加复杂[8]。简而言之, 搭载着虚拟服务功能的虚拟机故障也成为除了链路故障外导致网络服务故障的另一个主要原因。

为了减小网络功能故障发生的概率, 提高网络服务的可靠性, 文献设计出一种高容错率的中间件盒子 (Fault-Tolerant MiddleBox, FTMB), 通过回滚处理状态来对中间件盒子进行故障恢复。该方法仅针对传统基于硬件中间件内部进行优化, 但是大大增加了硬件和软件开销, 而且基于传统的中间件盒子进行改善存在着一定的局限性。文献首次对虚拟网络功能故障进行研究, 提出一个提高可靠性的算法——GREP (Guaranteeing Reliability with Enhanced Protection in NFV), 该算法旨在提高可靠性的同时减少资源消耗。但该方法在虚拟网络功能故障提供满足需求的备份时, 并没有考虑资源约束条件和实际备份开销, 模型较为理想化。

本文对服务功能链建立可靠性模型并提出双重共享式备份机制, 在计算、存储和带宽三重资源约束下对虚拟服务功能进行备份, 提出一种最大化资源效用的服务功能链备份方法 (Max Resource Utilization Backup algorithm, MRUB)。

1 服务功能链备份问题

图 1是网络功能虚拟化环境下的服务功能链映射图:给定一个底层物理网络拓扑Gs(Ns, Es), 其中, Ns是物理节点集合, Es是物理链路集合。对节点nNs, 其计算、存储和带宽资源容量为 (Cn, Mn, Bn)。节点n搭载的服务器上能提供kn种虚拟服务功能${f_{^n}} = \{ f_n^i|i \in [1, {k_n}]\} $, 其正常工作时资源消耗为$({c_n}, {m_n}, {b_n}) = \{ (c_n^i, m_n^i, b_n^i)|i \in [1, {k_n}]\} $。该网络中所能提供总的服务功能${F_s} = \mathop \cup \limits_{i = 1}^{{N_s}} f_n^i$。将一条给定服务功能链SFC请求r表示为Qr(Vr, Lr, θr), 其中:${V_r} = \{ v_r^1, v_r^2...v_r^{|{V_r}|}\} $是服务功能需求集合, 表示着每个虚拟服务功能${f_{v_r^j}} \in {F_n}$的资源消耗三元组vrj(cj, mj, bj), 其可靠性为rvrj${F_r} = \bigcup\limits_j {{f_{v_r^j}}} $表示服务功能请求r所需要的服务功能集合;Lr表示服务功能链路路径;θr则是该服务功能请求r的最低可靠性要求。

图 1 服务功能链映射拓扑图 Figure 1 Service function chain topological graph

对基础的虚拟服务功能进行简单映射是达不到所需要的最低可靠性要求的。当出现虚拟服务功能故障或者链路故障时, 达不到服务功能链可靠性要求, 底层网络无法满足SFC请求。因此, 定义可靠性备份问题如下:给定一系列SFC请求, 每个请求都有着特定的可靠性要求, 根据计算存储和带宽约束等资源约束, 确定备份机制并找到资源消耗最小的备份算法来满足所有的可靠性要求。

2 可靠性模型和备份机制 2.1 可靠性模型

衡量在网络功能虚拟化环境下部署的服务功能链这样一个复杂系统的可靠性时, 通常先考虑从可靠性易获取的虚拟服务功能入手[10]。虚拟服务功能由挂载在商用x86服务器上的虚拟机所提供, 绝大部分的虚拟服务功能故障是由虚拟机故障所引起的[11]。这里假设所有的虚拟服务功能故障都是虚拟机故障, 当服务器发生宕机、断电等灾难性故障时, 均引起虚拟服务功能故障。

2.1.1 虚拟服务功能可靠性

虚拟服务功能的可靠性等同于在任何时间能正常工作的概率, 因此, 可以通过虚拟服务功能正常工作的时间和非正常工作时间来衡量。通过大量的运行数据, 可以轻易地获取这些数据。因此, 虚拟服务功能可靠性R由平均故障发生间隔 (Mean Time Between Failures, MTBF) 与平均故障恢复时间 (Mean Time To Repair, MTTR) 所决定:

$ R = \frac{{MTBF}}{{MTBF + MTTF}} $ (1)
2.1.2 服务功能链可靠性

一条服务功能链由若干个虚拟服务功能所组成。为了评估服务功能链的可靠性, 需要对服务功能之间的连接形式进行区分。一般情况下, 服务功能链中虚拟服务功能都是以级联形式互相连接, 业务流量依次穿过特定顺序的虚拟服务功能, 如图 2(a)所示, 此时服务功能链的可靠性为:

图 2 虚拟服务功能连接形式 Figure 2 Connection forms of VNFs
$ {R_{{\rm{SFC}}}} = {R_{{\rm{VN}}{{\rm{F}}_1}}} \times {R_{{\rm{VN}}{{\rm{F}}_2}}} $ (2)

为了提高服务功能可靠性, 采用并联的形式将虚拟服务功能的备份引入服务功能链中, 如图 2(b)所示, 此时该服务功能链的可靠性为:

$ {R_{{\rm{SFC}}}} = 1 - (1 - {R_{{\rm{VN}}{{\rm{F}}_1}}}) \times (1 - {R_{{\rm{VN}}{{\rm{F}}_2}}}) $ (3)

在2.2节引入虚拟网络功能备份机制后, 将增加服务功能链的结构复杂性, 但通过这两个基本的模型, 可以对结构更加复杂的服务功能链进行可靠性建模与评估。

2.2 备份机制

针对传统的一对一式备份[12]可靠性不够高和共享式备份不能同时响应多个虚拟服务功能故障的情况, 文献提出联合备份 (Joint Protection, JP) 的思想, 但该机制将多个虚拟服务功能集中到同一个虚拟机, 资源高度集中的特点易增加物理机负担, 同时在资源约束条件下难以有效部署。本文提出一种双重共享式备份机制, 与文献的备份机制相比, 在总资源消耗相差不大的情况下, 提高了系统的可靠性。下面给出了两种机制的介绍, 以及本文机制对可靠性提高的证明。

2.2.1 联合备份

图 3所示, 联合备份 (JP) 机制对连接到它的虚拟服务功能 (这里用两个来举例) 均提供备份, 即fb= fi+fj, 而且其提供的备份虚拟服务功能b的资源等于虚拟服务功能ij之和, 这里用s笼统地表示三种资源, 则sb=si+sj。因此, 当虚拟服务功能ij同时故障时, 备份虚拟服务功能b正常工作, 服务功能链仍能正常工作。考察采用备份机制时服务功能链SFC的可靠性, 只有当虚拟服务功能ij发生故障的同时备份b也故障才导致整个服务功能链故障, 因此SFC的可靠性为:

图 3 联合备份机制 Figure 3 Joint protection mechanism
$ {R_{{\rm{jp}}}} = 1 - (1 - {r_b})(1 - {r_i}{r_j}) $ (4)
2.2.2 双重共享式备份

图 4所示, 双重共享式备份 (Double Share Protection, DSP) 机制对若干个 (这里用两个来举例) 连接到它的服务功能提供双重备份, 但是所能提供的备份虚拟服务功能b的资源等于其所备份虚拟服务ij的最大值, 即fb=max (fi, fj), sb=max (si, sj)。此时, 考察服务功能链的正常工作的三种情况:虚拟服务功能ij都正常, 虚拟服务功能ij有一个故障但备份b1b2不能同时故障, 以及虚拟服务功能ij都故障且备份b1和b2都正常。

图 4 双重共享式备份机制 Figure 4 Double share protection mechanism

因此SFC的可靠性:

$ \begin{array}{l} {R_{{\rm{dsp}}}} = {r_i}{r_j} + (1 - {r_i})(1 - {r_j}){r_{{b_1}}}{r_{{b_2}}} + \\ \;\;\;\;\;\;\;\;\;(1 - {r_i}){r_j}({r_{{b_1}}} + {r_{{b_2}}} - {r_{{b_1}}}{r_{{b_2}}}) + \\ \;\;\;\;\;\;\;\;\;(1 - {r_j}){r_i}({r_{{b_1}}} + {r_{{b_2}}} - {r_{{b_1}}}{r_{{b_2}}}) \end{array} $ (5)
2.2.3 两种机制的可靠性比较

下面将DSP机制比JP机制进行比较, 令二者相减得到:

$ \begin{array}{l} {R_{{\rm{dsp}}}} - {R_{{\rm{jp}}}} = (1 - {r_i})(1 - {r_j}){r_{{b_1}}}{r_{{b_2}}} + {r_b}(1 - {r_i}{r_j}) + \\ \;\;\;\;\;\;\;\;\;(1 - {r_i}){r_j}({r_{{b_1}}} + {r_{{b_2}}} - {r_{{b_1}}}{r_{{b_2}}}) + \\ \;\;\;\;\;\;\;\;\;(1 - {r_j}){r_i}({r_{{b_1}}} + {r_{{b_2}}} - {r_{{b_1}}}{r_{{b_2}}}) \end{array} $ (6)

假设所有备份的可靠性是一致的, 即Rbackup=rb=rb1=rb2, 则式 (6) 可化简为:

$ \Delta R = {R_{{\rm{dsp}}}} - {R_{{\rm{jp}}}} = (2{r_i} + 2{r_j} - 3{r_i}{r_j} - 1)(1 - {r_b}){r_b} $ (7)

对式 (7) 求偏导数可得:

$ \frac{{\partial \Delta R}}{{\partial {r_i}}} = (2 - 3{r_j})(1 - {r_b}){r_b} $ (8)
$ \frac{{\partial \Delta R}}{{\partial {r_j}}} = (2 - 3{r_i})(1 - {r_b}){r_b} $ (9)

令偏导数为零, 可得ri=rj=2/3时, 此时取得极大值ΔR=1/3(1-rb)rb>0;根据经验ri, rj∈(2/3, 1), 故ri=rj=1时取得最小值, 此时ΔR=0, 因此ΔR∈(0, 1/3(1-rb)rb)>0, 即在所用资源相差不大的情况下, 本文提出的DSP机制与文献所提出的JP机制相比, 可靠性更高。

3 最大化资源效用的备份方法 3.1 全局备份算法

为了尽可能满足所有服务功能链请求的可靠性要求, 需要利用第2章所提到的双重共享式备份机制来对虚拟服务功能进行备份。为此, 本文设计了一个最大化资源效用的启发式备份算法, 根据底层物理节点资源和服务功能请求, 利用该机制进行备份, 直到使可靠性满足服务功能链要求为止。

最大化资源效用的启发式备份算法的伪代码如下所示:

输入:Gs(Ns, Ls), Vr(Nr, Lr, θr)。

输出:备份节点BN, 备份链路BL和备份虚拟服务功能VNFb

1)  计算请求服务功能链的可靠性ρ

2)  if ρθr

    不需要提供备份

4)  while ρ < θr do

5)    X ←根据3.2节选择需要备份的x个VNF

6)    if X ≠ ∅

7)    BN ←按照2.2.2节机制从X中选择VNFb备份到节点BN

8)    BL ←备份连接VNFb的链路

9)    更新服务功能链的可靠性ρ

10) end

11) return BN, BL and VNFb

算法的输入部分是底层网络节点和服务功能请求, 输出部分是虚拟服务功能的备份节点和备份链路。首先, 根据服务功能请求中的虚拟服务功能集合序列及其可靠性来计算该服务功能链的实际可靠性, 当实际可靠性满足服务功能链请求中所要求的最低可靠性时, 不需要进行备份;否则, 需要进行备份操作。此时, 根据资源消耗模型, 制定备份策略, 选择出需要进行备份的x个虚拟服务功能构成备份集合。当X不是空集时, 从X中选择需要备份的虚拟服务功能备份到节点BN, 并选择备份路径, 更新此时节点BN的资源及备份以后服务功能链的可靠性。按上述步骤不断进行备份操作, 当服务功能链的可靠性满足需求的最低可靠性时, 跳出迭代, 输出备份节点、备份链路以及备份的虚拟服务功能。

3.2 备份选择策略

为了更有效地提高服务功能链的可靠性, 常用的方法是选取可靠性最低的若干个虚拟服务功能进行备份。对此, 文献选取两个虚拟服务功能进行备份, 并证明了这两个备份的可靠性最低才能达到最高的可靠性提高, 但并未就备份选取的数目给出解释与证明。针对此问题, 本文通过资源约束建模来寻找得到最大可靠性提高的最佳备份数目。

假设备份虚拟服务功能的数目为x, 备份集合为可靠性最低的服务功能集合Vx={v1′, v2′, …, vx′}。本文的主要目标是寻找最佳的备份数目使得部署在网络中的商用服务器的资源消耗最小, 资源效用最大, 并且使可靠性提高率也尽可能大。

由于物理机资源类型是多维的, 直接比较不同虚拟网络功能的资源需求十分困难。文献提出了多种函数处理多维资源类型问题。其中之一是加权求和, 即通过调整权重来改变资源类型的利用率比重, 从而整合不同的类型。本文参考文献, 定义了不同资源的加权求和函数, 如式 (10) 所示, 将函数值作为服务器nN的实际资源利用率的估计。

$ {U_n} = \sum\limits_{v{}_j \in {V_x}} {{H_j}} $ (10)

其中Hj表示虚拟网络功能备份vj利用物理机n资源的比率, 计算如下:

$ {H_j} = \log \left( {\omega _n^c\frac{{{c_j}}}{{{C_n}}} + \omega _n^m\frac{{{m_j}}}{{{M_n}}} + \omega _n^b\frac{{{b_j}}}{{{B_n}}}} \right) $ (11)

式 (11) 为实际多维资源利用率的加权和。ωncωnmωnb为不同类型资源的权重, 满足约束条件:ωnc+ωnm+ωnb=1。

由于本文通过均衡多维资源实现最大化物理机资源的利用率, 所以不同维资源的权值需要区别设置来达到多维资源间的均衡。如果某维资源的利用率高于其他维, 该维资源将成为物理机资源使用的瓶颈, 需要降低其对总的资源利用率的贡献。因此, 将多维资源权值定义为当前资源使用比率的反比例函数:

$ \left\{ \begin{array}{l} \omega _n^c = \frac{1}{{p_n^c}}/\sum\limits_i {\frac{1}{{p_n^i}}} \\ \omega _j^m = \frac{1}{{p_n^m}}/\sum\limits_i {\frac{1}{{p_n^i}}} \\ \omega _j^b = \frac{1}{{p_n^b}}/\sum\limits_i {\frac{1}{{p_n^i}}} \end{array} \right. $ (12)

其中: $\sum\limits_i {\frac{1}{{p_n^i}}} = \frac{1}{{p_j^c}} + \frac{1}{{p_j^m}} + \frac{1}{{p_j^b}}$pjcpjmpjb为物理机不同资源维度下的当前使用率, 即备份前的资源利用率。

$ \left\{ \begin{array}{l} p_n^c = \frac{1}{{{C_n}}}\sum\limits_{{v_i} \in {V_r}} {{c_i}} \\ p_n^m = \frac{1}{{{M_n}}}\sum\limits_{{v_i} \in {V_r}} {{m_i}} \\ p_n^b = \frac{1}{{{B_n}}}\sum\limits_{{v_i} \in {V_r}} {{b_i}} \end{array} \right. $ (13)

定义该服务功能链的可靠性提高率为f2(x) :

$ {f_2}(x) = {R_x}/{R_{{\rm{SFC}}}} $ (14)

其中:Rx是备份后的服务功能可靠性, 由式 (5) 计算得出; RSFC是备份前的服务功能链可靠性, 由式 (2) 计算得出。f2(x) 与x的取值成正相关, 当备份数量越多时, 提高率就越大, 但当备份数目增多时, 其提高率增加不明显, 最终该函数趋向于某一定值。

综上, 建立备份策略选择模型:

$ \max \;\;\;\{ {f_1}(x) = \sum\limits_{n \in N} {{U_n}} ,{f_2}(x)\} $ (15)
$ {\rm{s}}.{\rm{t}}.{\rm{ }}\sum\limits_{{v_i} \in {V_r}} {{c_i}} + \sum\limits_{{v_j} \in {V_x}} {{c_j}} \le {C_n};\forall n \in {N_s} $ (16)
$ \sum\limits_{{v_i} \in {V_r}} {{m_i}} + \sum\limits_{{v_j} \in {V_x}} {{m_j}} \le {M_n};\forall n \in {N_s} $ (17)
$ \sum\limits_{{v_i} \in {V_r}} {{b_i}} + \sum\limits_{{v_j} \in {V_x}} {{b_j}} \le {B_n},\forall n \in {N_s} $ (18)
$ {V_r} \cap {V_x} = {V_x},{V_r} \cup {V_x} = {V_r} $ (19)

该问题是在带宽、CPU和内存等多维资源约束下计算最优的虚拟网络功能备份策略。约束条件 (16)~(18) 是为了保证原虚拟网络功能vi和备份的虚拟网络功能vj资源使用量之和不会超出服务器所能提供的总量;式 (19) 是为了保证该备份虚拟服务功能是该服务功能链的子集。

3.3 求解算法

该模型为多目标规划 (Multi-Objective Programming, MOP) 问题, 目标是寻找最优的虚拟功能迁移数目x和此时的备份策略Vx, 使得SFC可靠率较大提高和资源消耗最少。而可靠率的提高势必会带来资源消耗的增多, 这两个目标函数互相冲突, 不存在唯一的全局最优解使得两者都达到最优。但是, 存在一些解使某个函数较优, 同时其他目标函数不至于劣化, 这样的解称之为非劣有效解 (Pareto最优解)。

粒子群优化 (Particle Swarm Optimization, PSO) 算法[14]是一种具有形式简洁、收敛快速和参数调节机制灵活等优点的进化算法, 并且已经成功应用于单目标优化问题, 被认为是求解多目标优化问题最具潜力的方法之一。

在粒子群优化算法中, 一个无质量的粒子i可以由位置向量xi和速度向量vi表示, 其中, xi=xi, 1, xi, 2, …, xi, D]TRD, vi=vi, 1, vi, 2, …, vi, D]TRD, i=1, 2, …, N(N是种群中的粒子个数), D是决策变量个数。种群中的每一个粒子, 在进化程中根据式 (1) 更新速度和位置:

$ \left\{ \begin{array}{l} {\mathit{\boldsymbol{v}}_i}\left( {t + 1} \right) = w{\mathit{\boldsymbol{v}}_i}\left( t \right) + {c_1}{r_1}\left( {\mathit{\boldsymbol{pBest}} - {\mathit{\boldsymbol{x}}_i}\left( t \right)} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{c_2}{r_2}\left( {\mathit{\boldsymbol{gBest}} - {\mathit{\boldsymbol{x}}_i}\left( t \right)} \right)\\ {\mathit{\boldsymbol{x}}_i}\left( {t + 1} \right) = {\mathit{\boldsymbol{x}}_i}\left( t \right) + {\mathit{\boldsymbol{v}}_i}\left( {t + 1} \right) \end{array} \right. $ (20)

其中:t表示迭代次数;w≥0表示惯性权重系数;c1, c2≥0表示加速系数;r1r2是在[0, 1]内均匀分布的随机数;pBest表示第i个粒子的个体最优解;gBest表示整个群体的全局最优解。在式 (20) 的速度更新方程中, 第1部分为粒子当前速度乘以惯性权重进行加速, 表示粒子对当前自身运动的信任, 依据自身的速度进行惯性运动; 第2部分为自我认知部分, 表示粒子对自身历史的思考; 第3部分为社会认知部分, 表示粒子在群体中的信息共享和相互合作。

针对该多目标规划模型, 参考文献设计算法具体步骤如下:

步骤1  初始化粒子群:给定群体规模N, 随机产生每个粒子的位置Xi、速度Vi;

步骤2  用目标函数f1(x), f2(x) 分别计算每个粒子的适应度值;

步骤3  在两个目标函数f1(x), f2(x) 下分别对每个粒子求得个体极值pBest[1, i], pBest[1, i];

步骤4  对两个目标函数f1(x), f2(x) 分别求两个全局极值gBest[1]gBest[2];

步骤5  计算两全局矢量的均值pBest和距离dgBest;

步骤6  计算每个粒子pBest[1, i]和pBest[2, i]之间的距离dpBest[i];

步骤7  对每个粒子计算更新位置Xi、速度Vi时所要用的个体极值pBest[i];

步骤8  用步骤5和步骤7所得的gBest[i]、pBest[i]更新每个粒子位置Xi、速度Vi;

步骤9  如满足终止条件则退出, 否则返回步骤2。

3.4 算法复杂度分析

假设群体规模即待备份虚拟功能数量为n, 则求解算法中步骤1到步骤5仅需分别迭代一次, 算法时间复杂度为O(2n); 步骤6需要迭代2次, 算法时间复杂度为O(n2)。假设执行p次求解出结果, 则总算法时间复杂度为O(pn2)+O(2pn)。求解出最佳备份虚拟功能数量和备份策略后, 仍需代入全局备份算法中继续求解出最终备份策略, 假设该迭代次数为q, 则全局备份算法时间复杂度为O(pqn2)+O(2pqn), 加号后者相对前者可忽略不计, 则该算法时间复杂度为O(pqn2), 不考虑系数即O(n2)。

4 实验仿真与性能评估 4.1 实验场景与平台

实验仿真建立在4节点的网络中, 网络拓扑如图 5所示。网络每个节点都能提供计算、存储和带宽三种资源, 假设都是1 000个单元。假设网络中有8种网络功能, 每个物理节点能提供4到6个网络功能。每种类型网络功能可靠性在[0.9, 0.99]内随机分布。每条服务功能链都由互相连接的2到6个虚拟网络功能所组成, 它们对三种资源的消耗在[0, 30]个单元之间随机分布。参考谷歌应用的服务等级协议[16], 对每个服务功能链请求, 在{95%, 96%, 97%, 98%, 99%, 99.9%}之间选择它们的可靠性。算法仿真通过一台配置为3.4 GHz Intel Core i7处理器, 4 GB内存的计算机完成。

图 5 实验网络拓扑 Figure 5 Experimental network topology
4.2 仿真结果与分析

在仿真中, 与文献所提出的GREP方法、联合备份机制加上随机选择策略 (JP+random selection) 及双重共享式备份机制加上随机选择策略 (DSP+random selection) 作对比, 分别从请求接收率、平均服务功能备份数量、平均链路备份数量和资源效用利用率四个方面进行分析。其中, 请求接收率反应模型可靠性能, 平均服务功能备份数量和平均链路备份数量反映资源消耗情况, 资源利用率则反映模型对资源的利用情况。

首先, 模拟不同虚拟服务功能备份机制和策略下的服务功能链请求接受率。从图 6可以看到, 本文所提出MRUB方法和双重共享式备份机制加上随机选择策略相比, 在发送请求相同的情况下, 接受请求数量明显较高, 说明了该方法备份选择策略的有效性。同时, 和联合备份机制加上随机选择策略及GREP方法相比, 服务功能链请求接受率最高, 特别是在发送请求数目增多时表现更加明显, 请求接收率提高约18.8%。该仿真结果表明了本文方法在大量服务功能链请求环境下的优异性能。主要原因是MRUB方法在负载较重情况下能够使得物理机存储、计算、带宽三种资源负载均衡, 且与其他两种方法相比MRUB方法的可靠率提高较大, 能够最大化满足用户服务功能链请求。

图 6 请求接受率 Figure 6 Request acceptance rate

图 7~8所示为平均虚拟服务功能备份数量及平均链路备份数量。本文MRUB方法稍劣于GREP, 但明显优于其他两种方案, 这是因为GREP方法中并未考虑部署备份虚拟网络功能物理机的实际资源约束, 将若干个备份的虚拟功能集中到某一个上, 其模型较为理想化, 所得结果比实际效果好。虽然GREP方法所需的备份VNF数量和链路备份数量相对较少, 但其资源集中的特点加重了物理机的负担。

图 7 平均虚拟服务功能备份数量 Figure 7 Average number of VNF backups
图 8 平均链路备份数 Figure 8 Average number of link backups

图 9所示四种方案资源效用利用率对比, 可以看到除本文方案外的其他三种方案并未对资源效用进行优化, 三者的资源利用率相差不大, 而本文MRUB方法和三者相比, 提高15%~20%, 明显优于其他三种方案, 即以最小的资源开销得到最大的网络效用。

图 9 资源效用利用率 Figure 9 Resource utility utilization
5 结语

本文主要针对网络功能虚拟化环境下的服务功能链备份问题进行了研究。首先, 针对服务功能链的可靠性评估, 提出了可靠性模型及可靠性提高的备份机制; 其次, 对备份虚拟服务功能的计算、存储和带宽资源进行建模, 提出一种最大化资源效用的备份方法; 最后, 仿真实验结果表明了该方法在大规模服务功能链请求下的优异性能, 且其与一般的备份方法相比在资源利用率上也得到了提高。但本文方法在虚拟功能备份数量和链路备份数量上, 并未有明显提高。下一步主要工作是对虚拟服务功能备份数量和链路备份数量进行优化。

参考文献
[1] MEHRAGHDAM S, KELLER M, KARL H. Specifying and placing chains of virtual network functions[C]//Proceedings of the 2014 IEEE 3rd International Conference on Cloud Networking. Piscataway, NJ: IEEE, 2014: 7-13.
[2] BARI M F, CHOWDHURY S R, AHMED R, et al. On orchestrating virtual network functions in NFV[C]//CNSM 2015: Proceedings of the 201511th International Conference on Network and Service Management. Washington, DC: IEEE Computer Society, 2015: 50-56.
[3] CARAPINHA J, JIMÉNEZ J. Network virtualization: a view from the bottom[C]//Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. New York: ACM, 2009: 73-80.
[4] HWANG J, RAMAKRISHNAN K K, WOOD T. NetVM: high performance and flexible networking using virtualization on commodity platforms[J]. IEEE Transactions on Network and Service Management, 2015, 12 (1) : 34-47. doi: 10.1109/TNSM.2015.2401568
[5] HALPERN J, PIGNATARO C. RFC 7665, Service Function Chaining (SFC) architecture[S]. Geneva: IETF, 2015.
[6] BRODKIN J. Why Gmail went down: Google misconfigured load balancing servers[EB/OL].[2016-03-10]. http://arstechnica.com/information-technology/2012/12/why-gmail-went-down-google-misconfigured-chromes-sync-server/. https://arstechnica.com/information-technology/2012/12/why-gmail-went-down-google-misconfigured-chromes-sync-server/
[7] POTHARAJU R, JAIN N. Demystifying the dark side of the middle: a field study of middlebox failures in datacenters[C]//Proceedings of the 2013 Conference on Internet Measurement Conference. New York: ACM, 2013: 9-22.
[8] FAN J, YE Z, GUAN C, et al. GREP: guaranteeing reliability with enhanced protection in NFV[C]//Proceedings of the 2015 ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization. New York: ACM, 2015: 13-18.
[9] SHERRY J, GAO P X, BASU S, et al. Rollback-recovery for middleboxes[C]//Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. New York: ACM, 2015: 227-240.
[10] SCHÖLLER M, KHAN N, ADAMS R, et al. ETSI GS NFV-REL 001, V1.1.1-Network Functions Virtualisation (NFV) resiliency requirements[S]. Sophia Antipolis, France: ITSI, 2015.
[11] GILL P, JAIN N, NAGAPPAN N. Understanding network failures in data centers: measurement, analysis, and implications[J]. ACM SIGCOMM Computer Communication Review, 2011, 41 (4) : 350-361. doi: 10.1145/2043164
[12] MISHRA M, SAHOO A. On theory of VM placement: anomalies in existing methodologies and their mitigation using a novel vector based approach[C]//Proceedings of the 2011 IEEE International Conference on Cloud Computing. Piscataway, NJ: IEEE, 2011: 275-282.
[13] KENNEDY J. Particle swarm optimization[M]//SAMMUT C, WEBB G I. Encyclopedia of Machine Learning. Berlin: Springer, 2010: 760-766.
[14] 张利彪, 周春光, 马铭, 等. 基于粒子群算法求解多目标优化问题[J]. 计算机研究与发展, 2004, 41 (7) : 1286-1291. ( ZHANG L B, ZHOU C G, MA M, et al. Solutions of multi-objective optimization problems based on particle swarm optimization[J]. Journal of Computer Research and Development, 2004, 41 (7) : 1286-1291. )
[15] 胡旺, YENG G, 张鑫. 基于Pareto熵的多目标粒子群优化算法[J]. 软件学报, 2014, 25 (5) : 1025-1050. ( HU W, YEN G G, ZHANG X. Multiobjective particle swarm optimization based on pareto entropy[J]. Journal of Software, 2014, 25 (5) : 1025-1050. )
[16] UCSC. Google Apps service level agreement[EB/OL].[2016-03-10]. http://its.ucsc.edu/sla/google-sla.html. http://its.ucsc.edu/sla/google-sla.html