物联网中虚拟网络功能转发图算法设计

doi:10.3778/j.issn.1673-9418.2407089

摘要/Abstract

摘要： 近年来，物联网的迅速发展和其终端数量的爆炸式增长对物联网网络服务提出了更高要求。结合网络功能虚拟化（NFV）和软件定义网络（SDN）技术，对新一代物联网服务功能虚拟化和软件化，可以将网络服务表示为虚拟网络功能转发图（VNF-FG）。现有的研究主要关注VNF-FG嵌入（VNF-FGE）问题，把VNF-FG作为确定输入，忽略了VNF-FG的设计问题；又或者在设计VNF部署算法时，没有充分利用VNF-FG的图结构，使算法有一定局限性。因此，研究VNF-FG有向无环图（DAG）设计问题。针对一组到达物联网终端的服务请求，设计约束，建立一个整数线性规划（ILP）模型生成最优无环VNF-FG；以最小化虚拟节点总数为目标，提出一种高效的虚拟网络功能转发无环图设计算法，充分利用已有虚拟节点，并找出导致成环的关键VNF实例，通过反向增扩恰当数量的关键VNF以消除VNF-FG中的环路，在保证无环和最小化虚拟节点数量之间进行折中。实验结果表明，该算法与ILP模型之间的差距很小；与其他已有算法相比，在不同SFC请求数量下，该算法生成的虚拟节点个数平均降低了17.67%。

关键词: 网络功能虚拟化, 物联网, 整数线性规划, 虚拟网络功能转发图

Abstract: In recent years, the rapid development of the Internet of things (IoT) and the explosive growth in the number of its terminals have imposed higher demands on IoT network services. Combined with network function virtualization (NFV) and software defined network (SDN) technology, the virtualization and softwarization of the new generation of IoT services can be represented as a virtual network function forwarding graph (VNF-FG). However, existing researches primarily focus on the VNF-FG embedding (VNF-FGE) problem, treating VNF-FG as a predetermined input and neglecting its design. Moreover, current VNF deployment algorithms often fail to fully leverage the graph structure of VNF-FG, resulting in certain limitations of these algorithms. To address these issues, this paper investigates the design of the VNF-FG directed acyclic graph (DAG). Given a set of service requests arriving at an IoT terminal, this paper first establishes constraints and formulates an integer linear programming (ILP) model to generate the optimal acyclic VNF-FG. Subsequently, this paper proposes a high-efficiency acyclic graph design algorithm that aims to minimize the total number of virtual nodes. This algorithm fully utilizes existing virtual nodes and identifies the key VNF instances that cause loops. By reversely expanding an appropriate number of key VNFs to eliminate loops in the VNF-FG, this paper achieves a balance between ensuring loop-free and minimizing the number of virtual nodes. Simulation results show that the difference between the proposed algorithm and the ILP model is minimal. Compared with other existing algorithms, the proposed method reduces the average number of virtual nodes generated by 17.67% for different service function chain (SFC) request quantities.

Key words: network function virtualization, Internet of things, integer linear programming, virtual network function forwarding graph

任诚, 刘静, 王宇, 李亚鑫, 李红伟. 物联网中虚拟网络功能转发图算法设计[J]. 计算机科学与探索, 2025, 19(6): 1632-1639.

