近年來有許多深度強化學習及圖神經網路應用在路由最佳化的研究，但其中有研究認為單憑深度強化學習代理並不足以達到最佳化，還需要配合啟發式演算法才有機會找到最佳解。因此提出了 ENERO，一種結合深度強化學習、圖神經網路及局部搜索演算法的架構，但即使這樣還是無法達到最佳解。我們認為 ENERO 還有很多可以改進的空間。在本文中，我們針對三個方向提出了改善方案，深度強化學習演算法使用 Soft Actor Critic 希望增加系統的容錯度，引入 RouteNet 的圖神經網路架構加強模型的路徑選擇及泛化能力，最後使用 K-path 作為候選路來確保路徑的合理性。在實驗中我們比較了三個改善方向各自帶來的實際好處，並與 ENERO 做比較。最後結果表明，經過改善以後，我們的方法優於 ENERO，可以更有效的降低最大鏈路利用率，在部分情況中，我們的 DRL agent 不需要 LS 輔助就可以有與 ENERO 相等甚至更好的效能。

In recent years, numerous studies have been conducted on the application of Deep Reinforcement Learning (DRL) and Graph Neural Networks (GNNs) in routing optimization. However, some suggest that sole reliance on a DRL agent is not enough to achieve optimal results. It is believed that a combination with heuristic algorithms is necessary to have a chance of finding the optimal solution. This led to the proposal of ENERO, a framework combining DRL, GNNs, and local search algorithms. Nevertheless, it does not always produce the desired optimal solutions, indicating significant room for improvement in ENERO. In this paper, we propose enhancements in three main areas. First, we incorporate the Soft Actor Critic into the DRL algorithm, aiming to augment the system's fault tolerance. Second, we introduce the RouteNet GNN architecture to bolster the model's path selection capabilities and generalizability. Lastly, we employ K-path as a candidate path to ensure the rationality of the chosen path. Through our experiments, we evaluated the tangible benefits delivered by each of these three enhancements, contrasting them with the existing ENERO framework. Our results reveal that, after improvements, our approach outperforms ENERO, effectively reducing maximum link utilization. Interestingly, under certain circumstances, our DRL agent can achieve equal, if not superior, performance to ENERO without the need for local search assistance.

