research-article

GROM: : A generalized routing optimization method with graph neural network and deep reinforcement learning

Authors:

Huan LuoAuthors Info & Claims

Volume 229, Issue C

https://doi.org/10.1016/j.jnca.2024.103927

Published: 19 September 2024 Publication History

Abstract

Routing optimization, as a significant part of Traffic Engineering (TE), plays an important role in balancing network traffic and improving quality of service. With the application of Machine Learning (ML) in various fields, many neural network-based routing optimization solutions have been proposed. However, most existing ML-based methods need to retrain the model when confronted with a network unseen during training, which incurs significant time overhead and response delay. To improve the generalization ability of the routing model, in this paper, we innovatively propose a routing optimization method GROM which combines Deep Reinforcement Learning (DRL) and Graph Neural Networks (GNN), to directly generate routing policies under different and unseen network topologies without retraining. Specifically, for handling different network topologies, we transform the traffic-splitting ratio into element-level output of GNN model. To make the DRL agent easier to converge and well generalize to unseen topologies, we discretize the huge continuous traffic-splitting action space. Extensive simulation results on five real-world network topologies demonstrate that GROM can rapidly generate routing policies under different network topologies and has superior generalization ability.

References

[1]

Agarwal S., Kodialam M., Lakshman T.V., Traffic engineering in software defined networks, in: 2013 Proceedings IEEE INFOCOM, 2013, pp. 2211–2219,.

[2]

Azzouni A., Pujolle G., Neutm: A neural network-based framework for traffic matrix prediction in SDN, in: NOMS 2018 - 2018 IEEE/IFIP Network Operations and Management Symposium, 2018, pp. 1–5,.

Digital Library

[3]

Balon S., Monfort G., The traffic matrices and topology of the abilene network, 2019.

[4]

Barreto F., Wille E.C., Nacamura Jr. L., Fast emergency paths schema to overcome transient link failures in ospf routing, 2012, arXiv preprint arXiv:1204.2465.

[5]

Bernárdez, G., Suárez-Varela, J., López, A., Wu, B., Xiao, S., Cheng, X., Barlet-Ros, P., Cabellos-Aparicio, A., 2021. Is Machine Learning Ready for Traffic Engineering Optimization?. In: 2021 IEEE 29th International Conference on Network Protocols. ICNP, pp. 1–11.

[6]

Chu J., Lea C.-T., Optimal link weights for IP-based networks supporting hose-model VPNs, IEEE/ACM Trans. Netw. 17 (3) (2009) 778–788,.

Digital Library

[7]

Dadashi, R., Hussenot, L., Vincent, D., Girgin, S., Raichuk, A., Geist, M., Pietquin, O., 2022. Continuous Control with Action Quantization from Demonstrations. In: Proceedings of the 39th International Conference on Machine Learning. Vol. 162, pp. 4537–4557.

[8]

Engstrom L., Ilyas A., Santurkar S., Tsipras D., Janoos F., Rudolph L., Madry A., Implementation matters in deep policy gradients: A case study on PPO and TRPO, 2020, arXiv:2005.12729.

[9]

Ferriol-Galmés M., Paillisse J., Suárez-Varela J., Rusek K., Xiao S., Shi X., Cheng X., Barlet-Ros P., Cabellos-Aparicio A., RouteNet-Fermi: Network modeling with graph neural networks, IEEE/ACM Trans. Netw. (2023) 3080–3095,.

Digital Library

[10]

Fortz B., Thorup M., Internet traffic engineering by optimizing OSPF weights, in: Proceedings IEEE INFOCOM, Vol. 2, 2000, pp. 519–528,.

[11]

Freeman L.C., Borgatti S.P., White D.R., Centrality in valued graphs: A measure of betweenness based on network flow, Soc. Netw. 13 (2) (1991) 141–154.

[12]

Gao K., Li D., Chen L., Geng J., Gui F., Cheng Y., Gu Y., Incorporating intra-flow dependencies and inter-flow correlations for traffic matrix prediction, in: 2020 IEEE/ACM 28th International Symposium on Quality of Service, IWQoS, 2020, pp. 1–10,.

[13]

Geyer, F., Carle, G., 2018. Learning and generating distributed routing protocols using graph-based deep learning. In: Proceedings of the 2018 Workshop on Big Data Analytics and Machine Learning for Data Communication Networks. pp. 40–45.

