Beyond Shortest-Paths: A Benchmark for Reinforcement Learning on Traffic Engineering

[2/2]

Evaluation TE objectives (W4/Q5): We agree on MLU and throughput being common TE objectives and would like to explain our motivation for using the metrics you find in our evaluation: Most of our paper’s experiments concern UDP traffic in the peak traffic mode, which has been chosen to mimic stress scenarios in networks where certain periods of congestion are unavoidable when using OSPF or EIGRP (i.e. the maximum LU over an episode is always 1.0). We have made this fact more clear in Section 5 and Appendix A.4. Since UDP in its base form simply sends out packets with the full desired sending rate and all parallel evaluations of OSPF, EIGRP, GNN etc. use the same traffic matrices, the amount of sent packets in each parallel episode is effectively the same (of course, it can change between episodes). Therefore the main indicators of an improved routing capability in these scenarios are fewer packet drops which in the case of “fixed” sent packet counts is fully correlated with throughput, and lower packet delay. Concerning the evaluations on TCP traffic, TCP controls the datarate of the sender applications to minimize congestion, and so in addition to the amount of dropped packets (because TCP is not able to prevent them all) throughput indeed is a relevant performance metric. In Figure 7 we chose to display the amount of sent packets over the entire episode as an episode-wide average of the throughput, next to the amount of dropped packets as an indicator of data actually reaching its goal and not just being distributed into the network nicely.

References:

[1] Bernárdez, Guillermo, et al. "MAGNNETO: A Graph Neural Network-Based Multi-Agent System for Traffic Engineering." IEEE Transactions on Cognitive Communications and Networking 9.2 (2023): 494-506.

[2] Gay, Steven, Renaud Hartert, and Stefano Vissicchio. "Expect the unexpected: Sub-second optimization for segment routing." IEEE INFOCOM 2017-IEEE Conference on Computer Communications. IEEE, 2017.

[3] Jadin, Mathieu, et al. "Cg4sr: Near optimal traffic engineering for segment routing with column generation." IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019.

[1/2]

We thank you sincerely for your review, which exposes some important aspects we should work on as well areas where should improve the presentation of our findings. We address your concerns by topic (Weakness=W, Question=Q):

Novelty of the eleganTE framework (W1/Q1): While it is true that several related works have used ns-3 or other simulators/emulators to evaluate similar scenarios, we would like to emphasize that these are either not openly available, or restricted to a specific scenarios. A core part of the novelty of eleganTE is the combination of providing versatile and repeatable scenarios with an arbitrary number of graph topologies and traffic patterns, and making it fully available for fellow researchers as a new benchmark suite. The three custom ns-3 modules are necessary extensions to the simulator to faithfully implement the SwarMDP formalism proposed in Section 4 (now Section 3) and thus their roles in implementation are briefly presented in Section 5 (now Section 4), while we leave a more detailed explanation of eleganTE’s inner workings to Appendix A. As reviewer 3jBT has made similar remarks, we acknowledge that we did not present the limitations of related work and the unique position of eleganTE clearly enough, and have revised the structure and improved the presentation of the first three chapters to better motivate our framework.

Novelty of / Motivation for the SwarMDP formulation, State of related work (W2/Q2/Q3): We intend to introduce the requirements for RO suitable for TE, and then highlight how only our proposed formalism is able to perspectively fulfill all of them. We fully agree with your remarks and realize that we did not link existing RL-based TE work to the stated requirements well enough. We have revised the introduction, related work and requirements section (and integrated the requirements into the introduction) to better expose the conceptual weaknesses of existing work, and the proposed improvement of our formalism. Furthermore, we have improved the presentation of our formalism’s advantages in what is now Section 3.

Comparison in evaluation with related work (W3/Q4): Most of the mentioned related RL-based TE approaches do not warrant a comparison due to their limitations with respect to our requirements, but we do acknowledge that since we did not highlight the conceptual shortcomings of related work clearly enough (see the previous paragraph) it seemed as if the mentioned related work is directly comparable to our proposed approach. Furthermore, most related work lacks a publicly available reference implementation and/or detailed enough description of the algorithm and evaluation procedure to warrant an honest comparison. We will modify Section 2 to highlight this fact. However, despite the conceptual differences, we aim at including a comparison against [1] for reference in future work due to their remarkable results. Concerning non-RL approaches, we would like to point out that label-based approaches like MPLS or Segment Routing (SR) introduce additional layers, components and dependencies into the networking system stack that possibly counteract the idea of a general-purpose TE approach in the face of heterogeneous network types and hardware setups (c.f. requirement “Compatibility”). On the other hand, our odd-routing module with RL-based routing serves as a drop-in replacement for Routing Protocols like OSPF or EIGRP. Nevertheless, we agree that comparison to non-RL TE approaches should not be neglected, and will provide a reference comparison to modern label-based TE approaches [2, 3] in future work.

