Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case

Paul Almasan; José Suárez-Varela; Krzysztof Rusek; Pere Barlet-Ros; Albert Cabellos-Aparicio

Source-linked AI summary

Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case

Paul Almasan, José Suárez-Varela, Krzysztof Rusek, Pere Barlet-Ros, Albert Cabellos-Aparicio

arXiv:1910.07421v3Oct 16, 2019cs.NIcs.LG

TL;DR

Existing DRL networking solutions have limited generalization to unseen topologies, hindering their use in production networks. The paper integrates GNNs into DRL agents for optical-network routing and reports effective performance on unseen synthetic and real-world topologies. The authors also identify out-of-distribution data as a limitation and leave further generalization improvements for future work.

Problem
Existing DRL networking solutions fail to generalize to unseen network scenarios, limiting their potential deployment in production networks.
Method
The paper integrates a GNN-based graph model with a DRL agent for routing optimization in optical networks.
Results
The DRL+GNN agent achieves strong generalization and effectively operates on network topologies never seen during training, including real-world networks.
Takeaways & Limitations
Modeling network environments with GNNs allows the DRL agent to operate on different networks than those used for training.
Takeaways & Limitations
Performance is expected to drop on out-of-distribution topologies, link features, and traffic matrices that radically differ from training data.

Abstract

from arXiv · show

Deep Reinforcement Learning (DRL) has shown a dramatic improvement in decision-making and automated control problems. Consequently, DRL represents a promising technique to efficiently solve many relevant optimization problems (e.g., routing) in self-driving networks. However, existing DRL-based solutions applied to networking fail to generalize, which means that they are not able to operate properly when applied to network topologies not observed during training. This lack of generalization capability significantly hinders the deployment of DRL technologies in production networks. This is because state-of-the-art DRL-based networking solutions use standard neural networks (e.g., fully connected, convolutional), which are not suited to learn from information structured as graphs. In this paper, we integrate Graph Neural Networks (GNN) into DRL agents and we design a problem specific action space to enable generalization. GNNs are Deep Learning models inherently designed to generalize over graphs of different sizes and structures. This allows the proposed GNN-based DRL agent to learn and generalize over arbitrary network topologies. We test our DRL+GNN agent in a routing optimization use case in optical networks and evaluate it on 180 and 232 unseen synthetic and real-world network topologies respectively. The results show that the DRL+GNN agent is able to outperform state-of-the-art solutions in topologies never seen during training.

I. INTRODUCTION

Network operators face demanding optimization problems, while existing DRL networking solutions struggle to generalize beyond training topologies. The paper combines GNNs with DRL to support routing decisions across unseen network structures.

Modern applications impose high-throughput and low-latency requirements, increasing the need for efficient network-resource management.Operators typically rely on expert knowledge or ILP and Constraint Programming solvers.
ILP or Constraint Programming solvers can take substantial time on production networks with hundreds of nodes, while heuristics are far from optimal.
Existing DRL networking solutions fail to generalize effectively to network scenarios not seen during training.Here, generalization means adapting to new topologies or configurations.
Training directly in customer networks is often infeasible because it is costly, lengthy, requires instrumentation, and can degrade service during exploration.
The agent is designed to generalize across unseen arbitrary topologies, supporting deployment without retraining or customer-network instrumentation.
The proposed architecture integrates GNNs into DRL agents to model graph-structured network scenarios and target routing optimization in optical networks.Its GNN is inspired by Message-passing Neural Networks and captures relations between links and network traffic.
The evaluation reports strong generalization against state-of-the-art DRL algorithms, including tests on 232 different real-world topologies.
After training, the agent makes routing decisions in approximately milliseconds, with cost scaling linearly with network size.

II. BACKGROUND

GNNs represent graph-structured network data by iteratively exchanging information among connected elements. The paper combines this graph modeling capability with DRL for network optimization.

The proposed solution combines GNN-based network modeling with DRL, which learns to operate networks toward a specified optimization objective.
GNNs associate initial states with graph elements and iteratively update them according to graph connectivity to produce task outputs.
MPNNs propagate information by generating messages between neighboring nodes, aggregating those messages, and updating node hidden states.
After message passing, a readout function uses final node states to predict individual-node or graph-level properties.
Because computer networks are represented as graphs, GNNs are inherently suited to network modeling compared with fully connected or convolutional architectures.

B. Deep Reinforcement Learning

The paper frames OTN routing as a sequential decision problem in which a DRL agent selects routes for incoming demands while managing persistent link capacity. DQN addresses high-dimensional state and action spaces, but exact MDP solutions become infeasible as networks grow.