[1] Ning Wang, Kin Hon Ho, George Pavlou and Michael Howarth, “An overview of routing optimization for internet traffic engineering”, IEEE Communications Surveys & Tutorials, vol. 10, no. 1, pp. 36-56, 2008.
[2] Ian F. Akyildiz, Ahyoung Lee, Pu Wang, Min Luo and Wu Chou, “A roadmap for traffic engineering in SDN-OpenFlow networks”, Computer Networks, vol. 71, pp. 1-30, 2014.
[3] Sugam Agarwal, Murali Kodialam and T. V. Lakshman, “Traffic Engineering in Software Defined Networks”, 2013 Proceedings IEEE INFOCOM, pp. 2211-2219, 2013.
[4] Daniela M. Casas-Velasco, Oscar Mauricio Caicedo Rendon and Nelson L. S. da Fonseca, “Intelligent Routing Based on Reinforcement Learning for Software-Defined Networking”, IEEE Transactions on Network and Service Management, vol. 18, no. 1, pp. 870-881, 2020.
[5] Yang Xiao, Jun Liu, Jiawei Wu and Nirwan Ansari, “Leveraging Deep Reinforcement Learning for Traffic Engineering: A Survey”, IEEE Communications Surveys & Tutorials, vol. 23, no. 4, pp. 2064-2097, 2021.
[6] Daniela M. Casas-Velasco, Oscar Mauricio Caicedo Rendon and Nelson L. S. da Fonseca, “DRSIR: A Deep Reinforcement Learning Approach for Routing in Software-Defined Networking”, IEEE Transactions on Network and Service Management, 2021.
[7] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li and Maosong Sun, “Graph neural networks: A review of methods and applications”, AI open, vol. 1, pp. 57-81, 2020.
[8] Krzysztof Rusek, José Suárez-Varela, Paul Almasan, Pere Barlet-Ros and Albert Cabellos-Aparicio, “RouteNet: Leveraging Graph Neural Networks for Network Modeling and Optimization in SDN”, IEEE Journal on Selected Areas in Communications, vol. 38, no. 10, pp. 2260-2270, 2020.
[9] Paul Almasan, José Suárez-Varela, Krzysztof Rusek, Pere Barlet-Ros and Albert Cabellos-Aparicio, “Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case”, Computer Communications, vol. 196, pp. 184-194, 2022.
[10] Xiangyu Zheng, Wanwei Huang, Hui Li and Guangyuan Li, “Research on Generalized Intelligent Routing Technology Based on Graph Neural Network”, Electronics, vol. 11, no. 18, pp. 2952, 2022.
[11] Paul Almasan, Shihan Xiao, Xiangle Cheng, Xiang Shi, Pere Barlet-Ros and Albert Cabellos-Aparicio, “ENERO: Efficient real-time WAN routing optimization with Deep Reinforcement Learning”, Computer Networks, vol 214, pp. 109166, 2022.
[12] Bo Chen, Di Zhu, Yuwei Wang and Peng Zhang, “An Approach to Combine the Power of Deep Reinforcement Learning with a Graph Neural Network for Routing Optimization”, Electronics, vol. 11, no. 3, pp. 368, 2022.
[13] Mohammad M. Tajiki, Mohammad Shojafar, Behzad Akbari, Stefano Salsano, Mauro Conti and Mukesh Singhal, “Joint failure recovery, fault prevention, and energy-efficient resource management for real-time SFC in fog-supported SDN”, Computer Networks, vol. 162, pp. 106850, 2019.
[14] Min Yee Teh, Shizhen Zhao, Peirui Cao and Keren Bergman, “Enabling Quasi-Static Reconfigurable Networks With Robust Topology Engineering”, IEEE/ACM Transactions on Networking, vol. 31, no. 3, pp. 1056-1070, 2023.
[15] Zeyu Qin, Haipeng Yao and Tianle Mai, “Traffic Optimization in Satellites Communications: A Multi-agent Reinforcement Learning Approach”, 2020 International Wireless Communications and Mobile Computing (IWCMC), pp. 269-273, 2020.
[16] Bruno Astuto A. Nunes, Marc Mendonca, Xuan-Nam Nguyen, Katia Obraczka and Thierry Turletti, “A survey of software-defined networking: Past, present, and future of programmable networks”, IEEE Communications surveys & tutorials, vol. 16, no. 3, pp. 1617-1634, 2014.
[17] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals and George E. Dahl, “Neural Message Passing for Quantum Chemistry”, International conference on machine learning, pp. 1263-1272, 2017.
[18] Junjie Zhang, Minghao Ye, Zehua Guo, Chen-Yu Yen and H. Jonathan Chao, “CFR-RL: Traffic Engineering With Reinforcement Learning in SDN”, IEEE Journal on Selected Areas in Communications, vol. 38, no. 10, pp. 2249-2259, 2020.
[19] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford and Oleg Klimov, “Proximal Policy Optimization Algorithms”, arXiv preprint arXiv:1707.06347, 2017.
[20] Randeep Bhatia, Fang Hao, Murali Kodialam and T.V. Lakshman, “Optimized network traffic engineering using segment routing”, 2015 IEEE Conference on Computer Communications (INFOCOM), pp. 657-665, 2015.
[21] Binghao Yan, Qinrang Liu, JianLiang Shen and Dong Liang, “Flowlet-level multipath routing based on graph neural network in OpenFlow-based SDN”, Future Generation Computer Systems, vol. 134, pp. 140-153, 2022.
[22] Ting Zhu, Xiaohui Chen, Li Chen, Weidong Wang and Guo Wei, “GCLR: GNN-Based Cross Layer Optimization for Multipath TCP by Routing”, IEEE Access, vol. 8, pp. 17060-17070, 2020.
[23] Yangzhe Kong, Dmitry Petrov, Vilho Räisänen and Alexander Ilin, “Path-Link Graph Neural Network for IP Network Performance Prediction”, 2021 IFIP/IEEE International Symposium on Integrated Network Management (IM), pp. 170-177, 2021.
[24] Mahnoor Yaqoob, Ramona Trestian and Huan X. Nguyen, “Data-Driven Network Performance Prediction for B5G Networks: A Graph Neural Network Approach”, 2022 IEEE Ninth International Conference on Communications and Electronics (ICCE), pp.55-60, 2022.
[25] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel and Sergey Levine, “Soft Actor-Critic Algorithms and Applications”, arXiv preprint arXiv:1812.05905, 2018.
[26] Petros Christodoulou, “Soft Actor-Critic for Discrete Action Settings”, arXiv preprint arXiv:1910.07207, 2019.
[27] Aric Hagberg, Pieter Swart and Daniel S. Chult, “Exploring network structure, dynamics, and function using NetworkX”, Proceedings of the 7th Python in Science Conference, pp. 11-15, 2008
[28] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai and Soumith Chintala, “Pytorch: An imperative style, high-performance deep learning library”, Advances in neural information processing systems, vol. 32, 2019.
[29] Ilya Loshchilov and Frank Hutter, “Decoupled Weight Decay Regularization”, ICLR, 2019.
[30] Renaud Hartert, Stefano Vissicchio, Pierre Schaus, Olivier Bonaventure, Clarence Filsfils, Thomas Telkamp and Pierre Francois, “A Declarative and Expressive Approach to Control Forwarding Paths in Carrier-Grade Networks”, ACM SIGCOMM computer communication review, vol. 45, no. 4, pp. 15-28, 2015.
[31] Simon Knight, Hung X. Nguyen, Nickolas Falkner, Rhys Bowden and Matthew Roughan, “The Internet Topology Zoo”, IEEE Journal on Selected Areas in Communications, vol. 29, no. 9, pp. 1765-1775, 2011.
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser and Illia Polosukhin, “Attention Is All You Need”, Advances in neural information processing systems, vol. 30, 2017.
[33] Yi-Ren Chen, Amir Rezapour, Wen-Guey Tzeng and Shi-Chun Tsai, “RL-Routing: An SDN Routing Algorithm Based on Deep Reinforcement Learning”, IEEE Transactions on Network Science and Engineering, vol. 7, no. 4, pp. 3185-3199, 2020.
[34] Bob Lantz, Brandon Heller and Nick McKeown, “A Network in a Laptop: Rapid Prototyping for Software-Defined Networks”, Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks, pp. 1-6, 2010.
[35] András Varga and Rudolf Hornig, “An overview of the omnet++ simulation environment”, 1st International ICST Conference on Simulation Tools and Techniques for Communications, Networks and Systems, 2010.