We thank you very much for your review and for exposing the need for improvement in presentation clarity.

The multi-agent RL portion is poorly described. It appears that the author simply utilize the multi-agent toolboxes available, with an appropriate state, action, stewards functions. As such, I am not clear as to the level of ML related contributions in this paper. It looks like a use case of an existing approach, with small modifications to the approach and the ns3 simulator appropriate the situation.

As part of our contribution, we intend to expose the conceptual weaknesses of related work by first stating the requirements that we deem critical for RO that can work for autonomous TE, and then provide an MDP formulation that in contrast to previous work lends to RO mechanisms that fulfill all stated requirements. We agree with your statement in that our work does not clearly motivate the MDP formulation and its uniqueness, and have considerably improved its presentation to motivate its need and novel features more clearly. While it is true that our TE SwarMDP is similar to the formulations of the cited papers, our action space formulation permits agents with varying neighbor counts without losing the homogeneous nature of their respective action spaces. We have also adjusted the section (which is now Section 3) to present this improvement more clearly. Furthermore, a core contribution of this paper is the disclosure of eleganTE, a versatile framework that enables repeatable experiments within this formalism. Given the shortcomings and non-comparability of related work, we believe eleganTE complements our formalism in a way that is of great value for the ML x Computer Networking community.

Q1. It appears that the traffic, although dynamic, is essentially fixed for periods of time where routing optimization is performed. Is this correct?

For our answer we assume that by “periods of time where routing optimization is performed” you refer to the “execution” of the timestep in the simulator (please let us know if we have misunderstood you here). The traffic behavior is “fixed” in the way that, at the start of each simulation period (i.e. environment step), the implementing demand-driven-applications adopt a constant sending bitrate so that, over the course of \tau_{\text{sim}}, an amount of data is injected into the network that matches the corresponding entry in the traffic matrix. We will improve the wording in the framework Section (now Section 4) to clarify that the bitrate is constant throughout a timestep. As the concept of traffic matrices themselves is a discretization of the continuous time-series nature of traffic dynamics, it is an interesting question how to achieve a fully variable sending rate without moving away from using traffic matrices altogether.

Q2. It is not clear what the full set of observations is. Does it include the traffic demand on each node? If so, how is it measured?

We observe network device load values and link utilization values locally for each edge. These values range from 0 (no load/usage) to 1 (full network device buffer/fully utilized link). Also, we observe global maximum link utilization and average bandwidth utlilization, which we by default store in each node. As traffic patterns in modern enterprise networks can be highly volatile and inherently unpredictable [1], we choose to not include traffic statistics directly in our observation function but rather via the observed utilization values. This means that we treat the traffic dynamics as part of the unknown transition function of our SwarMDP for which we would like to find an approximately optimal solution using RL. The observation procedure is explained in Appendix B.2, and we will add a brief note in teh formalism Section to improve the section’s clarity of presentation.

References:

[1] Gay, Steven, Renaud Hartert, and Stefano Vissicchio. "Expect the unexpected: Sub-second optimization for segment routing." IEEE INFOCOM 2017-IEEE Conference on Computer Communications. IEEE, 2017.

We thank you for your review and the acknowledgement of the strengths of our work. We agree on the listed weaknesses and, as indicated in the paper, will work on resolving them in the future. Concerning the training stability issue, we would like to emphasize the role of implementation details when using the widely popular PPO algorithm [1]. Given the focus of our work, it is conceivable that despite the executed hyperparameter ablation studies available in Appendix D, it is conceivable that the instability can be reduced by optimizing the learning algorithm implementation, and we have stated this fact more clearly in the conclusion.

References:

[1] Engstrom, Logan, et al. "Implementation matters in deep policy gradients: A case study on ppo and trpo." arXiv preprint arXiv:2005.12729 (2020).

[2/2]

