基于联合备份的服务功能链可靠性保障的部署方法

汤红波; 邱航; 游伟; 季新生

doi:10.11999/JEIT190013

基于联合备份的服务功能链可靠性保障的部署方法

doi: 10.11999/JEIT190013

国家数字交换系统工程技术研究中心郑州 450002

基金项目: 国家重点研发计划网络空间安全专项(2016YFB0801605)，国家自然科学基金创新群体项目(61521003)，国家自然科学基金(61801515)

详细信息

作者简介:
汤红波：男，1968年生，教授、博师生导师，主要研究方向为移动通信网络、新型网络体系结构

邱航：男，1994年生，硕士生，研究方向为新一代移动通信技术、5G网络安全

游伟：男，1984年生，博士，讲师，研究方向为移动通信网络安全，新一代移动通信网络技术

季新生：男，1968年生，教授、博师生导师，主要研究方向为新一代移动通信技术、网络安全

通讯作者:
邱航　hangsoon@foxmail.com

中图分类号: TN393.03
计量
- 文章访问数: 2862
- HTML全文浏览量: 1155
- PDF下载量: 75
- 被引次数: 15
出版历程
- 收稿日期: 2019-01-07
- 修回日期: 2019-04-22
- 网络出版日期: 2019-05-24
- 刊出日期: 2019-12-01

A Reliability-guarantee Method for Service Function Chain Deployment Based on Joint Backup

National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China

Funds: The National Key R & D Program Cyberspace Security Special (2016YFB0801605), The National Natural Science Foundation Innovative Groups Project of China (61521003), The National Natural Science Foundation of China (61801515)

摘要

摘要: 在网络功能虚拟化(NFV)环境中，针对服务功能链(SFC)部署时的可靠性问题，该文提出对备份虚拟网络功能选择、备份实例放置和服务功能链部署的联合优化方法。首先，定义一个单位开销可靠性提高值的虚拟网络功能衡量标准，改进备份虚拟网络功能选择方法；其次，采用联合备份的方式调整相邻备份实例之间的放置策略，以降低带宽资源开销；最后，将整个服务功能链可靠性保障的部署问题构建成整数线性规划模型，并提出一种基于最短路径的启发式算法，克服整数线性规划求解的复杂性。仿真结果表明，该方法在优先满足网络服务可靠性需求的同时，优化资源配置，提高了请求接受率。
- 网络功能虚拟化(NFV) /
- 服务功能链(SFC) /
- 可靠性 /
- 单位开销可靠性提高值 /
- 整数线性规划
Abstract: In the Network Function Virtualization (NFV) environment, for the reliability problem of Service Function Chain (SFC) deployment, a joint optimization method is proposed for backup Virtual Network Function (VNF) selection, backup instance placement and service function chain deployment. Firstly, the method defines a virtual network function measurement standard named the unit cost reliability improvement value to improve the backup virtual network function selection method. Secondly, the joint backup mode is used to adjust the placement strategy between adjacent backup instances to reduce bandwidth resources overhead. Finally, the reliability-guarantee problem of the whole service function chain deployment is modeled as integer linear programming, and a heuristic algorithm based on the shortest path is proposed to overcome the complexity of integer linear programming. The simulation results show that the method optimizes resource allocation while prioritizing the network service reliability requirements, and improves the request acceptance rate.
- Network Function Virtualization (NFV) /
- Service Function Chaining (SFC) /
- Reliability /
- Unit cost improvement value /
- Integer linear programming

HTML全文

图 1 服务功能链部署示例

下载: 全尺寸图片幻灯片

图 2 专用备份与联合备份示例

下载: 全尺寸图片幻灯片

图 3 请求接受率比较

下载: 全尺寸图片幻灯片

图 4 带宽使用率比较

下载: 全尺寸图片幻灯片

图 5 节点计算资源使用率比较

下载: 全尺寸图片幻灯片

图 6 不同可靠性下请求接受率比较

下载: 全尺寸图片幻灯片

表 1 基于ILP的保障SFC可靠性的部署方案

初始化输入
${\rm{NU}}{{\rm{M}}_{ij}} = 1, (i \in {[1, \left\| S \right\|]_z}, j \in {[1, \left\| {{F_i}} \right\|]_z})$ ；
Finished_flag=1;
While true
求解最优化问题：目标函数式(6)
约束条件：式(7)—式(25)(线性化)
计算SFC的可靠性 ${Q_i}$
For $i = 1:\left\| S \right\|$
If ${Q_i} < Q_i^{{\rm{req}}}$
选择单位开销可靠性提高值最大的VNF $j$ 进行备份；
${\rm{NU}}{{\rm{M}}_{ij}} = {\rm{NU}}{{\rm{M}}_{ij}} + 1$ ；
If ${g_{ij}} = 0$ ；
If VNF $j - 1$ 的备份实例可联合备份；
${g_{ij}} = 1$
End；
Finished_flag=0；
End

