基于知识图谱的服务功能链在线部署算法

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

Abstract

Abstract:

The emergence of new network services such as immersive cloud XR and holographic communication puts forward higher requirements for network service quality.To ensure the availability of network services, the network service delay and reliability must be controlled within a certain quality of service according to the attributes and dependencies of network functions.However, the traditional network representation forms, such as bitmap and matrix, cannot cover these key network information, resulting in the information loss in the input stage of the algorithm, which leads to the deviation of the calculation results.Therefore, in order to accurately extract user needs and reflect the dynamic changes of network resources, knowledge graph was adopted to represent the network and its services, an online placement algorithm of service function chain based on knowledge graph was proposed.Based on this, a relationship alignment method based on editing distance was designed to guide the online placement of service function chains under complex dependency relationships.Experimental results show that the proposed algorithm can improve the placement accuracy of service function chain by 10%~15% and reduce the average network energy consumption by about 13%.The proposed algorithm has low complexity and high timeliness.

Key words: network function virtualization, service function chain, knowledge graph, entity alignment, virtual network function placement

CLC Number:

TP393

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.

Figures/Tables 16

References 24

[1]	MIJUMBI R , SERRAT J , GORRICHO J L ,et al. Network function virtualization:state-of-the-art and research challenges[J]. IEEE Communications Surveys ＆ Tutorials, 2016,18(1): 236-262.
[2]	ETSI. European telecommunications standards institute[R]. 2016.
[3]	SHERRY J , RATNASAMY S . A survey of enterprise middlebox deployments[R]. 2012.
[4]	YANG S , LI F , YAHYAPOUR R ,et al. Delay-sensitive and availability-aware virtual network function scheduling for NFV[J]. IEEE Transactions on Services Computing, 2022,15(1): 188-201.
[5]	YANG S , LI F , TRAJANOVSKI S ,et al. Recent advances of resource allocation in network function virtualization[J]. IEEE Transactions on Parallel and Distributed Systems, 2021,32(2): 295-314.
[6]	PHAM C , TRAN N H , REN S L ,et al. Traffic-aware and energy-efficient VNF placement for service chaining:joint sampling and matching approach[J]. IEEE Transactions on Services Computing, 2020,13(1): 172-185.
[7]	ZHANG Q , QIU X H , ZHU X R . A novel resource optimization algorithm for dynamic networks combined with NFV and SDN[C]// Inter national Conference on Wireless and Satellite Systems. Berlin:Springer, 2019: 283-296.
[8]	FREITAS B D , SANTOS G L , GON?ALVES G , ,et al. Optimizing NFV placement for distributing micro-data centers in cellular networks[J]. The Journal of Supercomputing, 2021,77(8): 8995-9019.
[9]	SOUALAH O , MECHTRI M , GHRIBI C ,et al. An efficient algorithm for virtual network function placement and chaining[C]// Proceedings of IEEE Annual Consumer Communications ＆ Networking Conference. Piscataway:IEEE Press, 2017: 647-652.
[10]	袁泉, 游伟, 季新生 ,等. 虚拟网络功能资源容量自适应调整方法[J]. 电子与信息学报, 2021,43(7): 1841-1848.
	YUAN Q , YOU W , JI X S ,et al. Adaptive scaling of virtualized network function resource capacity[J]. Journal of Electronics ＆ Information Technology, 2021,43(7): 1841-1848.
[11]	CHEN J , CHEN J , ZHANG H K . DRL-QOR:deep reinforcement learning-based QoS/QoE-aware adaptive online orchestration in NFV-enabled networks[J]. IEEE Transactions on Network and Service Management, 2021,18(2): 1758-1774.
[12]	陈康, 向勇, 喻超 . 大数据时代机器学习的新趋势[J]. 电信科学, 2012,28(12): 77-85.
	CHEN K , XIANG Y , YU C . New trend of machine learning in the age of big data[J]. Telecommunications Science, 2012,28(12): 77-85.
[13]	郭丽丽, 丁世飞 . 深度学习研究进展[J]. 计算机科学, 2015,42(5): 28-33.
	GUO L L , DING S F . Research progress on deep learning[J]. Computer Science, 2015,42(5): 28-33.
[14]	周传鑫, 孙奕, 汪德刚 ,等. 联邦学习研究综述[J]. 网络与信息安全学报, 2021,7(5): 77-92.
	ZHOU C X , SUN Y , WANG D G ,et al. Survey of federated learning research[J]. Chinese Journal of Network and Information Security, 2021,7(5): 77-92.
[15]	PAULHEIM H . Knowledge graph refinement:a survey of approaches and evaluation methods[J]. Semantic Web, 2016,8(3): 489-508.
[16]	刘峤, 李杨, 段宏 ,等. 知识图谱构建技术综述[J]. 计算机研究与发展, 2016,53(3): 582-600.
	LIU Q , LI Y , DUAN H ,et al. Knowledge graph construction techniques[J]. Journal of Computer Research and Development, 2016,53(3): 582-600.
[17]	庄严, 李国良, 冯建华 . 知识库实体对齐技术综述[J]. 计算机研究与发展, 2016,53(1): 165-192.
	ZHUANG Y , LI G L , FENG J H . A survey on entity alignment of knowledge base[J]. Journal of Computer Research and Development, 2016,53(1): 165-192.