General GNN Performance (Q5): We are aware of the high variance of GNN performance in our experiments, but would like to point out that the GNN was able to achieve comparable performance at least occasionally in the experiments. Combined with the results of related work, it is clear to us that GNNs can be a viable model architecture choice, especially since in contrast to MLPs they are able to handle graph-shaped inputs while not relying on a particular ordering of the input features. We do not think that the shown performance contradicts the claim, however we acknowledge that we have to considerably improve the reliability of our trained GNN policies, e.g. via implementation improvements in future work.

Multi-Objective RL (W4/Q5): Network performance is assessed in several different metrics that sometimes cannot be optimized without trade-offs. As such, we fully agree that using Multi-Objective RL (MORL) is a very interesting Idea and might be a better fit for our TE problem in the long run. However, Multi-Agent Multi-Objective RL is highly complex, still largely uncharted research area [2], not least because it is unclear how to weight the different common TE objectives since they themselves are proxies for performance metrics that network users actually care about [3]. Given the novelty of the framework as well as the difficulty of the considered problem even with single-objective RL, for this work we have decided to run with the approximate solution of scalarized rewards and fixed scaling factors. These scaling factors have been selected so that the expected average values for the individual scaled reward components lie in the same order of magnitude (and thus each corresponding objective is valued roughly equally), except for $R_\text{loop}$ which can range considerably higher the more loops have been introduced to the routing. We have added a short note in Appendix D.4 for improved clarity. Concerning the lack of evidence in the reward function ablations, we hope to add reward function ablation experiments on random graphs in future work.

References:

[1] Knight, Simon, et al. "The internet topology zoo." IEEE Journal on Selected Areas in Communications 29.9 (2011): 1765-1775.

[2] Hayes, Conor F., et al. "A practical guide to multi-objective reinforcement learning and planning." Autonomous Agents and Multi-Agent Systems 36.1 (2022): 26.

[3] Dukkipati, Nandita, and Nick McKeown. "Why flow-completion time is the right metric for congestion control." ACM SIGCOMM Computer Communication Review 36.1 (2006): 59-62.

[1/2]

Thank you very much for your very detailed review and the various concerns you have rightly pointed out. You have mentioned many very valuable points that we would like to address by topic (Weakness=W, Question=Q):

Overall Performance vs. Standard RPs, Motivation for RL-based TE (W2/Q1): We fully agree that the performance of our own trained policies is not superior to the presented RP baselines. However, this does not mean that Routing Protocols like OSPF adjust to changing traffic. They use fixed equations to calculate shortest paths per source-destination pair, using configuration parameters like link datarate. Traffic Engineering, which includes adjusting “shortest paths” to respect traffic conditions, is achieved either by manually adjusting the link weights for such routing protocols in the face of traffic changes (which is obviously highly inefficient at scale), or by technologies such as Segment Routing (SR), MPLS or ECMP. These techniques however, as indicated in the RO requirements that now form part of the introduction (c.f. general response), introduce additional complexity into the overall network structure, and are not guaranteed to react adequately in previously unencountered situations since they operate on pre-defined heuristics, too. Here, a routing policy that is learned e.g. via RL, can cover an unprecedented breadth of situations, a promise that has been partially validated by related work. This paper’s main goal is to highlight the shortcomings of related work, and then introducing a formalism and an implementing framework which facilitate the training of policies that can be used for real-world autonomous TE without the shortcomings of related work. We believe that this alone is already a notable contribution, combined with the fact that related work has shown the superiority of RL-based approaches for select TE use cases. In fact, we have provided the admittedly sub-optimal policies mainly as a demonstration of the framework’s features and of the difficulty of the implemented decision problem, and we are confident that future work building on our framework (our own as well as others that might use it) will show substantially improved performance and clearly outperform existing baselines. However, we fully acknowledge that the existing structure of the paper does not motivate the need for eleganTE well enough, and thus we have revised the first few sections to better highlight its novelty and value (c.f. general response).

SwarMDP vs. Heterogeneous Agents (W3/Q2): In small networks we might get away with modeling our routing agents heterogeneously, however when scaling the network size the complexity of problem formulations with heterogeneous agents will grow uncontrollably due to its combinatorial nature. We believe that the optimal behavior of a node can be derived from its input features (i.e. local connectivity and utilization statistics) alone. As a consequence, routing nodes are well modeled as homogeneous agents that differ only in the varying amounts of neighbors, which we respect with our action space formulation.

