NFV中基于量子遗传算法的网络服务扩展算法

doi:10.11959/j.issn.1000-436x.2022218

通信学报 ›› 2022, Vol. 43 ›› Issue (11): 44-52.doi: 10.11959/j.issn.1000-436x.2022218

NFV中基于量子遗传算法的网络服务扩展算法

邱航, 汤红波, 游伟, 赵宇, 柏溢

信息工程大学信息技术研究所，河南郑州 450002

修回日期:2022-09-13 出版日期:2022-11-25 发布日期:2022-11-01
作者简介:邱航（1994− ），男，河南驻马店人，信息工程大学博士生，主要研究方向为5G移动通信网络架构、网络功能虚拟化等
汤红波（1968− ），男，湖北孝感人，博士，信息工程大学教授、博士生导师，主要研究方向为新型网络体系结构、移动通信网络空间安全
游伟（1984− ），男，江西丰城人，博士，信息工程大学副教授，主要研究方向为5G移动通信网络架构、移动通信网络安全等
赵宇（1984− ），男，吉林辽源人，博士，信息工程大学讲师，主要研究方向为移动通信网络安全、新型网络体系架构等
柏溢（1975− ），男，江苏盐城人，信息工程大学副研究员，主要研究方向为移动通信网络安全、新型网络体系架构等
基金资助:
国家重点研发计划基金资助项目(2020YFB1806607)

QGA-based network service extension algorithm in NFV

Hang QIU, Hongbo TANG, Wei YOU, Yu ZHAO, Yi BAI

Institute of Information Technology, Information Engineering University, Zhengzhou 450002, China

Revised:2022-09-13 Online:2022-11-25 Published:2022-11-01
Supported by:
The National Key Research and Development Program of China(2020YFB1806607)

摘要/Abstract

摘要：

为满足用户新的应用需求或者添加额外的安全保护功能，研究了基于网络功能虚拟化的云网络中已部署网络服务实例的功能扩展问题。将云网络中的网络服务扩展建模为整数线性规划模型，考虑到初始服务部署不受影响、扩展图部署、资源容量和节点亲和性等约束。同时，为应对未来大规模云网络的动态性和复杂性，提出了一种基于量子遗传算法的网络服务扩展算法，该算法基于量子态通过量子并行运算来提高求解效率和求解质量。仿真结果表明，所提算法在扩展成功率和平均资源开销等方面均表现较好，且具有较低的时间复杂度。

关键词: 网络功能虚拟化, 网络服务扩展, 虚拟网络功能转发图, 量子遗传算法

Abstract:

To meet the client’s new business requirements or add additional security protection functions, the already hosted network service extension problem in the cloud network based on network function virtualization was researched.The network service extension in the cloud network was modeled as an integer linear programming, considering the impact on initial service, extended graph deployment, resource capacity and virtual network function affinity constraints, and so on.To deal with the computational complexity and dynamism of future large-scale cloud networks, a QGA-based network service extension algorithm was proposed to improve solution efficiency and solution quality through quantum parallel computing.Simulation results prove that the efficient performance of the proposed algorithm in terms of extension successful ratio and average resource costs, and the proposed algorithm has low time complexity.

Key words: network function virtualization, network service extension, VNF-forwarding graph, quantum genetic algorithm

中图分类号:

TP393.0

邱航, 汤红波, 游伟, 赵宇, 柏溢. NFV中基于量子遗传算法的网络服务扩展算法[J]. 通信学报, 2022, 43(11): 44-52.

Hang QIU, Hongbo TANG, Wei YOU, Yu ZHAO, Yi BAI. QGA-based network service extension algorithm in NFV[J]. Journal on Communications, 2022, 43(11): 44-52.

图/表 8

图1

图2

表1

量子门旋转策略"

x_i	best_i	f(x)＞ f(best)	$Δ θ_{i}$	$s (α_{i}, β_{i})$
x_i	best_i	f(x)＞ f(best)	$Δ θ_{i}$	$α_{i} β_{i} > 0$	$α_{i} β_{i} < 0$	$α_{i} = 0$	$β_{i} = 0$
0	0	FALSE	0	0	0	0	0
0	0	TRUE	0	0	0	0	0
0	1	FALSE	0.01 π	+1	-1	0	±1
0	1	TRUE	0.01 π	-1	+1	±1	0
1	0	FALSE	0.01 π	-1	+1	±1	0
1	0	TRUE	0.01 π	+1	-1	0	±1
1	1	FALSE	0	0	0	0	0
1	1	TRUE	0	0	0	0	0

