# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 3 Supervised Learning for Network Modeling
### Literature Review  
RouteNet [92; 93; 30; 61] is the first GNN network model based on the MPNN, with the optimization goal of minimizing per-source/destination average delay and/or jitter, with the input of the network topology, traffic matrix, routing scheme, and output of the performance metrics. Based on the packet-level simulator OMNeT++, simulated datasets are generated using real-world computer network topologies and used to train the GNN model. The topologies used in the training and test stages are different for evaluating the model performance in the unseen cases. RouteNet can predict the delay distribution (mean delay and jitter) and loss accurately; even when information regarding the topologies, routing and traffic is unavailable in the training, it still achieves a worst-case mean relative error (MRE) of 15.4%. The predictions of RouteNet are further leveraged in a network planning use case to select optimal link placement. RouteNet (including its improved variants) and the simulated dataset are further used in the Graph Neural Networking Challenge 2020 as one of the open global challenges for ITU AI/ML in the 5G challenge [94]. Additional GNN-based network models are further developed following the basic ideas of RouteNet. A new GNN model is proposed to predict the per-path mean delay based on the input topology, routing configuration, queue scheduling policy, and traffic ma trix [95]. Compared to RouteNet, the new GNN model adds support for different queuing policies and produces more accurate delay estimates in cases with complex queue scheduling configurations. To solve the problem that the generalization of RouteNet suffers greatly when predicting on super large graphs, the invariant features from the analytical queueing theory approach are extracted and fed into the GNN-based model QT-Routenet [96]. The traffic intensity and probability of being in state zero are calculated using the analytical baseline which is derived from queueing theory and used as new features. QT-RouteNet outperforms both RouteNet and the analytical baseline, which reduces the analytical baseline's 10.42 mean absolute percent error (MAPE) to 1.45 (1.27 with an ensemble). QT-RouteNet achieved first place in the GNNet Challenge 2021. RouteNet-Erlang [97] extends the input of RouteNet with multi-queue scheduling policies and outperforms all queueing theory baselines under several different traffic models with a worst-case delay prediction error of 6%. Based on a graph network (GN) [98], a GNN model is used to determine the flow completion time (FCT) in [99], which infers FCT statistics directly from the network topology and flow matrix in real-time. The estimation of unseen network states is then used for traffic optimization, including inflow routing, flow scheduling, and topology management, with a GNN-based optimizer that explores the optimal configuration based on both the network's state and the administrator's target. The proposed solution significantly reduces the flow completion time. The multipath TCP (transmission control protocol) is considered in [100] for an SDN-based 5G network, and an MPNN-based GNN model is proposed to predict the expected throughput given the network topology and multipath routes. A topology explorer is responsive to maintaining the network topology information and three key features, namely bandwidth, delay, and packet loss rate of a link, as used to model the input. A routing generator is responsible for generating potential routing schemes using random or greedy algorithms based on the latest network topology and transmission demand. The GNN model is trained offline and deployed online to evaluate the performance of different routing schemes with the expected throughput as the metric. A decision maker chooses the optimal MPTCP scheme and sends the configurations to network devices, for example, routers and switches. The proposed approach is compared with a globally optimal baseline, which is computationally unrealistic in practice, and a traditional MPTCP full-mesh algorithm.