Multicast Service Function Tree Embedding Algorithm Based on Delay and Jitter Awareness

LIU Liang; CHEN Xiang; GUI Xiaojing; XU Yongjun; DU Yarong; HOU Zetian; DUAN Jie

doi:10.11999/JEIT230015

Volume 46 Issue 1

Jan. 2024

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 > 46(1): 184-194

LIU Liang, CHEN Xiang, GUI Xiaojing, XU Yongjun, DU Yarong, HOU Zetian, DUAN Jie. Multicast Service Function Tree Embedding Algorithm Based on Delay and Jitter Awareness[J]. Journal of Electronics & Information Technology, 2024, 46(1): 184-194. doi: 10.11999/JEIT230015

Citation:

LIU Liang, CHEN Xiang, GUI Xiaojing, XU Yongjun, DU Yarong, HOU Zetian, DUAN Jie. Multicast Service Function Tree Embedding Algorithm Based on Delay and Jitter Awareness[J]. Journal of Electronics & Information Technology, 2024, 46(1): 184-194. doi: 10.11999/JEIT230015

Citation:

PDF( 3028 KB)

Multicast Service Function Tree Embedding Algorithm Based on Delay and Jitter Awareness

doi: 10.11999/JEIT230015

1.
School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
2.
School of Automation, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Funds: The National Natural Science Foundation of China (62171070, 61701058),Chongqing University of Posts and Telecommunications Doctoral Initiation Foundation (A2023007)

Received Date: 2023-01-12
Accepted Date: 2023-08-15
Rev Recd Date: 2023-08-07

Available Online: 2023-08-19

Publish Date: 2024-01-17

Abstract

Abstract

To solve the problem that Multicast Request flows (MRs) need to traverse sequentially a Service Function Tree (SFT) consisting of Virtual Network Functions (VNFs) as well as ensuring stringent delay and jitter constraints of SFT in Network Function Virtualization (NFV)-enabled Software-Defined Networks (SDNs), a routing algorithm for constructing a multicast SFT based on depth-first search with an optimal link selection function is proposed. Firstly, the relative cost functions of network resources are proposed to guarantee the automatic load balancing of the network. Secondly, an Integer Linear Programming model (ILP) for the SFT dynamic embedding is constructed by jointly considering network resources, VNF dynamic placement and delay and jitter constraints of a multicast flow. Finally, for this NP-hard problem, an auxiliary edge-weight graph and optimal link selection function are designed for routing path selection, and a delay and jitter-aware SFT Embedding Algorithm (SFT-EA) is proposed with the objective of minimizing the resource consumption cost. Simulation results demonstrate the SFT-EA has better performance in terms of throughput, traffic acceptance rate, and network load balance.
- Network Function Virtualization (NFV),
- Service Function Tree (SFT),
- Multicast,
- Delay and Jitter

FullText(HTML)

References(22)

References