表1

图3

图4

图5

图6

图7

参考文献 27

[1]	ETSI GS NFV. Network functions virtualisation (NFV):architectural framework[R]. 2014.
[2]	ORDONEZ-LUCENA J , AMEIGEIRAS P , LOPEZ D ,et al. Network slicing for 5G with SDN/NFV:concepts,architectures,and challenges[J]. IEEE Communications Magazine, 2017,55(5): 80-87.
[3]	ETSI GS NFV. Network functions virtualisation (NFV):use case[R]. 2013.
[4]	YAO H , XIONG M Z , LI H ,et al. Joint optimization of function mapping and preemptive scheduling for service chains in network function virtualization[J]. Future Generation Computer Systems, 2020,108: 1112-1118.
[5]	HAWILO H , JAMMAL M , SHAMI A . Network function virtualization-aware orchestrator for service function chaining placement in the cloud[J]. IEEE Journal on Selected Areas in Communications, 2019,37(3): 643-655.
[6]	ZHANG B , FAN Q L , ZHANG X ,et al. A survey of VNF forwarding graph embedding in B5G/6G networks[J]. Wireless Networks, 2021(8): 1-24.
[7]	ADDIS B , BELABED D , BOUET M ,et al. Virtual network functions placement and routing optimization[C]// Proceedings of IEEE 4th International Conference on Cloud Networking. Piscataway:IEEE Press, 2015: 171-177.
[8]	MEHRAGHDAM S , KELLER M , KARL H . Specifying and placing chains of virtual network functions[C]// Proceedings of IEEE 3rd International Conference on Cloud Networking. Piscataway:IEEE Press, 2014: 7-13.
[9]	TASTEVIN N , OBADIA M , BOUET M . A graph approach to placement of service functions chains[C]// Proceedings of IFIP/IEEE Symposium on Integrated Network and Service Management. Piscataway:IEEE Press, 2017: 134-141.
[10]	PEI J N , HONG P L , XUE K P ,et al. Efficiently embedding service function chains with dynamic virtual network function placement in geo-distributed cloud system[J]. IEEE Transactions on Parallel and Distributed Systems, 2019,30(10): 2179-2192.
[11]	KIM S , PARK S , KIM Y ,et al. VNF-EQ:dynamic placement of virtual network functions for energy efficiency and QoS guarantee in NFV[J]. Cluster Computing, 2017,20(3): 2107-2117.
[12]	LI X , QIAN C . The virtual network function placement problem[C]// Proceedings of IEEE Conference on Computer Communications Workshops. Piscataway:IEEE Press, 2015: 69-70.
[13]	WANG S Y , LV T J . Deep reinforcement learning for demand-aware joint VNF placement-and-routing[C]// Proceedings of IEEE Globecom Workshops. Piscataway:IEEE Press, 2019: 1-6.
[14]	袁泉, 汤红波, 黄开枝 ,等. 基于Q-learning算法的vEPC虚拟网络功能部署方法[J]. 通信学报, 2017,38(8): 172-182.
	YUAN Q , TANG H B , HUANG K Z ,et al. Deployment method for vEPC virtualized network function via Q-learning[J]. Journal on Communications, 2017,38(8): 172-182.
[15]	YU H , YANG J H , FUNG C . Elastic network service chain with fine-grained vertical scaling[C]// Proceedings of IEEE Global Communications Conference. Piscataway:IEEE Press, 2018: 1-7.
[16]	ETSI GS NFV-TST. Network functions virtualisation (NFV),predeployment testing,report on validation of NFV environments and services[R]. 2016.
[17]	HOUIDI O , SOUALAH O , LOUATI W ,et al. Virtualized network services extension algorithms[C]// Proceedings of IEEE 17th International Symposium on Network Computing and Applications. Piscataway:IEEE Press, 2018: 1-5.
[18]	LIU J J , LU W , ZHOU F ,et al. On dynamic service function chain deployment and readjustment[J]. IEEE Transactions on Network and Service Management, 2017,14(3): 543-553.
[19]	HOUIDI O , SOUALAH O , LOUATI W ,et al. Dynamic VNF forwarding graph extension algorithms[J]. IEEE Transactions on Network and Service Management, 2020,17(3): 1389-1402.
[20]	QIU H , TANG H B , YOU W ,et al. Robust service provisioning of service function chain under demand uncertainty[J]. IET Communications, 2022,16(7): 803-814.
[21]	邱航, 汤红波, 游伟 . 基于深度Q网络的在线服务功能链部署方法[J]. 电子与信息学报, 2021,43(11): 3122-3130.
	QIU H , TANG H B , YOU W . Online service function chain deployment method based on deep Q network[J]. Journal of Electronics ＆Information Technology, 2021,43(11): 3122-3130.
[22]	LIU L , ZHOU Y Q , YUAN J H ,et al. Economically optimal MS association for multimedia content delivery in cache-enabled heterogeneous cloud radio access networks[J]. IEEE Journal on Selected Areas in Communications, 2019,37(7): 1584-1593.
[23]	BOIXO S , ISAKOV S V , SMELYANSKIY V N ,et al. Characterizing quantum supremacy in near-term devices[J]. Nature Physics, 2018,14(6): 595-600.
[24]	GONG L H , XIANG L Z , LIU S H ,et al. Born machine model based on matrix product state quantum circuit[J]. Physica A:Statistical Mechanics and Its Applications, 2022,593:126907.
[25]	ZHOU N R , XIA S H , MA Y ,et al. Quantum particle swarm optimization algorithm with the truncated mean stabilization strategy[J]. Quantum Information Processing, 2022,21(2): 1-23.
[26]	LAHOZ-BELTRA R . Quantum genetic algorithms for computer scientists[J]. Computers, 2016,5(4): 24.
[27]	ORLOWSKI S , WESSAELY R , PIORO M ,et al. SNDlib 1.0-survivable network design library[J]. Networks, 2010,55(3): 276-286.

NFV中基于量子遗传算法的网络服务扩展算法

QGA-based network service extension algorithm in NFV

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 27

相关文章 15

Metrics

推荐阅读 0

[1]	陈浩, 杨芫, 徐明伟, 裴丹, 尤艺霖. 支持多模态网络的可扩展异构服务功能链并行编排部署系统[J]. 通信学报, 2022, 43(9): 1-11.
[2]	徐泽汐, 庄雷, 张坤丽, 桂明宇. 基于知识图谱的服务功能链在线部署算法[J]. 通信学报, 2022, 43(8): 41-51.
[3]	杨力, 潘成胜, 孔相广, 黄琦龙, 戚耀文. 5G融合卫星网络研究综述[J]. 通信学报, 2022, 43(4): 202-215.
[4]	王泽南, 张娇, 汪硕, 黄韬, F.RichardYu. 端到端时延上限确定的服务链部署算法[J]. 通信学报, 2021, 42(11): 66-78.
[5]	王侃,赵楠,李军怀,王怀军. 移动边缘计算网络中联合无线多播的服务功能链部署算法[J]. 通信学报, 2020, 41(10): 37-47.
[6]	孙晨,毕军,郑智隆,王舒鹤,胡宏新. MicroNF：基于微服务的异构网络功能虚拟化框架[J]. 通信学报, 2019, 40(8): 54-59.
[7]	钱红燕,薛昊,陈鸣. UDM：基于NFV的防止DDoS攻击SDN控制器的机制[J]. 通信学报, 2019, 40(3): 116-124.
[8]	兰巨龙,金子晋,孙鹏浩,江逸茗,王月. 基于可靠性的服务功能链构建算法[J]. 通信学报, 2019, 40(1): 64-70.
[9]	张红旗,黄睿,杨英杰,常德显,张连成. 基于Q-learning的跨域服务链映射机制[J]. 通信学报, 2018, 39(12): 102-112.
[10]	魏亮,黄韬,张娇,王泽南,刘江,刘韵洁. 基于强化学习的服务链映射算法[J]. 通信学报, 2018, 39(1): 90-100.
[11]	马丁,庄雷,兰巨龙. 基于离散粒子群优化的多目标服务路径构建算法[J]. 通信学报, 2017, 38(2): 94-105.
[12]	樊富有,杨国武,乐千桤,吕凤毛,赵超. 基于量子遗传算法的无线视频传感网络优化覆盖算法[J]. 通信学报, 2015, 36(6): 94-104.
[13]	王慧强,陈晓明,吕宏武,冯光升,朱强. 认知网络基于跨层感知的接入选择机制[J]. 通信学报, 2015, 36(10): 188-199.
[14]	郭剑,孙力娟,许文君,王汝传,肖甫. 基于移动sink的无线传感器网络数据采集方案[J]. 通信学报, 2012, 33(9): 176-184.
[15]	张雪. 多媒体无线网中QoS降级的公平性研究[J]. 通信学报, 2007, 28(5): 102-108.