# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 2 Basics
### Machine Learning Basics  
Traditional routing algorithms are mainly based on the idea of finding the shortest path based on delay, distance, or hop count, without considering the real-time status of links. They are prone to problems including the local congestion of network links, low link utilization ratio, and waste of network resources. To overcome these problems, some manual routing policy optimization solutions have been proposed, for example, manual routing configuration optimization or switching among pre-defined routing configuration parameter sets for typical traffic scenarios. However, these solutions are neither effective nor efficient, and their routing performance deteriorates significantly in the worst case. ML techniques, especially deep learning (DL), are introduced to optimize the routing strategy automatically, which learns a desired routing configuration for future cases based on the knowledge of past conditions [1; 55]. Another challenge for traditional routing algorithms is traffic bursts, which overwhelm physical links in a short time and cause traffic congestion, frequent packet losses and  
Figure 3: An example of the suboptimal routing decision made by OSPF [54]. increased end-to-end delays. Traffic bursts arise for different reasons, such as protocol-side (e.g., different TCP window sizes caused by the congestion control mechanism) or application-side (e.g., different data sizes used for different frames in video streaming). Most of the existing routing protocols are traffic-free and lack adaptation ability under different traffic scenarios. Centralized routing algorithms, which are mainly based on linear programming methods, require a long computational time overhead, making it infeasible to handle traffic bursts. ML-based routing solutions can overcome this problem and adapt to traffic bursts quickly because the inference time of the trained ML models is negligible compared with that of traditional solutions. For example, the inference time of the trained ML models is about 10 s, and traditional solutions require more than 1000 s [56]. The third concern regarding traditional routing algorithms is the limitation of their best-effort optimization ability for finding the shortest path as the only objective, which cannot meet the differentiated QoS requirements of new network services, such as multimedia and remote cloud services. Nonetheless, more routing optimization objectives can be adopted in ML-based routing schemes, such as data packet reachability, algorithm scalability, latency, bandwidth, throughput, packet loss rate, and network stability. Two specific ML-based approaches are widely used for routing optimization: supervised learning and reinforcement learning. In a supervised learning approach, input and output samples are collected and used to train a model so that the model can accurately complete a class of machine learning tasks that are mapped from input to output. The general framework for applying supervised learning to routing optimization is shown in Figure 4, in which the network topology and network state information are the inputs, and the routing decisions are the outputs. Supervised learning methods rely on many labeled data samples. In routing scenarios, it is difficult to obtain a large number of labeled samples within a short period. Fortunately, the reinforcement learning approach does not rely on a training process using historical data. The performance of an RL agent gradually improves in the process of continuous interaction with the environment, based on the reward as feedback to update the model parameters. The general framework for applying reinforcement learning for routing optimization [57] is shown in Figure 5. Reinforcement learning strategies further extend the capabilities of GNNs by enabling adaptive routing policies based on feedback from the environment [58].