基于多目标优化的可靠网络切片配置算法研究

网络切片指的是将同一物理网络资源划分至多个虚拟网络，这些虚拟网络也称为网络切片。作为5G网络和即将到来的 6G 网络中不可或缺的一种技术手段，网络切片技术为自动驾驶、远程医疗、虚拟现实及增强现实等应用场景提供了高可靠、低时延、大带宽等专用需求。网络切片领域现有的研究热点包括网络切片的嵌入和重配置问题。其中，网络切片的嵌入是基础，是保障切片正常工作前最关键的一步，近年来网络切片嵌入问题受到了广泛关注和研究。然而，现有的研究工作主要集中在网络切片的利润最大化或成本最小化中，网络可靠性的提升经常被忽视。因此，本文重点研究了网络切片嵌入中的利润与可靠性同时优化的问 题，通过问题定义和优化算法的设计，最大化利润的同时提升网络嵌入的可靠性，为网络切片嵌入提供多样化的选择，以应对不同网络场景的需求。本文将网络切片嵌入建模为多目标优化问题，最大化网络切片的利润和可靠性。为此，本文提出了一个新的多目标优化算法 RNSMOEA，充分利用了多目标优化算法 C-TAEA 的优势，解决了其在网络切片增多时性能表现不佳的问题。为验证算法在同时优化利润和可靠性方面的有效性，本研究在传统规模网络切片上进 行了广泛测试，使用真实和模拟生成的物理网络，并采用多目标优化领域广泛使 用的评估指标 HV（Hypervolume）对比不同算法表现。结果表明，RNSMOEA分别在4个和 11个测试实例上优于 C-TAEA 和 NSGA-II，在当前多目标优化算法中表现最好。为了进一步验证该方案的有效性，本文对比了几种经典的单目标优化算法，结果表明采用多目标优化算法在利润和可靠性方面均优于单目标优化算法。在传统规模网络切片中，RNSMOEA 提供了多种最优利润和可靠性的嵌入方案。 由于未来网络服务需求更广泛，对网络切片规模提出了更高要求。然而，RNSMOEA 在大规模网络切片实例上性能不佳且可靠性评估时间过长。因此，本文设计了一种面向大规模网络切片嵌入问题的多目标优化算法 RNSMOEA-LS。通过对 10 种不同模拟生成网络实例的对比实验，结果显示 RNSMOEA-LS 在 9 种不同实例上优于 RNSMOEA，为解决大规模网络切片嵌入问题提供了新方法。 综上，本研究对网络切片的建模和算法设计研究工作提供了理论和方法支持，有助于推动网络切片技术在实际场景中得到更广泛的应用和发展。

Network slicing involves dividing the same physical network resources into multiple virtual networks, also known as network slices. As an essential technology in 5G and upcoming 6G networks, network slicing provides specialized requirements such as high reliability, low latency, and high bandwidth for applications like autonomous driving, remote healthcare, virtual reality, and augmented reality. Network slicing focuses on embedding and reconfiguration problems. Embedding network slices is foundational and critical for ensuring their regular operation, and there has been extensive research on this topic in recent years. However, existing research prioritizes profit maximization or cost minimization in network slicing, often overlooking enhancing network reliability. Therefore, this thesis focuses on simultaneously optimizing profit and reliability in network slice embedding. Through problem definition and optimization algorithm design, we aim to maximize profit while improving the reliability of network embedding. This approach provides diverse options for network slice embedding to meet the requirements of various network scenarios. In this thesis, network slice embedding is formulated as a multi-objective optimization problem to maximize the profit and reliability of network slice. A novel multi-objective optimization algorithm named RNSMOEA is proposed to solve the problem. Leveraging the advantages of the two-archive multi-objective optimization algorithm C-TAEA, RNSMOEA overcomes its performance limitations when dealing with increasing network slices. Extensive testing uses real-world and simulated network topologies to validate the algorithm’s effectiveness in optimizing profitability and reliability. The performance of different multi-objective optimization algorithms is compared using the widely-used evaluation metric HV (Hypervolume). The results demonstrate that RNSMOEA outperforms C-TAEA in 4 instances and NSGA-II in 11 instances. Furthermore, several classical single-objective optimization algorithms are compared to validate the proposed approach’s effectiveness further. The results indicate that multi-objective optimization algorithms outperform these single-objective optimization algorithms in both profit and reliability. The RNSMOEA provides multiple optimal embedding solutions for conventional-scale network slices. Due to the broader future network service demands, higher requirements are posed on the scale of network slice. However, RNSMOEA exhibits poor performance and reliability assessment times on large-scale network slicing instances. Therefore, this thesis designs a multi-objective optimization algorithm, RNSMOEA-LS, tailored for large-scale network slice embedding problems. Comparative experiments on 10 different simulated network instances demonstrate that RNSMOEA-LS outperforms RNSMOEA in 9 instances, offering a new approach to address large-scale network slice embedding problems. In summary, this thesis provides theoretical and methodological support for the modeling and algorithmic design research of network slicing, contributing to the broader application and development of network slicing technology in practical scenarios.

