Is machine learning ready for traffic engineering optimization?

Is Machine Learning Ready for Traffic Engineering Optimization? Guillermo Bernárdez∗, José Suárez-Varela∗, Albert López∗, Bo Wu†, Shihan Xiao†, Xiangle Cheng†, Pere Barlet-Ros∗and Albert Cabellos-Aparicio∗ ∗Barcelona Neural Networking Center, Universitat Politècnica de Catalunya, Barcelona, Spain {gbernard, jsuarezv, alopez, pbarlet, acabello}@ac.upc.edu †Network Technology Lab., Huawei Technologies Co., Ltd., Beijing, China {wubo.net, xiaoshihan, chengxiangle1}@huawei.com NOTE: Accepted as a main conference paper at IEEE ICNP 2021. ©2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Abstract— Traffic Engineering (TE) is a basic building block of the Internet. In this paper, we analyze whether modern Machine Learning (ML) methods are ready to be used for TE optimization. We address this open question through a comparative analysis between the state of the art in ML and the state of the art in TE. To this end, we first present a novel distributed system for TE that leverages the latest advancements in ML. Our system implements a novel architecture that combines Multi-Agent Reinforcement Learning (MARL) and Graph Neural Networks (GNN) to minimize network congestion. In our evaluation, we compare our MARL+GNN system with DEFO, a network optimizer based on Constraint Programming that represents the state of the art in TE. Our experimental results show that the proposed MARL+GNN solution achieves equivalent performance to DEFO in a wide variety of network scenarios including three real-world network topologies. At the same time, we show that MARL+GNN can achieve significant reductions in execution time (from the scale of minutes with DEFO to a few seconds with our solution). Index Terms—Traffic Engineering, Routing Optimization, Multi-Agent Reinforcement Learning, Graph Neural Networks I. INTRODUCTION Traffic Engineering (TE) is a well-established mechanism that plays a fundamental role in the performance of today’s Internet [1]. Particularly, its main goal is to provide efficient and reliable network operations, while optimizing the network resources [2]. As a result, there exists a rich body of proposals based on different technologies (e.g., flow-based routing, link-state protocols, overlay networking) that target various optimization goals and network scenarios [3], [4]. Beyond this broad definition, a fundamental TE problem traditionally addressed in the literature is intradomain TE, where the classic optimization goal is to minimize the maximum link load within a self-administered network domain (e.g., a carrier-grade network) [5]–[7]. This is a well-known NP-hard problem [8]. This work was supported by the Spanish MINECO under contract TEC2017-90034-C2-1-R (ALLIANCE), the Catalan Institution for Research and Advanced Studies (ICREA) and the Secretariat for Universities and Research of the Ministry of Business and Knowledge of the Government of Catalonia as well as the European Social Fund. The last few years have seen an increasing interest in the application of Machine Learning (ML) to complex network control and management problems [9]. Particularly, the outstanding results of Deep Reinforcement Learning (DRL) in other domains (see [10] and references therein) have awakened the interest of the networking community in understanding the true potential of this new technology for online network optimization tasks, such as TE (e.g., [11]–[14]). In this paper, we raise an open question: Is ML ready for Traffic Engineering optimization? Here we refer to ready as achieving -at leastcomparable performance and speed to state-of-the-art TE solutions based on classical optimization methods. In order to answer this question, we seek to create a TE solution leveraging the latest advancements in the ML field, and then experimentally compare it to the best TE approach available in the literature. We present a novel TE optimizer based on a combination of Multi-Agent Reinforcement Learning (MARL) [15] and Graph Neural Networks (GNN) [16], which can be considered as the most advanced ML technologies for online optimization problems over graphs, such as TE. The proposed solution is distributed over the network devices and is tasked to address the intradomain TE problem. In particular, given a set of estimated traffic demands, the distributed agents of our MARL system cooperate to jointly optimize the link weights used by OSPF [17], with the ultimate goal of minimizing the most loaded link in the network. The proposed system is compatible with any network running a link-state intradomain routing protocol (e.g., OSPF, IS-IS, etc)1. Unlike previous ML-based proposals for TE (e.g., [11], [12], [18]), the combination of MARL and GNN allows us to handle topologies of various sizes and structures in a distributed fashion; and more importantly, to achieve combinatorial generalization over the information exchanged by agents in the 1The source code and all data needed to reproduce our experiments is available at https://github.com/BNN-UPC/Papers/wiki/MARL-GNN-TE © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. DOI: 10.1109/ICNP52444.2021.9651930 New Traffic Matrix m1 m4m7 m8 m3 m6 m0OSPF OSPF OSPF OSPF OSPF OSPF OSPF OSPF m5 m5 m9 m9 m2 m2New OSPF Weights (TE) OSPF Convergence Our Proposal Multi-Agent Reinforcement Learning and Graph Neural Netwroks Traffic Monitoring Platform Identifies (or predicts) new Traffic Matrix OSPF Convergence: OSPF distributes the new Link Weights for Traffic Engineering Normal Operation: Traffic flows through Traffic Engineered Network 1234 Figure 1: Network Traffic Engineering scenario. network, which is naturally represented as a graph [19], [20]. At the time of this writing, the most advanced proposals for TE are based on refined optimization algorithms, such as Constraint Programming [7], Local Search [21], Mixed Integer Linear Programming [22] or Column Generation [23]. All these solutions offer significant performance improvements with respect to traditional routing strategies, such as shortest path routing or load balancing. In our evaluation, we focus on DEFO [7] as a benchmark for comparison, which is arguably among the best performing and most advanced TE solutions available [24]. DEFO is a sophisticated proposal that represents the result of decades of research in TE. One of the main challenges in TE optimization is to reduce the dimensionality of the vast search space. To this end, DEFO proposes iddlepoint Routing (MR), a smart abstraction of routing inspired by Segment Routing [25]. With this approach, and leveraging the SDN paradigm to implement a fully centralized optimization algorithm, the authors are able to optimize a network with close-to-optimal performance within few minutes, which allows for near real-time operation. In our experimental evaluation, we benchmark the proposed MARL system against DEFO across a wide variety of network scenarios. We first evaluate the performance of our solution in a set of real-world network topologies with realistic traffic matrices, and report comparable performance to DEFO. Then, we analyze the execution time (speed) of both solutions and show that our MARL system only requires few seconds to optimize a network, while DEFO operates at the scale of minutes [7]. This improvement in terms of execution time is a result of the inherent distributed nature of our MARL system, which allows us to share the computation among the network devices without requiring any centralized entity. This enables for sub-minute real-time operation with comparable performance to the state-of-the-art in TE. II. NETWORK TRAFFIC ENGINEERING SCENARIO In this section, we describe the network scenario considered in this paper. Particularly, we address the intradomain TE problem, where network traffic is measured and routed to optimize the network resources. Typically, IP networks run link-state Interior Gateway Protocols (IGP), such as Open Shortest Path First (OSPF) [17], that choose paths using the Dijkstra’s algorithm over some pre-defined link weights. TE can be achieved through different approaches. Network operators use commercial tools [26], [27] to fine-tune link weights. Other mechanisms propose to add extra routing entries [28] or end-to-end tunnels (e.g., RSVP-TE [29]) to perform source-destination routing, expanding the solution space. In the literature, we can find a wide range of proposed architectures and algorithms for TE [30]. Our proposed ML solution is a fully distributed architecture that optimizes link weights (similar to existing commercial solutions [26], [27]) and interfaces with standard OSPF. It does not require any changes to OSPF, while it can be implemented with a software update on the routers where it is deployed. Relying on well-known link-state routing protocols, such as OSPF, also offers the advantage that the network is easier to manage compared to finer-grained alternatives, such as flowbased routing [31]. In what follows, we describe the three operational steps of our solution (see Fig. 1): 1) Traffic Measurement: In step 1 , a traffic measurement platform deployed over the network identifies a new Traffic Matrix (TM). This new TM needs to be communicated to all participating routers, which upon reception will start the next step and optimize the routing for this TM. We leave out of the scope of this paper the details of this process, as TM estimation is an extensive research field with many established proposals. For instance, this process can be done periodically (e.g, each 510 minutes as in [32]), where the TM is first estimated and then optimized. Some proposals trigger the optimization process when a relevant change is detected in the TM [33], while others use prediction techniques to optimize it in advance [34]. Finally, some real-world operators make estimates considering their customers’ subscriptions and operate based on a static TM. Our proposal is flexible and can operate with any of these approaches. 2) Proposed MARL+GNN TE optimization system: Upon reception of the TM, routers run the MARL+GNN optimization process (step 2 ), which eventually computes the per-link weights that optimize OSPF routing in the subsequent step. Particularly, we set the goal to minimize the maximum link load (MinMaxLoad), which is a classic TE goal in carriergrade networks [5]–[7]. This problem is known to be NP-hard, and even good settings of the weights can deviate significantly from the optimal configuration [6], [31]. Our MARL optimization system is built using a distributed Graph Neural Network (GNN) that exchanges messages over the physical network topology. Messages are sent between routers and their directly attached neighbors. The content of such messages are hidden states that are produced and consumed by artificial neural networks and do not have a human-understandable meaning. The GNN makes several message iterations and, during this phase, local configuration of the router remains unchanged, thus having no impact on the current traffic. More details about the inner workings, performance, communication overhead, and computational cost can be found in Sections IV and V. 3) OSPF convergence: Finally, step 3 is the standard OSPF convergence process based on the new per-link weights computed by the MARL+GNN system. Specifically, each agent has computed the optimal weigths for its locally attached links. For OSPF to recompute the new forwarding tables, it needs to broadcast the new link weights; this is done using the standard OSPF Link-State Advertisements (LSAs) [17]. Once the routers have an identical view of the network, they compute locally their new forwarding tables, and traffic is routed following the optimization goal. Convergence time of OSPF is a well-studied subject. For instance, routing tables can converge in the order of a few seconds in networks with thousands of links [35]. III. BACKGROUND The solution proposed in this paper incorporates two MLbased mechanisms: GNNs and MARL. In this section, we provide some background on these technologies. A. Graph Neural Networks GNNs are a novel family of neural networks designed to operate over graphs. They were introduced in [16], and numerous variants have been developed since [36]. In their basic form, they consist in associating some initial states to the different elements of an input graph, and combine them considering how these elements are connected in that graph. The resulting state representations, which now may encode some topological awareness, are then used to produce the final output of the GNN, which can be at the level of graph elements, or at a global graph level. In particular, we will focus on Message Passing Neural Networks (MPNN) [37], which is a well-known type of GNN whose operation is based on an iterative message-passing algorithm that propagates information between the selected elements of the graph –for simplicity, let us assume that we consider as elements the nodes of such graph. First, each node vinitializes its hidden state h0 vusing some initial features already included in the input graph. At every message-passing step k, each node vreceives via messages the current hidden state of all the nodes in its neighborhood B(v), and processes them individually by applying a message function m(·) together with its own internal state hk v. Then, the processed messages are combined by an aggregation function a(·): Mk v=a({m(hk v, hk i)}i∈B(v))(1) Finally, an update function u(·) is applied to each node v; taking as input the aggregated messages Mk vand its current hidden state hk v, it outputs a new hidden state for the next step (k+ 1): hk+1 v=u(hk v, Mk v).(2) After a certain number of message passing steps K, a readout function r(·) takes as input the final node states hK vto produce the final output of the GNN model. This readout function can predict either features of individual elements (e.g., a node’s class) or global properties of the graph. We note that a MPNN model generates a single set of message, aggregation, update, and readout functions that are replicated at each selected graph element. This means that these functions should be generic and flexible enough to adapt their behaviour to different scenarios, which is why they are usually modeled as traditional neural networks –specially fully connected and recursive neural networks, with the only exception of the aggregation function that is commonly an element-wise summation. B. (Multi-Agent) Reinforcement Learning In the standard Reinforcement Learning (RL) setting [38], an agent interacts with the environment in the following way: at each step t, the agent selects an action atbased on its current state st, to which the environment responds with a reward rtand then moves to the next state st+1. This interaction is modeled as an episodic, time-homogeneous Markov Decision Process (MDP) (S,A, r, P, γ), where Sand Aare the state and action spaces, respectively; Pis the transition kernel, st+1 ∼P(·|st, at);rtrepresents the immediate reward given by the environment after taking action atbeing in state st; and γ∈(0,1] is the discount factor used to compute the return Gt, defined as the –discounted– cumulative reward from a certain time-step tto the end of the episode T:Gt=PT t=0 γtrt. The behavior of the agent is described by a policy π:S → A, which maps each state to a probability distribution over the action space, and the goal of an RL agent is to find the optimal policy in the sense that, given any considered state s∈ S, it always selects an action that maximizes the expected return ˆ Gt. In this work, we focus on model-free Policy Gradient Optimization methods [39], where the agent learns an explicit policy representation πθwith some parameters θ–typically a neural network. In most cases, during the training process, they involve learning as well a function approximator Vφ(s) of the state value function Vπθ(s), defined as the expected discounted return from a given state sby following policy πθ: Vπθ(s) = E πθ [Gt|st=s](3) This defines the so-called Actor-Critic family of Policy Gradient algorithms [39], where actions are selected from the function that estimates the policy (i.e., the actor), and the training of such policy is guided by the estimated value function to assess the consequences of the actions taken (i.e., the critic). Our solution is precisely based on an Actor-Critic method named Proximal Policy Optimization (PPO) [40], which offers a favorable balance between reliability, sample complexity, and simplicity; we refer the reader to the original paper [40] for further details. Contrary to a single-agent RL setting, in a Multi-Agent Reinforcement Learning (MARL) framework there is a set of agents Vinteracting with a common environment that have to learn how to cooperate to pursue a common goal. Such a setting is generally formulated as a Decentralized Partially Observable MDP (Dec-POMDP) [15] where, besides the global state space Sand action space A, it distinguishes local state and action spaces for every agent –i.e., Svand Av for v∈ V. At each time step tof an episode, each agent may choose an action av t∈ Avbased on local observations of the environment encoded in its current state sv t∈ Sv. Then, the environment produces individual rewards rv t(and/or a global one rt), and it evolves to a next global state st+1 ∈ S – i.e., each agent vturn into the following state sv t+1 ∈ Sv. Typically, a MARL system seeks for the optimal global policy by learning a set of local policies {πθv}v∈V . For doing so, most state-of-the-art MARL solutions implement traditional (single-agent) RL algorithms on each distributed agent, while incorporating some kind of cooperation mechanism between them [15]. The standard approach for obtaining a robust decentralized execution, however, is based on a centralized training where extra information can be used to guide agents’ learning [41]. IV. MARL+GNN ARCHITECTURE The TE scenario described in Section II is implemented through a MARL architecture that, thanks to the use of GNN, yields good generalization properties over networks [19], [20]. We will first introduce our generic MARL+GNN framework, which is especially designed for distributed networking tasks, and then we will provide details on how it is adapted to the intradomain TE use case addressed in this paper. A. Framework Formulation We model a networked MARL environment as a graph G= (N,E), with some nodes n∈ N and edges e∈ E, where a set of agents Vcontrol some of the graph entities (nodes or edges). Our architecture extends the single-agent PPO method [40] to accommodate the distributed multi-agent environment. In contrast to the standard MARL setting described in Section III-B, where a policy πθvis learned for each agent v∈ V, we propose to directly learn a global policy πθ:S → A in a distributed fashion over the global state and action spaces, defined as the joint and union of the respective agents’ local spaces – i.e., S=Qv∈V Svand A=Sv∈V Av. This allows us to formulate the problem as a classic MDP, thus avoiding the more complex Dec-POMDP scenario. An important novelty of our design is that all agents v∈ V are able to internally construct the global policy representation πθmainly through message communications with their direct neighboring agents B(v)and their local computations. Thus, we no longer need a centralized entity responsible for collecting and processing all the global information together to provide πθ. Such a decentralized, message-based generation of the global policy can be achieved by modeling the actor with a MPNN (see Sec. III-A), so that πθis now encoded as a GNN rather than as a classical, non-relational neural network Algorithm 1: MARL+GNN execution pipeline. Require: A graph G= (N,E)with a set of agents V, MPNN trained parameters θ={θi}i∈{m,a,u,r} Input: Initial graph configuration X0 G, episode length T, number of message passing steps K 1Agents initialize their states s0 vbased on X0 G 2for t←0to Tdo 3Agents initialize their hidden states h0 v←(st v,0,...,0) 4for k←0to Kdo 5Agents share their current hidden state hk vto neighboring agents B(v) 6Agents process the received messages Mk v←aθa({mθm(hk v, hk µ)}µ∈B(v)) 7Agents update their hidden state hk+1 v←u(hk v, Mk v) 8end for 9Agents compute their actions’ logits {logitv(a)}a∈Av←rθr(hK v) 10 Agents receive the actions’ logits of the rest of agents and compute the global policy πθ←CategoricalDist ({{logitv(a)}a∈Av}v∈V ) 11 Using the same probabilistic seed, agents sample an action at∈ Av0, for v0∈ V, from policy πθ 12 Agent v0executes action at, and the environment updates the graph configuration Xt+1 G 13 Agents update their states st+1 vbased on Xt+1 G 14 end for Output: New graph configuration X∗ Gthat optimizes some pre-defined objective or metric (e.g., fully-connected NN). In particular, this implies that all agents Vdeployed in the network are actually elements of a larger-scale mechanism –orchestrated by the MPNN– that requires them to perform regular message exchanges with their neighbors. Algorithm 1 summarizes the full execution pipeline of our solution. Inherently, at each step tof the episodic MDP, the MPNNdriven process of estimating the policy πθ(·|st)first requires engineering a meaningful hidden state hvfor each agent v∈ V. Each hidden state hvbasically depends on the hidden representations of the neighboring agents B(v), and its initialization h0 vis a function of the current agent state st v, which is in turn based on some pre-defined internal agent features xt v. Those representations are shaped during Kmessage-passing steps, where hidden states are iteratively propagated through the graph via messages between direct neighbors. In particular, successive hidden states hk v, where krefers to the messagepassing step, are computed by the message, aggregation and update functions of the MPNN, as described in Section III-A. Once agents generate their final hidden representation, a readout function –following the MPNN nomenclature– is applied to each agent to finally obtain the global policy distribution πθ. Particularly, in our system the readout is divided into two steps: first, each agent v∈ V implements a local readout that takes as input the final representation hK v, and produces as output the unnormalized log probability (i.e., logit) of every possible action in the agent’s space Av. The second and last step involves a communication layer that propagates the logits among agents, so that all of them can internally construct the global policy πθfor the overall network state st=Qv∈V st v. To ensure that all the distributed agents sample the same actions along the message-passing process at v0∼πθ(·|st),v0∈ V, they share a common seed before initiating this process. Consequently, only the agent v0 whose action has been selected does execute an action at each time-step t. For each step of an episode – of length T– our solution runs the MPNN-based actor model described above, after applying the action selected in the previous step. Note that each action could modify one or several agent’s internal states, which would vary their hidden state initializations, hence leading to a completely new optimization process. During training, each agent stores the global trajectory {st, at, st+1}T t=0, from which they can learn the configuration that leads to better global performance at the end of the episode. One especial characteristic of the proposed system with respect to common MARL settings emerges from the internal implementation of a MPNN model. As a result, rather than having independent functions for each agent as in the standard MARL setting [15], in our system all agents implement the same functions (i.e., message, aggregation, update, and readout) with the same parameters θ. Hence, all agents run exactly the same processing pipeline, and their outcome depends on both their initialization and the local information received from their neighbors. Indeed, our solution produces a single universal agent implementation that builds upon the inner functions of the MPNN, which are jointly learned during training across all the agents instances in the network (see Sec. III-A for more details). Thus, after training, each agent v∈ V can be interpreted as a replica of this universal agent that behaves based on its local environment. This so-called parameter sharing feature provides compelling generalization and scalability properties, which can be beneficial to effectively deploy the solution in networks with topologies of different size and structure, not necessarily seen during the training phase [20], [42]. B. Application to Traffic Engineering A straightforward approach to map the previously described MARL+GNN setting to the intradomain TE problem is to associate agents to each element of the physical topology –i.e., given a network topology, each agent can control individually the configuration of a network device, or some configuration parameters of a link connecting two devices. In the network scenario described in Section II, we consider that each agent controls a link (i.e., V=E). In practice, these link-based agents are executed in the adjacent device of the link (e.g., router). Figure 2 shows a visual representation of our distributed MARL+GNN system adapted to the TE use Message Passing &Action Selection (c) Agents process the received messages, and update their Hidden States based on the aggregated information m(·), a(·), u(·) A9 (a) Hidden States are initialized based on Input Features A2 A4 A5 A6 A7 A8 A10 A9 A3 W3 %3 0 0 A1 h0 1= h0 2=h0 3==h0 4=h0 5 h0 6= h0 8= =h0 7 =h0 9 W1 %1 0 0 W4 %4 0 0 =h0 10 W10 %10 0 0 W5 %5 0 0 W2 %2 0 0 W6 %6 0 0 W7 %7 0 0 W8 %8 0 0 (b) Agents share their Hidden States with direct neighbors via messages m m m m m m m m m m hk 9 hk 5,hk 7 hk 10 hk+1 9 (d) Agents may select an action (i.e. modify their weight) based on their final Hidden State wt 1 wt 2 90% 60% wt 3 wt 4 10% 30% 50% wt 5 wt 6 wt 7 wt 8 wt 9 wt 10 50% 40% 20% 70% 60% wt+1 1 wt+1 2 70% 80% wt+1 3 wt+1 4 40% 40% 50% wt+1 5 wt+1 6 wt+1 7 wt+1 8 wt+1 9 wt+1 10 40% 40% 30% 70% 60% W9 %9 0 0 K iterations Network at time-step t of the episode Network at time-step t+1 r(·) A9 hK 9wk+1 9 Figure 2: Description of the message passing and action selection process of our MARL+GNN solution in a timestep. The full procedure is repeated Ttimes, which is the pre-defined episode length. case, particularly with the goal of minimizing the most loaded link [5]–[7]. Taking this figure as a reference, we describe the particular adaptations of our MARL framework to be applied to the selected intradomain TE scenario: 1) Environment: In the traditional MDP setting, we consider episodes of a fixed number of time-steps T. At the beginning of each episode, the environment provides with a set of traffic demands between all source-destination pairs (i.e., an estimated traffic matrix [32]–[34]). Each link e∈ E has an associated capacity ce, and it is initialized with a certain link weight w0 e. These link weights are in turn used to compute the routers’ forwarding tables (via standard OSPF convergence). Each agent ve∈ V has access to its associated link features, which in our case are the current weight, its capacity, and also the estimated traffic matrix and the weights of the other links. This can be achieved with standard procedures in OSPF environments (see Sec. II). 2) State Space and Message Passing: At each time-step t of an episode, each link-based agent ve∈ V,feeds its MPNN module with its input features xt eto generate its respective initial hidden state h0 e(Figure 2-a). In particular, agents consider as input features the current weight wt eand the utilization ut e[0,1] of the link, and construct their initial link hidden representations h0 eas a fixed-size vector where the first two components are the input features and the rest is zero-padded. Note that the link utilization can be easily computed by the agent with the information of the estimated traffic matrix and the global link weights locally maintained. Then, the algorithm performs Kmessage-passing steps (Figures 2-b and 2-c). At each step k, the algorithm is executed in a distributed fashion over all the links of the network. Particularly, for each link, the corresponding agent receives the hidden states of its neighboring agents (i.e., adjacent links), and combines them individually with its own state hk e(message function), using a fully-connected NN. Then, all the messages computed in each link (with its neighbors) are aggregated using an elementwise sum, producing an aggregated message Mk e. Afterwards, another fully-connected NN is used as update function, which combines the link hidden state hk ewith the new aggregated information Mk e, and produces a new hidden state representation for that link (hk+1 e). As mentioned above, this process is repeated Ktimes, leading to some final link hidden state representations hK e. In short, during this K message-passing process, agents increasingly transform their initial link hidden states (initialized with the link weight and utilization) based on their local communications with adjacent agents (i.e., links). 3) Action Space: In our TE approach, the possible action of each agent e∈ E is to modify the weight of its associated link we. Due to parameter sharing, all of them share the same action space Ae. In our specific implementation each agent has only one possible action at each time-step: to increase the link weight in one unit. Note that the same agent can increment more than once its weight along an episode, thus providing enough expressiveness to generate potentially any combination of link weights at the end of the episode. In particular, the agent’s action selection (Figure 2-d) is done as follows: first, every agent applies a local readout function –implemented with a fully-connected NN– to its final hidden state hK e, from which it obtains the global logit estimate of choosing its action (i.e., increase its link weight) over the actions of the other agents. Then, as previously described in Section IV-A, these logits are shared among agents in the network, so that each of them can construct the global policy distribution πθ. By sharing the same probabilistic seed (from the beginning of the episode), all the agents sample locally the same action at e0 from πθ, thus selecting the agent ve0∈ V that will increase its weight and, consequently, each agent increases by one the weight of the selected link in its internal global state copy, which is then used to initialize its hidden state representation in the next time-step t+ 1; particularly, to compute the new link utilization ut+1 eunder this new weight setting. 4) Reward Function: During training, a reward function is computed at each step tof the optimization episode. In our case, as the optimization goal is to minimize link congestion, we define the reward rtas the difference of the global maximum link utilization between steps tand t+ 1. Note that this reward can be computed locally in each agent from its global state copy, which is incrementally updated with the new actions applied at each time-step at e0. C. Training Phase Formally, during training the goal is to optimize the parameters {θ, φ}so that: •The previously described GNN-based actor πθbecomes a good estimator of the optimal global policy; •The critic Vφlearns to approximate the state value function of any global state2. In particular, the training pipeline is done as follows: An episode of length Tis generated by following the current policy πθ, while at the same time the critic’s value function Vφ evaluates each visited global state; thus, the episode defines a trajectory {st, at, rt, pt, Vt, st+1}T−1 t=0 , where pt=πθ(at|st) and Vt:= Vφ(st). When the episode ends, this trajectory is used to update the model parameters –through several epochs of minibatch Stochastic Gradient Descent– by maximizing the global PPO objective LPPO(θ, φ)described in [40]. V. EVALUATION In this section we make an extensive set of experiments – over real-world network topologies– to evaluate the proposed MARL+GNN architecture (Sec. IV). We particularly focus on comparing the proposed solution with DEFO [7], which is arguably among the best performing and most advanced TE solutions available at the time of this writing [24]. A. Experimental Setup Along the evaluation section, we consider three real-world network topologies for training and evaluation of our model: 42-link NSFNet, 54-link GBN, and 72-link GEANT2 [43]. The length Tof the training and evaluation episodes is predefined, and it varies from 100 to 200 steps, depending on the network topology size (see more details later in Sec. V-F). At the beginning of each episode, the link weights are randomly selected as an integer in the range [1,4], so our system is evaluated over a wide variety of scenarios with random routing initializations. From that point on, at each step of an episode a single agent can modify its weight by increasing it in one unit, thus chaining the selected actions on the T time-steps of an episode. Taking [44] as a reference for defining the hyperparameters’ values of the solution, we ran several grid searches to appropriately fine-tune the model. The implemented optimizer is Adam with a learning rate of 3·10−4,β=0.9, and =0.9. Regarding the PPO setting, the number of epochs for each training episode is set to 3with batches of size 25, the discount factor γis set to 0.97, and the clipping parameter to 0.25. We implement the Generalized Advantage Estimate (GAE), to estimate the advantage function with λ=0.9. In addition, we multiply the critic loss by a factor of 0.5, and we implement an entropy loss weighted by a factor of 0.001. Finally, links’ hidden states heare encoded as 16-element vectors, and in each MPNN forward propagation K=8message passing steps are executed. We consider two different traffic profiles: (i) uniform distribution of source-destination traffic demands, and (ii) traffic 2The critic is exclusively used for training, it is no longer needed at runtime. We have implemented it as an independent link-based MPNN, similar to the actor, in order to exploit the relational reasoning provided with GNNs. However, other alternative designs would be valid as well. distributions following a gravity model [45], which produces more realistic Internet traffic matrices. For each set of experiments, the training process of our MARL+GNN system took about 24 hours running in a machine with a single CPU of 2.20 GHz (∼1M training steps). B. Baselines This section describes the baselines we use to benchmark our MARL+GNN system in our experiments. We particularly consider two well-known TE alternatives: •Default OSPF: We consider the routing configuration obtained by applying the OSPF protocol with the common assumption that link weights are inversely proportional to their capacities. We consider traffic splitting over multiple paths (OSPF with ECMP), which is a standard recommended best practice. •Declarative and Expressive Forwarding Optimizer (DEFO) [7]: A centralized network optimizer that translates high-level goals of operators into network configurations in real-time (in the order of minutes). DEFO starts from a routing configuration already optimized with a commercial TE tool [26], and it uses Constraint Programming [46] and Segment Routing [25] to further optimize it. To this end, DEFO reroutes traffic paths through a sequence of middlepoints, spreading their traffic over multiple ECMP paths. DEFO obtains closeto-optimal performance considering several network optimization goals, one of them being our intradomain TE goal of minimizing the most loaded link. We use the code publicly shared by the authors of DEFO3. For the sake of comparison, we also use OSPF-ECMP in the evaluation of our system (MARL+GNN), although it can also operate in scenarios without ECMP support. C. Performance Evaluation over different Traffic Matrices In this subsection we present the results of our first experiment, which evaluates the performance of our proposed MARL solution over traffic matrices that have not been seen during the training process. More in detail, we consider a fixed network topology and a set of traffic matrices; then our model is trained in that single topology using a subset of traffic matrices, and finally the trained system is evaluated over a different set with unseen traffic. In particular, we analyze two different traffic profiles (uniform and gravity model), each of them in two network topologies (NSFNet and GEANT2). In total we run four independent experiments, one for each combination of traffic profile and topology. At each experiment, we stop the training when the system has observed around 100 different traffic matrices (TM), and the model is evaluated over 100 new TMs. During training, TMs change every 50 training episodes. Figure 3 shows the evaluation result considering a uniform traffic profile. For the sake of readability, these plots show both the raw Minimum Maximum Link Utilization values obtained 3https://sites.uclouvain.be/defo/ 0 20 40 60 80 100 Traffic Matrix Evaluated 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 Min Max Link Utilization Default OSPF DEFO MARL+GNN (a) MinMaxLoad NSFNet 0 20 40 60 80 100 Traffic Matrix Evaluated 0.8 1.0 1.2 1.4 1.6 Min Max Link Utilization (b) MinMaxLoad GEANT2 0.7 0.8 0.9 1.0 1.1 1.2 1.3 Min Max Link Utilization 0.0 0.2 0.4 0.6 0.8 1.0 F(x) Default OSPF DEFO MARL+GNN (c) CDF NSFNet 0.8 1.0 1.2 1.4 1.6 Min Max Link Utilization 0.0 0.2 0.4 0.6 0.8 1.0 F(x) (d) CDF GEANT2 Figure 3: Evaluation results of Minimum Maximum Link Utilization with uniform traffic profiles in the NSFNet and GEANT2 network topologies. The evaluation is done over 100 traffic matrices unseen during training. for each TM, and the Cumulative Distribution Function (CDF) of these results. In this case, we can observe that our proposed MARL+GNN solution performs significantly better than default OSPF in both topologies (on average, ≈23% better in NSFNet and 42% in GEANT2) and stays near to the close-tooptimal solutions produced by DEFO algorithm (in GEANT2, it even improves it by 11%). Analogously, Figure 4 presents the evaluation results in scenarios with the gravity traffic profile. Again, our proposed MARL+GNN solution outperforms default OSPF in both topologies (on average, ∼25% better in NSFNet and 17% in GEANT2) and attains a comparable performance to DEFO. D. Generalization over other Network Topologies While traditional TE optimizers are typically designed to operate on arbitrary networks, current state-of-the-art MLbased solutions for TE suffer from a lack of topology generalization, partly explained by the fixed-size input scheme of most ML models (fully-connected NNs, convolutional NNs). That is, previous ML solutions could only operate on those toplogies seen during the training phase. Therefore, achieving generalization over different topologies is an essential step towards the versatility of state-of-the-art classical TE methods. Given that our distributed GNN-based proposal naturally allows variable-size network scenarios, as well as relational reasoning [20], [42], we are particularly interested in evaluating the generalization potential of our MARL+GNN solution over other networks not considered in training. For these experiments, we train our model in both NSFNet and GEANT2 topologies, and then evaluate it in a never-seen network (GBN). In this case, we stop the training when the 0 20 40 60 80 100 Traffic Matrix Evaluated 0.3 0.4 0.5 0.6 0.7 Min Max Link Utilization Default OSPF DEFO MARL+GNN (a) MinMaxLoad NSFNet 0 20 40 60 80 100 Traffic Matrix Evaluated 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 Min Max Link Utilization (b) MinMaxLoad GEANT2 0.3 0.4 0.5 0.6 0.7 Min Max Link Utilization 0.0 0.2 0.4 0.6 0.8 1.0 F(x) Default OSPF DEFO MARL+GNN (c) CDF NSFNet 0.4 0.5 0.6 0.7 Min Max Link Utilization 0.0 0.2 0.4 0.6 0.8 1.0 F(x) (d) CDF GEANT2 Figure 4: Evaluation results of Minimum Maximum Link Utilization with gravity-based traffic profiles in the NSFNet and GEANT2 network topologies. The evaluation is done over 100 traffic matrices unseen during training. 0 20 40 60 80 100 Traffic Matrix Evaluated 0.8 1.0 1.2 1.4 1.6 Min Max Link Utilization Default OSPF DEFO MARL+GNN (a) MinMaxLoad GBN 0.8 1.0 1.2 1.4 1.6 Min Max Link Utilization 0.0 0.2 0.4 0.6 0.8 1.0 F(x) (b) CDF GBN Figure 5: Evaluation results of Minimum Maximum Link Utilization for 100 different configurations in GBN after training the model using exclusively with samples of NSFNet and GEANT2. system observes a total of 100 TMs –alternating NSFNet and GEANT2 instances every 50 training episodes– and evaluate it over 100 TMs in GBN. Figure 5 presents the evaluation results of this experiment, showing the Minimum Maximum Link Utilization values obtained at each sample, as well as the CDF of these results. Here we can observe that the proposed solution significantly outperforms default OSPF (35% better on average) and it is very close -only within a 2% differenceto DEFO. E. Robustness against Link Failures The ability to generalize over different network topologies opens the door to address other uses cases that could not be solved with previous ML-based solutions. For example, in this section we assess how our solution performs when the network experiences link failures, which inevitably result in changes in the topology. To this end, we design the following 0123456789 Number of link failures 400 300 200 100 0 Performance decrease (%) DEFO MARL Figure 6: Performance degradation with increasing link failures for our NSFNet+GEANT2 model (applied to GBN), and DEFO. The plot shows the mean and standard deviation for 5 different TMs; for each TM we average the results on 10 scenarios with nrandom link failures. experiment: given a traffic matrix and a topology, our model previously trained in Section V-D is applied in networks with increasing number of random link failures –up to a maximum of 9failures. We repeat this experiment 10 times for a given number of failures n, exploring at each iteration different combinations of link failures. Figure 6 shows the mean and standard deviation of the performance degradation –w.r.t. the original network scenario with all the links– over 5different traffic matrices, using the model trained exclusively in NSFNet and GEANT2 (Sec. V-D) and applying it over the GBN network topology. These results are compared against DEFO, which is evaluated under the same conditions (i.e., same TMs and network scenarios). As we can observe, the performance decays gracefully as the number of removed links increases, showing an almost identical behavior to that of the state-of-the-art DEFO technique. F. Performance vs. Message Passing Iterations Previous experiments have shown that the proposed solution achieves comparable performance to DEFO across a wide variety of scenarios. However, there are still another important feature: the execution cost, which can be a crucial aspect to assess whether the proposed ML-based solution can achieve reasonable execution times for near real-time operation, as in DEFO. With the above objective in mind, in this section we first analyze the impact of one main hyperparameter of our MARL system, which is the episode length T. This is the maximum number of optimization steps that the MARL system needs to execute before producing a good set of link weights. Given that in our framework only one of the agents selects an action (i.e., increase its link weight) at each time-step of the episode, we expect a straightforward correlation between the number of steps and the total amount of links in the network: the larger the number of links, the larger should potentially be the episode explorations to achieve a good configuration. Finding the exact relation, though, depends on multiple complex factors (e.g., the distribution of links, the initialization of weights, the estimated traffic demands). By exploring systematically a variable number of steps in the three topologies considered above (NSFNet, GBN, NSFNet GBN GEANT2 SYNTH500 SYNTH1000 Episode Length 100 150 200 5,250 9,600 Execution Time (s) 9.98 ·10−21.33 ·10−12.12 ·10−18.40 19.2 Average MPNN-based Link Overhead∗(MB/s) 1.20 1.32 1.20 1.60 1.41 ∗It includes a 20% extra cost per message considering headers and metadata. Table I: Cost of our solution – Execution time and average link overhead. Applied to variable-sized network topologies, and assuming that hidden states are encoded as 16-element vectors of floats, and each Message Passing runs K=8steps. 0 25 50 75 100 125 150 175 200 Message Passing Iteration 100 2 × 100 3 × 100 4 × 100 MinMaxLoad So Far GEANT2 GBN NSFNet Figure 7: Evolution of the MinMax link load so far along an episode when applying our model (trained in NSFNet+GEANT2) respectively to NSFNet, GBN, and GEANT2. Plots show the mean and std. dev. over 5 runs, each considering a different TM. GEANT2), we have empirically found that with an episode length ≈2-3 times the number of links in the network, our system reaches its best performance –which is comparable to the near-optimal results of DEFO, as observed in previous sections. For instance, in our experiments it is sufficient to define T=100 for NSFNet, T=150 for GBN, and T=200 for GEANT2. This can be observed in Figure 7, which shows the evolution of the maximum link utilization achieved by our MARL system along an episode in the three network topologies. G. Cost Evaluation Considering the previous evaluation on the episode length (Sec. V-F), in this section we aim to evaluate the execution time of our solution to reach its best optimization potential. This is probably the main advantage that we can expect from ML-based solutions w.r.t. to near-optimal state-of-theart TE techniques, such as DEFO. Indeed, if we analyze the main breakthroughs of DRL in other fields (e.g., [10]), we can observe they have been mainly achieved in complex online decision-making and automated control problems. Note also that, after training, our multi-agent system is deployed in a distributed way over the network, thus distributing the computation of the global TE optimization process. Table I shows the execution time of our MARL+GNN trained system for the three real-world topologies used in our evaluation: NSFNet, GBN and GEANT2. Moreover, we also simulated executions over two synthetic networks –SYNTH500 (500 nodes, 1750 links) and SYNTH1000 (1000 nodes, 3200 links)– in order to analyze the cost of our distributed system in larger networks. As we can see, the execution time of our solution scales in a very cost-effective way with respect to the size of the network; from the order of milliseconds in NSFNet, GBN and GEANT2, to the tens of seconds in the SYNTH1000 network, with thousands of nodes and links. In contrast, DEFO requires 3 minutes for optimizing networks of several hundreds of nodes [7]. This shows an important reduction in the execution cost of our solution; particularly it represents a one-order-of-magnitude improvement in the case of the largest network (SYNTH1000). We note, though, that this improvement is achieved at the expense of exchanging additional GNN messages between nodes (MPNN). We show in Table I the MPNN communication cost in terms of the average link overhead resulting from such extra messages. As expected, the cost is quite similar in all topologies, as the messaging overhead of our distributed protocol is directly proportional to the average node degree (i.e., number of neighbors) of the network, and computations are distributed among all nodes. In particular, we can see that the average link overhead only involves a bandwidth of few MB/s per link independently of its capacity, which can reasonably have a negligible impact in today’s real-world networks with 10G/40G (or even more) interfaces. VI. RELATED WORK Network optimization is a well-known and established topic whose fundamental goal is to operate networks efficiently. Most of the work in the literature uses classical methods to optimize the network state (e.g., ILP). During the last decade a plethora of algorithms have been proposed, exploring a wide spectrum of techniques and network abstractions [7], [21]–[23]. Some works have previously attempted to apply DRL [11], [12], [47] or MARL [14], [18] to TE. However, they were unable to report a performance comparable to the state of the art, as they were compared to simpler routing schemes, such as SP routing (e.g., [12], [18], [48]), SP+ECMP (e.g., [14]), Load Balancing (e.g., [12], [47]) or oblivious routing (e.g., [11]). Our work is the first to be benchmarked against a stateof-the-art optimizer –i.e., DEFO [7]– and to provide enough evidence to address the open question posed in this paper. Moreover, most of the current state-of-the-art (MA)RLbased TE solutions [11], [12], [18] suffer from another limitation: they fail to generalize to unseen scenarios (e.g., different network topologies) as the implemented traditional neural networks (e.g., fully connected, convolutional) are not wellsuited to learn and generalize over data that is inherently structured as graphs. One exception is the work of [14], a