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

### 引用本文

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.

### 文章历史

1. 国家数字交换系统工程技术研究中心 第三研究部, 郑州 450002;
2. 中华人民共和国科学技术部 信息中心, 北京 100000

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 引言

1 服务功能链备份问题

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

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

2.1.1 虚拟服务功能可靠性

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

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

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

2.2 备份机制

2.2.1 联合备份

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

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

 $\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 两种机制的可靠性比较

 $\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)

 $\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)

 $\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)

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

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

3.2 备份选择策略

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

 ${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)

 $\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)

 $\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)

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

 $\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)

3.3 求解算法

 $\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)

3.4 算法复杂度分析

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

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

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

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

 图 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