下载: 导出CSV

表 2 基于最短路径的贪婪保障SFC可靠性的部署方案

初始化输入
${\rm{NU}}{{\rm{M}}_{ij}} = 1, (i \in {[1, \left\| S \right\|]_z}, j \in {[1, \left\| {{F_i}} \right\|]_z})$ ；
For $i = 1:\left\| S \right\|$
网络状态信息更新
生成初始路径集合 ${{\rm P}_i}$
For ${{\rm P}_i}$ 中选择初始路径 $ip$
For $j = 1:\left\| {{F_i}} \right\|$
沿着路径 $ip$ 依次部署VNF $j$ ，同时考虑备份实例 ${\rm{NU}}{{\rm{M}}_{ij}}$ 和　　　 ${g_{ij}}$ 的取值
End；
If ${F_i}$ 中存在未部署的VNF实例
Continue；
End；
计算SFC的可靠性 ${{\varTheta} _i}$
If ${Q_i} < Q_i^{{\rm{req}}}$
选择单位开销可靠性提高值最大的VNF $j$ 进行备份；
${\rm{NU}}{{\rm{M}}_{ij}} = {\rm{NU}}{{\rm{M}}_{ij}} + 1$ ；
If ${g_{ij}} = 0$
If VNF $j - 1$ 的备份资源可联合备份；
${g_{ij}} = 1$ ；
End；
End

下载: 导出CSV

表 3 8节点网络3条SFC的部署结果

算法	SFC	部署结果	可靠性	带宽使用率(%)	运行时间(s)
IRG-SFC	${f_1} \to {f_2} \to {f_3}$	$8 \to 4\left( {{f_1}} \right) \to 7\left( {{f_2}} \right)\left( {3\left\{ {{f_1}, {f_2}} \right\}} \right) \to 2\left( {{f_3}} \right) \to 1\left( {{f_3}} \right) \to 5$	0.99	17.18	463
	${f_1} \to {f_3} \to {f_2}$	$1 \to 2\left( {{f_1}} \right) \to 6\left( {{f_1}} \right) \to 3\left( {{f_3}} \right) \to 8\left( {{f_2}} \right)\left( {7\left\{ {{f_2}, {f_3}} \right\}} \right) \to 4$	0.99
	${f_2} \to {f_1} \to {f_3}$	$3 \to 4\left( {{f_2}} \right) \to 7\left( {{f_2}} \right) \to 2\left( {{f_1}} \right) \to 5\left( {{f_3}} \right)\left( {6\left\{ {{f_1}, {f_3}} \right\}} \right) \to 1$	0.99
GSP-SFC	${f_1} \to {f_2} \to {f_3}$	$8 \to 4\left( {{f_1}} \right) \to 6\left( {{f_2}} \right)\left( {3 \to 2\left\{ {{f_1}, {f_2}} \right\}} \right) \to 1\left( {{f_3}} \right) \to 5\left( {{f_3}} \right) \to 5$	0.99	19.09	0.49
	${f_1} \to {f_3} \to {f_2}$	$1 \to 2\left( {{f_1}} \right) \to 6\left( {{f_1}} \right) \to 3\left( {{f_3}} \right) \to 8\left( {{f_2}} \right)\left( {7\left\{ {{f_2}, {f_3}} \right\}} \right) \to 4$	0.99
	${f_2} \to {f_1} \to {f_3}$	$3 \to 4\left( {{f_2}} \right) \to 7\left( {{f_2}} \right) \to 2\left( {{f_1}} \right) \to 5\left( {{f_3}} \right)\left( {6\left\{ {{f_1}, {f_3}} \right\}} \right) \to 1$	0.99

下载: 导出CSV

参考文献(17)

NGMN A. 5G White Paper[OL]. https://www.ngmn.org/5g-white-paper/5g-white-paper.html, 2015.

BO Han, VIJAY G, JI Lusheng, et al. Network function virtualization: Challenges and opportunities for innovations[J]. IEEE Communications Magazine, 2015, 53(2): 90–97. doi: 10.1109/MCOM.2015.7045396

GIL H J, and FELIPE B J. Resource allocation in NFV: A comprehensive survey[J]. IEEE Transactions on Network & Service Management, 2017, 13(3): 518–532. doi: 10.1109/TNSM.2016.2598420

ALLEG A, TOUFIK A, MOS M, et al. Delay-aware VNF placement and chaining based on a flexible resource allocation approach[C]. The 13th International Conference on Network and Service Management, Tokyo, Japan, 2017: 1–7.

OUS S, MAR M, CHAIMA G, et al. Energy efficient algorithm for VNF placement and chaining[C]. The 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, Madrid, Spain, 2017: 579–588.

刘彩霞, 卢干强, 汤红波, 等. 一种基于Viterbi算法的虚拟网络功能自适应部署方法[J]. 电子与信息学报, 2016, 38(11): 2922–2930. doi: 10.11999/JEIT160045