Figure 4/Outperforming Scenario (W1): Concerning the results on predef4s, we realize that the employed method of visualization is not accurate enough to showcase the performance of our NN methods, especially with respect to the claim of “outperforming” OSPF and EIGRP. The main goal of the presented policies is to showcase the versatility of eleganTE and to expose the limitations of conventional Routing Protocols in certain situations, and we hope to add routing visualizations that further support the claim made with respect to predef4s by the end of this rebuttal period.

Topologies and Scalability (W5/Q4): The pre-defined topologies are synthetic, and we would like to extend our topology generation procedure to include bigger real networks e.g. from the TopologyZoo [1] in future work. However we are confident that our randomly generated topologies already cover a wide variety of conceivable networking scenarios due to the multiple supported random graph models. Concerning the scalability requirement, our framework eleganTE is only practically bounded in network size due to a quadratic scaling of sender application count and size of the shared memory used for communication. As reviewer Jksb has also requested results on larger networks, we hope to extend our evaluations on random graphs by evaluations on randomly generated 150- and 500-node networks to support this statement.

Thank you very much for your review and your raised concerns. We address them individually:

W1. The SwarMDP formulation in Section 4 lacks details on handling heterogeneous action spaces and scaling to large network sizes.

We view the action spaces of the routing nodes as homogeneous, in the way that they all consist of unique gateway preferences per possible packet destination. This means that despite varying neighbor counts and different locations, all routing nodes fulfill the same task. We handle the varying neighbor counts with our proposed action space formulation, which therefore permits us to view this problem as one of homogeneous agents. Concerning the scalability to large networks, the proposed formalism is not constrained by network size. We have added a short clarification in the formalism Section (now Section 3), stating that it thus supports large networks.

W2 The eleganTE framework description in Section 5 needs specifics on the implementation, particularly how network state information is extracted into the monitoring graph representation.

Due to page constraints, In the framework Section (now Section 4) we cover essential information about eleganTE’s implementation and refer to Appendix A for more extensive implementation details, including the monitoring procedure described in Appendix A.3. We will make this reference more clear in the paper.

W3 Experiments only evaluate small networks of up to 50 nodes in Section 7. Testing generalization performance to 500+ node networks is needed.

eleganTE implements the SwarMDP described in the Formalism Section (now Section 3) and is only practically bounded in network size due to a quadratic scaling of sender application count and size of the shared memory used for communication. As reviewer HzR2 has also requested results on larger networks, we hope to extend our evaluations on random graphs by evaluations on randomly generated 150- and 500-node networks to support this statement.

W4. The GNN agent in Section 7.2 shows high variance in some experiments, indicating instability issues.

As you have correctly pointed out the stability issues of the GNN in particular, we would like to emphasize the role of implementation details when using the widely popular PPO algorithm [1]. Since with our policies we primarily wanted to expose the challenging nature of this problem, it is conceivable that the instability can be reduced by optimizing the learning algorithm implementation, despite the already executed hyperparameter ablation studies available in Appendix D.

Q1. Is the SwarMDP formulation described in section 4 able to handle changes in network topology within an episode?

While we will explore scenarios with changing network topology in future work, we think that the present SwarMDP formulation will be able to handle such changes with minimal modifications, i.e. substituting $V$ and $E$ with time-dependent counterparts $V_t$ and $E_t$. We have adjusted the notation to include this modification, with a note in the experiments Section (now Section 5) that currently, the topology stays constant.

Q2. Provide more specifics of neural network architectures used in section 6.1 

We agree in that Section 6.1 (now Section 5.1) does not cover the full details of the NN architectures. Due to page constraints, it only provides a brief overview of the used NN architectures, and we will make our reference to Appendix B.5, where we provide more architecture details, more clear.

Q3. Explore complex benchmark traffic patterns and dynamics in section 5.1 

We assume that by complexity you mean the variety of generated traffic patterns. We use the Gravity model [2] to create Traffic Matrices that mimic spiking traffic, and increase the variety (and thus complexity) of the generated traffic dynamics by introducing small random perturbations. Please let us know if this is not what you meant.

Q4. The authors should explore algorithm ablations like reward function, network architecture, etc.

We have explored these ablations and provide their results in Appendix D.

References:

[1] Engstrom, Logan, et al. "Implementation matters in deep policy gradients: A case study on ppo and trpo." arXiv preprint arXiv:2005.12729 (2020).

[2] Roughan, Matthew. "Simplifying the synthesis of Internet traffic matrices." ACM SIGCOMM Computer Communication Review 35.5 (2005): 93-96.