DRL learns a policy by exploring states and actions, receiving rewards after transitions, and maximizing cumulative reward over an episode.
DQN uses a deep neural network to approximate q-values when tabular Q-learning becomes difficult in high-dimensional state and action spaces.
The OTN agent receives source-destination-bandwidth demands and selects an end-to-end path through a logical topology of ROADM nodes and lightpaths.
A demand is allocated only when every lightpath on its selected route has sufficient available capacity, and accepted demands occupy capacity until episode end.
MDP state-space complexity is approximately O(N^E), making optimal iterative solutions infeasible for large and complex networks.N is the number of different link capacities and E is the number of links.

IV. GNN-BASED DRL AGENT DESIGN

The proposed agent combines DQN with a GNN that represents the network as link entities and processes graph-structured observations through message passing. Link capacity and betweenness provide the state features used to evaluate routing actions.

The DRL agent implements DQN with a GNN modeling the q-value function, while actions allocate demands on candidate paths.
At each time step, the GNN builds a graph from the observed network state and initializes link hidden states from link features and the routing action being evaluated.
Each link state includes available capacity and link betweenness, which measures the fraction of candidate end-to-end paths crossing that link.The authors report that betweenness helps the agent converge faster to a good policy.

B. Action Space

The agent reduces routing complexity by evaluating four shortest candidate paths per source-destination pair and encoding each action as a link-level feature. Its MPNN propagates link information before producing a q-value.

Action Space: The action space is limited to k=4 shortest paths by hop count for each source-destination pair.This reduces action dimensionality while preserving a fixed action definition across topologies.
Action Space: Each routing action is encoded as the requested bandwidth on selected links and zero on unselected links, using an N-element one-hot vector for discrete demands.
Action Space: The link hidden states jointly represent network state and the candidate action used to evaluate Q(s, a).
GNN Architecture: The hidden-state size must preserve both each link’s own features and aggregated neighbor information without making the GNN unnecessarily large.
GNN Architecture: The MPNN performs T message-passing steps, sums neighboring-link messages, updates link states with an RNN, and applies a readout DNN to estimate the q-value.

D. DRL Agent Operation

The DRL agent interacts iteratively with an environment that generates traffic demands and network states, evaluates candidate routing actions, and updates its experience through replay.

The agent initializes link features, traffic demand, environment state, action-set size, cumulative reward, and an experience replay buffer.

A. Evaluation Setup

The evaluation uses an OTN simulator with multiple demand types and a DRL agent that selects among candidate paths while learning from allocation rewards.

The implementation uses TensorFlow and an OpenAI Gym-based OTN network simulator, with source code and results publicly available.
Traffic demands use ODU2, ODU3, and ODU4 types requiring 8, 32, and 64 ODU0 bandwidth units, respectively.
Correct allocation receives an immediate reward equal to the demand bandwidth, whereas unsuccessful allocation receives zero reward.
The agent operation initializes the environment and repeatedly evaluates candidate paths, selects an action, updates the state, and stores experience.
Uniform traffic makes all demand types equally probable, limiting opportunities to anticipate difficult-to-allocate future demands.
Link hidden states are 27-element vectors containing the defined link features, with larger or more complex scenarios potentially requiring larger states.

B. Methodology

The methodology benchmarks DRL+GNN routing against state-of-the-art DRL and reference policies, including tests on trained and unseen network topologies.

The experiments assess performance and generalization, using a state-of-the-art DRL routing optimizer as the principal baseline.
Exact optimal MDP solutions are infeasible because even a small six-node, eight-edge example has approximately 1.17e7 states.
The theoretical fluid model splits traffic across k=4 paths according to available capacity, while the load-balancing policy randomly selects one path.
Training uses the 14-node Nsfnet topology, 1,000 iterations, and an action set containing its k=4 shortest paths.
6.6% more bandwidth is allocated by DRL+GNN than SoA DRL on Nsfnet, while the corresponding Geant2 comparison reports 3% more bandwidth.
On unseen Geant2 after training on Nsfnet, DRL+GNN achieves more than 45% performance improvement over SoA DRL in 80% of experiments.

D. Use case: Link failure resilience

The deployment analysis examines resilience to link failures, scalability across unseen topologies, and computation time after deployment.