[1]	唐伦, 吴婷, 周鑫隆, 等. 一种基于联邦学习资源需求预测的虚拟网络功能迁移算法[J]. 电子与信息学报, 2022, 44(10): 3532–3540. doi: 10.11999/JEIT210743 TANG Lun, WU Ting, ZHOU Xinlong, et al. A virtual network function migration algorithm based on federated learning prediction of resource requirements[J]. Journal of Electronics &Information Technology, 2022, 44(10): 3532–3540. doi: 10.11999/JEIT210743
[2]	LIU Liang, GUO Songtao, LIU Guiyan, et al. Joint dynamical VNF placement and SFC routing in NFV-enabled SDNs[J]. IEEE Transactions on Network and Service Management, 2021, 18(4): 4263–4276. doi: 10.1109/TNSM.2021.3091424
[3]	徐勇军, 谷博文, 谢豪, 等. 全双工中继协作下的移动边缘计算系统能耗优化算法[J]. 电子与信息学报, 2021, 43(12): 3621–3628. doi: 10.11999/JEIT200937 XU Yongjun, GU Bowen, XIE Hao, et al. Energy consumption optimization algorithm for full-duplex relay-assisted mobile edge computing systems[J]. Journal of Electronics &Information Technology, 2021, 43(12): 3621–3628. doi: 10.11999/JEIT200937
[4]	MALI R, ZHANG Xijun, and QIAO Chunming. Benefits of multicasting in all-optical networks[C]. SPIE 3531, All-Optical Networking: Architecture, Control, and Management Issues. Boston, United States, 1998: 209–220.
[5]	Grand View Research. Video streaming market size, share & trends analysis report by streaming type, by solution, by platform, by service, by revenue model, by deployment type, by user, by region, and segment forecasts, 2023 – 2030[EB/OL].https://www.grandviewresearch.com/industry-analysis/video-streaming-market, 2023.
[6]	XIE Yanghao, HUANG Lin, KONG Yuyang, et al. Virtualized network function forwarding graph placing in SDN and NFV-Enabled IoT networks: A graph neural network assisted deep reinforcement learning method[J]. IEEE Transactions on Network and Service Management, 2022, 19(1): 524–537. doi: 10.1109/TNSM.2021.3123460
[7]	XU Zichuan, LIANG Weifa, HUANG Meitian, et al. Approximation and online algorithms for NFV-enabled multicasting in SDNs[C]. 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), Atlanta, USA, 2017: 625–634.
[8]	MUHAMMAD A, SORKHOH I, QU Long, et al. Delay-sensitive multi-source multicast resource optimization in NFV-enabled networks: A column generation approach[J]. IEEE Transactions on Network and Service Management, 2021, 18(1): 286–300. doi: 10.1109/TNSM.2021.3049718
[9]	孔紫璇, 李航, 向万, 等. 用户动态接入下的多播业务链部署和调整方法[J]. 北京邮电大学学报, 2022, 45(6): 53–59. doi: 10.13190/j.jbupt.2022-116 KONG Zixuan, LI Hang, XIANG Wan, et al. Multicast service chain deployment and adjustment method under user dynamic access[J]. Journal of Beijing University of Posts and Telecommunications, 2022, 45(6): 53–59. doi: 10.13190/j.jbupt.2022-116
[10]	WANG Xinhan, XING Huanlai, SONG Fuhong, et al. Dynamic multicast-oriented virtual network function placement with SFC request prediction[C]. 2022 14th International Conference on Communication Software and Networks (ICCSN), Chongqing, China, 2022: 81–88.
[11]	JIA Mike, LIANG Weifa, HUANG Meitian, et al. Routing cost minimization and throughput maximization of NFV-enabled unicasting in software-defined networks[J]. IEEE Transactions on Network and Service Management, 2018, 15(2): 732–745. doi: 10.1109/TNSM.2018.2810817
[12]	XU Zichuan, LIANG Weifa, HUANG Meitian, et al. Efficient NFV-enabled multicasting in SDNs[J]. IEEE Transactions on Communications, 2019, 67(3): 2052–2070. doi: 10.1109/TCOMM.2018.2881438
[13]	REN Bangbang, GUO Deke, SHEN Yulong, et al. Embedding service function tree with minimum cost for NFV-enabled multicast[J]. IEEE Journal on Selected Areas in Communications, 2019, 37(5): 1085–1097. doi: 10.1109/JSAC.2019.2906764
[14]	ASGARIAN M, MIRJALILY G, and LUO Zhiquan. Trade-off between efficiency and complexity in multi-stage embedding of multicast VNF service chains[J]. IEEE Communications Letters, 2022, 26(2): 429–433. doi: 10.1109/LCOMM.2021.3132134
[15]	REN Haozhe, XU Zichuan, LIANG Weifa, et al. Efficient algorithms for delay-aware NFV-enabled multicasting in mobile edge clouds with resource sharing[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(9): 2050–2066. doi: 10.1109/TPDS.2020.2983918
[16]	ALHUSSEIN O, DO P T, YE Qiang, et al. A virtual network customization framework for multicast services in NFV-enabled core networks[J]. IEEE Journal on Selected Areas in Communications, 2020, 38(6): 1025–1039. doi: 10.1109/JSAC.2020.2986591
[17]	REN Cheng, CHEN Xuxiang, XIANG Haiyun, et al. On efficient delay-aware multisource multicasting in NFV-Enabled softwarized networks[J]. IEEE Transactions on Network and Service Management, 2022, 19(3): 3371–3386. doi: 10.1109/TNSM.2022.3188777
[18]	LI Hang, WANG Luhan, ZHU Zhenghe, et al. Multicast service function chain orchestration in SDN/NFV-Enabled networks: Embedding, readjustment, and expanding[J]. IEEE Transactions on Network and Service Management, 2023.
[19]	MIRJALILY G, ASGARIAN M, and LUO Zhiquan. Interference-aware NFV-enabled multicast service in resource-constrained wireless mesh networks[J]. IEEE Transactions on Network and Service Management, 2022, 19(1): 424–436. doi: 10.1109/TNSM.2021.3083798
[20]	Python Community. Networkx 3.1[EB/OL]. https://pypi.org/project/networkx/, 2023.
[21]	Internet topology[EB/OL]. http://topology-zoo.org/maps/, 2022.
[22]	CHENG Yulun and YANG Longxiang. VNF deployment and routing for NFV-enabled multicast: A Steiner tree-based approach[C]. 2017 9th International Conference on Wireless Communications and Signal Processing (WCSP), Nanjing, China, 2017: 1–4.