[1] MOBILE, RADIODETERMINATION, AMATEUR, et al. IMT Vision–Framework and overall objectives of the future development of IMT for 2020 and beyond[M]. Electronic Publication Geneva, Switzerland, 2015.
[2] NIGHTINGALE J, SALVA-GARCIA P, CALERO J M A, et al. 5G-QoE: QoE modelling for ultra-HD video streaming in 5G networks[J]. IEEE Transactions on Broadcasting, 2018, 64(2): 621-634.
[3] EROL-KANTARCI M, SUKHMANI S. Caching and computing at the edge for mobile augmented reality and virtual reality (AR/VR) in 5G[C]//2017 9th International Conference (AdHocNets). Niagara Falls, ON, Canada. Springer, 2018: 169-177.
[4] TANGE K, DE DONNO M, FAFOUTIS X, et al. A systematic survey of industrial Internet of Things security: Requirements and fog computing opportunities[J]. IEEE Communications Surveys & Tutorials, 2020, 22(4): 2489-2520.
[5] SERROR M, HACK S, HENZE M, et al. Challenges and opportunities in securing the industrial internet of things[J]. IEEE Transactions on Industrial Informatics, 2020, 17(5): 2985-2996.
[6] KHAN W Z, REHMAN M, ZANGOTI H M, et al. Industrial internet of things: Recent advances, enabling technologies and open challenges[J]. Computers & electrical engineering, 2020, 81: 106522.
[7] XU H, YU W, GRIFFITH D, et al. A survey on industrial Internet of Things: A cyber-physical systems perspective[J]. IEEE Access, 2018, 6: 78238-78259.
[8] 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.
[9] BARAKABITZE A A, AHMAD A, MIJUMBI R, et al. 5G network slicing using SDN and NFV: A survey of taxonomy, architectures and future challenges[J]. Computer Networks, 2020, 167: 106984.
[10] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Network function virtualization: State-of-the-art and research challenges[J]. IEEE Communications surveys & tutorials, 2015, 18(1): 236-262.
[11] NGMN ALLIANCE. Description of network slicing concept[EB/OL]. (2016-01-13)
[2024-03-29]. https://ngmn.org/wp-content/uploads/160113_NGMN_Network_Slicing_v1_0.pdf.
[12] TANG L, ZHAO G, WANG C, et al. Queue-aware reliable embedding algorithm for 5G network slicing[J]. Computer Networks, 2018, 146: 138-150.
[13] GUERZONI R, DESPOTOVIC Z, TRIVISONNO R, et al. Modeling reliability requirements in coordinated node and link mapping[C]//2014 33rd International Symposium on Reliable Distributed Systems (SRDS). Nara, Japan. IEEE, 2014: 321-330.
[14] CHANTRE H D, DA FONSECA N L. Multi-objective optimization for edge device placement and reliable broadcasting in 5G NFV-based small cell networks[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(10): 2304-2317.
[15] AFOLABI I, TALEB T, SAMDANIS K, et al. Network slicing and softwarization: A survey on principles, enabling technologies, and solutions[J]. IEEE Communications Surveys & Tutorials, 2018, 20(3): 2429-2453.
[16] CHAI R, XIE D, LUO L, et al. Multi-objective optimization-based virtual network embed ding algorithm for software-defined networking[J]. IEEE Transactions on Network and Service Management, 2019, 17(1): 532-546.
[17] NGMN ALLIANCE. 5G white paper[EB/OL]. (2015-02-17)
[2024-03-29]. https://ngmn.org /wp-content/uploads/NGMN_5G_White_Paper_V1_0.pdf.
[18] 3GPP. Study on management and orchestration of network slicing for next generation network [M]. 3rd Generation Partnership Project (3GPP). Valbonne, France, 2017.
[19] BÄCK T, SCHWEFEL H P. An overview of evolutionary algorithms for parameter optimization [J]. Evolutionary computation, 1993, 1(1): 1-23.
[20] MITCHELL M. An introduction to genetic algorithms[M]. MIT press, 1998.
[21] KENNEDY J, EBERHART R. Particle swarm optimization[C]//1995 Proceedings of ICNN’95- international conference on neural networks (ICNN). Perth, WA, Australia. IEEE, 1995: 1942- 1948.
[22] STORN R, PRICE K. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11: 341-359.
[23] LAUMANNS M, ZITZLER E, THIELE L. A unified model for multi-objective evolutionary algorithms with elitism[C]//Proceedings of the 2000 Congress on Evolutionary Computation (CEC). La Jolla, CA, USA. IEEE, 2000: 46-53.
[24] DEB K. Multi-objective optimisation using evolutionary algorithms: an introduction[M]// Multi-objective Evolutionary Optimisation for Product Design and Manufacturing. Springer, 2011: 3-34.
[25] LI K, CHEN R, FU G, et al. Two-archive evolutionary algorithm for constrained multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(2): 303-315.
[26] LAUMANNS M, THIELE L, ZITZLER E. An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method[J]. European Journal of Operational Research, 2006, 169(3): 932-942.
[27] MIETTINEN K. Nonlinear multiobjective optimization[M]. Springer Science & Business Media, 1999.
[28] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[29] ZHANG Q, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition [J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.
[30] LI B, TANG K, LI J, et al. Stochastic ranking algorithm for many-objective optimization based on multiple indicators[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(6): 924- 938.
[31] MEI C, LIU J, LI J, et al. 5G network slices embedding with sharable virtual network functions [J]. Journal of Communications and Networks, 2020, 22(5): 415-427.
[32] LI H, KONG Z, CHEN Y, et al. Slice-Based Service Function Chain Embedding for End-to-End Network Slice Deployment[J]. IEEE Transactions on Network and Service Management, 2023, 20(3): 3652-3672.
[33] ESTEVES J J A, BOUBENDIR A, GUILLEMIN F, et al. A heuristically assisted deep reinforcement learning approach for network slice placement[J]. IEEE Transactions on Network and Service Management, 2021, 19(4): 4794-4806.
[34] YUSUPOV J, KSENTINI A, MARCHETTO G, et al. Multi-objective function splitting and placement of network slices in 5G mobile networks[C]//2018 IEEE Conference on Standards for Communications and Networking (CSCN). Paris, France. IEEE, 2018: 1-6.
[35] GONG L, WEN Y, ZHU Z, et al. Toward profit-seeking virtual network embedding algorithm via global resource capacity[C]//2014 IEEE Conference on Computer Communications (INFO COM). Toronto, Canada. IEEE, 2014: 1-9.
[36] YAN Z, GE J, WU Y, et al. Automatic virtual network embedding: A deep reinforcement learning approach with graph convolutional networks[J]. IEEE Journal on Selected Areas in Communications, 2020, 38(6): 1040-1057.
[37] WEI F, FENG G, SUN Y, et al. Network slice reconfiguration by exploiting deep reinforcement learning with large action space[J]. IEEE Transactions on Network and Service Management, 2020, 17(4): 2197-2211.
[38] WANG G, FENG G, QUEK T Q, et al. Reconfiguration in network slicing—Optimizing the profit and performance[J]. IEEE Transactions on Network and Service Management, 2019, 16 (2): 591-605.
[39] LIU Q, CHOI N, HAN T. Atlas: automate online service configuration in network slicing[C]// 2022 Proceedings of the 18th International Conference on emerging Networking Experiments and Technologies (CoNEXT). Roma, Italy. ACM, 2022: 140-155.
[40] CHOWDHURY M, RAHMAN M R, BOUTABA R. ViNEYard: Virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE/ACM Transactions on Networking, 2011, 20(1): 206-219.
[41] BENKACEM I, TALEB T, BAGAA M, et al. Optimal VNFs placement in CDN slicing over multi-cloud environment[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(3): 616-627.
[42] LANGE S, GRIGORJEW A, ZINNER T, et al. A multi-objective heuristic for the optimization of virtual network function chain placement[C]//2017 29th International Teletraffic Congress (ITC). Genoa, Italy. IEEE, 2017: 152-160.
[43] WOLSEY L A. Integer programming[M]. John Wiley & Sons, 2020.
[44] FISCHER A, BOTERO J F, BECK M T, et al. Virtual network embedding: A survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(4): 1888-1906.
[45] HAERI S, TRAJKOVIĆ L. Virtual network embedding via Monte Carlo tree search[J]. IEEE transactions on cybernetics, 2017, 48(2): 510-521.
[46] LIU Q, CHOI N, HAN T. OnSlicing: online end-to-end network slicing with reinforcement learning[C]//2021 Proceedings of the 17th International Conference on emerging Networking Experiments and Technologies (CoNEXT). Virtual Event, Munich, Germany. ACM, 2021: 141- 153.
[47] WAXMAN B M. Routing of multipoint connections[J]. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617-1622.
[48] LI J, ZHANG X. Deep reinforcement learning-based joint scheduling of eMBB and URLLC in 5G networks[J]. IEEE Wireless Communications Letters, 2020, 9(9): 1543-1546.
[49] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: Substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38 (2): 17-29.
[50] WANG G, FENG G, TAN W, et al. Resource allocation for network slices in 5G with network resource pricing[C]//2017 IEEE Global Communications Conference (GLOBECOM). Singa pore. IEEE, 2017: 1-6.
[51] DOLATI M, HASSANPOUR S B, GHADERI M, et al. DeepViNE: Virtual network embedding with deep reinforcement learning[C]//2019 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). Paris, France. IEEE, 2019: 879-885.
[52] WEN R, FENG G, TANG J, et al. On robustness of network slicing for next-generation mobile networks[J]. IEEE Transactions on Communications, 2018, 67(1): 430-444.
[53] MLADENOVIĆ N, HANSEN P. Variable neighborhood search[J]. Computers & operations research, 1997, 24(11): 1097-1100.
[54] ESTEVES J J A, BOUBENDIR A, GUILLEMIN F, et al. Heuristic for edge-enabled network slicing optimization using the “power of two choices”[C]//2020 16th International Conference on Network and Service Management (CNSM). Izmir, Turkey. IEEE, 2020: 1-9.
[55] MITZENMACHER M. The power of two choices in randomized load balancing[J]. IEEE Transactions on Parallel and Distributed Systems, 2001, 12(10): 1094-1104.
[56] ESTEVES J J A, BOUBENDIR A, GUILLEMIN F, et al. Location-based data model for optimized network slice placement[C]//2020 6th IEEE Conference on Network Softwarization (NetSoft). Ghent, Belgium. IEEE, 2020: 404-412.
[57] CHANTRE H D, DA FONSECA N L S. The location problem for the provisioning of protected slices in NFV-based MEC infrastructure[J]. IEEE Journal on Selected Areas in Communications, 2020, 38(7): 1505-1514.
[58] SIERRA M R, COELLO COELLO C A. Improving PSO-based multi-objective optimization using crowding, mutation and 𝜖-dominance[C]//2005 International conference on evolutionary multi-criterion optimization (EMO). Guanajuato, Mexico. Springer, 2005: 505-519.
[59] ABUSUBAIH M. Intelligent wireless networks: challenges and future research topics[J]. Journal of Network and Systems Management, 2022, 30(1): 18.
[60] ABOOD M S, WANG H, HE D, et al. Intelligent network slicing in V2X networks–A comprehensive review[J]. Journal of Artificial Intelligence and Technology, 2023, 3(2): 75-84.
[61] KUO S Y, YEH F M, LIN H Y. Efficient and exact reliability evaluation for networks with imperfect vertices[J]. IEEE Transactions on Reliability, 2007, 56(2): 288-300.
[62] BRYANT R E. Graph-based algorithms for boolean function manipulation[J]. IEEE Transactions on Computers, 1986, 100(8): 677-691.
[63] LI K, DEB K, ZHANG Q, et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J]. IEEE Transactions on Evolutionary Computation, 2014, 19(5): 694-716.
[64] WANG H, JIAO L, YAO X. Two_Arch2: An improved two-archive algorithm for many objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 19(4): 524- 541.
[65] ORLOWSKI S, WESSÄLY R, PIÓRO M, et al. SNDlib 1.0—Survivable network design library [J]. Networks: An International Journal, 2010, 55(3): 276-286.
[66] Blank J, Deb K. Pymoo: Multi-Objective Optimization in Python[J]. IEEE Access, 2020, 8: 89497-89509.
[67] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271.
[68] WIJETHILAKA S, LIYANAGE M. Survey on network slicing for Internet of Things realization in 5G networks[J]. IEEE Communications Surveys & Tutorials, 2021, 23(2): 957-994.
[69] JI L, HE S, WU W, et al. Dynamic network slicing orchestration for remote adaptation and configuration in industrial IoT[J]. IEEE Transactions on Industrial Informatics, 2021, 18(6): 4297-4307.
[70] SKONDRAS E, MICHALAS A, VERGADOS D J, et al. Network slicing on 5G vehicular cloud computing systems[J]. Electronics, 2021, 10(12): 1474.
[71] BAI G, LIU T, ZHANG Y A, et al. An improved method for reliability evaluation of two terminal multistate networks based on state space decomposition[J]. IEEE Transactions on reliability, 2020, 70(3): 1084-1095.
[72] FRIEDMAN S J, SUPOWIT K J. Finding the optimal variable ordering for binary decision diagrams[C]//1987 Proceedings of the 24th Design Automation Conference (DAC). Miami Beach, FL, USA. ACM, 1987: 348-356.
[73] GAREY M R, JOHNSON D S. Computers and intractability: A Guide to the Theory of NP Completeness[M]. W. H. FREEMAN AND COMPANY, 1979.
[74] SAHINOGLU M, RAMAMOORTHY C, SMITH A E, et al. A reliability block diagramming tool to describe networks[C]//2004 Annual Symposium Reliability and Maintainability (RAMS). Los Angeles, CA, USA. IEEE, 2004: 141-145.
[75] SHARAFAT A R, MA’ROUZI O R. All-terminal network reliability using recursive truncation algorithm[J]. IEEE Transactions on Reliability, 2009, 58(2): 338-347.
[76] TRIVEDI K S, BOBBIO A. Reliability and availability engineering: modeling, analysis, and applications[M]. Cambridge University Press, 2017.
[77] ZHAI E, CHEN A, PISKAC R, et al. Check before you change: Preventing correlated failures in service updates[C]//2020 17th Symposium on Networked Systems Design and Implementation (NSDI). Boston, MA, USA. USENIX, 2020: 575-589.
[78] ECHARD B, GAYTON N, LEMAIRE M. AK-MCS: an active learning reliability method combining Kriging and Monte Carlo simulation[J]. Structural Safety, 2011, 33(2): 145-154.
[79] SYSWERDA G, et al. Uniform crossover in genetic algorithms.[C]//1989 3rd International Conference on Genetic Algorithms (ICGA). East Lansing, MI, USA. Morgan Kaufmann, 1989: 2-9.
[80] POZZA M, NICHOLSON P K, LUGONES D F, et al. On reconfiguring 5G network slices[J]. IEEE Journal on Selected Areas in Communications, 2020, 38(7): 1542-1554.