D. Use case: Link failure resilience: The link-failure use case tests whether DRL+GNN can adapt routing configurations when network connectivity changes unpredictably.
D. Use case: Link failure resilience: Experiments randomly remove n ∈[1, 10] links from Geant2 while the agent avoids affected links and maximizes allocated bandwidth.
Deployment discussion: Deployment analysis frames generalization as enabling laboratory training before shipping the agent to production networks.
Deployment discussion: Scalability experiments measure effectiveness across larger unseen synthetic and real-world topologies and measure post-deployment routing-decision computation time.
Deployment discussion: The agent is trained on 14-node Nsfnet and evaluated on unseen topologies of up to 100 nodes.

1) Synthetic topologies:

The DRL+GNN agent was evaluated on synthetic and real-world topologies unseen during training, showing strong generalization across network sizes and structures. Performance remains robust as topology size increases, while results across real-world topologies support topology-independent operation.

Synthetic evaluation: 180 synthetic topologies with 20–100 nodes were generated, using 1,000 evaluation episodes per topology.The topologies had an average node degree similar to Nsfnet, enabling analysis of network-size effects.
Synthetic evaluation: Performance scaled inversely with topology size, but the agent maintained remarkable performance on unseen topologies.Relative scores were computed against the theoretical fluid model.
Synthetic evaluation: 30-node topologies matched the theoretical fluid model despite doubling the 14-node training topology, while 100-node topologies showed only a 15% performance drop.The results indicate graceful degradation as network size diverges from training.
Real-world evaluation: The architecture operated effectively on 232 real-world topologies, including networks differing substantially from the single 14-node training topology.Good performance extended to real-world topologies with up to 100 nodes.
Real-world evaluation: Training only on Geant2 produced a mean relative score of +4.78% against the theoretical fluid model across all real-world topologies.This result was obtained by evaluating on the complete real-world topology set.

B. Computation Time

The trained DRL+GNN agent operates with millisecond-scale inference time whose growth is approximately linear in topology size. Its generalization is strongest for topologies resembling training data and weakens as structural characteristics diverge.

Computation time: Inference takes a few milliseconds and grows linearly with topology size on off-the-shelf hardware.The measured time is the duration required to select paths for all incoming traffic requests.
Generalization limitations: The agent’s out-of-distribution performance is expected to drop when topology, link features, or traffic matrices differ radically from training data.The method learns from past interactions with the environment, making distribution shift a stated limitation.
Generalization limitations: Performance issues on some topologies are attributed primarily to changes in network topology, since link features are normalized and traffic demand bandwidths are fixed.Topology changes directly affect DRL-agent performance in the reported experiments.
Topology dependence: As synthetic topologies become larger, lower node and edge betweenness indicate more distributed shortest paths and worsening performance relative to Nsfnet.The topology metrics show that increasing structural difference from Nsfnet accompanies poorer DRL performance.
Topology dependence: Real-world topologies with the worst performance differ radically from Nsfnet, including cases with nodes having very high connectivity.The same relationship between topology difference and performance appears in the real-world evaluation.
Future work: Improving generalization through broader training topologies, regularization, dropout, or richer neighbor aggregation remains future work.The authors explicitly leave these improvements outside the scope of the paper.

VII. RELATED WORK

Prior network-optimization research relies mainly on ILP, constraint programming, heuristics, or DRL with fixed-size representations. This paper addresses the resulting generalization problem by combining DRL with GNNs for unseen network topologies, while acknowledging broader deployment challenges.

Traditional optimization: Traditional network-optimization methods include ILP, constraint programming, and genetic-algorithm heuristics for routing and configuration problems.These methods target efficient network operation but may involve computational complexity or locally optimal solutions.
DRL-based approaches: Routing optimization from a traffic matrix is NP-hard, motivating DRL-based approaches for spectrum assignment and related network-control tasks.Earlier DRL solutions used Q-learning, convolutional neural networks, or richer fixed representations of network state.
Generalization gap: Most prior DRL networking solutions fail on unseen topologies because fixed-size matrix representations and traditional neural networks do not generalize over graph-structured networks.These agents consequently perform poorly when evaluated on topologies absent from training.
GNN-based networking: Related work has applied GNNs to shortest-path routing, max-min routing, network planning, metric prediction, and distributed traffic engineering.The paper positions its DRL+GNN architecture within this emerging use of graph-based learning for communications networks.
Paper contribution: The proposed GNN-based DRL architecture operates on unseen network topologies, addressing a deployment obstacle identified for DRL in production networking.The authors describe it as a first step toward DRL-based networking products.
Deployment challenges: DRL remains difficult to deploy because its black-box behavior offers no guaranteed performance across all network scenarios and complicates troubleshooting.This challenge persists even when generalization to unseen topologies is improved.