LIU Caixia, LU Ganqiang, TANG Hongbo, et al. Adaptive deployment method for virtualized network function based on viterbi algorithm[J]. Journal of Electronics &Information Technology, 2016, 38(11): 2922–2930. doi: 10.11999/JEIT160045

YUAN Quan, TANG Hongbo, YOU Wei, et al. Virtual network function scheduling via multilayer encoding genetic algorithm with distributed bandwidth allocation[J]. Science China Information Sciences, 2018, 61(9): 92–107. doi: 10.1007/s11432-017-9357-7

COT D, DE SIMONE L, IAN A K, et al. Network function virtualization: challenges and directions for reliability assurance[C]. IEEE International Symposium on Software Reliability Engineering Workshops. Naples, Italy, 2014: 37–42.

SUN Jian, ZHU Guangyang, SUN Gang, et al. A reliability-aware approach for resource efficient virtual network function deployment[J]. IEEE Access, 2018, 6: 18238–18250. doi: 10.1109/ACCESS.2018.2815614

GEM A, VIS R, PAR C, et al. OpenNF: Enabling innovation in network function control[C]. ACM Conference on Sigcomm, Chicago, USA, 2014: 163–174.

FAN Jingyuan, YE Zilong, GUAN Chaowen, et al. GREP: Guaranteeing reliability with enhanced protection in NFV[C]. ACM Sigcomm Workshop on Hot Topics in Middleboxes & Network Function Virtualization, London, United Kingdom, 2015: 13–18.

QU Long, CHA A, KHA S, et al. A Reliability-aware network service chain provisioning with delay guarantees in NFV-enabled enterprise datacenter networks[J]. IEEE Transactions on Network and Service Management, 2017, 14(3): 554–568. doi: 10.1109/TNSM.2017.2723090

ZHU Zhikai, LU Hancheng, LI Jian, et al. Service function chain mapping with resource fragmentation avoidance[C]. 2017 IEEE Global Communications Conference, Singapore, 2017: 1–6.

SARA A, ZHANG Yanhong, and CHADI A. RAS: Reliable auto-scaling of virtual machines in multi-tenant cloud networks[C]. IEEE International Conference on Cloud Networking, Niagara Falls, Canada, 2015: 1–6.

HOY A, and RAUSAND M. System Reliability Theory: Models and Statistical Methods[M]. WILEY: Hoboken, USA, 2004: 97–106.

KHEB S, HADJI M, and ZEG D. Scalable and cost-efficient algorithms for VNF chaining and placement problem[C]. Innovations in Clouds, Internet & Networks, Paris, France, 2017: 92–99.

YEN J Y. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712–716. doi: 10.1287/mnsc.17.11.712

施引文献

期刊类型引用(11)

1.	王忠，吴炀，宋化宇，李飞龙. 基于可靠性的卫星服务功能链保护方法. 指挥控制与仿真. 2024(01): 147-153 . 百度学术
2.	孟芸，牛永豪，王萍，代亮. 车路协同网络中服务功能链可行时长优化映射算法. 交通运输系统工程与信息. 2023(01): 114-122 . 百度学术
3.	胡海岩，康巧燕，赵朔，王建峰，付有斌. 基于节点综合重要度排序的服务功能链部署优化方法. 计算机应用. 2023(03): 860-868 . 百度学术
4.	王颖，陈可，喻鹏，李文璟，邱雪松，孟洛明. 多级隔离的网络切片可用性保障方法. 软件学报. 2023(12): 5757-5772 . 百度学术
5.	宋鑫康，赵尚弘，王翔，郝少伟. 航空信息网络服务功能链协同构建与映射策略. 系统工程与电子技术. 2022(11): 3556-3563 . 百度学术
6.	张岳，张俊楠，吴晓春，洪晨，周静静. 基于改进灰狼优化算法的服务功能链映射算法. 电信科学. 2022(11): 57-72 . 百度学术
7.	韩晓阳，孟相如，康巧燕，翟东，刘鹏飞. 可靠性与拓扑感知的服务功能链备份保护方法. 系统工程与电子技术. 2021(07): 1961-1970 . 百度学术
8.	阳勇，孟相如，康巧燕，赵文文. 基于流量优化的可靠服务功能链部署方法. 系统工程与电子技术. 2021(10): 3017-3025 . 百度学术
9.	孙士清，彭建华，游伟，李英乐. 5G网络下资源感知的服务功能链协同构建和映射算法. 西安交通大学学报. 2020(08): 140-148 . 百度学术
10.	翟东，孟相如，康巧燕，胡航，韩晓阳. 面向时延与可靠性优化的服务功能链部署方法. 电子与信息学报. 2020(10): 2386-2393 . 本站查看
11.	唐伦，曹睿，廖皓，王兆堃. 基于深度强化学习的服务功能链可靠部署算法. 电子与信息学报. 2020(12): 2931-2938 . 本站查看