REN Cheng, LIU Jing, WANG Yu, LI Yaxin, LI Hongwei. Virtual Network Function Forwarding Graph Design in IoT Networks[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(6): 1632-1639.

参考文献

[1] ZOURE M, AHMED T, RéVEILLèRE L. Network services anomalies in NFV: survey, taxonomy, and verification methods[J]. IEEE Transactions on Network and Service Management, 2022, 19(2): 1567-1584.
[2] ANEROUSIS N, CHEMOUIL P, LAZAR A A, et al. The origin and evolution of open programmable networks and SDN[J]. IEEE Communications Surveys & Tutorials, 2021, 23(3): 1956-1971.
[3] SHAHZADI S, AHMAD F, BASHARAT A, et al. Machine learning empowered security management and quality of service provision in SDN-NFV environment[J]. Computers, Materials & Continua, 2021, 66(3): 2723-2749.
[4] SCHARDONG F, NUNES I, SCHAEFFER-FILHO A. NFV resource allocation: a systematic review and taxonomy of VNF forwarding graph embedding[J]. Computer Networks, 2021, 185: 107726.
[5] SUBRAMANYA T, RIGGIO R. Centralized and federated learning for predictive VNF autoscaling in multi-domain 5G networks and beyond[J]. IEEE Transactions on Network and Service Management, 2021, 18(1): 63-78.
[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,27(6): 1-24.
[7] VARASTEH A, MADIWALAR B, VAN BEMTEN A, et al. Holu: power-aware and delay-constrained VNF placement and chaining[J]. IEEE Transactions on Network and Service Management, 2021, 18(2): 1524-1539.
[8] PULIAFITO C, MINGOZZI E, LONGO F, et al. Fog computing for the Internet of things[J]. ACM Transactions on Internet Technology, 2019, 19(2): 1-41.
[9] GASMI K, DILEK S, TOSUN S, et al. A survey on computation offloading and service placement in fog computing-based IoT[J]. The Journal of Supercomputing, 2022, 78(2): 1983-2014.
[10] XIE Y H, HUANG L, KONG Y Y, 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.
[11] REN C, LI H, LI Y X, et al. On efficient service function chaining in hybrid software defined networks[J]. IEEE Transactions on Network and Service Management, 2022, 19(2): 1614-1628.
[12] LIN R P, HE L, LUO S, et al. Energy-aware service function chaining embedding in NFV networks[J]. IEEE Transactions on Services Computing, 2023, 16(2): 1158-1171.
[13] LIU Y C, LU Y, LI X, et al. A Lagrangian-relaxation-based approach for service function chain dynamic orchestration for the Internet of things[J]. IEEE Internet of Things Journal, 2021, 8(23): 17071-17089.
[14] LIU Y C, LU Y, QIAO W X, et al. Reliability-aware service chaining mapping in NFV-enabled networks[J]. ETRI Journal, 2019, 41(2): 207-223.
[15] LIU Y C, LU H, LI X, et al. An approach for service function chain reconfiguration in network function virtualization architectures[J]. IEEE Access, 2019, 7: 147224-147237.
[16] LIU Y C, LU H, LI X, et al. Dynamic service function chain orchestration for NFV/MEC-enabled IoT networks: a deep reinforcement learning approach[J]. IEEE Internet of Things Journal, 2021, 8(9): 7450-7465.
[17] LIU Y C, LU Y, LI X, et al. SFC embedding meets machine learning: deep reinforcement learning approaches[J]. IEEE Communications Letters, 2021, 25(6): 1926-1930.
[18] ZHANG J N, LIU Y C, LI Z W, et al. Forecast-assisted service function chain dynamic deployment for SDN/NFV-enabled cloud management systems[J]. IEEE Systems Journal, 2023, 17(3): 4371-4382.
[19] ZHAO D H, LU Y, LI X W, et al. Cross-domain service function chain routing: multiagent reinforcement learning approaches[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2022, 69(12): 4754-4758.
[20] CHEN H D, WANG S P, LI G J, et al. Distributed orchestration of service function chains for edge intelligence in the industrial Internet of things[J]. IEEE Transactions on Industrial Informatics, 2022, 18(9): 6244-6254.
[21] GHAZNAVI M, SHAHRIAR N, KAMALI S, et al. Distributed service function chaining[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(11): 2479-2489.
[22] DIEYE M, JAAFAR W, ELBIAZE H, et al. Market driven multidomain network service orchestration in 5G networks[J]. IEEE Journal on Selected Areas in Communications, 2020, 38(7): 1417-1431.
[23] 周廷枢. 虚拟网络功能转发图设计及映射研究[D]. 成都: 电子科技大学, 2018.
ZHOU T S. Research on design and embedding of virtualized network function forwarding graph[D].Chengdu: University of Electronic Science and Technology of China, 2018.
[24] CAO J Y, ZHANG Y, AN W, et al. VNF-FG design and VNF placement for 5G mobile networks[J]. Science China Information Sciences, 2017, 60(4): 040302.
[25] HOUIDI O, SOUALAH O, LOUATI W, et al. Dynamic VNF forwarding graph extension algorithms[J]. IEEE Tran-sactions on Network and Service Management, 2020, 17(3): 1389-1402.
[26] SAHRAOUI R, HOUIDI O, BANNOUR F. Energy-aware VNF-FG placement with transformer-based deep reinforcement learning[C]//Proceedings of the 2024 IEEE Network Operations and Management Symposium. Piscataway: IEEE, 2024: 1-9.