Learning Sub-Second Routing Optimization in Computer Networks requires Packet-Level Dynamics
Authors: Andreas Boltres
Niklas Freymuth
Patrick Jahnke
Holger Karl
Gerhard Neumann
Venue: Accepted by TMLR ()

Abstract: Finding efficient routes for data packets is an essential task in computer networking. The optimal routes depend greatly on the current network topology, state and traffic demand, and they can change within milliseconds. Reinforcement Learning can help to learn network representations that provide routing decisions for possibly novel situations. So far, this has commonly been done using fluid network models. We investigate their suitability for millisecond-scale adaptations with a range of traffic mixes and find that packet-level network models are necessary to capture true dynamics, in particular in the presence of TCP traffic. To this end, we present PackeRL, the first packet-level Reinforcement Learning environment for routing in generic network topologies. Our experiments confirm that learning-based strategies that have been trained in fluid environments do not generalize well to this more realistic, but more challenging setup. Hence, we also introduce two new algorithms for learning sub-second Routing Optimization. We present M-Slim, a dynamic shortest-path algorithm that excels at high traffic volumes but is computationally hard to scale to large network topologies, and FieldLines, a novel next-hop policy design that re-optimizes routing for any network topology within milliseconds without requiring any re-training. Both algorithms outperform current learning-based approaches as well as commonly used static baseline protocols, particularly in high-traffic volume scenarios. All findings are backed by extensive experiments in realistic network conditions in our fast and versatile training and evaluation framework.

Published in Transactions on Machine Learning Research (10/2024)
Learning Sub-Second Routing Optimization in Computer Networks requires Packet-Level Dynamics
Andreas Boltres
andrassboltress@pprteer...
Autonomous Learning Robots,
Karlsruhe Institute of Technology
SAP SE
Niklas Freymuth
miklas.freymetn @kit. edu
Autonomous Learning Robots, Karlsruhe Institute of Technology
Patrick Jahnke Turba AI
pj@turbo.
Holger Karl
de
Internet-Technolln Technology and Softwarization,
Hasso- Plattner-Instee Polsdam
Gerhard Neumann
gerhard nernaannneummannnccm newmann Skit. edu
Autonomous Learning Robots, Karlsrahe Institute of Technology
Reviewed OpenReview: https:// net/ forum? id= 895g8Up YKY
Abstract
Finding efficient routes for data packets an essential task in computer networking. The optimal routes depend greally on the current network topology, state and traflic demand, and they change within milliseconds. Reinforcement Learning help to learn network representations that provide routing decisions for possibly novel situations. So far, this has commonly been done using fluid network models. We investigate their suitability for millisecond-sent adaptations with a range of traffic mixes and find that packet-level network models are necessary to capture true dynamics, particular in the presence of TCP traffic. To this end, we present PackeRL, the first packet-level Reinforcement Learning environment for routing generic network topologies. Our experiments confirm that learning- based strategies that have been trained in fluid environments do not generalize well to this more realistic, but more challenging setup. Hence, we also introduce two algorithms for learning sub-second Routing Optimization. We present M-Slim, a dynamic shortest-patie algorithm that excels at high traffic volumes but is computationally hard to scale to large network topologies, and FieldLines, a novel next-hop policy design that re-optimizes routing for any network topology within milliseconds without requiring any re-training. Both algorithms outperform current learning- based approaches as well as commonly used static baseline protocols in scenarios with high-traffic volumes. All findings backed by extensive experiments in realistic network conditions in our fast and versatile training and evaluation framework
1 Introduction
Routing data packets efficiently is an essential task in computer networks. A well-working routing mechanism maximizes service quality and minimizes operational cost. Several conditions make network traffic routing
Code available via project webpage: http://ahhw...ttttu..i.i/icaraea

---

Published in Transactions on Machine Learning Research (10/2024)
Traflic/
Frrafic/Lood Load Incresses
Re-optimise Routes
Observation C,
Run Network
Network State S
Routing Update x(a G.)
Next State S:
Reward
Figure 1: Re-optimizing packet routes based on the network topology and current utilization and load values can minimize congestion, delay and packet drops: Here, the longer but higher-capacity path (thicker edges) is preferred to the shorter path when traffic spikes for the orange (top) and purple (bottom) node, causing the algorithm to re-route traffic over the blue (left) node instead of the green (right) one.
complex problem: i) It can be optimized with respect to various performance metrics, like packet delay or loss of data (Wang et al. 2008). ii) Traffic demands are often highly volatile and umpredictable, e.g. in datacenter or content delivery networks (Alizadeh et al. 2014 Wendell & Freodman 20011] ). iii) Network topologies are
al. 2008 Turner al. 2010). iv) The space of possible routing decisions grows exponentially with network size. Traffic Engineering (TE) is a highly active research area that tackles this problem (Farrel
often subject unexpected changes like link and switch failures (Gill al.) [001 Markopoulou
2024) by means of regular monitoring and control. Within TE, core problem is Routing Optimization (RO). In various network setups, TE algorithms claim to produce optimal or near-optimal routing at sensible cost (Mendiola et al. 2016) Yet finding optimal routes given a. network configuration and traffic information is often computationally intractable (Xu et al. 2011p. Also, to deal with the uncertainty about future traffic conditions, conventional TE methods are limited to optimize for previously observed or speculated future traffic. They may perform poorly even when the observed traffic is only slightly off (Valadarsky et al. 2017). As a remedy, researchers have turned to data-driven optimization via deep Reinforcement Learning (RL) (iaoo et al., 2021
With deep RL, routing policies can use learned representations of network states to provide routing decisions for possibly novel situations. These states are conditioned on the encountered network scenario, i.e., the network topology and configuration and their changes over time, as well as traffic demands. Contributors of RL for TE have presented performance improvements widely varying experiment settings. They range from handful of experiments on real or emulated testbed networks (Guo et al.) 2022 Huang et al.) 2022 al. 2019) to small ranges of network scenarios evaluated in simulations with more
Pinyoamunappon
2023). Covering the variety of network scenarios abstract network models [Bernárdez et al. 2023 Xu et al.
that is required to thoroughly evaluate RT- based RO approaches Zhang et al. 2018) can become prohibitively 2010). Consequently, building realistic yet
expensive when using real testbed networks (Shewoood et al.
versatile simulation environments is particularly important.
Out of the publicly available environments, only the one by Bernárdez et al. (0023 supports arbitrary network topologies and traffic patterns. But it uses fluid-based network model, i.e., a model that treats traffic flows in a flow network. Such models abstract away from packet-level interactions encountered in the real world, e.g. in TCP traffic, where sending and forwarding dynamics very different from flow distributions in flow networks. Hence, it is unclear how models trained in such environments perform in more realistic scenarios, where the traffic patterns are shaped by the dynamics of transport protocols like TCP. Besides the increased realism, including lacket-level interactions in the environment also permits routing control on a finer temporal scale. Related work has indoed recognized the importance of sub-second RO in an incrcasing number of network scenarios (Gay et al.] (2017a), stressing the need for such packet-level environments. To address these shortcomings of fluid-based simulation, we hence introduce new leck training and
2

---

Published in Transactions on Machine Learning Research (10/2024)
evaluation environment PackeRL that is tailored to learning sub-sccond RO. It realistically simulates network scenarios with versatile network topologies, traffic data, and various transport protocols.
Current RL-powered RO approaches either need to compute shortest paths multiple times for every re- optimization step (Bernárdez et al. 2023 which does not scale to sub-second RO for large network architectures, or select next-hop neighbors separately at each routing node (Valadarsky et al., 2017 Pinyoa- nuntapong et al., 2019 You et al., 2022 Guo et al., 2022 Bhavanasi et al., 2022), which does not generalize to arbitrary network topologies without the need for re-training adjusting the policy architecture. This paper presents two new RL- RL-powered approaches for sub-second RO: M-Slim and FieldLines. M-Slim is a scalable RO policy that only requires, per update, single All Pairs Shortest Paths (APSP) calculation for obtaining a new routing strategy, unlike existing methods that require many optimizations (Bernárdez et al., 2023). While this reduces the time required to re-optimize routing significantly, the computation time still grows cubically with the number of network nodes when using the Floyd- Warshall algorithm (Cormen et al., 2022). FieldLines is a novel next-hop selection RO approach that leverages the permutation equivariance properties of its Graph Neural Network (GNN) architecture (Bronstein et. al., 2021 | to generalize to unseen network topologies. It is the first next-hop selection design that provides competitive RO performance in packet-level environments on any kind and scale of network topology, while only requiring training on small
networks with up to 10 nodes.
In summary, our contributions are as follows: i) PackeRL is the first packet-level simulation environment RI-powered RO that supports arbitrary yet realistic network topologies and traffic data, including UDP and TCP traffic. ii) Using PackeRL, we show that an existing RL-based RO policy trained in a based environment like MAGNNETO (Bernárdez et al. 2023) cannot cope with packet-level network dynamics and performs significantly worse than common static shortest-paths routing strategies. This motivates the need for packet-level training environments like PackeRL. iii) We present M-Slim, a novel RL-based shortest path RO method that scales to sub-second RO and is trainable in our packet-level environment PackeRL. It outperforms static shortest-path routing strategies by a significant margin. iv) We present FieldLines, a novel next-hop routing policy that provides competitive performance for traffic-nntense scenarios and does not suffer from the computational limitations of shortest-path based policies.
2 Related Work
Researchers working on conventional TE approaches have recognized the need for standardized evaluation environments: REPETITA (Gay et al. 2017b) aims at fostering reproducibility in TE optimization research, and the goal of YATES (Kumar et al. not deliberately designed with RL in mind, it is possible to extend them to support training and evaluating RL-based routing policics. These frameworks are limited by their abstract network model which does not model packet-level interactions. Our experiments demonstrate that RL routing policies trained in such environments perform significantly worse when tasked to route in more realistic packet-level environments.
2018) is to facilitate rapid protolyping of TE systems. While they are
The simulation frameworks RL4Net (Xiao et al. 2022). its successor RLANET+ (Chen et al. 2023 and PRISMA (Alliche et al. 2022 are perhaps the closest relatives to PackeRL. They provide the same kind of closed interaction loop between RT. models and algorithms in Python and packet-level network simulation in ns-3. However, in contrast to PackellL, out-of-the-box support for arbitrary network topologies including link datarates and delays is left to the user, and simulation is limited to constant bit-rate traffic between all pairs of nodes. The latter does not apply to PRISMA, which however only simulates UDP traffic. Moreover, Figure shows that PackeRL runs simulation steps several times faster than the numbers reported in Chen al. (2023). This may be due to PackeRL leveraging the shared-memory interface of ns3-ai for communication between learning and simulation components, instead of process communication via ZeroMQ (Hintjens) 2013). As the authors of nss-ai noted in Yin et al. (2020). this drastically cuts communication times between learning and simulation components.
A common approach to learn RO with deep RL is to infer link weights that are used to compute routing paths (Stampa et al., 2017 Pham et al.] 2019 Sun et al., 2021 Bernárdez et al. 2023). Out of the existing approaches, only MAGNNETO (Bernárdez et al. 2023) can generalize to unseen topologies by using GNNs in their policy designs. The caveat of MAGNNETO is the iterative process of e O(F) steps required to optimize
3

---

Published in Transactions on Machine Learning Research (10/2024)
routing for single Traffic Matrix (TMP Each iteration step, its actions denote set of links whose weight shall be incremented for the upcoming optimization iteration. These actions don't lend to paths directly. Instead, the link weights for path computation are obtained only after finishing the optimization process of
(EE) steps. Each step requires an APSP computation with a computational complexity of O(V3) when using Torsh-arshalll or O(V2 log V + EV) when using Johnson-Dijkstrra (Cormen et. al. 2022). g. Consequently, MAGNNETO is not able to provide sub-sccond RO in most networks, as the results in Figure show.
Instead of computing shortest paths for RO, some deep RL approaches are trained to select next-hop neighbors directly (Valadarsky et al. 2017 Pinyoanuntapong et al. 2019 You et al.) 2022 Guo et al. 2022 Bhavanasi et al. 2022p. However, these policies are not designed to generalize to arbitrary topologics and to handle topology changes, either because their GNN architect require a (re-) (te-)itaining process for each topology (Bhavanasi et al. 2022 Mai et al.] 2021
You et al. 2022), or because their non-GNN architecture
ties them to specific topologies Valadarsky et al.
2017
Pinyoanuntapong et al. 2019 Guo et al. 2022
A small portion of the existing RL- Rl-ppeeered RO approaches has open-sourced their training and evaluation
environments (Stampa et al. 2017 Bernárdez et al. the same limiting model abstractions as REPETITA and YATES [Brnáádezz et al. 2023 Xu et al. 2023), or, if they leverage network simulator backends, they only support limited subset of network scenarios (Stampa
2023 Xu et al. 2023). These environments either employ
et al. 2017). Therefore, they are not suited to become reference frameworks for training and evaluation.
Finally, recent related work has proposed learned network models as replacements for packet-based network simulation (Zhang et al.) 2021 Yang et al., 2022 Wang et al.] 2022 Perriol-Galméé et al. 2023). In general, such models receive network topologies, traffic and routing as input, and consult a. trained model to predict performance metrics like packet delay and link utilization. While these models promise smilar accuracy at
lower computational cost, the reported gaps in accuracy (Perriol-Galmés et al. 2023) suggest that these frameworks cannot fully replace the packet-level simulation offered by PackeRL.
In summary, there exists no framework for RL-powered RO approaches that offers both a realistic simulation backend, and a comprehensive toolset for training and evaluation on wide ranges of realistic network scenarios. Besides, there is no experimental evidence for why such packet-level frameworks are even needed, for instance by exposing the limits of routing policies trained in more abstract environments. Finally, none of the existing next-hop selection RO approaches work on arbitrary and changing topologies without re-traiming architectural adjustmmntts and the shortest-path based algorithms that do generalize across topologies are computationally too expensive to provide sub-second routing. We believe that PackelLL, our experimental results obtained for our shortest-path routing policy M-Slim in PackeRL, and our new next-hop policy design FieldLines close these gaps.
3 Preliminaries and Problem Formulation
We consider wired Internet Protocol (IP) networks using the connection-less User Datagram Protocol (UDP) (Postel 1980) and the connection-based Transmission Control Protocol (TCP) (Eddy 2022). TCP in
particular is responsible for the majority of today's internet trallic (Schumann el al. 2022
Routing selects paths in a network along which data packets are forwarded. To determine the best paths, the Routing Protocol (RP)'s algorithm uses the network topology as input. For example, Open Shortest-Pasd Path First (OSPF) (Myy 1997) propagates each link's 's data rate such that every router knows the entire network graph, annotated by data rate. Then, every router uses Dijkstra to compute shortest paths, where by default the path cost is the sum of the inverse of link data rates (Section B.5 explains the path cost calculation process). Several network performance indicators exist, such as goodput (i.e. the bitrate of traffic received at the destination), latency/ /elay (the time it takes for data to travel from the source to the destination), packet loss (the percentage of data that is lost during transmission), or packet jitter (the variability in packel arrival times, which can affect the quality of real-time applications or lead to out-of-order data arrival). Achieving a favorable trade-off between these performance metrics is non-trivial, not least because their importance may vary depending on the type/ use case of network and the traffic characteristics.
2A TMM contains average traffic flows between pains of nodes i.j V V a square matrix representation.
4

---