[18]	MONGE A E , ELKAN C . The field matching problem:algorithms and applications[C]// Proceedings of ACM International Conference on Knowledge Discovery ＆ Data Mining. New York:ACM Press, 1996: 267-270.
[19]	NAVARRO G . A guided tour to approximate string matching[J]. ACM Computing Surveys, 2001,33(1): 31-88.
[20]	MECHTRI M , GHRIBI C , ZEGHLACHE D . A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network and Service Management, 2016,13(3): 533-546.
[21]	ALMOHAMAD H A , DUFFUAA S O . A linear programming approach for the weighted graph matching problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993,15(5): 522-525.
[22]	The University of Adelaide. The Internet topology zoo[R]. 2012.
[23]	SOLOZABAL R , CEBERIO J , SANCHOYERTO A ,et al. Virtual network function placement optimization with deep reinforcement learning[J]. IEEE Journal on Selected Areas in Communications, 2020,38(2): 292-303.
[24]	奥德玛, 杨云飞, 穗志方 ,等. 中文医学知识图谱 CMeKG 构建初探[J]. 中文信息学报, 2019,33(10): 1-9.
	BYAMBASUREN O , YANG Y F , SUI Z F ,et al. Preliminary study on the construction of Chinese medical knowledge graph[J]. Journal of Chinese Information Processing, 2019,33(10): 1-9.

Metrics

Recommended 0

No Suggested Reading articles found!

知识图谱	Schema	描述
KG_f	（实体 1_TYPE：VNF_i，实体 2_TYPE：VNF_j，关系_TYPE：依赖）	三元组的主体是VNF_i，与主体关系为依赖的实体是VNF_i有向边的另一端的VNF_j
	（实体_TYPE：虚拟网络功能 f_i，属性_TYPE：f_i 的属性，属性值_TYPE：f_i的属性）	三元组的主体是f_i，属性与属性值分别是f_i的属性、属性值
KG_s	（实体1：物理节点a，实体2：物理节点b，关系_TYPE：连接）	三元组的主体是物理节点a，与主体关系为连接的实体是节点a另一端的物理节点b
	（实体_TYPE：物理节点 n，属性_TYPE：n 的属性，属性值_TYPE：n的属性值）	三元组的主体是VNF，属性与属性值分别是VNF的属性、属性值

实体ID	实体名	实体属性(Cap_cpu(n), Cap_mem(n))
1	n₁	(7,9)
2	n₂	(3,6)
3	n₃	(8.9)
4	n₄	(7,6)
5	n₅	(5,8)

关系ID	实体1ID	实体2ID
r₁	n₁	n₂
r₂	n₁	n₃
r₃	n₁	n₄
r₄	n₂	n₃
r₅	n₃	n₅
r₆	n₄	n₅

实体ID	实体名	实体属性(D_cpu(f), D_mem(f))
1	f₁	(6,8)
2	f₂	(5,4)
3	f₃	(7,6)
4	f₄	(3,4)

关系ID	实体1ID	实体2ID
r₁	n₁	n₂
r₂	n₁	n₃
r₃	n₁	n₄
r₄	n₂	n₃

Online placement algorithm of service function chain based on knowledge graph

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 24

Related Articles 15

Metrics

Recommended 0

[1]	Rongpeng LI, Bingyan WANG, Honggang ZHANG, Zhifeng ZHAO. Design of knowledge enhanced semantic communication receiver [J]. Journal on Communications, 2023, 44(6): 70-76.
[2]	Hao CHEN, Yuan YANG, Mingwei XU, Dan PEI, Yilin YOU. Parallel orchestration and deployment system for scalable heterogeneous service function chain supporting polymorphic network [J]. Journal on Communications, 2022, 43(9): 1-11.
[3]	Xiuzhang YANG, Guojun PENG, Zichuan LI, Yangqi LYU, Side LIU, Chenguang LI. Research on entity recognition and alignment of APT attack based on Bert and BiLSTM-CRF [J]. Journal on Communications, 2022, 43(6): 58-70.
[4]	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.
[5]	Xiaoguang LI, Lei GONG, Xiaoli LI, Xin ZHANG, Ge YU. Learner preferences prediction with mixture embedding of knowledge and behavior graph [J]. Journal on Communications, 2021, 42(8): 130-138.
[6]	Jiachen SUN, Jinlong WANG, Guoru DING, Jin CHEN, Yuping GONG. Spectrum knowledge graph: an intelligent engine facing future spectrum management [J]. Journal on Communications, 2021, 42(5): 1-12.
[7]	Xiaojuan ZHAO, Yan JIA, Aiping LI, Kai CHEN. Research on link prediction model based on hierarchical attention mechanism [J]. Journal on Communications, 2021, 42(3): 36-44.
[8]	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.
[9]	Shaohu DING,Jichao XIE,Peng ZHANG,Liming PU,Yunjie GU. Dynamic migration method of key virtual network function based on risk awareness [J]. Journal on Communications, 2020, 41(4): 102-113.
[10]	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.
[11]	Zhongnan ZHAO,Jian WANG,Hongwei GUO. Adaptive routing and wavelength assignment method based on SDN [J]. Journal on Communications, 2019, 40(9): 95-105.
[12]	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.
[13]	Dan LI,Julong LAN,Peng WANG,Yuxiang HU. Service function chain deployment algorithm based on optimal weighted graph matching [J]. Journal on Communications, 2019, 40(3): 10-18.
[14]	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.
[15]	Xiaorong ZHU,Qian ZHANG. Resource optimization algorithm of combination of NFV and SDN for application of multiple services [J]. Journal on Communications, 2018, 39(11): 54-62.

类型	CPU	MEM
1	4	4
2	3	3
3	3	3
4	2	2
5	2	2
6	2	2
7	1	1
8	1	1