[14]

Gilmer J., Schoenholz S.S., Riley P.F., Vinyals O., Dahl G.E., Neural message passing for quantum chemistry, in: Proceedings of the 34th International Conference on Machine Learning, Vol. 70, PMLR, 2017, pp. 1263–1272.

[15]

Gori M., Monfardini G., Scarselli F., A new model for learning in graph domains, in: Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005, Vol. 2, 2005, pp. 729–734,. vol. 2.

[16]

Guo Y., Wang Z., Liu Z., Yin X., Shi X., Wu J., Xu Y., Chao H.J., SOTE: Traffic engineering in hybrid software defined networks, Comput. Netw. 154 (2019) 60–72,.

Digital Library

[17]

Guo Y., Wang W., Zhang H., Guo W., Wang Z., Tian Y., Yin X., Wu J., Traffic engineering in hybrid software defined network via reinforcement learning, J. Netw. Comput. Appl. 189 (2021).

[18]

Hartert R., Vissicchio S., Schaus P., Bonaventure O., Filsfils C., Telkamp T., Francois P., A declarative and expressive approach to control forwarding paths in carrier-grade networks, SIGCOMM Comput. Commun. Rev. 45 (4) (2015) 15–28.

[19]

Hei X., Zhang J., Bensaou B., Cheung C.-C., Wavelength converter placement in least-load-routing-based optical networks using genetic algorithms, J. Opt. Netw. 3 (5) (2004) 363–378.

[20]

Hong, C.-Y., Kandula, S., Mahajan, R., Zhang, M., Gill, V., Nanduri, M., Wattenhofer, R., 2013. Achieving high utilization with software-driven WAN. In: Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM. pp. 15–26.

[21]

Jain S., Kumar A., Mandal S., Ong J., Poutievski L., Singh A., Venkata S., Wanderer J., Zhou J., Zhu M., et al., B4: Experience with a globally-deployed software defined WAN, ACM SIGCOMM Comput. Commun. Rev. 43 (4) (2013) 3–14.

[22]

Li, Y., Zemel, R., Brockschmidt, M., Tarlow, D., 2016. Gated Graph Sequence Neural Networks. In: Proceedings of ICLR’16.

[23]

Liu X., Mohanraj S., Pióro M., Medhi D., Multipath routing from a traffic engineering perspective: How beneficial is it?, in: 2014 IEEE 22nd International Conference on Network Protocols, 2014, pp. 143–154,.

Digital Library

[24]

McKeown N., Anderson T., Balakrishnan H., Parulkar G., Peterson L., Rexford J., Shenker S., Turner J., OpenFlow: Enabling innovation in campus networks, SIGCOMM Comput. Commun. Rev. 38 (2) (2008) 69–74.

Digital Library

[25]

Pedro J., Santos J., Pires J., Performance evaluation of integrated OTN/DWDM networks with single-stage multiplexing of optical channel data units, in: 2011 13th International Conference on Transparent Optical Networks, IEEE, 2011, pp. 1–4.

[26]

Perry Y., Frujeri F.V., Hoch C., Kandula S., Menache I., Schapira M., Tamar A., DOTE: Rethinking (predictive) WAN traffic engineering, in: 20th USENIX Symposium on Networked Systems Design and Implementation, NSDI 23, USENIX Association, 2023, pp. 1557–1581.

[27]

Pfaff B., Lantz B., Heller B., Barker C., Beckmann C., et al., Open Netw. Found., Menlo Park, CA, USA, 2012.

[28]

Roughan M., Simplifying the synthesis of internet traffic matrices, SIGCOMM Comput. Commun. Rev. 35 (5) (2005) 93–96.

[29]

Scarselli F., Gori M., Tsoi A.C., Hagenbuchner M., Monfardini G., The graph neural network model, IEEE Trans. Neural Netw. 20 (1) (2009) 61–80,.

Digital Library

[30]

Schulman J., Wolski F., Dhariwal P., Radford A., Klimov O., Proximal policy optimization algorithms, 2017, arXiv:1707.06347.

[31]

Shao, Z., Zhang, Z., Wang, F., Xu, Y., 2022. Pre-training enhanced spatial-temporal graph neural network for multivariate time series forecasting. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp. 1567–1577.

[32]

