# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 5 Reinforcement Learning for Routing Optimization
### Literature Review
GDDR [116] is proposed to minimize link congestion in intradomain traffic engineering, based on a combination of GNN and DRL. Given the network topology in graph format and the traffic demand matrix as inputs, GDDR predicts a routing strategy with proximal policy optimization (PPO) as the DRL algorithm. The reward is defined as the maximum link utilization ratio between the DRL-based routing and the optimal routing solved using a linear solver named Google OR-Tools. GDDR achieves a lower maximum link utilization ratio than the multilayer perceptron-based baseline and shortest path routing, with the ability to generalize unseen network topologies during training. Based on the MPNN and DQN, GROuting [117] is proposed to select the optimal routing path between two satellites in the fast-growing low Earth orbit (LEO) satellite network, with the routing objective of maximizing the utilization of satellite network resources while guaranteeing the requirement of transmission delay. The reward function is designed as the gain from successful transmission minus the delay penalty. The experiments show that GROuting outperforms four baseline algorithms, including the shortest path, random path, request balance, and DQN without GNN, in terms of throughput and shows better generalization for time-varying topologies. Based on GAT and DQN, deep graph attention network routing (DGATR) [48] is a multi-agent routing framework that minimizes end-to-end delay. GAT is introduced for the first time to perform routing by leveraging the local information at each router with the graph attention mechanism. Both RL-based and non-RL-based algorithms are used as baselines in the experiments, including the shortest path, tabular Q-learning, a hybrid method of tabular Q-learning and policy gradient method, DQN routing without GNNs, and optimal global routing. DGATR outperforms other RL-based algorithms without GNNs in terms of packet transmission delay and affordable load. DGATR also shows better adaptability and can sustain a higher network load than other algorithms, except for the optimal global routing scheme. Three different learning paradigms are proposed and compared: centralized, federated, and cooperated learning [118]. The experiments show that while the three learning paradigms achieve indistinguishable maximum affordable loads, the cooperated learning approach achieves a lower delay and better stability because the variation in the parameter update is relatively small when parameter aggregation is restricted in cooperated learning. A multi-task framework for joint routing and scheduling optimization in a time-sensitive network is proposed in [119] based on the combination of GCN and deep Q-learning. The GCN is leveraged to capture spatial dependency, and a priority experience replay is employed to accelerate the GCN training process. In the experiments, the proposed approach achieves good convergence and a lower end-to-end delay than baselines, including DQN-based, Q-learning-based, and shortest-path routing schemes. A deep graph reinforcement learning (DGRL)-based framework is proposed in [49] for intelligent traffic control in a software-defined wireless sensor network. DGRL is based on the actor-critic framework, in which a GCN model is used in the actor network to extract and aggregate the state features of the current node and all its neighbors. Each wireless node optimizes its own transmission path and creates the best hop policy in an online training approach. The reward function is well-designed for multiple objectives, including a shorter forwarding time, shorter forwarding path, and lower buffer occupation. The proposed DGRL outperforms the OSPF and DRL baselines without GNNs in simulation experiments based on the OMNet++ platform, in terms of packet transmission delay, PDR, and network congestion probability. An efficient real-time routing optimization (ENERO) solution is proposed in [51] for routing optimization in wide area networks (WANs) using a two-stage process.