# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 5 Reinforcement Learning for Routing Optimization
### Literature Review  
As a pioneering work on integrating DRL and GNN in network optimization, an MPNN-based deep Q-network (DQN) architecture is proposed in [109] to find the optimal routing configuration with a given traffic matrix and generalize over arbitrary network topologies. The GNN model is incorporated into the DRL agent to compute the Q value and the message-passing steps are briefly stated as follows. 1. The link features over its neighbors are combined for a single link with a fully connected neural network into messages. 2. The messages over its neighbors are aggregated for a single node with an element-wise sum. 3. The link hidden states are updated with the aggregated information with a recurrent neural network. 4. The resulting link states for \(T\) iterations are aggregated using an element-wise sum. 5. The q-value is the output of the readout function with a fully connected neural network. The proposed architecture outperforms the state-of-the-art DRL algorithms without using GNNs on unseen network topologies. Routing and spectrum assignment (RSA) in an elastic optical network are considered jointly in [110], in which a GCN is used to extract topology-related features and an RNN is used to extract path-related features. Then, the advantage actor critic (A2C) algorithm [111] is used to make the RSA decision, in which the reward function is designed as a binary value when a successful RSA decision (i.e., a successful provision of routing and spectrum assignment) generates a positive reward. The proposed approach achieves a lower blocking probability and exhibits good scalability, with different network topologies, bandwidth requirements, and traffic loads. Another multi-task deep reinforcement learning framework is proposed in [112] for joint network slicing and routing in an SDN-based 6G network. A customized GCN is used to capture topological information from the graph-structure network status. The actor-critic algorithm is used in the DRL agent to minimize packet loss while simultaneously maximizing the link bandwidth utilization and the service level agreement (SLA) satisfaction ratio with different importance coefficients. Multiple metrics such as throughput, latency, and packet loss rate are used in the evaluation. The numerical experiments demonstrate that the GCN-based multi-task DRL outperforms other learning-based algorithms for joint network slicing and routing tasks and is robust to diverse network environments. In AutoGNN [113], the MPNN is used to process traffic-related information collected by the SDN controller, and DRL is used to generate the action to be performed by the SDN controller. Numerical experiments demonstrate that AutoGNN improves the average end-to-end delay of the network by up to 19.7% and presents greater robustness against topology changes. Based on the combination of the MPNN and the deep deterministic policy gradient (DDPG) algorithm, GRL-NET [114] obtains a lower transmission energy consumption and shows good generalization ability for unseen topologies. MPNN is used to model the graph structure in network topology and DDPG is used for routing under the possible failure of network nodes, which causes the network topology change. GraphNET [115] is proposed to predict the optimal path in SDNs based on a combination of GNN and DQN. The GNN model is deployed in the SDN controller and selects the next node for each routing request received by the controller, in which the input is the hidden state matrix for all links, and the output is an expected reward vector for choosing each link. A deep Q-network is developed to train the GNN model with prioritized experience replay to maximize the expected reward and minimize the packet delay. Experiments on both small and large network topologies demonstrate that GraphNET outperforms q-routing without GNN and shortest-path routing algorithms in terms of packet delivery success ratio and average packet delay time. In addition, it is robust to changes in the network structure.