Published in Transactions on Machine Learning Research (10/2024)
3.1 Routing Optimization an RL Problem
We formalize RO as Markov Decision Process with the tuple TT,,,,,r), splitting the continuous-time network operation into time slices of length Tsim- The space of network states S consists of attributed graphs with global, node- and edge-level performance and load values, as well as topology characteristies like link datarate and packet buffer size. We model network states as directed graphs S, = (V. E,, xv,,,, with nodes Vi and edges Fr at step t. Node and edge features are given by Xv, (x,,* Rdy, | we Vi) and XF,,= = {xe.: IR e E Ei} respectively, and Xu, E Rd denotes global features that are shared between all nodes. Sections A.4 and [B.4] contain details on how network states are obtained in our framework. The action a, A consists of next-hop neighbor selection E Nu. per routing node u E Vi for each possible destination node e V,, or formally: a, = [(,
Xa,t)
u, U, E V,, v Nu). These destination-basen routing actions are valid for all packets processed in the upcoming timestep, i.e. the actions are taken in the control plane [Mestres et a 2017). The transition function : x A - evolves the current network state using the induced routing actions to obtain a new network state. Its transition probabilities are unknown because it depends on the upcoming traffic demands, which are often unprodictable in practice (Wendell & Freedman 2011]. Finally, r S A R is global reward function which assesses the fit of routing action in the given network topology and state. Here, we use the global goodput, measured MB received per step, our reward function. Our goal is to find policy π : A [o. 1] that maximizes the return, i.c., the expected discounted cumulative future reward J. := Ex(ajs) [Ex-o r( a++*]] Thus, in our default setting, an optimal policy maximizes the long-term global goodput. Despite its simplicity, this optimization objective provides competitive results. Section C.3 shows that optimizing for different objectives, including multi-component objectives, does not improve results consistently.
Next, introduce our packet-level simulation framework PackeRL which builds upon the above formalism.
4 PackeRL: An Overview
PackeRL framework for training and evaluating deep RL approaches that route packets in IP computer networks. It interfaces the discrete-event network simulator ns-3 (Henderson et al. 2008) for repeatable and highly configurable RO experiments with realistic network models. It provides Gymnasium- like interface TTwers et al., 2023) to the learning algorithm and provides near-instantancous communicttion between learning algorithn and simulation backend by using the shared memory extension ns3-ai (Yin el al, 2020 PackeRL. advances RT research for RO in the following ways:
supports optimization for several common objectives that can be combined with adjustable weightings. Nonetheless, both RL and non-RL approaches alike can be evaluated with respect to range of performance metrics. While optimize our approach for goodput by default, we show results for alternative optimization objectives in Section C.3
It provides access to an extensive range network scenarios. Section
4.1 provides further information.
It implements a closed interaction loop between RL policy and network simulation, using In-Band Network Telemetry (Kim et al. 2015) to monitor the network state and provide state snapshots S., The time period simulated per environment step can be arbitrarily large or small, and thus, unlike most existing frameworks, it supports online RO experiments with or without RT.
It can be used to train RL routing policies within a few hours and evaluate them within a few minutes. Thus dispel the concerns raised by related work that packet-based environments are too slow Sperrio--Galééé et al. 2023) or too complex to implement (Kunar et al. 2018
We provide a detailed explanation of PackeRL in Section A Section A.1 explains the structure of computer networks in ns-3, Section expands on the interaction loop between RL policy and environment, Section A.3 clarifics how the actions a, are installed in the simulated network, and Scction [A.4 provides details on how network states S, are obtained from the network simulation. Finally, general simulation parameters are explained in Section B.1
5

---

Published in Transactions on Machine Learning Research (10/2024)
3
3
compuse APSP
Link Weights
Shortest Paths
M-Slim actor
0,1
us
pachs to actions
9.1
D1
8.9
0.1
0.6
0.8
Observation Go
0.1
Routing Actions a
0.6
8.8
0.5
FieldLines octor
FieldLines selector
Next-Hop Rating
Figure 2: Example of how the learnable policies M-Slim and FieldLines obtain routing actions a, A from network states S,. The red edges denote highly loaded data pathways, e.g. due to full packet buffers. The actor of M-Slim outputs link weights that are used to calculate routing paths. These routing paths are then broken down into individual next-hop neighbor selections per destination node v E V and routing node u V to fit the definition of the action space A. FieldLines uses its actor module & to obtain next-hop ratings per edge and destination node, illustrated by the respective colors of the rating values. The selector module & then uses these ratings select next-hop neighbors per destination and routing node.
4.1 Network Scenario Generation with synnet
PackeRL offers versatile simulation conditions via synnet, a standalone module for network scenario generation. In synnel, network scenarios consist the network topology and set of events. The network topology consists of the graph of routing nodes, links between them, well as parameters like link data rate or delay and packet buffer size. For generating the topologics,
random graph models commonly found in the literalure (Barabási] 2009 Erdös et al. 1960 Walts & Strogalz) 1998). Events can be of two lypes: Traffic demand events contain an arrival time, demand size and type (UDP vs. TCP). We use random models to generate demand arrival times and volumes, such that the generated network traffic resembles observed worldworld traffic patterns [Benson et al. 2010 Link failure events consist of a failure time and the edge that is going to fail. Here, too, we use random models for link failure times that resemble the patterns found operative networks (Bogle et al., 2019). Sections A.5 and A.6 provide more details on the scenario generation
process well examples, while Sections B.2 and B.3 contain the parameters used for the random models.
5 Policy Designs for Routing in Packet-Levad Environments
This section introduces two RL policy designs for RO trainable in PackeRL, namely our next-hop selection policy FieldLines and our adaptation of MAGNNETO which we call M-Slim (short for MAGNNETO-Slimm Our results Section 7 show that both M-Slim and FieldLines clearly outperform MAGNNETO, underlining the benefit of learning to route PackeRI. Nevertheless, they use different approaches to obtain routing actions a, from the given network state S,. As illustrated in Figure 2 M-Slim adopts MAGNNETO's approach of computing routing paths from inferred link weights, while FieldLines directly selects next-hop

---

Published in Transactions on Machine Learning Research (10/2024)
TCP/UDP, medium traffic
TCP, high traffic
ReldLines (ours)
M-Slim fours] MAGNNETO OSP
Random (LW)
Random (NH))
FieldLines [ours]
M-Slim (ours) MAGNNETO OSPR
Random (LW)
Random
EIGRP
EIGRP
(NH)
Action Fluctuation
+3.04%
-B 96%
+38.75%
122.25%
65%
+4.4%
+9.21%%
+8.50%
421.1%
160.25%
Received (f)
35.38MB
15 15521155 73, 35
+0
9.37%
35.00
-1.26%
14%
-78.58%
61.7MB
16, 07 23,
-2.62%
-20.96%
-88. 63%
Avg. Delay (4)
7.2ms
.2.44%
.3.77%
.1.6%%
+2.57%
+.5 30%
+232 54%
7.53ms
.1.04%
3.97%
.0.2%
+1.83%
+2.46%
+170.26%
Dropped 1.25%
(.37.14)
1.55.1400
11.39 2.011
+0.03%
-0.02%
+1.20%%
+16 66%
5.74%
9.89
+0.16%
+1.93%
420.76%
Figure 3: Results on the nx-X8 topology preset, displayed per approach and performance metric. Cells show the mcan values ovcr 100 evaluation episodes in the first line, and min and max values across random scods in the second line. Values are relative to Enhanced Interior Gateway Routing Protocol (EIGRP). The stark contrast wetween random and learned routing shows that efficient routing is not a trivial task, and using RL to learn it is very beneficial. Both our approaches outperform the shortest-path baselines in high-traffic scenarios, and the difference in performance to MAGNNETO shows that learning to route in nacket-based environments is important.
neighbors per destination node V and routing node V. Section 5.2 explains how this circumvents the need for computing shortest paths every ro-optimization.
The information available in the RO problem can be represented as graphs with node, edge and global features. Thus, GNNs are highly suitable models because their permutation equivariance enables generalization to arbitrary network topologics. While MAGNNETO uses Message Passing Neural Networks (MPNNs) GGilmer
et. al.] 2017) for its actor module, we use a variant. valled Message Passing Networks (MPNs) (Sanchez.
Gonzalez et al. 2020 Freymuth et al. 2024) that supports node, edge, and global features. Using Multilayer Perceptrons (MLPss 8, initial features x and xe with (v, u) E, the 1-th step is given
1+1 (x( x,),
x.11
(
For the permutation cermutation-invaiiant aggregation + we use a concatenation of the features' mean and minimum. We provide implementation details on the MPNN architecture of MAGNNETO and the MPN architecture used by M-Slim and FieldLines in Appendix B.8
5.1 M-Slim: Learning Link-Weight Optimization in Packet-Level Simulation
Section 2 states that MAGNNETO's iterative process for obtaining routing paths is too slow to warrant sub-second RO. In fact, the inference limes reported in Figure 7 are too high even to follow our training protocol in PackeRL because it involves larger number of temporally fine-grained interaction steps. Reducing inference time is required to enable training in PackeRL, and to this end we present our MAGNNETO adaptation called M-Slim. While the output of MAGNNETO's actor architecture specifies set of links whose weights shall be incremented, in M-Slim we interpret this output as link weights directly. This reduces the amount of model inference steps and APSP computations per routing update from O(E) to 1 and enables sub-second routing re-optimization in larger network topologics.
The change in interpretation of the actor's output requires further design adjustments. To account for exploration during training rollouts, we treat the actor output as the mean Pr for diagonal Gaussian M(H,, M-SSmm) from which we then sample the actual link weights. d is learnable parameter. During evaluation, the values of μr are used as link weights directly. Finally, we apply the Softplus function (Zheng ct al. 2015) to the output of the actor module to ensure the values are positive and thus usable as link weights. Concerning the archilecture of the actor module, we replace the MPNN design used by MAGNNETO by an MPN-based design with L = 2 steps and parameters as detailed in Appendix [.S] to reduce model complexity. As Figure 17 Appendix shows, compared to when using MAGNNETO's MPNN architecture for M-Slim, the MPN design further decreases inference time without compromising on performance. Otherwise, M-Slim uses the same input and output. representations MAGNNETO: They receive the latest Link Utilization

---

Published in Transactions on Machine Learning Research (10/2024)
(LU) values and past link weights imput and operate the Line Digraph representation to obtain link weights as node features. Section B.6 further explains Line Digraphs.
5.2 FieldLines: Fast Hop Routing in any Network Topology
M-Slim greatly reduces computation time per re-optimization step, but it still requires one APSP pass per routing update illustrated in Figure 2 A single such computation overshadows the computational complexity term OVVD) of GNN inference (Alkin et al. 2024) for a maximum node degree D as the network grows in scale, making the shortest-paths computation the computational bottleneck. We thus lurn to our next-hop selection RO approach FieldLines to further reduce inference times: It utilizes the results of one initial APSP computation and only requires re-computing APSP when the network topology changes.
FieldLines consists of an actor module & and selection module eे: The actor module o: 5 R [ first creates an embedding of the network state that it then uses to provide numerical values Φz.0 for cach possible combination of network edge E and destination node e V. We implement & as an MPN with L 2 steps and parameters as described in Appendix B.S. Intuitively, the output values éz.e describe how well e (u, u) is suited as a next-hop edge from node u for packets destined for 2. Producing such an output requires the network fcatures to contain some form of positional embodding. However, by default, a GNN cannot spatially identify nodes and edges of the input topology in relation to each other due to its permutation equivariance property (Bronstein al.) (021)). Therefore, we provide auxiliary positional information as node input features by calculating APSP once, and then supplying the resulting path distances between nodes. For the path computation, we use the link weights calculated by EIGRP as described in Section B.5 For high-frequency RO, removing the need for APSP on every re-optimization reduces the overall computational complexity. Importantly, the actor module is still aggosiic because the topology and positional information is supplied as input, allowing FieldLines to generalize to novel topologies during inference.
The selection module db RIV|X[E1 - A treats the next-hop edge rating supplied by ø as logits over outgoing edges per node e V and destination z. During training rollouts, & uses Boltzmann exploration by sampling next-hop edge from these distributions, using learnable temparature paramcter Th- During evaluation, it simply chooses the maximum probability edges for each pair of routing node and destination node 2. In both cases, the resulting next-hop choices correspond to rules in destination-based routing. Importantly, this policy design is able to form non-coalescent routing paths (i.e routing loops) because we do not force coalescence. Our results show that constraining our routing to coalescent paths is not necessary, and there is evidence that, in certain network situations, routing loops can even be beneficial to routing performance (Brundiers et al. 2021
6 Experiment Setup
In our experiments, we consider episodic RT. setting in which every training and evaluation episode comes with its own network scenario. This includes the network topology as well as traffic demands and link failure events for the entire longth of simulation T. To account for packot-level dynamics in PackeRL, we simulate и = 100 steps per episode and set Tsim, the time simulated per enviromment step, to 5 ms, which yields T 500 ms. This implies that, as opposed to existing fluid-based environments, training and evaluation in PackeRL involves a larger number of temporally fine-grained inference steps. Furthermore, our training and evaluation protocols cover varying network topologies, traffic situations, and the presence of link failures. Since such a setting requires routing algorithms to provide quick updates for arbitrary topologies without the need for re-training, we do not evaluate approaches that are hand-crafted or fine-tuned to a specific network topology. Instead, as Bernárdez et al.] (2023) have shown that learning useful general-purpot representations for RO is possible, we design our evaluation to shed light on the importance of packet-levad dynamics for lcarning more suitable representations.
We are aware that the examples presented in Brundiers al. 2021 use Equal- Costl-Cost. Multipath (ECMP) routing Chiesa el al. 2016), which at the moment is not supported by Ra.
8

---

Published in Transactions on Machine Learning Research (10/2024)
FieldLines, Received (1)
FieldLines, Avg.
Delay (4)
Lines, Dropped (L)
low
medium
high
very high
low
medium
high
very high
low
medium
high
very high
UDP
-0.22%
-0. 0.12%
+0.0 0.02%
+0.22%
-1.54%
1.99%
-2. 2,03%
2 2.44%
+0.05%
+0. 0.08%
0.0%
-0.02%
TCP/UDP
.0.5%
+0.28%
[55
(BMB3
+2.48%
06. 36.78msi
2.24%
2.82%
22 3.35%
+0.15%
(..89)
0.05%
-0.35%
-1.03%
+1.2%% (62.00M5)
+2.69% 17087
-1.86%
-1.84% (7.3 7..30mll
+0.17% (0.98%)
-0.14%
-..66%
(4M54M5)
(40 2618)
(6.85mal
17.22ms)
17.45ma)
(2.78%
(9.22)
M-Slim, Received (T)
M-Slim, Avg. Delay (4)
M-Slim, Dropped (4)
low
medium
high
very high
low
medium
high
very high
low
medium
high
very high
UDP
16.09 16.09M81
-0.4%
114 0000)
-0. -0.19%
-0.11% (27.41M6)
+0.85% 151779611
(7.26mal
-1.56% 17.18ms)
-1.75%
0.32msl
-4. 4.23% 18.12mm)
+0.07% 10.15s
+0.3 -0.13% (0.2%)
+0.16% 10 4645))
-0.56% (2.6911
TCP/UDP
(15.11M5)
-2.36%
[55 2610)
-0.37%
+3. +3.61%
(38.2944)
+4.58%
183 20KB1
(8.72ma)
-3.4%
18. (8.90mm))
-3.37%
-3.86%
(7 (7.23mal
17.70mm)
33.44%
+00.7%
10 (0.095)
+0.15% (1.4%)
-0, 0.14%
(2 330%
-0.58%
(6.409)
TCP
07:54483)
22. 34%
+3.55%%
[48.97740
+33 2.5%
053.77 (13.711943
(91 (138B
+-4.1 4%1%
-2.65% (6.78mc)
-3.5 -3.57%
(7.12mm)
-2.87%
0.311m
-2.46%
[7.41mmm)
+0,21% (1.01%)
-0, 0..99
(2.7%)
-0. -0.23%
(5.5150
-0. -0.54%
(9.579]
Figure 4: Results for our approaches FieldLines and M-Slim on the nar XS topology preset, displayed for varying traffic kinds and intensities. Cells show the mean value over 100 episodes relative to EIGRP's performance in the first line, and the absolute mean value in the second line. Both approaches consistently improve the average packet delay. Moreover, for more intense traffic, they outperform EIGRP in goodput and drop ratio. The sending rate dynamics of TCP-dominated traffic amplify the reported difference.
6.1 Evaluated Routing Approaches
We compare MAGNNETO, which is trained in a fluid-based environment, to M-Slim and FieldLines, which are trained in PackeRL. To evaluate MAGNNETO in PackeRL, at each timestep, we feed it the latest TM of sent bytes. Beginning with zero L.U and randomly initialized integer link weights, uses current LU and link weights as edge features and increments one or more link weights. Its fluid-based environment then distributes the TM's traffic volumes across the flow network using the paths obtained from APSP computation and obtains new LU values for the next iteration. This way, MAGNNETO uses the initial TM for @(E) optimization steps in which it itcratively adjusts the link weights for path computation. The final link weights are used to obtain the actual routing paths communicated to PackeRL. On the contrary, M-Slim and FieldLines are evaluated by doing one deterministic inference pass on the respective policy architecture, which directly yields shortest path weights in the case of M-Slim, and node-centric next-hop selections per packet destination in the case of FieldLines. In addition to the learned approaches, we consider two shortest-path baselines: OSPF is introduced in Section 3.1 and EIGRP (Savage et. al. 2016) also involves link delays in its link weight calculation. These two routing protocols are widely adopted because their topology discovery mechanisms allow for routing in any network topology, and the hcuristics used for computing shortest paths work well in most practical siluations. Yel, by default, these protocols are oblivious to varying traffic conditions and network utilization. Therefore, for evaluating the two baselines it is sufficient. to compute shortest paths once at the start of the episode and every time the network topology changes. We use standard reference values for the path computation process, which is explained in Section B.5] Lastly, we include results of two random policies for reference: Random (NH) chooses random next-hop edges for each possible destination Z V at each routing node E V, and Random (LW) uses shortest-path routing with randomly generated link weights. While Random (LW) corresponds to an untrained MAGNNETO/ M-Slim policy, Random (NH) corresponds to an untrained FieldLines policy.
6.2 Network Scenarios
We consider five groups of randomly generated topologies of varying scale, generated as described in Appendix A.5 We call these groups the nr family and work with nx-XS (6-10 nodes), na-S (11-25 nodes), nw-M (26-50 50 nodes), nodes, nz-L (51-100 nodes) and nx-XL (101-250 nodes). Figures 10 and 11 visualize example topologies. We train and evaluate on grid of combinations of traffic scaling values Mtraffic and TCP fractions
9

---

Published in Transactions on Machine Learning Research (10/2024)
TCP/UDP, medium traffic, 11-25 nodes
TCP/UDP, medium traffic, 26-50 nodes TCP/UDP, medium traffic, 101-250 nodes
RellLines (ours)
M-Slim (ours)
FieldLines (ours)
M-Slim (ours)
FieldLines (ours)
M M-Slim (ours)
EIGRP
MAGNNETO
EIGRP
MAGNNETO
EIGRP
MAGNNETO
Action Fluctuation
0%
+2. -2.00% 11.07.2779
+1..02% 23.7. 32.311
+8.4% 03.4 12:56
0%
+1.16% 10.00 1.441
+12.32% 10.35
+9.23% 111. 14.77
0%
+0.33% 12.44 0.41
11.55% 00015
N/A
Received (1)
65.55MB
193.6, 66.77
06.41 17.01)
199 54, 66
102.66MB
(1016) 109
(105 007.48
19:11 106
221.72MB
122086 228 513
-0.35%
5224 68 237 8M
+2.05%
N/A
Avg. Delay (4)
9.86ms
+0.10%
-0.73%
42.35 12.28%
12.63ms
.0.33%
-0.84%
42.70%
20.22ms
40.11%
.0.7%%
22.33
Dropged (4)
1.74%
11 1.800
+0.07%
0.07% 01 1K
+0.27% 044
1.93%
-9.02% 11 00, 1:901
0 0.29% 0.32 Ag0
+0.22% 11,0)7.911
1.68%
+0.02% 03.66
-0.31% 2129...0
N/A
TCP, high traffic, 11-25 nodes
TCP. high traffic, 26-50 nodes
TCP. high traffic, 101-250 nodes
ReldLines (ours)
M-Slim (ours)
ReldLines (ours)
M-Slim tours)
ReldLines (ours)
M-Slim (ours)
EIGRP
MAGNNETO
EIGRP
MAGNNETO
EIGRP
MAGNNETO
Action Fluctuation
0%
12 6.70
8888%
01/78 (861)
12.92%
+10.56%
0678 1457)
0%
+1.27% 16 3.991
+13.0% (1 74 MAM
+11 18%
11M 16.211
0%
+0.35%%
+11.15% 0M697 $1.00
N/A
Received (1)
117.17MB
1118 126.79)
6..5%%
(11..5 35, 323.36)
3.56%
(107.43 330.0
3.52%
185.16MB
(30.3) 102
(100 183.10
1227 91, 190.58 50
372.96MB
(372.66 375.59)
40.08%
200.17 384.50
+4.45%
Avg. Delay (4)
9.85ms
-2.8%
19.16, 5:91
0..1%
06/5
+1 0999%
12:51ms
132.5, 12:791
+0.43%
+0.21%
+1.60%
16:911
20.73ms
12b10) 20:10
+0.03%
+0.1%
N/A
Dropped (4)
6.68%
13.24 6.50)
-0.44%
-0.38%
+0.26% 18.31. 7.201
7.29%
17.2%.
-0.01%
06.53. 7.40
-0.45%
+0.23% 18.00 7:331
7.34%
40.08%
(7.17440
-0.64% (6..19)
N/A
Figure 5: Results for the nx-S S (11-25 nodes), nx-M (26-50 nodes) and XL (101-250 nodes) presets. Cells show the mean values over 100 evaluation episodes (30 for nz-XL) in the first line, and min and max values across seeds in the second line. Values and colors are relative to EIGRP. Our approaches generalize to larger topologies, but the routing of FieldLines becomes more and more similar to that of EIGRP. We did not. evaluate MAGNNETO on the næ nx-XL preset due to excessive inference times.
PrCP- Specifically, we use Meraftie {0.25, 0.75, 1.5.3.0), which we denote as 'low", 'medium', "high', and 'very high" traffic in the following, and prcr (0%, 50%, 100%), which we denote as "UDP", "TCP/UD) and "TCP". Finally, while we do not include link failure events in our experiments by default, in Section 7.2 we also provide evaluation on the nu S topology set that includes randomly generated link failures described in Section A.6 This amounts to an average of 2.38 link failures per episode, distributed as shown in Figure on the left side. Importantly, we do not work with pre-generated datasets of network scenarios. Instead, using synnel and controllable random seeds for training and evaluation, we generate a new network topology, traffic demands and link failures for all timesteps at the start of every episode.
6.3 Training and Evaluation Details
We train M-Slim and FieldLines on 16 random seeds for 100 iterations of 16 episodes each. We train FieldLines on the nu -S topologies while restricting the training of M-Slim to the two well-known network topologies NSFNet and GEANT2, with link datarate values taken from Bernárdez et al. (2023), for better comparability to MAGNNETO. For both approaches, we use PPO (Schulman et al.) 2017) and refer to Section B.7 for hyperparameter details. Given the episode length H 100, this results in total of 160000 training steps per training run which, depending on TCP ratio and amount of traffic, take between 3 and 14 hours of training on 4 cores of an Intel Xeon Gold 6230 CPU. For FieldLines, the first five iterations are warm-start iterations. In these iterations, we replace the actions sampled during rollout by the ones suggested by the EIGRP baseline. We train MAGNNETO on 8 random link weight initialization seeds as per their protocol (Benáárdez et al., 2023), using their fluid-based environment and PPO implementation. The performance values presented in this work are obtained by taking the mean over 100 evaluation episodes, except for nx nx-XL for which we use 30 evaluation episodes. For the learned approaches, we exclude non-convergent runs by showing the performance of the belter-performing half of the used random seeds.
7 Results
We describe the results of our experiments in Sections 7.1
7.3 and discuss their implications in Section 7.4
10

---

Published in Transactions on Machine Learning Research (10/2024)
TCP/UDP, medium traffic
TCP, high traffic
TCP, very high traffic
ReldLines (ours)
M-Slim (ours)
FeeldLines
M-Slim
FieldLines (ours)
M-Slim (ours)
EIGRP
MAGNNETO
EIGRP
lours)
MAGNNETO
EIGRP
MAGNNETO
Received (f)
62.82MB
[91.), 62.77)
-1.1%
+1 062 17, 66.34
.. 1.36% 155.45, 12.351
106.06MB
(U0A 66, 107.34
1366.66 216-31)
+2.66%
.437% 19.42 108.2)
142.29MB
+0.67% [14242, (43.7)
[196722 A2)
42.76%
(124 66, 145
3355%
Avg. Delay (4)
9.94ms
-0.0%
-0. 14.94%
19.0
+2.08%
10.23ms
33.45%
110.5 10:171
-0.63%
+0.74%
10-31
9,99ms
-2 22.61%
-0.06%
-0.28%
Dropped (4)
2.14%
12.16 2240
+0.07%
(L.0.
12.08.2.971
7.42%
(5.66
0.52%
16.88.7
0.38%
17.13.0122
12.23%
(26.38.32.191
123.00 12.00)
01..64 12
-0.22%
Figure 6: Results on the nr-S topology preset with link failures. Cells show the mean values over 100 evaluation episodes in the first line, and min and max values across random seeds in the second line. Values and colors are relative to EIGRP. While all learned approaches can adapt to link failures, only approaches stay above EIGRP. When dealing with link failures, FieldLines favors lower-delay paths over higher goodput.
7.1 Learning to Route in PackeRL
In Figure 8 we report results of all evaluated approaches on the nr-XS topology preset. EIGRP slightly outperforms OSPF in all evaluated scenarios, which is the reason why we do not include OSPF in the remaining results, Furthermore, the two random policies perform significantly worse than all other approaches. Concerning the learned approaches, for MAGNNETO, unlike the results reported in Bernárdez et al. (2023), even the best run does not beat static shortest-paths routing. On the other hand, our policies M-Slim and FieldLánes provide routing performance that rivals EIGRP, with consistently lower average packet delays. Also, as further illustrated by Figure 4 both policy designs improve goodput and packet drop ratio for network scenarios with high-intensity and TCP-dominated traffic. Unlike Figure 3 each matrix of Figure ! displays the values of a single metric and a single approach, but over a grid of traffic setups of varying intensity and TCP ratio. This way, it becomes evident that the performance FieldLines and M-Slin relative to EIGRP improves for scenarios with intense and TCP-heavy traffic, and that learned particularly beneficial for such kinds of traffic. On the other hand, for scenarios with low traffic intensity, EIGRP is able to maintain slightly higher goodput.
RO is
7.2 Generalizing to Unseen Network Topologies
Figure 5 shows the results of evaluating above section's policies on the larger topology presets nu S, ne M, and nı nx-XL. Relative to EIGRP, MAGNNETO's performance stays inferior yet stable, but due to the excessive inference times depicted in Section 7.3 we did not evaluate it on topology presets larger than næ M. Interestingly, M-Slim is able to increase its goodput advantage over EIGRP with increasing network scale while maintaining solid values for other metrics. On the other hand, FieldLines's performance becomes more and more similar to that of the EIGRP baseline as the network scale increases.
New network topologies can also arise due to failure events. Figure G shows results on the nx-S topology preset with randomly generated link failures as described in Section A.6. All learned approaches are able to adapt in the face of one or more link failures. However, FieldLines and M-Slim seem to behave slightly differently upon registering a link failure: While FieldLines favorizes a lower average packet delay, M-Slim maintains goodput and instead gives away its delay advantage. In any case, both our policy designs drop less data after link failures in traffic-intense situations.
7.3 Simulation and Inference Speed
The left side of Figure 7 reports the mean inference time of the evaluated policies on the various network scales of the næ topology preset. MAGNNETO's optimization loop quickly leads to inference times of several seconds. The single-pass inference of M-Slim and FieldLines brings down inference time considerably, but for large networks the inference time of M-Slim exceeds one second because it requires an APSP pass every step. FieldLines, which only requires that when the topology changes, keeps its inference times in the millisecond
11

---

Published in Transactions on Machine Learning Research (10/2024)
Inference Time in (TCP, high traffic, log-scale)
Simulation steps hour (FieldLines, log-scale)
10000
10000
1M
1M
MAGNNETO
UDP, low traffic
M-Slim lours)
UDP, high traffic
1000
RieldLines (ours)
1000
100K
TCP, low
100K
TCP, high traffic
100
100
10K
10K
10
10
100
100
6-10 (nx-XS)
11-25
26-50
51-100
101-250
6-10
11-25
26-50
51-100 (nx-L)
101-250 (nx-XL)
(nx-M)
(nx-L)
(nx-XL)
(nx-X5)
(nx-5)
(nx-M)
Figure 7: Left side: Mean inference times per PackeRL step different network sizes. Our policies reduce the inference time required by MAGNNETO, which was not evaluated on larger topologics due to excessive inference times, by multiple orders of magnilude. Right side: Simulation steps per hour, including shared memory communication but excluding inference and learning times. Simulating TCP traffic PackeRL. is more costly than UDP traffic, and simulation speed depends on traffic intensity and network scale.
range for all evaluated graph scales. The right side of Figure shows that simulating TCP traffic PackeRL is more costly than UDP traffic, and that simulation speed depends on traffic intensity and network scale.
7.4 Discussion
The results shown in earlier parts of this section suggest several findings, which we will discuss in the following.
Firstly, the two random policies shown in Figure 3 perform notably worse than all other approaches. The performance of Random (NH) in particular is far off, since it does not check for routing path coalescence and thus frequently includes routing loops and detours in its actions. This shows that obtaining high-quality routing actions not a trivial task, and that using RL to learn to route is beneficial. Next, we note a contrast between the performance of MAGNNETO and M-Slim. While MAGNNETO performs worse than the static shortest-path baselines (EIGRP), M-Slim outperforms them in all scenarios except those with low-volume traffic. This shows that placing routing policy trained in fluid-based environment into packet-based one hurts performance, which is avoidable by directly training in packet-based environment like PackeRL. In general, both our RL-powered approaches outperform EIGRP in scenarios with more intense traffic. We assume that congestion events happen more frequently in these scenarios and that the dynamic routing provided by M-Slim and FieldLines can better deal with this challenge. We also note that the advantage over EIGRP slightly more pronounced for TCP-heavy traffic. This may be explained by TCP's sending rate adjustment. TCP actively probes for the maximum sending rate maintainable without loss of data. This likely leads to more congestion events, which in turn may be handled better by adaptive routing policy.
Section 7.2 suggests that all learned approaches can deal with link failures effortlessly and that they generalize to large topologies even though they have been trained on much smaller and/or random topologies. Interestingly, while M-Slim seems to maintain its relative advantage over EIGRP, FieldLines seems to prioritize maintaining low latency over maximum global goodput when faced with link failures. Also, we note that the advantage of FieldLines over EIGRP disappears with growing network topology size. possible explanation for the generalization behavior of FieldLines is indicated by the "Action Fluctustion" row of Figure It denotes the average percentage of next-hop decisions all routing and destination nodes rate that change between timestep and the next. Evidently, the action fluctuation is much lower for Fieldines than for M-Slim, which indicates that FieldLines changes its routing actions much less frequently. Figure 21 of the appendix provides an illustrating example for this difference. Moreover, as the network scale increases, the routing of FieldLines becomes even more static. We suspect that this is the reason why, with growing network size, FieldLines performance becomes more and more similar that of EIGRP. The performance reported for M-Slim in Figures and c suggests that re-optimizing routing less conservatively may further increase the performance of FieldLines. We hypothesize that, in order to increase the dynamicity of FieldTines
12

---

Published in Transactions on Machine Learning Research (10/2024)
for large network topologies, we will need to adjust the action selection mechanism used during training and/or evaluation. For now, given the larger inference times of M-Slim on large network topologies, choosing between M-Slim or FieldLines is currently a matter of trading routing performance for responsiveness.
8 Conclusion
This work highlights the importance of packet-level simulation environments for RI-cnabled routing optimiza- tion, together with policy designs that are trainable in such environments. Firstly, we show that a recently proposed approach trained in a fluid-based network environment fails to reproduce its training performance in packet-based simulation. Adapting the approach to the more realistic packet-based simulation setting negates the decline in performance and shows why packet-based training and evaluation environments are even needed. Our adaptation called M-Slim also cuts the time needed to re-optimize routing by one to two orders of magnitude, but still requires more than second for large network topologies. Our novel next-hop selection policy desigu FieldLines is the first of its kind that can oplimiie rouling within milliseconds for any network topology without the need for re-training. Finally, our evaluation setup demonstrates the versatility of our new packet-level training and evaluation framework PackeRL. It supports training and evaluating policies on a wide range of realistic network topologies and traffic setups, provides closed-loop simulation via its ns-3 network simulator backend, and facilitates a detailed analysis of RT-based approaches with respect to a handful of well-known performance metries. With the findings of this work, we hope inspire future rescarch on RL-enabled routing optimization, and provide few pointers in the following final subsection.
8.1 Future Work
We have demonstrated the usefulness of PackeRL only for single-path routing but not for multi-path routing. This is due to the absence of standard Multipath TCP (MPTCP) implementations for ns-3 or any other popular packet-level network simulatof [ As existing implementations of MPTCP for ns-9 are incomplete with respect to the official specification Nadeem & Jadoon 2019 of PackeRL to multipath routing for future work.
Ford et al. 2020 we leave the extension
In this work, for simplicity, we have evaluated the routing performance when optimizing for a single objective or a weighted sum of multiple components with fixed weights. But in different network scenarios, the relative importance of these metrics may vary. Further efforts may investigate the relative importance of the optimization components in different network scenarios and turn to Multi-Objective RL (Hayes et al. 2022 to train family of policies that provides better control over performance.
Despite the strong results of FieldLines, Section 7.4 has shown that its routing becomes increasingly static as network sizes grow, making it gradually lose its advantage. Figure 16 suggests that adding more message passing steps to the MPN module does not solve the problem on its own, but revisiting the action-selection mechanism used during the training of FieldLines may alleviate this issue. Furthermore, despite greatly reduced inference times, FieldLines still requires several ms to re-optimize routing. This does not influence routing in our experiments because we pause the environment during action selection as is commonly done in RL research. Long inference times may however degrade routing quality in the even more realistic setting where network operation would continue during action inference. Learning sub-sccond routing optimization with RL in such a soft real-time setting (Marchand et al., 2004) is an interesting and challenging avenue for further research, not least because hardware specifications will start to influence the routing results.
Finally, we note that the RL approaches considered in our experiments were trained and evaluated in a fully centralized manner. This raises the question: How do we account for the delays incurred by communicatig state information across the computer network? High-frequency RO policies may need to respect Age of Information (Aol) (Yates et al. 2021) when capturing and processing the network state. Here, redistributing routing control to the nodes could reduce the influence of AoI, as nodes may restrict the topological coverage of input and output to their neighborhoods. It is an open question whether such systems of networked agents can achieve efficient routing, and if so, how they should be designed and deployed. We believe that building on FieldLines' hop routing design can help to answer this question in future work.
&Consequently other recent. RO approaches like TEAL [u et
2023 can not yet be evaluated in packet-level simulation.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Broader Impact Statement
Automating computer networks promises to greatly increase operational efficiency and save costs through over-provisioning or manual configuration. Here, RI-powered RO may become cornerstone in autonomous computer networks. Other infrastructures like road networks or power grids may also benefit from this progress, given their structural similarity. Our work opens the door for future rescarch on automation for such kinds of systems. Anyhow, as for most RL application domains, misusing RL approaches in computer networks for malicions intents is conceivable. Specifically, the black-box nature of RI.-powered RO approaches can be abused to infiltrate the network's 's decision making, causing disturbances or loss of data if appropriate security measures are not taken. Furthermore, learned routing approaches may put certain kinds of traffic at an unnatural disadvantage order to optimize overall routing performance. In addition to mindful deployment by the network enginoers, RI-pooered networking components should therefore include safeguards against. the most common allack vectors.
References
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhileng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Tan Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Tlya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL attps://wwy tensorflow.c org/
Software available from tensorflow.org.
Mohammad Alizadeh, Tom Edsall, Sarang Dharmapurikar, Ramanan Vaidyanathan, Kevin Chu, Andy Fingerhut, Vinh The Lam, Francis Matus, Rong Pan, Navindra Yadav, and George Varghese. CONGA: Distributed rongestion-aware load balancing for datacenters. In ACM SIGCOMM Conference 2014, pp. 503-514, 514, New York, NY, USA, August 2014. Association for Computing Machinery. ISBN 978-1-4503--836-4. doi: 10.1145/2619283 261.422669939.2266666. URL pestps:/ddl. acm. www.m.orr///////...m 10..0..115/2221990 26266116
Benedikt Alkin, Andreas Fürst, Simon Schmid, Lukas Gruber, Markus Holzleituer, and Johannes Brandstetter. Universal physics transformers. arXiv preprint arXiv:2402.12965, 2024.
Redha A Alliche, Tiago Da Silva Barros, Ramon Aparicio-Pardo, and Lucile Sassatelli. PRISMA: A packet routing simulator for multi-agent reinforcement learning. In 2022 IFIP Networking Conference (IFIP Networkingg), pp. 1-6. TEFF, 2022.
Marcin Andrychowiez, Anton Raichuk, Piotr Stańczyk, Manu Orsini, Sertan Girgin, Raphaël Marinier, Leonard Hussenot, Matthicu Geist, Olivier Pictquin, Marcin Michalski, Sylvain Gelly, and Olivier Bachem. What matters for on-policy deep actor-critic methods? a large-scale study. In 8th International Conference on Learning Representations (ICLR 2020), October 2020. URL https://openrevier.. wttp:/iwww.e//ooummmmmmmm DiAxisniDzzá
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint 600600000000.....0 2016.
Albert-László Barabási. Scale-free networks: A decade and beyond. Science, 325 (5339)) 2009.
Theophilus Benson, Aditya Akella, and David A Maltz. Network traffic characteristics of data centers in the wild. In ACM SIGCOMM Internet Measurement Conference (IMC'10), pp. 267-280, 2010.
Guillermo Bernárdez, José Suárez-Varela, Albert López, Xiang Shi, Shihan Xiao, Xiangle Cheng, Pere Barlet-Ros and Albert Cabellos- Apariiio.. MAGNNETO: A graph neural network- baasork-based multi-agent system for traffic engincering. IEEF Transactions on Cognitive Communications and Networking, pp. 1-1, 2023. ISSN 1332-7731. doi: 10.11099TTCC..22288.2. wiki/MAGNNENT TE
URL htttps://giii wwwp:hhwww..ooun//tttuteee
14

---

Published in Transactions on Machine Learning Research (10/2024)
Sai Shreyas Bhavanasi, Lorenzo Pappone, and Flavio Esposito. Routing with graph convolutional networks and multi-agent deep reinforcement learning. In 2022 IEEE Conference on Network Funclion Virtualization and Software Defined Networks (NFV-SDN), pp. 72 77, November 2022. doi:
2022.9974607.
Jeremy Bogle, Nikhil Bhatia, Manya Ghobadi, Ishai Menache, Nikolaj Bjorner, Asaf Valadarsky, and Michael Striking the right Proceedings of the ACM Special Interest Group on Data Communication, pp. 29-43. Association for Computing Machinery, 2019.
Schapira. TEAVAR:
balance in WAN traffic engineering. In
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličkovié. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXto:2104.134 2021.
Alexander Brundiers, Timmy Schüller, and Nils Aschenbruck. On the benefits of loops for segment routing traffic engineering. In 2021 IEEE 46th Conference on Local Computer Networks (LCN), pp. 32-40. IEEE, 2021.
Gustavo Carneiro, Pedro Fortuna, and Manuel Ricardo. Flowmonitor: A network monitoring framework for the network simulator 3 (ns-3). In 4th International ICST Conference on Performance Evaluation Melhodologies and Tools (VALUETOOLS pp. 1-10, 2009.
Bo Chen, Di Zhu, Yuwei Wang, and Peng Zhang. An approach to combine the power of deep reinforcement learning with graph neural network for routing optimization. Electronics, 11(3))368, January 2022. ISSN 2079-9292. doi:
Jiawei Chen, Yang Xiao, and Guocheng Lin. RIANET++: packet-level network simulation framework for drl-based routing algorithms. In 8th IEEE International Conference on Network Intelligence and Digital Content (IC-NIDC 2023), pp. 248 253. IEEE, 2023.
Marco Chiesa, Guy Kindler, and Michael Schapira. Traffic engineering with equal-cost-mmllipathe An algorithmic perspective. JEEE/ACM Transactions on Networking, 25(2):779-783 2016.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Fourth Edition. MIT Press, 2022. ISBN 9780262046305.
Wesley M. Eddy, RFC 9293:
Transmission control protocol (TCP), 2022.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 5(1):17-60, 1960.
Aian Farrel. Overview and principles of internet traffic engincering. Roquest for Comments RFC 9522, Internet Engineering Task Force, January 2024. URL https://datttraaeerreettt ietf http://ccrrr..eet..rrrr/////aaaa
Miquel Ferriol-Galmós, Jordi Paillisse, José Suárez-Varela Krzysztof Rusck, Shihan Xiao, Xiang Shi, Xianglc Cheng, Pere Barlet-Ros, and Albert Cabellos- Aparicio. RouteNees-Fermi: Network modeling with graph neural networks. JEEE/ACM Transactions on Networking, pp. 1-0, 2023. ISSN 1558-2566, doi: 10.1109/ NTTTT2222..36099.
Alan Ford, Costin Raiciu, Mark J. Handley, Olivier Bonaventure, and Christoph Paasch. TCP extensions for multipath operation with multiple addresses. RFC 8684, 2020. URL https://www.wtt. rfc- http:///wwwwffoioorrroo.ommo org/
info/rfc8634
Niklas Freymuth, Philipp Dahlinger, Tobias Würth, Simon Reisch, Luise Kärger, and Gerhard Neumann. Swarm reinforcement learning for adaptive mesh refinement. Advances in Neural Information Processing Systems 2024 (NeurIPS '24), 36, 2024.
Thomas M. J. Fruchterman and Edward M. Reingold. Graph drawing by force-directed placement. Software: Practice and Experience, 21(11):1129-11 1164, November 1991. ISSN 00380644, 1097024X. doi: 10.1002/spe. 4380211 102.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Qiongxiao Fu, Enchang Sun, Kang Meng, Meng Li, and Yanhua Zhang. Deep Q-Learning for routing
schemes in SDN-based data center networks. IEEE Access, 8:103491-1034990 2020. ISSN 2169-3536. doi: ACCESSC
Steven Gay, Renaud Hartert, and Stefano Vissicchio. Expect the unexpected: Sub-second optimization for segment routing. In IEEE Conference on Computer Communiccations (INFOCOM 2017), pp. 1 May 2017a. doi: 1LL109/XFOCCOM.200..66666
Steven Gay, Pierre Schaus, and Stefano Vissicchio. REPETITA: Repeatable experiments for performance evaluation of eagfic-engineering algorithms. arXic preprint arXiv:1710. 08665, 2017b.
Phillipa Gill, Navendu Jain, and Nachiappan Nagappan. Understanding network failures in data centers: Measurement, analysis, and implications. In ACM SIGCOMM Conference 2011, pp. 350 361, 2011.
Justin Gilmer, Samuel S. Schocnholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quanturn chemistry. In 34th International Conference on Machine Learning (ICML 2017), pp- 1263- 1272. PMLR, 2017.
Yingya Guo, Yulong Ma, Huan Luo, and Jianping Wu. Traffic engineering in shared Inter-DC WAN via deep reinforcement learning. IEEE Transactions on Network Science and Engineering, 944):2870-288) July 2022. ISSN 2327-4697. doi: 10.1109/NN9::202.317722
Sangtae Ha, Injong Rhee, and Lisong Xu. CUBIC: A new TCP-friendly high-speed TCP variant. ACM SIGOPS Operaling Systems Review, 42(5):64-77 74, 2008.
Aric Hagberg, Pieter J. Swart, and Daniel A. Schult. Exploring network structure, dynamics, and function using NetworkX, 2008. URL htttps://witt wwt.:.ossiiggoo Betel_.goo/bbbbio/666611
Frank Harary and Robert Norman. Some properties of line digraphs. Rendiconti del Circolo Motematico di Polermo, 9:161-168, 1960.
Conor F. Hayes, Roxana Rädulescu, Eugenio Bargiacchi, Johan Källström, Matthew Macfarlane, Mathieu Reymond, Timothy Verstracten, Luisa M. Zintgraf, Richard Dazeloy, Fredrik Heintz, et al. A practical guide to multi-objective reinforcement learning and planning. 21th Conference on Aulonomous Agents and Multiagent Systems (AAMAS 2022), 36(1):26, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 29th IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016), pp. 770 778, 2016.
Thomas R. Henderson, Mathicu Lacage, and George F. Riley. Network simulations with the ns-3 simulator. SIGCOMM Demonstration, 14(14):527, 2008.
Pieter Hintjens. ZeroMQ: Messaging for Many Applications. O'Reilly Media, 2013.
Wanwei Huang, Bo Yuan, Sunan Wang, Jianwei Zhang, Junfei Li, and Xiaohui Zhang. A generic intelligent routing method using deep reinforcement learning with graph neural networks. IET Communications, 16 (19):2343 2351, 2022. ISSN 1751-8636. doi: 10.1049/cmm2..24877 URL https:///onlnnnnlbrrrryy... wwlly com/doi/abs/10. 1049// cmu2. 12487
Changhoon Kim, Anirudh Sivaraman, Naga Katta, Antonin Bas, Advait Dixit, Lawrence J. Wobker, et al. In-band network telemetry via programmable dataplanes. In ACM SIGCOMM Conference 2015, volume 15, pp. 1-2, 2015.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Simon Knight, Hung X. Nguyen, Nickolas Falkner, Rhys Bowden, and Matthow Roughan. The Internet Topology Zoo. IEEE Journal on Selected Areas in Communications, 1765)11753 October 2011. ISSN
1558-0008. doi: 10. 10.110//SAA.2201.11000
16

---

Published in Transactions on Machine Learning Research (10/2024)
Praveen Kumar, Chris Yu, Yang Yuan, Nate Foster, Robert Kleinberg, and Robert Soulé. YATES: Rapid prototyping for traffic engineering systems. In ACM Symposium on SDN Research (SOSR), pp- 1-7, 2018.
Xuan Mai, Quanzhi Fu, and Yi Chen. Packet routing with graph attention multi-agent reinforcement learning. In 2021 IEEE Global Communications Conference (GLOBECOM), pp. 1-6, December 2021. doi: 10. ///////OBBCCOA/100.0....
Audrey Marchand, Maryline Silly-Chetto, and Rue Christian Pauc. Dynamic scheduling of soft aperiodic tasks and periodic tasks with skips. In 25th IEEE Real-Time Systems Symposium Work-In-Progress Session, 2004.
Athina Markopoulon, Gianluca Iannaccone, Supratik Bhattacharyya, Chen-Nee Chuah, Yashar Ganjali, and Christophe Diot. Characterization of failures in operational IP backbone network. IEEE/ACM Transactions on Networking, 16(4):744-775 762, 2008.
Matt Mathis, Jamshid Mahdavi, Sally Floyd, and Allyn Romanow. RFC2018: TCP selective acknowledgement options, 1996.
Alaitz Mendiola, Jasone Astorga, Eduardo Jacob, and Marivi Higuero. A survey on the contributions of software-define networking to traffic engineering. IEFE Communications Surveys & Tutorials, 19(2): 918 953, 2016.
Albert Mestres, Alberto RodriiuuzzNNatl, Josep Carner, Pere Barlet-Ros, Eduard Alarcón, Marc Solé, Victor Mulnéés-uulero, David Meyer, Sharon Barkai, Mike J Hibbett, et al. Knowledge-defined networking. ACM SIGCOMM Computer Communication Review, 47(3):2- 10, 2017.
John Moy. OSPF Version 2. Request for Comments RFC 2178, Internet Engineering Task Force, July 1997.
URL httpp:://atatrraceer. wtt.::feetf.....coooooeeooooot org//oc/ff/2/1//
Kashif Nadeem and Tariq M. Jadoon. An ns-3 MPTCP implementation. In 14th EAT International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness (QSHINE pp. 48 60. Springer, 2019.
Sebastian Orlowski, Roland Wessaly, Michal Pióro, and Artur Tomaszewski. SNDlib 1.0 Survivable Network Design Library, Networks, 55(3):276 286, 2010. ISSN 1097-0037. doi: 10.1002/net.2037/ URL
httra:///omiimll..aarr......... wwwp://ycccom///oaaaa//000.....0 wttp:///.....///eee......00 20371
Adam Paszke, Sam Gross, Francisco Massa, Adamn Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, tigh-performanc deep learning library. Advances in Neural Information Processing Systems (NeurIPS '19), 32, 2019.
Tran Anh Quang Pham, Yassine Hadjadj- Aoul,, and Abdelkader Outtagarts. Deep reinforcement learning based QoS-aware routing in knowledge-defined networking. In Trung Q, Duong, Nguyen-Son Vo, and Van Ca Phan (eds.), Quality, Reliability, Security and Robustness in Heterogeneous Systems, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommuicatiooss Engineering, pp. 14-26, Cham, 2019. Springer International Publishing. ISBN 978-3-030-144133 doi: 10.10077/97--3-000-444111
2.
Pinyarash Pinyoanuntapong, Minwoo Lee, and Pu Wang. Distributed multi-hop traffic engineering via stochastic policy gradient reinforcement learning. In 2019 IEEE Global Communications Conference (GLOBECOM), pp. 1-6, December 2019. doi: 10.1109 (LL100/C...BEEO03337700000000000
Jon Postel. RFC 0768: User datagram protocol (UDP), 1980.
Matthew Roughan. Simplifying the synthesis of internet traffic matrices. SIGCOMM Compul. Commun. Rev., 35(5):93 96, October 2005. ISSN 0146-4833. doi: 01145/1096536.00880 URL https://aoi..rg/ 10. 10.1145/1096536.100
Alvaro Sanchez-Gonzaler, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovee, and Peter Battaglia. Learning to simulate complex physics with graph networks. In 37th International Conference on Machine Learning (ICML, 2020), pp. 8459 8468. PMLRR 2020.
17

---

Published in Transactions on Machine Learning Research (10/2024)
Donnie Savage, James Ng, Steven Moore, Donald Slice, Peter Paluch, and Russ White. Cisco's Enhanced Interior Gateway Routing Protocol (EIGRP). Request for Comments RFC 7868, Internet Engineering Task Force, May 2016. URL https: wwt.eeettett.ee...o.. org/doc/rfc7868
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. Xiv preprint arXiv:1707.063/ 2017.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation, October 2018. URL http://arxiv.. wrw../ggggao....
1506.02433
Luca Schumann, Trinh Viet Doan, Tanya Shreedhar, Ricky Mok, and Vaibhav Bajpai. Impact of evolving protocols and COVID-19 on internet raffic shares. arXiv preprint arXiw:2201.00143 2022.
Rob Sherwood, Glen Gibb, Kok- Kok-Kiong Yap, Guido Appenzeller, Nick Mckeown, and Guru Parulkar. Can the production network be the testbed? In 9th USENIX Symposium on Operating Systems Design and Implementation. (OSDI '10), 2010.
Bruce Spang, Serhat Arslan, and Nick McKeown. Updating the theory of buffer sizing. ACM SIGMETRICS Performance Fvaluation Review, 49(3):55- 56, 2022.
Neil Spring, Ratul Mahajan, and David Wetherall. Measuring ISP topologies with rocketfuel. SIGCOMM Comput. Comman. Rev., 13)433333314 August 2002. ISSN 0146-4833. doi:
URL
attpp://dl.aat acm. wwcm.oog//oi/1/////////o/ wtt.:/i.....111/111111 1145/964725 633039
Giorgio Stampa, Marta Arias, David Sanrhez-Charles, Victor Muntes-Muleroo and Albert Cabellos. A deep-reinforcement learning approach for software-defined networking routing optimization, September 2017. URT.
org/ wtt.aa////...000000 07080
Penghao Sun, Zehua Guo, Julong Lan, Junfei Li, Yuxiang Hu, and Thar Baker. ScaleDRL: A scalable deep reinforcement. learning approach for traffic enginecring SDN with pinning control. Computer Networks, 190:107891, May 2021. ISSN 1389- 1286. doi: (0006//.commet.222111777..
Mark Towers, Jordan K. Terry, Ariel Kwiatkowski, John U. Balis, Gianluca de Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Arjun KG, Markus Krimmel, Rodrigo Perez-Vicente Vicentee Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Andrew Tan Jin Shen, and Omar G. Younis. Gymnasium, March 2023. URL https://zenodo..ov wtt.://nww..o.reeeerr/////000000
Daniel Turner, Kirill Levehenko, Alex C Snocren, and Stefan Savage. California fault lines: Understanding the causes and impact of network failures. In ACM SIGCOMM Conference 2010, pp. 315 326, 2010.
Asaf Valadarsky, Michael Schapira, Dafna Shahaf, and Aviv Tamar. Learning to route. In 16th ACM Workshop on Hot Topics in Networks (HotNNtts 2017), pp. 185- 191, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 978-1-4503-5569- doi: 10.1 10.1145/31524844.1552
URL httpp://ddg
org/ 10. 101111141112220 3152434. 111444341154444115444111
Mowci Wang, Linbo Hui, Yong Cui, Ru Liang, and Zhenhua Liu. xNet: Improving expressiveness and granu- larity for network modeling with graph neural networks. In IEEE Conference on Computer Communications (INFOCOM 2022), pp. 2028 2037. TEFE, 2022.
Ning Wang, Kin Hon Ho, George Pavlou, and Michael Howarth. An overview of routing optimization for internet traffic engineering. JEEE Communications Surveys & Tutorials, 10(1):36 56, 2008. ISSN 1553-877X. doi: 10.1109 CO//SOCSTTTOO 200.2.040686.... 4483669.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684): 440-442, 1998.
Patrick Wendell and Michael J. Freedman. Going viral: Flash crowds in an open CDN. In ACM SIGCOMM Internet Measurement. Conference (IMC'11), pp. 649-558, 2011.
18

---

Published in Transactions on Machine Learning Research (10/2024)
Yang Xiao, Jun Liu, Jiawei Wu, and Nirwan Ansari. Leveraging deep reinforcement learning for traffic engineering: A survey. TEEE Communications Surveys & Tulorials, 23(4):2064 20977 2021. ISSN 1553-877X. doi: 10.1109/COMST 20D.ST.2222..0 3021000
Yang Xiao, Jianxue Li, Jiawei Wu, and Jun Liu. On design and implementation of reinforcement learning based cognitive routing for autonomous networks. IEEE Communications Letters, 27(1):205-20,) 2022.
Dahai Xu, Mung Chiang, and Jennifer Rexford. Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering. IEEE/ACM Transactions on Networking, 19(6):1717-1730, December 2011. ISSN 1558-2566. doi: 2..1099/NNTT.201111 2011.2134
Zhiying Xu, Francis Y. Yan, Rachee Singh, Justin T. Chiu, Alexander M. Rush, and Minlan Yu. Teal: Learning-acceleran optimization of WAN traffic engineering. In ACM SIGCOMM Conference 2023, pp. 378-393, New York, NY, USA, September 2023. Association for Computing Machincry. ISBN 9798400702365. doi: 10.1145 00444///603293360000
URL https: acm wwt.e/oggg///o//eeoeooooooooe/oo 01t.:/111111130099999903999
Qingqing Yang, Xi Peng, Li Chen, Libin Liu, Jingze Zhang, Hong Xu, Baochun Li, and Gong Zhang. Deepqueuenet: Towards scalable and generalized network performance estimation with packet-level visibility. In ACM SIGCOMM Conference 2022, pp. 441 441-457, 2022.
Roy D. Yates, Yin Sun, D. Richard Brown, Sanjit K. Kaul, Eytan Modiano, and Senmur Ulukus. Age of Information: An introduction and survey, IEEE Journal on Selected Areas in Communications,, 39(5): 1183-1210, 2021.
Hao Yin, Pengyu Liu, Keshu Liu, Liu Cao, Lytianyang Zhang, Yayu Gao, and Xiaojun Hei. ns3-ai: Fostering artificial intelligence algorithms for networking research. In Proceedings of the 2020 Workshop on ns-3 (WNS3), pp. 57 57-64, 2020.
Xinyu You, Xuanjie Li, Yuedong Xu, Hui Feng, Jin Zhao, and Huaicheng Yan. Toward packet routing with fully distributed multiagent deep reinforcement learning. IEEE Transactions Systems, Man, and Cyberneties: Systems, 52(2):855-868, February 2022. ISSN 2168-2232. doi: D0.109/TSMC.220033112333
Chiyuan Zhang. Oriol Vinyals, Remi Munos, and Samy Bengio. study on overfitting deep reinforccment learning. Xiv preprint arXiv:180. (at.:1804.68999 2018.
Qizhen Zhang, Kelvin K. W. Ng, Charles Kazer, Shen Yan, João Sedoc, and Vincent Liu. MimicNet: Fast performance estimates for data center networks with machine learning. In ACM SIGCOMM Conference 2021, pp. 287-304, 2021.
Hao Zheng, Zhanlei Yang, Wenju Liu, Jizhong Liang, and Yanpeng Li. Improving deep neural networks using softplus units. In 2015 International Joint Conference on Neural Networks (IJCNN), pp. 1-4. IEEE, 2015.
Hubert Zimmermann. OSI Reference Model the ISO model of architecture for open systems interconnection. IEEE Transactions on Communications,, 28(4):425 432, 1980. doi: 10.1109/TCOM.19980 109.0000000000019777777222
19

---

Published in Transactions on Machine Learning Research (10/2024)
A
PackeRL: Framework Details
Apsiigis,
JONSANTON Atlloy
Scenarlos
synnet
10. B1R
PackeriEnv (python)
ns3-ai
PackerlEnv (CH+
will
actions coard aqrvv
Learning
Loup
OddRouting
1
2
Figure Left: Structural overview of PackeRL. Right: Example 3-node network setup in ns-3 incl. applications (red boxes) and Internet Stack (blue boxes).
A.1 Network Structure and Simulation in ns-3
Networks in ns-3, by default, consist nodes and links/connections between nodes, as illustrated in Figure g For modeling simplicity, we limit ourselves to connected network topologies that hold full-duplex Point- to-Point (P2P) connections transmilting data error-free and at a constant pre-specified datarate. Nodes themselves do not generate or consume data; Instead, applications are installed on nodes that generate data destined for other applications, consume the data that is destined for them (red boxcs in example network nodes in Figure 8 To transport data between nodes install an Internet Stack on top of each node, adding TP and TUP/UDP components in way that mimics the OST reference model (Zimmermann) 1980 Also, nodes do not put data on the P2P link themselves, or read data from it. This is done by the network devices (rectangles attached to the nodes in Figure S that belong to a P2P connection, which are installed as interfaces on the two nodes that are being connected. Upon installation of the Internet Stack, the P2P connection between two nodes assigned an 1Pv4 address space, with concrete IPv4 addresses given to the incident network devices.
A.2 PackeRL's Online Interaction Loop
PackeRL uses a two-component Python/C++4 enviromment, with inter-component communication realized by shared memory module ns3-ai. The Python component provides a Gymnasium-like interface to the learning loop, while the C++ component is wrapper and entry point for simulations in ns-3. Initially, the Python environment starts instance of its C++ counterpart in subprocess, providing general simulation parameters fc.f. Section B.1 and network scenario generated with synmel. The C++ environment enters its simulation loop and first installs the network topology in ns-3: It configures nodes, links and network devices accordingly, as well as a TCP and UDP sink application per node. Then, it starts the ns-3 Simulator that runs the actual simulation steps. The initial network state Sp communicated from the C++ component to the Python environment. Within the episode loop, the Python part provides the current network state S, learned baseline policies, and communicates the routing action a, the C++ component alongside the upcoming traffic and link failure events. Source applications are then created according to the upcoming traffic demands, with sending start times set to the respective demand arrival times. For TCP traffic demands, the source application attempts to send its data as quickly as possible, and we use ns-3's default TCP CUBIC (Ha el al.) 2008)) to modulate the actual sending rate. Nole that we currently do not. support TCP Selective Acknowledgement (SACK) (Mathis et al. 1996) due to a presumed bug in ns-3 that causes simulation crashes. For UDP traffic demands, we use the sending rate provided by the scenario as explained in Section A.6 The provided routing actions are installed described in Section A.3 Next, using the Simulator ns-3 simulates the installed network for duration of Tsim: The installed source applications
20

---

Published in Transactions on Machine Learning Research (10/2024)
(one per traffic demand) send data to the specified destination nodes as configured, which gets wrapped into TP packets as they enter the routing plane. The RP that has been installed with the Internet Stack fills each node's i routing table and performs lookups when outgoing or incoming IP packets arrive, forwarding these packets to the specified noxt-hop neighbor or locally delivering them to the sink applications. Each node has a TCP and UDP packet sink. After having simulated for a duration of Taim, the C++ component pauses the simulation and obtains the network state St+1 for the completed timestep t. It communicates S1+1 to the Python component that uses it to obtain Tr. After H timesteps, the episode is done and the Python environment component sends a done signal to the C++ subprocess, which in turn ends its simulation loop and concludes the subprocess.
A.3 Installing and Using Routing Actions in ns-3
Routing in computer network involves two primary tasks: determining the best paths and forwarding the packets along these paths. For the latter, routers keep a set of routing rules in their memory. Each rule specifies a next-hop neighbor lo which packets with a certain destination are to be forwarded. This rule set- also known as a routing table gets populated by the installed RP, and we adopt this mechanism for our work. Most contemporary IP networks employ destination- finding the routing table entry that matches the packet's 's destination address, and sending the packet to the next-hop neighbor specified in that entry. As mentioned in Section B we adopt the commonly used forwarding mechanism using routing tables stored in the router's memory that may get updated by the RP. Therefore, regardless of the routing action's representation, we need to convert it into a set of routing table rules for each concerned routing node, where each rule contains a next-hop neighbor preference for a given destination node. We do the conversion prior to placing the actions into the shared memory module on the Python side. On the C++ side, the OddRouting module serves as a drop-in replacement for other routing protocols like OSPF that allows the installation of the provided routing next-hop preferences onto the network nodes. Since not all node pairs in a network necessarily communicate with each other, the OddRouting module stores the received routing preferences in a separate location on the routing node, and only fills the nodes" routing tables on-demand once a packet arrives at node for which no suitable routing rule exists in its routing lable. All subsequent packets destined for the same target node will have access to the newly installed table entry until the start of a new timestep, when new routing preferences will be stored in the node and its routing table will be flushed. Otherwise, OddRouting resembles the other IPv4 RPs implemented in ns-3, leveraging the line-speed capability of the forwarding plane.
routing, i.c. routers forward packets by
A.4 Network Monitoring in ns-3
In order to efficiently obtain the state of the computer network, we utilize the Tn-Band Network Telemetry capabilities provided by ns-3's FlowMonitor module (Carneiro al. (200)). It utilizes probes installed on packets to track per-flow statistics such as traffic volume, average and maximum packet delay, and nodo-level routing events down to the IP level. We use this information to obtain TMs of packets/bytte byttts////ee/eee sent and received (for visualization and the MAGNNETO baseline), as well as global average/ perragg/maximmm packet delay and node-level traffic statistics that form part of the monitored network state S. Moreover, our network topology is modeled as a graph with edges that consist of physical connections between network devices installed on nodes. FlowMonitor for does not capture queueing and drop events happening on the network device level, and we therefore also report events happening in network devices and channels obtain edge-level information on link utilization, packet buffer fill, and bytes/packett packets sent/r /tt////ecee///eeeee/ee /dropped. Since the P2P connections are full-duplex, we model the network monitoring a directed graph where an edge of the original network topology is replaced with one edge in cach direction. These directed edges contain the state of the respective sender device, i.e. edge (u, contains packet bulfer load, link utilization and traffic statistios for traflic buffered in u flowing to e. At the end of a timestep t, Se holds global, node and edge features that reflect the overall network performance and utilization during timestep f, as well as its load state at the end of timestop t. For the edges, we add their datarate, delay and packet buffer capacities to the list of features. For the initial state So, all utilization and traffic values are set to zero.
21

---

Published in Transactions on Machine Learning Research (10/2024)
Hast
11
12
20
Epsodes
13
2
Link fallures
Figure 9: Visualizations of graph scenarios. Left: Link failure distribution across episodes for nu-s with link failures. Center: NSFNet as used by MAGNNETO. Right: GEANT2 as used by MAGNNETO. Note that node positions for visualization the visualizations shown here may differ from related work.
not provided by MAGNNETO for NSFNet2 and GEANT2, and therefore
A.5 synnet: Generating Network Topologies
Network topologies vary greatly depending on the scope and use case of the network. For this work, we orientate our scenario generation towards the topologies spanned by the edge routers that connect datacenters in typical Inter-Datacenter Wide Area Networks (Inter-DC WANs). These are usually characterized by loosely meshed powerful edge routers and high-datarate medium-latency links that connect two such routers each. While we also employ link delay values the low ms range, we scale down typical datarate values for Inter-DC WANs to lie in the high Mbрs range, to speed up simulation times under stress situations without loss of generality of the simulation results. For simplicity, we sct the packet buffer sizes of network devices incident to P2P connections to the product of link datarate and round-trip delay, which is common throughout the networking literature (Spang et al. 2022
To generate random network topology graphs, we use the ER model Erdós et al. 1960 and the WS model (Watts & Strogatz] 1998), and, up to 50 nodes, the BA (Barabási 2009) model. All models are available via NetworkX graph analysis package (Hagberg et al., 2008). Figures I0 and II show examples for such random topology graphs. In any case, nodes and edges are assigned unique integer IDs for identification purposes. To add the missing datarate and delay values to the links, follow the following steps:
1. We first embed the random graph into a two-dimensional plane using the Manteerrman--einnggge force-directed algorithm (Fruchterman Reingold 1991] to create synthetic positional information for the random graph's nodes, similar to the position information provided for nodes related network datasets (Orlowski et al., 2010 Knight
2011 Spring al. 2002).
The resulting positional layout is centered around the two-dimensional point of origin, which we use to obtain location weights per node that are inversely proportional its distance the origin. We scale the location weights Wp to lie in [1, ".
3. We obtain degree weights wa from the array of node degrees scaled to lie in [1, W.m.aa
4. We obtain node traffic potentials c' = Aewa + (1 Xe) p by using a weight tradcoff parameter Xe: and normalize them by dividing by the max value to obtain normalized node traffic potentials
22

---

Published in Transactions on Machine Learning Research (10/2024)
Figure 10: Examples of 10-node network topologies generated with NetworkX. Bigger nodes indicate higher node weights, thicker edges indicate higher edge weights. Columns from left to right (2 examples each): Barabási-Albert (BA), Erdös-Rényi (ER), Watts-Strogatz (WS).
Figure 11: Examples 25-node network topologies generated with NetworkX. Bigger nodes indicate higher node weights, thicker edges indicate higher edge weights. Columns from left right (2 examples each): BA, ER, WS.
23

---

Published in Transactions on Machine Learning Research (10/2024)
5. The edge delay values are obtained by calculating the euclidean distance between the adjacent nodes, randomly perturbing them by &rand and rescaling them to average Máclay with a minimum delay value of 1 ms.
6. The datarate values per edge (i,j) obtained by taking the greater of the incident nodes' traffic potentials a and cj; randomly perturbing it by fannd and rescaling it to lic in the pro-specified interval of minimum and maximum datarales [Uminn Umax
A.6 synnet: Generating Traffic and Link Failure Events
Our process to generate flow-level traffic is inspired by reported traffic characteristics of real-world data centers [Benson al. 2010
1. Inspired by gravity TMs (Roughan 2005), we generate 'traffic potential matrix' B cc" and randomly perturb its values by Grand- Its values bi describe the expected (not actually measured) relative traffic intensity between each source-destinttion node pair i,j and will be used for the upcoming demand gencration. Diagonal entrics are set to to exclude self-traffic, mcaning that traffic demand generation is skipped.
2. We use a flow size tradeolf parameter Anow E [0, 1] to balance the frequency and size of arriving flows. Smaller values lead to more but smaller traffic demands, larger values lead to fewer but larger traffic demands.
3. In order to sample inter-arrival times between demands for each pair of nodes i, we log-logistic distribution with a fixed shape parameter & > O and a scale o; Ano parameter Marafiic depending on the evaluated task and class of graph topology. Starting from T = 0, we sample inter-arrival times for each node pair until we have reached the total simulated time scaled by traffic intensity r Tat (with H being the episode length, Tsim being the simulated time per episode step, and arrival times obtained via cumulative summation of inter-arrival times). Finally, we obtain the actual demand arrival times 7 < H1 per node pair i, by dividing the generated arrival times by bij capping at 50 ms.
marttto that uses a traffic scaling
For each generated traffic demand, we sample demand size using a Pareto distribution. It uses fixed scale parameter ag that also specifies the minimum demand size in bytes, and shape
8x Brpeee + log( Aow depending on shape base parameter Aruae that determines the tail weight of the demand size distribution. We cap the demand sizes at TB.
A fraction prcp [0. of the generated traffic demands is marked as TCP traffic demands, with the rest being marked UDP demands. While the simulation will try to finish TCP demands as quickly as possible and under the sending rate moderation of TCP, we assign constant sending rate of Gbps for UDP demands of less than 100 KB, and a constant sending rate drawn uniformly from [1,5] Mbps for all other UDP demands.
For creating link failure events, for each step of the episode, we obtain link failure probabilities from a Weibull distribution as explained in Section [B.3 and draw boolean sample for each edge that determines whether it will fail in the upcoming step. In order to maintain the connected-ness of the network topology, we then restrict the creation of link failure events to edges that are non-cut at the time of event.
24

---

Published in Transactions on Machine Learning Research (10/2024)
B Hyperparameters, Configuration And Defaults
The listed default hyperparameters and settings are used in all our experiments unless mentioned otherwise.
B.1 Simulation in ns-3
We set up the applications send data packets of up 1472 bytes, which accounts for the commonly used IP packet maximum Lransmission unit of 1500 bytes and the sizes for the IP (20 bytes) and ICMP (8 bytes) packet header. UDP packets thus are 1500 bytes large, whereas TCP may split up data units received from the upper layer as required. We set the simulation step duration Taim to 5 ms and make each episode last H = 100 steps, simulating a total of T = 500 ms per episode.
B.2 synnet: Topology Generation
For the BA model use attachment count of 2, and stop using the BA model altogether for networks above 50 nodes kurtosis of the node degree distribution becomes too high at that point. For the ER model set the average node degree to 3, and for the WS we choose rewiring probability of 30% and an attachment count of 4. For a deterministic positional embedding of the graphs' nodes via the Fruchterman -eiiterroaa-Reigooldd forco-directed algorithm, we set its random seed to 9001. We set the maximum node location weight upmax and the maximum node degree weight Wdaaa 10, and use a weight tradeoff parameter of A 0.6. We use base average edge delay value Mdelay of 5 ms, minimum and maximum edge datarate values of Umin 50e6 and Umax 200e6, and a random perturbation of 6rand 0.1 (i.e. random perturbation by up 100%).
B.3 synnet: Traffic and Link Failure Event Generation
For random perturbation, we again use 6rand = 0.1 (i.e. random perturbation by to 10%%.. The flow size tradeoff parameter Asow set to 0.5, the demand interarrival time distribution shape parameter 3 is set to 1.5, the demand size distribution scale parameter as set to 10 (i.c. demands are at least. bytes), and the distribution shape base parameter is to 8. 0.4. As per Bogle al. (2019), we model link failure probabilities per simulated step Weibull distribution (X k), using shape parameter À 0.8 and scale parameter k 0.001. Figure 12 iillustrates the resulting probability distributions for traffic demands and link failures.
0.9986
0.9993
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
10us
100
1ms
10
10
100
1K
10K
100K
1M
10M
100M
1G
Figure 12: Cumulative probabilities for demand interarrival times (left, log-logistic distribution) and demand sizes in bytes (right, Pareto distribution). The red points at the end of the curves denote the cumulative probability at 50 ms and GB.
25

---

Published in Transactions on Machine Learning Research (10/2024)
B.4 Monitoring Features
The following fealures are monitored in our ns-3 simulation:
maximum link utilization (maxLU e [o, 1]), average datarate utilization avgTDU [0,1], average packet delay avgPacketDelay e IRt, maximum packet delay maxPacketDelay Rt, average packet jitter avgPacket.Jitter& Rt, globally sent/receit
global:
bytes in No.
edge: link utilization LU E [0, 1J, maximum relative packet bulfer fill txQueueMaxLoad [0, relative packet buller fill at end of simulation step txQueueLastLood [0, 1], packet buffer capacity in N+, channel datarate and delay in N+, hwwreceiiee//dooppeeeee bytes in No.
node: http://cciieed/rrraannnnin
byles in No-
By default, we do not use the node features in our experiments. This is because our feature ablation in Section C shows that including this information globally and on an edge level is enough and leads to the best performance. Consequently, for our experiments we have dy 9, dg 10 and dy 0 for the monitored network state Gt- Also, normalize all input features akin to (Shhulman al. (2017). Finally, stack the four latest observations (S,-3, S1-, S.-1, using valoevalue padding.
B.5
OSPF and EIGRP Weight Calculation
The default calculation formula for OSPF link weights is
OSPF
weight(e) = v(C)
where v(e) denotes the datarate value of link and the reference datarate value vOOPP is set to 10 (Moy 1997). For EIGRP link weights, we use the classic formulation with default K-values, which yiclds
EIGRP ref v(e)
d(e)
weight(e) 256
EIGRP
where d(e) denote the delay value of link e, the reference datarate value BIGRP is set 10" and the reference eef delay value dEIGRP is set to 10 (Savage al. 2016). The two routing protocols use the link weights to dee
compute routing paths using the Dijkstra algorithm.
B.6 Line Digraphs
For directed graph G = E), its Line Digraph (Harary & Norman 1960) G' = P) is obtained by taking the original edge set E as node set, and connecting all those new nodes that, as edges in G, form a directed path of length two: P {(uu, v), (w, [u), v), (w,x) x) E E, U, w]..
Both MAGNNETO and our adaptation M-Slim operate on the Line Digraph of the network state S.. This means that edge input features like LU and past link weight are provided as node features in St and that M-Slim outputs link weight values node features.
B.7 PPO
Given the episode length // 100, each training iteration of 16 episodes by default uses 1600 sampled environment transitions to do 10 update epochs with minibatch size of 400. We multiply the value loss function with factor of 0.5, clip the gradient norm to 0.5 and use policy and value clip ratios of 0.2 per Schulman et al.] (2018). We use a discount factor of y 0.99 and use XGAE 0.95 for Generalized Advantage Estimation (Andrychowicz et al. 2020). We model the value function baseline that Proximal Policy Optimization (PPO) uses for variance reduction as separate network that is defined analogous to the respective policy, but uses mean over all outputs provide a single value estimate of the global observation. While MAGNNETO implemented and trained in Tensorflow (Abadi et al., 2015),, its PPO algorithm uses the same scaling and clipping parameters except. for additional entropy loss mixin of 0.001.
26

---

Published in Transactions on Machine Learning Research (10/2024)
B.8 Policy Architectures and Implementation
The original implementation of MAGNNETO uses an MPNN design (Gilmer et al. 2017 implemented in Tensorflow that consists of L 8 message passing layers described in Bernárdez et al. (0023]. Each layer uses 2-layer MLP with hidden size 128 and output size of 16 for the message processing function m(-), concatenation of min and max for the message aggregation operation Q and final node feature update h(-) that is realized by a 3-layer MLP with hidden dimensions 128 and 64. The base dimensionality of the feature vectors h2 is 16, meaning that every input and output of the MLP is of that size. At the start of inference, MAGNNETO uses vero-value padding to reach 16 dimensions since the input consists of only two features (LU and past link weights). After L message passing steps, final readout function yields the actions per edge. They specify which link weights should be incremented by onc. The readout function is implemented as 3-layer MLP with latent dimensions 128 and 64 and dropout layers with rate of 50% after the first two ML. layers. Except for the final readout layer, the weights for all MLP layers are initialized with an orthogonal matrix with gain of 22, and they are followed by a tanh(-) activation function.
Message Passing Network (MPN)
Embed
Message Passing Step (L x)
Global Update
Embed
Node Update
X²
Edge
Embed
Update
X
Figure 13: Illustration of the MPN architecture used in our routing approaches M-Slim and FieldLines.
For M-Slim and PieldLines, we use more compact policy architecture leveraging the MPN structure visualized in Figure 13 We use 2 message passing steps, the mean and min aggregation function in parallel for @ and Lea for all activation functions. Moreover, we apply layer normalization (Ba et al. residual connections (He et al. 2016) to node and edge features independently after each message passing. For all feature update blocks, we use MLPs with 2 layers and a hidden layer size of 12. In our experiments, the auxiliary distance measure provided to the readout of the FieldLines' actor module is the sum EIGRP link weights for the shortest path from to j. Finally, for the learnable softmax temperature To used during exploration by FieldLines's selector module vi, we use an initial value of 4. For the learnable standard deviation 0 M-Simm
2016) and
initial value of 1. We implement our policy modules in PyTorch (Paszke et al. 2019) and use the Adam optimizer with learning rate of 5e-5 (Kingma & Ba 2014 for FieldLines, and 3e-3 for M-Slim.
C Ablation Studies
In this section report results for additional experiments that represent ablation studics our policy design FieldLines. Except for Section C.4. all experiments are run on the XS topology preset. Default hyperparameter values are mentioned and explained in Section B We do the ablations on 8 random seeds each, and report results on the better half of them.
C.1 Learning Settings
Figure 14 shows results for learning hyperparameter ablations. The first two columns per matrix show results for different starting values for the learnable temperature parameter Tg- While a higher starting temperature does not significantly change performance, a lower starting temperature leads to inconsistent improvements and deteriorations across the metrics. The third and fourth columns per matrix show that a notably higher learning rate leads to a collapse performance, but also that an even lower learning rate is not needed because it does not improve performance. The last two columns show that a lower discount factor does not improve performance, while higher discount factor incurs minimal performance losses in intense UDP traffic.
27

---

Published in Transactions on Machine Learning Research (10/2024)
UDP, medium traffic
UDP, very high traffic
tau psi -1
tau pSi -7
alpha
alpha
gemma -0.97
garma -0.995
tau -1
tau_psi -7
elpha -1e-5
alphe -3e-4
gamma -0.97
gamma
-le-5
-3e-4
-0.995
Received (1)
-0.1%
0.0%
06% (53 $3.45M5)
0.066
0.05%
79%%
-0.7%% 01 43945
24 0698)
02200190
124.0596
114 00101
133 ASMB
101 46MB0
00 5140
Avg. Delay (4)
-0.15%
+0.00 00.04%
+0.155 16%
+1.14%
-0 0.08%
+0.01%
+0 00.05%
+0 1.1
+0 15%
+13, +13.18%
+0 +0.06%
+1.04%
Dropped (1)
-0.0%
-0.01% 10 L9N
-0.0%
0%00
00.05% (5 1891
7.% A3t0)
+0.07% 15 19.29
+0.16%
01 1491
(62440
10 18%
14h1
(5,000
15 UP9
(5.11%)
TCP, medium traffic alpha 51c.5
TCP, very high traffic
tau
tau psi
alpha =3c44
gamma -0.97
gamma -0.995
tau psl
tav psl
alpha -1e-5
aloha 4
gamma -0.97
gamma -0.995
Received (f)
+0.31%
-0. -.17%%
+00 1%
-7. 16%
+0.15%
+00 0.05%%
+0. 14%
+0 +0.03%
+0. 1..1%
-10 14%
+ +0.05%
-0.01%
Avg. Delay (4)
4.65% 01ikm
-017%
-3.17%
-0.1%
+0.02% (7 dimoo
-0.05%
23% M6 File
-0.07%
0.01%
17:7mml
(22009))
(731m0
0777mm
(148m)))
(1 (1:000))
[7.0819]
Dropped (1)
4.04%
0 0.0%
0.0%
+0.37%
-.00%
+0.01%
0..02
+0.01%
-0 0.0%
+2 9.95%%
0.0%
0.0%
Figure 14: Results for FieldT.ines on the no XS topology preset when training with different, learning hyperparameters as noted in the x-axis labels. The first row of each cell text displays results relative to the base sctting, i.c., FieldLines model using a 5c-5, & 0.99, and Tp initially set to 4. The second row of the cell text displays absolute numbers. Results show the mean values over 100 evaluation episodes.
C.2 Architecture Ablations
Figures 15 anc 16 shows results for architectural ablations on the FieldLines policy design. The first two columns of Figure 15 show variations on the latent dimension used by the MLPs within the MPN, which in our main experiments is set to 12. The numbers do not show a clear benefit of either a smaller or a larger latent dimension, but given the worse average delay for UDP traffic of lesser intensity, we keep the latent dimension of 12 even though for the evaluated scenarios a latent dimension of 6 may be enough. The last two columns show results when using either one of the minimum mean aggregation functions for the aggregation @ of the MPN's node feature update. The overall performances are very similar, such that using c.g. only the mean function for O to reduce complexity is conceivable. Concerning the depth of the used MPN architecture, Figure T6 shows that using I = 2 message passing layers provides the best overall results, but the best performing random seeds are very close across all MPN depths. Interestingly, for small graphs and high-volume UDP traffic as well as for larger graphs and medium-volume TCP traffic, average performance across multiple random seeds decreases for MPNs with more layers, because a growing number of seeds fails to converge properly. Also, the action fluctuation numbers show, adding more message passing layers does not solve FieldLines's problem of increasingly static routing for larger graph topologies.
permutation-invaateet
The M-Slim architecture used in this work is considerably smaller than the original MPNN architecture used for MAGNNETO (which is detailed in Section B.8p, since this further improves performance while further decreasing inference time. Figure 17 shows results for architectural ablations on M-Slim's policy architecture. The figure's M-Like column displays results of an M-Slim policy that uses the original MPNN- based policy architecture of MAGNNETO. While being worse than the default architecture for M-Slim, it still outperforms MAGNNETO clearly, particularly for TCP traffic. This demonstrates that most of the improvement is achieved by leveraging PockeRL's packet-level dynamics during training. Figure 17 also shows that reducing the number of message passing layers or the latent dimensionality further reduces inference times but compromises routing performance in some traffic settings. On the other hand, increasing the latent dimensionality or layer count increases inference time but does not improve routing performance.
C.3 Optimizing for Different Objectives
Recent deep RL-powered RO approaches optimize for varying objectives. For example, they have maximized throughput (Fu et a 2020), or minimized maximum LU (Bernárdez et al.) 2023 Chen et al. 2022). packet delay /latenyy Guo et al. (2022); Sun et al. (2021) or drop counts (Fu et al. 2020). Therefore, to assess the validity of our chosen reward function, Figure 18 presents results for Fnel on the nx-XX preset with
28

---

Published in Transactions on Machine Learning Research (10/2024)
UDP, medium traffic agg=mean
UDP, very high traffic
dim=6
dim=24
agg=min
dim
dim=24
agg=mean
agg=min
Received (1)
-0.02% (14.06MB)
-0.06% (14.05MB)
-0.1% (14.04MB)
-0.1% (14.04MB)
+0.4%
-0.09% (51.44M8)
-0.05% (51,46M6)
-0.03%
(51.69M6)
(51.47MB)
Avg. Delay (4)
+0. +0.7
+2.5%
-0.08%
-0.07%
-0 -0.45%
+0.03%
+0.02%
+0.69%
(7.33ms)
(7:14ms)
(7.14ms)
(8.23ms)
(8.27ms)
(8.27ms)
(8.33ms)
Dropped (4)
0.011%
00.01%
00.0%
-0.0%
-0.37%
+0.1%
+0.09% (3.22%)
+0.06%
(0.135)
(2.77%)
(3.19%)
TCP, medium traffic
TCP, very high traffic
dim==
dim=24
agg mean
agg min
dim=6
dim=24
agg mean
agg min
Received (1)
+0.32%
-0.05% (4B.23MB)
+0.09% (40.3MB)
+0.08% [48. (4M.29MB)
-0.0%
-0.0.3% (90.57MM)
+0.08% (90.67MB)
+0.05% (90 64MB)
(48.41MB)
(90.6MB)
Avg. Delay (4)
-0.18%
-0.23%
-0.23%
-0 -0.12% (7.21ms)
-0.03%
-0.05% (7 (7.48ms)
-0.66
-0.66% (7.48ms)
(7 (7.21mm)
(7.21ms)
(7.2m5)
(7.48m6)
(7.48ms)
Dropped (1)
+0.03% (2.81%)
+0.01% (2.79%)
+0.01%
+0.02% (9.84%)
-0.0% (9.82%]
-0.01 (9.81%5)
(2.77%)
(2.78%)
(9.83%)
Figure 15: Results for FieldLines on the nx-XS topology preset when training with policy architecture ablations as noted in the x-axis labels. The first row of cach cell text displays results relative the basc setting, i.., a PieldLines model using concatenation of min and mean aggregation and latent dimension of 12. The second row of the cell text displays absolute numbers. Results show the mean values over 100 evaluation episodes.
varying optimization objectives. We denote our default reward function describing global goodput in MB by r. Let the step-wise penalty function a describe the average packet delay in ms, function d the ratio of dropped bytes to dropped and received bytes, and function 1 the maximum LU observed in the past step. We can obtain multi-component reward functions by combining these functions. When combined with r, we scale the penalty functions by and by 0.25. We found these scaling factors by ensuring that. the values lie in the same order of magnitude, meaning that each objective is weighted roughly equally. Figure 18 shows the results per optimization objective, where rd, ra and rda denote the corresponding combinations. Optimizing for the drop ratio (d) decreases the drop ratio slightly but may lead to compromises in the other metrics. In turn, optimizing for packet delay (a) yields lower delay values, but at the expense of goodput. Interestingly, optimizing solely for LU (1) works well in UDP-only traffic, but collapses when dealing with TCP traffic. Finally, the results show large improvements average delay and drop ratio for the composite optimization objectives in traffic-intense TCP situations, but otherwise show equal minimally worse performance, All in all, conclude that optimizing for global goodput alone is viable objective for our sctup. While composite optimization objectives can improve packet delay and drop ratio in some settings, they do not do so consistently and thus do not warrant the additional complexity introduced by multi-component optimization.
C.4 Training Different Topologies
Furthermore, investigate how the choice of training topologies affects FieldLines' routing performance. For this, we evaluate three models on the na-S topology preset that have been trained on different topologics. In addition to the default model which is trained on nr-XS, we train model on nz-S and another on just the two topologies NSFNet and GEANT2, configured in the same way as in Bernárdez et al. (2023). Figure [9 shows that training on just NSFNet and GEANT2 yields minimally worse results, implying that covering wide range of different network topologies in the training procedure may be beneficial. On the other hand, training larger topologies does not improve performance and is therefore not preferred due to longer training times (up to 37 hours to simulate the same amount of training steps).
29

---

Published in Transactions on Machine Learning Research (10/2024)
UDP, medium traffic 6-10 nodes
UDP, medium traffic 11-25 nodes
UDP, medium traffic 26-50 nodes
L=2
L-1
L-33
L
L=2
L=1
L-3
L=4
L-2
L=1
L=3
L=4
3.65%
.012%
21:253
0.16
89%
1.95%
+0,07%
d1 160
19.12%
+0.04%
1.17%
0..5%
+0.16% 210
Received (t)
13.91MB
0.01%
0.0
0.0%
31.99MB
0.02%
0.0%
19 32m
0.0%
57.43MB
0.01%
0.0%
0.0%
Avg. Delay (4)
7.11ms
10,85% 1331
+1.18%
10.20ms
130.25 30.4
+0.07%
19.05%
1628.30.25
13.4ms
122 23431
+0.01%%
10.17%
Dropped
0.13%
036
.0.1%% ILOR C30)
0.1%
12.0 5.0
00.6% B31
0.07%
18.0 637
12 sam
0.0%
UDP, very high traffic 6-10 nodes
UDP, very high traffic
UDP, very high traffic
11-25 nodes
51-100 nodes
L-2
L-1
L-3
L-4
L-2
L-1
L-3
L-4
L-2
L-1
L-3
L-4
Action Fluctuation
4.35%
1244.8.00 5.06)
12.55. (3.55.5.71
14.13, 0443:
3.13%
11.35, 4.231
23 4.1
12/76
1.94%
18:55 1.20
00 1.00
00.5 1.
Received (t)
(51
00.02%
2 454
130.75
38.05%
.0.1 1..14%
115.31
n00 113.001
0.69%
1166) 711.8)
(27 308.44
.0.24%
0.32%
0.33%
197.59)
Avg. Delay (4)
8.16ms
-0.93%
+7 0%
+13.02%
12.18ms
-0.03%
+1 35%
+2 36%
21.76ms
+0.06%
0.00%
-0.22%
Dropped
2.76%
G- 14
18TA 57%
9.18%
15. (617
16.7 11.3
18.04%
13.07 36.30
OM PA
116 18.51
TCP, medium traffic 6-10 nodes
TCP, medium traffic 11-25 nodes
TCP, medium traffic
51-100 nodes
L-2
L-1
L-3
L=4
L-2
L-1
L-3
L=4
L-2
L-1
L-3
L=4
Action Fluctuation
4.23%
-0.6%% 11.4
12.0 2,89)
10.81%
(371
2.36%
-0.30% 0.10
1.63%
1836
(0.45
0.666
-0 -0.09% 1033
Received
48.6MB
MEX 12:27)
MEAT 16:01
2 76%
86.36MB
164.07MB
2
10.02%
Avg. Delay (4)
7.02ms
+0.05%
1155%%
+1 +1,43%
9.5ms
+0.11%
+0 11%
+0.50%
16.15ms
.0.0%%
0,39%
to
3.27%
Dropped (4)
2.7%
00.03%
+0.27% 12.86
3.39%
15.30
+0.3
+9.03% 15.38,345
4.1%
(43.
18% 5
6..6%%
TCP, very high traffic 6-10 nodes
TCP, very high traffic
TCP. very high traffic 51-100 nodes
11-25 nodes
L-3
L=2
L-3
L-2
Action Fluctuation
5.7%
+0.69%
-0.0%%
+0.02%
3.19%
-0.60%
-9.4%%
-0, -0.54%
0.93%
+0. 40.22%
-0.16%
-0 0..%%%
Received
91.28MB
in 48, 92.00
299 31.371
HHS. 11.41
154.63MB
(13 135.11
us4 135
cur 135.1
327.61MB
1328.3 353.34
+0.52%
1828.3
505
1935 336
Avg. Delay (4)
+2.49%
12.89%
.0.01%%
9.83ms
+1.29%
2571
50 12:20)
+1.81%
10.83%
26-301
115 16.00
+0.77%
115.23 18.301
10.65%
Drapped (4)
9.39%
+0 4%
41.51%
+0.01%
11.25%
+0.23%
+0 34%
12.33%
+0.13%
+0 15%
Figure 16: Results for FieldLines with different MPN depths, trained on the nr DS- topology preset and evaluated the nx-XS, nx-S and næ-L presets. Results show the mean values over 100 evaluation episodes. Overall, using L 2 steps yields the best results, but the best performing random seeds are very close across all MPN depths. Also, adding more message passing layers does not solve FieldTines's problem of increasingly static routing for larger graph topologies.
30

---

Published in Transactions on Machine Learning Research (10/2024)
UDP, medium traffic
UDP, very high traffic
M-Slim
dim-6
din-24
L-1
L-4
M-Ukke
MAGNNETO
M-Slim
dim-6
dim-24
L-1
L-4
M-Lkke
MAGNNETO
Received (?)
13.9MB
-0.0%
-0.01%
+3.02%
-0.01%
+0.01%
-0 -0.05%
52.02MB
-1.73%
-0.21%
-0.0%
-0.01%
-0.37%
-2.39%
1430
12501
5232
Avg. Delay (+)
7:15ms
0.04%
0.0%
0.08%
0.1%
0.06%
+1.62%
7.93ms
+2.49%
+0.58%
+0.2155
0.07%
-0.55%
+5.96%
(222-337)
0332 12h
0332 1371
0322.110 130
012 710
0133 17M
0.5.33%
(337
0351 033
0.55 750
055 0.01
2:40 9.10
Dropped (+)
+0.01%
+0.01%
-0.01%
-0.0%%
0.0%
2.14%
+1.57%
+0.19%
00.01%
+0.01%
+0.3%
+2.07%
12322
Inference Time (4)
11.32ms
-2.34%
+3.67%
21.33%
39.39%%
+7.05%
19009.579
11.41ms
00.1%%
14.18%
19.7%
+2.00%
7.12%%
18665 75%
1L.00
02.39
12:0
1372 9231
16.77
12.72 12.49
22389
02:35 31.90
(1:22 3233
18.4
16.7
02.78 12.51
120.5 227.33
TCP, medium traffic
TCP. very high traffic
M-5lim
dim-24
L-1
M-Uka
MAGNNETO
M-5lmm
dim-6
dim-24
M--ike
MAGNNETO
Received (?)
49.59MB
-2.54%
-0.36%
-1.41%
-0.53%
.0.72%
3 14%
92.81MB
-0.94%
10.08%
1.. 55.556
-0.24%
-0.83%
-0.21%
Avg. Delay (4)
6.94ms
+0.15%
+0.02%
+3.05%
0.01%
0.00%
+1.72%
7.43ms
0.25%
0.04%
+0.095%
0.05%
0.19%
+1.25%
11.54 1.911
5:51
6:01
0:50
09.0 1.531
744
17.3% 7441
1745
07.5
1.41
07.00 7:81
Dropped (-)
2.59%
9.58%
12.9..350 3.0
(2.3.2887)
2:44
03.1 2.81
0.44 2011
0/46 3:71
14.9% 13:33
18.4% 9-3)
18.45 4:501
(9:2 9:M
-2.97%
+5.3%
71%%
+42 43%
8.2
11908.949 945
-2,04%
+7.78%
11..33%
+45 85%
-12 25%
-1788.360
Inference Time (L)
11.6ms
11.85ms
Figure 17: Results for M-Slim on the næ XS topology preset with policy architecture ablations as noted in the x-axis labels. Results show the mean values over 100 evaluation episodes. Overall, the MPN design with default parameters that we use for M-Slim slightly improves performance and inference time over using the original MPNN policy architecture of MAGNNETO (column M-Like) explained in Section B.& Reducing the number of MPN layers or the latent dimensionality further reduces inference times but compromises routing performance in some traffic settings. In any case, the M-Slóm designs clearly outperform MAGNNETO especially for TCP traffic, showing the importance of packot-level dynamics in training.
UDP, medium traffic
UDP, very high traffic rd
1
rd
rda
1
rda
Received (t)
14.08MB
-0.2%
-1.33%
-0.22%
-0.0%
-0.0%
-0.0%
51.48MB
+0.1%
-16.51%
-0.01%
-0.03%
-0.03%
-0.44%
Avg. Delay (4)
7.13ms
+9.0%
-0.09%
+0.17%
+0.03%
0.0%
0.0%
8.24ms
-0.19%
-8.25%
-0.0%
+0.25%
+0.25%
+0.27%
Dropped (L)
0.14%
40.5%%
+0.96%
0.0%
0.0%
0.0%
3.11%
0.14%
+14.91%
+0.02%
+0.13%
+0.13%
+3.13%
TCP, medium traffic
TCP, very high traffic
1
rd
ra
rda
rd
ra
rda
Received (f)
48.31MB
-3.66%
99.21%
-100.0%
+0.11%
+0.05%
90.65MB
-0.33%
-100.0%
-0.18%
-0.18%
Avg. Delay (4)
7.23ms
-2.22%
-20.37%
-92.6%
-0.22%
-0.15%
+0.11%
7.48ms
-1.04%
118.93%
-84.4%%
-9.14%
9.29%
-481%
Dropped (L)
2.78%
.0.99%
-1.05%
+95.98%
0.0%
+0.01%
9.82%
-3.32%
+89.21%
-1.65%
-1.68%
-1.05%
Figure 18: Results for FieldLines optimized for different objectives. Results show the mean values over 100 evaluation episodes. Values and colors are relative to the default optimization objective r (optimizing for goodput). Letters d, and 1 denote optimization for drop ratio, average delay maximum LU respectively, and concatenated letters denote composite objectives. Optimizing for different objectives influences routing behavior, but no alternative for r improves performance consistently.
C.5 Feature Importance
Finally, Figure 20 shows results for FieldLines when restricting or adjusting the policy's access to some features. Overall, while the individual interactions between available features and policy performance are complex, the results generally show that all monitored global and edge features relevant to some extent, and that removing global or edge features generally decreases performance in some of the evaluated settings. Adding node-level sent s retransmilted features (first. two columns of the plot) does not improve performance, and in conjunction with a larger latent dimension leads to notable deterioration. Removing odge features, general, decreases performance in most scttings. Interestingly, some edge feature removals can come with improvements the average delay, and discarding edge features altogether is the next best approach. Concerning global features, all features are relevant. to some extent, but the combined removal of
31

---

Published in Transactions on Machine Learning Research (10/2024)
UDP, medium traffic
UDP, very high traffic
TCP, medium traffic
TCP, very high traffic
NSFNet +GEANT2
NSFNet +GEANT2
NSFNet +GEANT2
NSFNet +GEANT2
nx-S
nx-5
nx-S
nx-5
Received (1)
-0111% (30.33MB)
0.0% (30.36MB)
-0.26% (109:57MB)
-0.05% (109:0M6)
-0.0% (83.31M6)
+0.06% (63.37MB)
-0,27% (159.8MB)
0..1% (159.9MB)
Avg. Delay (4)
-0.1%
+0.07%
+ 6.%
+1.09%
+0.16%
+0.14%
+0.11%
+0.01%
(10.1ms)
ms)
(12.66ms)
(9.53ms)
(9.53ms)
(9.64ms)
(9.83ms)
Dropped (4)
-0.01% % (0.0595)
-0.0% (0.05%)
+0.17% (9.15%)
+0.05% (9.03%)
-0.0% (3.46%)
0.0% (3.46%)
+0.05% (11.48%)
+0.01% %
(11.43%
Figure 19: Results for FieldLines the nz-S topology preset when training on different topologies noted in the x-axis labels. The first row of each cell text displays results relative to the base seiting, i.e., a FieldLines model that is trained on nr-XS. The second row of the cell text displays absolute numbers. Results show the mean values over 100 evaluation episodes.
mntt/receivel//roopeall retransmittedd bytes and average delay and jitter, or the removal of global load features (link utilization and average datarate utilization) lead to the largest performance penalties. Interestingly, again, removing all global features mitigates a portion of the performance penalties observed when removing parts of the global features. Finally, removing both edge-level and global information about network load (LU and datarate utilization) results in severe performance penalties for UDP traffic, which is also the case information.
when restricting both edge and global features to sent/ reettt/eeevedd//eooooo pettropped/retrannninnn
UDP, medium traffic
al
al
esge
odge:
odge:
no SRD
edge:
dlebal 11 SNOR
global:
global load
no SRDR
global:
SRD:
SRD:
dmm-12
dim224
nu
cortly
no feed
1D curifig
TRIM
DJ
no D1
load
mode crlyaage maade load only
SRD only
no
Received (1)
4.0%
0.01%
0.29%
6.0%
DEN 13 (10M 1200
4.01%
0.0%
5.%
4.00%
0.01%
5.x
1.04 03.000
5.02%
0.0%
41%
01201 200011000 118011 17 S0MIAAS 12:0
0.3%
0.5%
00%
0.07%
3.4%
Avg. Delyy (4)
133
4.0%
+2.1%%
703 7301
40.55%
(13L 154)
41.00%
17.1) 7.20
22.45%
(133 1.9
+0.84%
40.33%
40.37%
(133 T/
+3.53%
013 72
+0.33%
113 0:0
48 78%
011 120
+0.47%
2111 093A)
40.24%
7113 73N
+0.18%
03 135
40.45%
+0.23%
+3.03%
(411.44
Dropped (4)
0.0%
0.0%
+0 10.05%
0.01%
0.0%
JAN ALI
0.01%
4. 0%
15.6 201
0.0%
0 01.%%
0.01%
+8 23%
Sut a1n
0.01%
Ha. 6:10
+0.00%
0.0%
0.0%
15.04 C.0
0.01%
+0.05%
15:08.2.00
-2 -2.00%
UDP, very high traffic
all
all
edge:
odge:
cdge:
no SAD
edoe: HROM
global:
global:
no SHOR
global:
SAD:
SRD:
dmm-1
dim-34
contin
crlywdge--nn
only
Received (1)
0.0%
4.07%
0..6%
12 11.9%
1.00%
1002 31.40
0.55%
IS1 NY RUUN
0.31%
3.32%
4..5%
0.02%
8.00%
14.8 53.4
-.77%
10.0 23.9
0,39%
st M. 51.4111 De KhAt
-.10%
+0.00%
-..7%
94 17
-7.01%
11.00
-1.22
Avg. Delay (4)
183 8.71
-121%%
+15. 91%
5:34 1093
+7.15%
840 914
1000 1004
18.1 A33)
T..%%
+0.41%
40.50
EL 260
18.0 0.21
-0.7%
0.48 92
+1
K:0 12.85
0.52 82
+1.17%
13 11.21
+0.9%
1006 8:4)
+0.19%
13:06 11.30
+6.011
300 12.31
+18 89%
Dropped (4)
12222200
0.01%
10.3%
+1.03%
00.37%
+6.07%
10.27%
+0.04%%
0.0%
12.53%
+3.82%
16.27%
+6.1%
0.04%
+1.6%
+1.9%%
TCP, modium traffic
esgc:
global
w1
edgec
edge:
edge:
no
edge:
dubal
global:
global:
SROn
global:
SRD:
SRD:
42
only
SRD
Received (1)
4433 90
+0.02%
-22 b.
15.20
2.02%
73%
4 5252%
35,
+4.44%
3X
85045.9
99, MURTHALLE
8.9%%
+0.01 0..03%
.0.77%
33,
27.8
-32
+0.0%%
31
..31%
-.55%
+0.11%
.0.3%%
T0
-0.05%
40.73%
Aug, Delay
+0.07%
0.57%
0.01%
+0.3%
0.18%
+0.2%
11.02%
0.79%
Dropped
10.15%
0..6%
10.01%
4.07%
0.0%
10.01%
15.
4.06%
10.01%
0.06%
very high traffic
global
d2n
dim-24
no SAD
no contg
load
no conffy
none
SHOR
load
no E4
none
no load
node onwyedge--eeeooooo Mootgg--oode load only SRD only
no SRD
Received (1)
+017%
0.3%
05%
+0.02%
+0.7%%
4.43%
-3.16%
-3.00%
+0.10%
Aug. Delay (1)
42.78%
02.54%
4.15%
3.66%
-3.26%
+0.32%
Dropped
13 1sse 10:30) 9091
10.4%%
+0.36%
+0.48%
1783 9381
-0.04%
(7.02
+2.18%
137 18
+0.46%
59 9881
3.05%
1535
4,83%
19:44 1191
+0.48%
+0.37%
9281
0.35%
0356 909
+0.42%
1047. 9991
.3.44%
-0.7%%
2950 0301
+0.4%
2900
10.45%
19503390
40.08%
3555 0.01
-0.39%
Figure 20: Results for FieldLines trained with different available features. Results show the mean val- ues over 100 evaluation episodes. Values and colors are relative to the default feature setting explained rreceived/droppeer bytes, SRDR abbreviates
in Section B.4 In the column names, SRD abbreviates rent/received/dropre /ropppeeeeeeeeeennnttte bytes, and DJ abbreviates average packet delay and jitter. The interac- tions between the policy's access to features and its routing performance are very complex, as the combination of some missing features may result in severe performance issues while others may not have strong effect. Adding node features and thus using the full set of monitored features does not improve performance, and even leads to large penalties when increasing the latent dimensionality of the policy's 's MPN.
32

---

Published in Transactions on Machine Learning Research (10/2024)
M-Slim
4+1
FieldLines
t
Figure 21: Illustration of network monitoring graphs (left column) and corresponding routing actions (right column) in two consecutive timesteps, taken from the evaluation the nz nz-XS topology preset of Section 7.1 The dark red color on the monitoring graph's edge illustrations denote the maximum packet buffer fill of the incident network device in the past timestep, the light red color denotes the packet buffer fill at the end of the past. timestep (e.g. 50% red = 50% filled.. In the action visualization, routing nodes hold distinct. colors, and the small colored arrows placed on the edges show where packets destined for the correspondingly colored destination node are sent next. The two upper rows of the figure show network states seen and actions taken by M-Slim, the Iwo lower adjusts few routing selections relevant edges of the monitoring graph become less congested (e.g. edges 7 5. 3 0 and 0 - 2) from the first to the second timestep. On the other hand, FieldLines is much more conservative and only changes the next-hop selection for nodes 0 and 8 at routing node 5, even though e.g. the edges between nodes 0 and 7 have considerably changed in state.
show network states
and actions taken by FieldLines). M-Slim
33


Reviews:
[{"review_id": "8BsLagG6jI", "reviewer": "Reviewer_QwUa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The proposed packet-level simulation environment with RL-powered routing optimization is a nice contribution that addressed the various gaps in the existing literature. In the absence of real testbeds, the next best thing is accurate simulators. Flow-level simulators do not take into account the various intricacies, subtleties, and complexities of real routing protocols, as opposed to packet-level simulators. In that sense, PackeRL is an important addition that can be used for a more fair and precise benchmark evaluation.\n2. I like the fact that the authors propose two different algorithms, each with different strengths and weaknesses, and possibly different applicability. This is in fact quite aligned with standard routing protocols, where we observe a significant variety (e.g., OSPF, BGP, EIGRP, etc.). Having a variety of choices is a strength, depending on the application scenario.\n3. The overall framework is quite flexible, as it can accept different reward definitions, state configurations, traffic types,, network topologies, etc.\n4. The experimental study is extensive and quite through. The results indicate that the proposed methods have potential as competitors not only to other ML-based frameworks but also other traditional routing protocols. M-Slim, in particular, seems to perform very strongly with high traffic. Also, compared to other ML methods, inference time for M-Slim and, in particular, FieldLines is significantly lower, which makes the framework more practical.\n\nWeaknesses\nI have concerns on several fronts. In detail:\n1. The results are somehow mixed. Let's for example focus on the table in Figure 3. In the TCP/UDP mixed traffic regime, M-Slim reduces average delay by 0.24/7.2=3.33%. But it increases the percentage of dropped packets by 0.15/1.25=12%, while it reduces the number of received MB by 0.13/35.38=0.37%. Similarly, in the same setting, FieldLines reduces average delay by 0.16/7.2=2.22%, but increases the percentage of dropped packets by 0.14/1.25=11.4%. In the TCP high regime, the results are arguably better for the two methods, and this is again seen in Figure 4, where for high and very high traffic the two introduced algorithms fare better than EIGRP. But for low or medium traffic, the results are bad or mixed in the best case. To me this creates various challenges:\n- First, note that the real competitor of the proposed algorithm is not random algorithms or other ML-based algorithms, but standard routing protocols. This is the comparison that matters the most, if the goal of this work is to argue that the proposed framework is a viable competitor for practical routing in real computer networks.\n- Second, the fact that performance depends so critically on the nature of the traffic could be an issue. In particular, I find it rather distressing that both algorithms give mixed or even negative results for low or medium traffic. If the goal is for these algorithms to be deployed to real networks, then we would ideally want them to perform strongly under all settings. Traffic naturally fluctuates, so performing strongly under a narrow regime of traffics may be a weakness.\n- Actually, the aforementioned point may be related to the optimization objective: if, for instance, we want to minimize delay or maximize throughout, RL may find it beneficial to increased the number of dropped packets under some circumstances. On the other hand, standard routing protocols are based on strong intuitions, heuristics or combinatorial algorithms, which have been found to be very effective in practice.\n- Overall, the mixed results provide at the very best mixed evidence about the potential of RL-based approaches to act as substitutes for the traditional routing protocols.\n\n2. I am confused by the POMDP formulation. In deep learning, one could argue that we feed the raw data to the algorithm, and RL will learn over time to extract the features that are important for optimizing the chosen reward function. On the other hand, the authors adopt a POMDP formulation, where only a subset of the features are chosen. But doesn't that complicate the problem formulation unnecessarily? What do the authors gain from this? At the end of the day, MDP (rather than POMDP) approaches are used. So, why introduce a complex formulation, and not simply let the system learn the correct representation on its own?\n\n3. I am not clear whether this is the best venue for such a work. The packet-level simulator and the innovations therein are great but not of interest to the ML community. The ML/RL part of this work is what is potentially of interest. But, as I previously wrote, I am not sure this work provides strong evidence that the RL-based framework is good under all traffic settings. If the goal of the authors was simply to argue that their algorithms have some potential but without totally solving the routing problem, then a networking venue would have been more appropriate in my view. Given the actual machine learning contribution is not pronounced, I think an ML audience would at least want to see more compelling empirical evidence. I was quite surprised that the authors decided to leave some key RL aspects (e.g., reward function design and/or scalarization, multi-objective RL, etc.) as future work, even though these are precisely the aspects that an ML audience would be more interested in.\n\n4. I was not so clear about the role of $\\tau_{sim}$, when it comes to standard optimization strategies. In principle, couldn't protocols like EIGRP or OSPF deal with much lower values for $\\tau_{sim}$? I mean, can't we run them several times in the the period of $\\tau_{sim}$, given their comparatively lower computational cost? For example, in the high traffic regime, do the authors currently run, say, EIGRP only once in the simulation period $\\tau_{sim}$,? What if they ran it several times, which should be feasible given this protocol is more lightweight? Wouldn't then EIGRP adapt better to the high-volume traffic? In general, I was not clear how the standard protocols interact with the simulation period $\\tau_{sim}$, and how many times each method is run within that period. For the same reason, I was not clear whether it is fair to give the same $\\tau_{sim}$ to, say, EIGRP, or whether it can afford an even lower value due to its lower computational cost.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates reinforcement learning (RL) - based routing algorithms for sub-second routing optimization in computer networks. The authors argue that standard routing protocols such as OSPF or EIGRP may not be able to exploit the monitored information (including events such as link failures) as effectively as RL-based approaches, On the other hand, RL-based approaches can be computationally more expensive; furthermore, most prior work on such methods relies on fluid network models that do not accurately capture the complex nature of packet-level dynamics (e.g., via the UDP or TCP protocols). To fill this gap in the literature, the authors introduce PackeRL, a packet-level RL environment for routing in generic network topologies. To enable sub-second routing optimization, they additionally propose two algorithms, namely, M-Slim and FieldLines. M-Slim is a shortest path algorithm that performs very strongly with high traffic (especially TCP), but is hard to scale to larger networks. Its lack of scalability is addressed by the second algorithm, FieldLines, which relies on a next-hop (as opposed to shortest path) policy design. To assess the effectiveness of the proposed algorithms, the authors conduct an extensive empirical study, on PackeRL which corroborates their various claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am open to changing my score, but I would want to understand what the authors think about all aforementioned weaknesses, If there are points I have misunderstood, I would appreciate additional clarifications.\n\nFurthermore, something I found a bit confusing in the various tables was that the authors provide only the absolute changes. Wouldn't it have been better to show the percentage changes? I was curious as to why the authors made this particular presentation choice. I actually had to work out the percentage changes myself on many occasions, which was inefficient.", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nzVd4s1BHb", "reviewer": "Reviewer_BM42", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The packet-level simulation environment appears very useful, with more realistic behavior than fluid-based models\n- Good detail is provided on the configuration of simulation tasks, generation of topologies, and simulated events\n- Experiments on proposed RL methods include varying topologies and\n  traffic compositions (UDP vs. TCP mixes, intensity, etc.)\n\n**Weaknesses**\n\n- The paper could use more detail on the architectures of the two\n  methods, M-Slim and FieldLines, and a clearer discussion of changes\n  from MAGNNETO (in the case of M-Slim)\n- Some ablation tests conducted are only carried out over a very limited\n  range of parameters, making trends somewhat less clear (although the\n  costs of the RL training do seem make to these already expensive to\n  conduct)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper details the construction of a new network routing\nsimulation environment, PackeRL, which simulates network flows and\nallows training RL route optimization networks with packet-level\nsimulation. This is in contrast to fluid-based models, which lack the\nfiner granularity of packet-level simulation. The authors also train\ntwo new RL routing networks using this environment: M-Slim (a\nmodification of an existing method MAGNNETO) and FieldLines, both\nGNNs. The authors observe better routing performance (in particular\ngoodput) when trained using the packet data, and the architectures\nallow for faster evaluation allowing, routing decisions to be made\nmore frequently.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "First, a few cases where I think additional discussion would enhance\nclarity and help make the paper a bit more self-contained:\n\n1. I would appreciate more details on MAGNNETO and the changes made in\n   constructing M-Slim--architecturally as well as in how the networks\n   are evaluated.\n\n2. Overall, more details on the architectures I think would help as\n   well. I did see the discussion of latent dimensions, etc but I\n   think being a bit more explicit on the architectures would help\n   readers (even with the future release of source code).\n\n3. And one question just for clarity: it appears that the training\n   topologies in each nx-(XS,S,...) etc are generated once and then fixed.\n   Is the same true at evaluation and true of the traffic events at\n   evaluation time? (Just to understand which aspects of the evaluation\n   episodes were the same for each set of networks.) It might help to\n   briefly mention this alongside the training and evaluation details\n   in section 6.2.\n\nThen a few questions I have: some discussion of these might help\nreaders, but I think is certainly less critical:\n\n1. At a somewhat quick glance, it looks like MAGNNETO carried out a\n   sort of distributed evaluation while the process here might be more\n   centralized (i.e. it appears inference is carried out while the\n   simulation is paused and is therefore instantaneous w.r.t. the\n   packet events). Is this correct? Is this another difference from\n   MAGNNETO, or does the fact that simulation used in that work lacks\n   packet-level behavior reduce their ability to account for this\n   effect?\n\n2. If that is correct do you have some sense of whether accounting for\n   the costs of inference (possibly lagging the application of the\n   networks' routing decisions) would change the behavior\n   significantly? I suppose this may intersect with a possible future\n   extension to account for age-of-information while performing\n   inference.", "broader_impact_concerns": "No specific concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "mLcDtiHXKG", "reviewer": "Reviewer_HPV1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have qualms about my ability to stringently evaluate all the claims made in this paper, as this is far from my area of expertise.\nNonetheless, with the caveat that I am taking many claims at face value, my evaluation is as follows\n\n## Strengths\n\n### PackeRL\n\nIntroduces a novel training environment (PackeRL) which seems to expand the range of capabilities of algorithms that learn to solve problems of network traffic routing. This is a non-trivial engineering task, as far as I can see\n\n## M-Slim/FieldLines\n\nUses this framework to devise two novel packet routing algorithms which have improved performance with respect to various baselines (uniformly-at-random routing, OSPF, ...)\n\nThese two things seem to be independently publishable together form a strong basis for the paper\n\n## Weaknesses\n\n### Packet/flow framing\n\nThere is an odd structural choice that starts in the title \"... Learning Sub-Second Routing Optimization in Computer Networks _requires Packet-Level Dynamics_\" \n\nOut of the publicly available environments, only  [  MAGNNETO ] supports arbitrary network\ntopologies and traffic patterns. But it uses a fluid-based network model, i.e., a model that treats traffic as\nflows in a flow network. Such models abstract away from packet-level interactions as encountered in the real\nworld, e.g. in TCP traffic, where sending and forwarding dynamics are very different from flow distributions\nin flow networks.\n\nSo in the field of _algorithms which support arbitrary toplogies_ MAGENNTO uses a continuous approximation of a discrete time system of events to perform its modeling, and the title makes it sound like this is the reason that it doesn't work as well as the authors' own M-Slim. IS that what is actually shown in the paper though? According to the authors MAGENNTO is slowed down by its nested loop (e.g. section 7.3 \"MAGNNETO’s optimization loop quickly leads to inference times of several seconds\" ) which does not seem to be related to the continuous modellng approximation\n\n### Wall-clock modeling\n\nIt would be good to have the net computational burden of the routing algorithms *at run time* more transparent. The authors note \"FieldLines still requires more time to re-optimize routing than the duration $\\tau_\\text{sim}$ we simulate per step\" which is... good to know, but also suggests that we should be graphing inference time for all algorithms *against $\\tau_\\text{sim}$*; I understand that this inference-time performance is potentially complicated, but it seems to be a metric of great importance to practical application, so it should be easier to extract this information.\n\n## Evaluation against alternatives\n\nThe authors restrict their comparison to only MAGENNTO, on the basis that it is the only approach that generalises to novel topologies. It does nonetheless seem that (Stampa et al., 2017; Pham et al., 2019; Sun et al.) might provide a useful baseline case for fixed-topology networks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces\n\n1. PackeRL, an augmentation of the existent network routing simulation frameworks \n2. two RL-based routing algorithms\n\n   1. M-Slim\n   2. FieldLines\n\n3. and a demonstration by simulation that the performance of these algorithms is superior to the existing alternative learned routing algorithms", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "IMO work would be stronger if changes were made to address the weaknesses I raised above, but I don't think these are \"dealbreakers\"; the paper seems to already represent a publication-worthy body of work. I nonetheless recommend clarifying", "broader_impact_concerns": "There are many concerns raised by this work, but they seem to be already addressed by the Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers find the proposed packet-level simulation environment is valuable to tackle more realistic network topologies, and also believe the proposed M-Slim/FieldLines algorithms are quite useful for RL-based routing optimization. After rebuttal, most of the raised concerns have been properly addressed, and two reviewers voted to accept this paper while one reviewer leaned toward accepting.

I read the paper in detail and totally agree with all reviewers that this work has made a solid contribution (a packet-level simulation environment and two powerful algorithms) to routing optimization in computer networks, the claims made in this paper are well supported, and some TMLR audience will find this work useful. Therefore, I am happy to accept this work as is.  

In addition, I also agree with the reviewers that testing the proposed algorithms on different real networks could be very helpful to fully demonstrate their pros and cons in a practical scenario. The proposed future extenstions such as multipath and/or multi-objective routing optimization is also crucial for a good RL-for-RO benchmark environment.
Decision: Accept (poster)