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

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

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

CLC Number:

TP393.0

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.

Figures/Tables 8

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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

QGA-based network service extension algorithm in NFV

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 27

Related Articles 11

Metrics

Recommended 0

[1]	Zexi XU, Lei ZHUANG, Kunli ZHANG, Mingyu GUI. Online placement algorithm of service function chain based on knowledge graph [J]. Journal on Communications, 2022, 43(8): 41-51.
[2]	Ze’nan WANG, Jiao ZHANG, Shuo WANG, Tao HUANG, F.Richard Yu. Service chain deployment algorithms for deterministic end-to-end delay upper bound [J]. Journal on Communications, 2021, 42(11): 66-78.
[3]	Kan WANG,Nan ZHAO,Junhuai LI,Huaijun WANG. Service function chain embedding algorithm with wireless multicast in mobile edge computing network [J]. Journal on Communications, 2020, 41(10): 37-47.
[4]	Chen SUN,Jun BI,Zhilong ZHENG,Shuhe WANG,Hongxin HU. MicroNF:a microservice-based hybrid framework for NFV [J]. Journal on Communications, 2019, 40(8): 54-59.
[5]	Hongqi ZHANG,Rui HUANG,Yingjie YANG,Dexian CHANG,Liancheng ZHANG. Cross-domain service chain mapping mechanism based on Q-learning [J]. Journal on Communications, 2018, 39(12): 102-112.
[6]	Liang WEI,Tao HUANG,Jiao ZHANG,Zenan WANG,Jiang LIU,Yunjie LIU. Service chain mapping algorithm based on reinforcement learning [J]. Journal on Communications, 2018, 39(1): 90-100.
[7]	Ding MA,Lei ZHUANG,Ju-long LAN. Discrete particle swarm optimization based multi-objective service path constructing algorithm [J]. Journal on Communications, 2017, 38(2): 94-105.
[8]	Fu-you FAN,Guo-wu YANG,Qian-qi LE,Feng-mao LV,Chao ZHAO. Optimized coverage algorithm of wireless video sensor network based on quantum genetic algorithm [J]. Journal on Communications, 2015, 36(6): 94-104.
[9]	Hui-qiang WANG,Xiao-ming CHEN,Hong-wu LV,Guang-sheng FENG,Qiang ZHU. Access point selection mechanism based on cross-layer awareness for cognitive networks [J]. Journal on Communications, 2015, 36(10): 188-199.
[10]	Jian GUO,Li-juan SUN,Wen-jun XU,Ru-chuan WANG,Fu XIAO. Mobile sink-based data collection scheme for wireless sensor networks [J]. Journal on Communications, 2012, 33(9): 176-184.
[11]	HANGXue Z. Research on the fairness of QoS degradation in multimedia wireless networks [J]. Journal on Communications, 2007, 28(5): 102-108.