# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 2 Basics  
### Routing Basics  
Routing is a process of transmitting data packets from a source node to a destination node. A node can be a server or user device in a communication network. Routing is widely considered and applied to the networking layers. This process involves two steps in general, namely, optimal path selection and data forwarding. The former is the key problem in designing a routing algorithm, and the latter is typically performed by a router based on the corresponding routing policy. As shown in Figure 1, routing optimization methods have evolved significantly since their inception, starting with classical algorithms like Dijkstra's and Bellman-Ford in the 1950s and 1960s, which provided foundational techniques for finding the shortest paths in graphs. The 1980s introduced heuristic methods, such as the A* algorithm, which utilized heuristics to enhance search efficiency. The 1990s saw the rise of metaheuristic approaches, including Genetic Algorithms and Simulated Annealing, which employed evolutionary and probabilistic strategies to solve more complex routing problems. In the 2000s, techniques like Particle Swarm Optimization and Tabu Search emerged, inspired by natural phenomena and memory-based strategies. The 2010s marked the incorporation of machine learning, with neural networks and reinforcement learning being applied to optimize routing dynamically. Today, hybrid methods that combine various techniques \begin{table}
\begin{tabular}{l l} \hline \hline
**Abbreviation** & **Full Name** \\ \hline DQN & Deep Q-Network [50] \\ DRL & Deep Reinforcement Learning \\ ENERO [51] & EfficientNet rEal-time Routing Optimization \\ FANET & Flying Ad Hoc Network \\ FCT & Flow Completion Time \\ GAT & Graph Attention Network \\ GCN & Graph Convolutional Network \\ GG-NN & Gated Graph Neural Network [52] \\ GN & Graph Network \\ GNN & Graph Neural Network \\ GQNN & Graph-Query Neural Network [53] \\ IBN & Intent-Based Networking \\ IoT & Internet of Things \\ LEO & Low Earth Orbit \\ MANET & Mobile Ad Hoc Network \\ MAPE & Mean Absolute Percent Error \\ ML & Machine Learning \\ MPNN & Message Passing Neural Network \\ MPTCP & Multipath TCP \\ MRE & Mean Relative Error \\ OSPF & Open Shortest Path Protocol \\ PDR & Packet Delivery Ratio \\ PyG & PyTorch Geometric \\ QoS & Quality of Service \\ RIP & Routing Information Protocol \\ RL & Reinforcement Learning \\ RSA & Routing and Spectrum Assignment \\ SAGIN & Space-Air-Ground Integrated Network \\ SDN & Software Defined Networking \\ SDR & Software Defined Router \\ SLA & Service Level Agreement \\ S-LRR & Sequential Link-Reversal Routing \\ TCP & Transmission Control Protocol \\ UAV & Unmanned Aerial Vehicle \\ WAN & Wide Area Network \\ WSN & Wireless Sensor Network \\ \hline \hline \end{tabular}
\end{table} 
Table 2: _Cont._including DNNs and DRLs are increasingly prevalent, addressing the growing complexity and variability of real-world routing challenges. Existing routing optimization methods are interconnected through their foundational principles and strategies, often influencing one another to enhance performance and applicability. Classical algorithms like Dijkstra's and Bellman-Ford provide essential frameworks for shortest-path calculations, while heuristic methods like A* build on these foundations by incorporating heuristics to improve search efficiency in more complex scenarios. Metaheuristic techniques, such as Genetic Algorithms and Simulated Annealing, expand on these concepts by applying natural and probabilistic principles, allowing for effective solutions to difficult optimization problems. Additionally, methods like Tabu Search and Particle Swarm Optimization introduce memory and swarm intelligence concepts, respectively, showcasing diverse strategies that complement traditional approaches.