Suárez-Varela J., Almasan P., Ferriol-Galmés M., Rusek K., Geyer F., Cheng X., Shi X., Xiao S., Scarselli F., Cabellos-Aparicio A., Barlet-Ros P., Graph neural networks for communication networks: Context, use cases and opportunities, IEEE Netw. 37 (3) (2023) 146–153,.

Digital Library

[33]

Swaminathan A., Chaba M., Sharma D.K., Ghosh U., GraphNET: Graph neural networks for routing optimization in software defined networks, Comput. Commun. 178 (2021) 169–182.

[34]

Troia S., Alvizu R., Zhou Y., Maier G., Pattavina A., Deep learning-based traffic prediction for network optimization, in: 2018 20th International Conference on Transparent Optical Networks, ICTON, 2018, pp. 1–4,.

[35]

Valadarsky A., Schapira M., Shahaf D., Tamar A., Learning to route, in: Proceedings of the 16th ACM Workshop on Hot Topics in Networks, in: HotNets-XVI, Association for Computing Machinery, 2017, pp. 185–191.

[36]

Wang N., Ho K.H., Pavlou G., Howarth M., An overview of routing optimization for internet traffic engineering, IEEE Commun. Surv. Tutor. 10 (1) (2008) 36–56,.

Digital Library

[37]

Wang Y., Wang Z., Explicit routing algorithms for internet traffic engineering, in: Proceedings Eight International Conference on Computer Communications and Networks (Cat. No.99EX370), 1999, pp. 582–588,.

[38]

Wu, Z., Pan, S., Long, G., Jiang, J., Zhang, C., 2019. Graph wavenet for deep spatial-temporal graph modeling. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. pp. 1907–1913.

[39]

Xu Z., Tang J., Meng J., Zhang W., Wang Y., Liu C.H., Yang D., Experience-driven networking: A deep reinforcement learning based approach, in: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, 2018, pp. 1871–1879,.

Digital Library

[40]

Xu Z., Yan F.Y., Singh R., Chiu J.T., Rush A.M., Yu M., Teal: Learning-accelerated optimization of WAN traffic engineering, in: Proceedings of the ACM SIGCOMM 2023 Conference, in: ACM SIGCOMM ’23, Association for Computing Machinery, 2023, pp. 378–393.

[41]

Ye M., Zhang J., Guo Z., Chao H.J., LARRI: Learning-based adaptive range routing for highly dynamic traffic in WANs, in: IEEE INFOCOM 2023, 2023, pp. 1–10,.

[42]

Zhang B., Bi J., Wu J., Baker F., Cte: cost-effective intra-domain traffic engineering, ACM SIGCOMM Comput. Commun. Rev. 44 (4) (2014) 115–116.

[43]

Zhang J., Ye M., Guo Z., Yen C.-Y., Chao H.J., CFR-RL: Traffic engineering with reinforcement learning in SDN, IEEE J. Sel. Areas Commun. 38 (10) (2020) 2249–2259.

Index Terms

GROM: A generalized routing optimization method with graph neural network and deep reinforcement learning
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
    2. Machine learning approaches

Index terms have been assigned to the content through auto-classification.

Recommendations

SmartEntry: Mitigating Routing Update Overhead with Reinforcement Learning for Traffic Engineering
NetAI '20: Proceedings of the Workshop on Network Meets AI & ML

Traffic Engineering (TE) has been used by Internet service providers to improve their network performance and provide better service quality to users. While flow-based TE is an alternative, destination-based TE is a more readily deployed solution. This ...
Traffic Engineering in Hybrid Software Defined Network via Reinforcement Learning
Abstract
The emergence of Software Defined Network (SDN) provides a centralized and flexible approach to route network flows. Due to the technical and economic challenges in upgrading to a fully SDN-enabled network, hybrid SDN, with a partial ...
Adaptive quality of service-based routing approaches: development of neuro-dynamic state-dependent reinforcement learning algorithms: Research Articles

In this paper, we propose two adaptive routing algorithms based on reinforcement learning. In the first algorithm, we have used a neural network to approximate the reinforcement signal, allowing the learner to take into account various parameters such ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Network and Computer Applications

Journal of Network and Computer Applications Volume 229, Issue C

Sep 2024

282 pages

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Academic Press Ltd.

United Kingdom

Publication History

Published: 19 September 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents