# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 2 Basics
### Routing Basics
In recent years, machine learning methods, including neural networks and reinforcement learning, have emerged, often integrating with existing algorithms to create adaptive and efficient routing solutions, highlighting a trend toward hybridization in optimization techniques. Based on different criteria, existing routing solutions and protocols can be classified into different types, for example, central versus distributed, deterministic versus probabilistic, and static versus dynamic [7]. A comparison between centralized and distributed routing schemes is shown in Figure 2. The advantages of centralized routing include global optimization and control abilities, while the disadvantages include higher time and traffic overhead for real-time network status collection. The high decision delay for obtaining a global optimal routing solution as the network scale increases is both impractical and unacceptable. In distributed routing, each router makes its own decision based on its local information; thus, the decision-making time overhead is low, and some recent progress has been made to further improve the distributed routing efficiency, for example, multi-agent reinforcement learning algorithms. However, distributed routing has difficulty achieving a globally optimal solution. Some classical distributed routing protocols include distance vector routing protocols, such as Routing Information Protocol (RIP) and BGP, and link state routing protocols,  
Figure 1: The timeline of routing optimization methods. Figure 2: The comparison between centralized and distributed routing schemes [10]. (**a**) Centralized routing; (**b**) Distributed routing. such as OSPF. Link state routing is generally based on the shortest path first idea and consumes more resources (e.g., computer memory and computation units) than distance vector routing. However, it is free from the count-to-infinity problem and performs better when the network size is small. Although these classical routing protocols have already been applied in real-world networks, for example, the Internet, they are not perfect. An example of the suboptimal routing decision made by the OSPF is shown in Figure 3, in which the traditional shortest path-based routing algorithm assigns all traffic to the bottleneck link when the available bandwidth (e.g., 100 Mbps) of the selected path is much smaller than the service demand (e.g., 500 Mbps) and a smarter route with two paths and a traffic split exists. More routing solutions emerge with the development of SDNs, including both centralized and distributed ones, facilitated by the ability to capture the real-time link status and perform global optimization. The introduction of software-defined routers (SDRs) allows complex routing operations to be integrated into programmable routers [1]. Currently, sophisticated intelligent routing schemes can be deployed in centralized controllers or distributed smart routers such as RouteFlow, which provides virtualized IP routing services over OpenFlow enabled hardware ([[http://cpqd.github.io/RoutFlow/](http://cpqd.github.io/RoutFlow/)]([http://cpqd.github.io/RoutFlow/](http://cpqd.github.io/RoutFlow/)), accessed on 22 September 2024). Several metrics are widely adopted to evaluate and compare different routing schemes, including packet delivery ratio (PDR), transmission delay, throughput, and routing overhead [20]. * PDR is defined as the ratio of successfully transmitted packets between the source and destination nodes. * Transmission delay is defined as the transfer time from the source to the destination. * Throughput is defined as the multiplication of the packet size and the data packet number in a unit of time. * Routing overhead is defined as the ratio of the control packet number, e.g., route discovery and maintenance packets, to the total transmitted data packet number.