## 5 Algorithm
### E2E Operation and DGA Architecture
getPath complexity can be expressed as follows:

\[O^{getPath}=k\cdot[O(VlogV+E)+O(E)+O(F)] \tag{24}\]

where \(O(E)\) is the worst case for the virtual path allocation procedure (number of hops equal to number of graph edges) and \(O(F)\) is the inference complexity of DGA's Q-network. To simplify the above terms, it is approximated that the number of edges is approximately the number of nodes times the average node degree \(E\approx deg(V)\cdot V\), leading to the following:

\[O^{getPath} =k\cdot[O(V[logV+deg(V)])+O(V\cdot deg(V))+O(F)]\] \[=k\cdot[O(VlogV)+O(V\cdot deg(V)+O(V\cdot deg(V))+O(F)]\] Figure 4.0 Figure 4.1 Figure 4.2

The E2 EP calculation complexity \(O^{getPath}_{total}\) is affected by computing the rough E2 EP and IDPs:

Figure 4.3 Figure 4.4

As described in Section 5.3, the applied DGA model exploits GNNs to aggregate the node/edge information based on the neighbourhood. Hence, the linear increase in network size will not require linear scaling of the model size to maintain performance (\(O(F)\approx O(1)\)). This allows for omitting the \(O(kF)\) term and simplifying Equation (26) to the following:

Figure 4.5

Finally, each path undergoes verification regarding QoS constraints on both the local and domain levels, which requires iterating over path segments, giving the worst-case complexity of \(O(E)\). Nonetheless, this term can be omitted as the overall complexity of path computation (cf. Equation (27)) will always be dominant, and the path length will usually be much lower than the number of edges. Finally, the overall complexity depends on the number of candidate paths and network graph properties: node degree, number of nodes, topology, and domain split. Figure 5 shows the 3 DQR complexity for a different number of domains \(|\mathfrak{v}|\). For complexity calculation, the percentage of BNs \(\psi_{r}=0.2\) (i.e., \(V^{\Psi}=V\cdot\psi_{r}\)) and an equal split of nodes across domains (i.e., \(|V^{\mathfrak{v}}|=\frac{|V|}{|\mathfrak{v}|}\)) are assumed. For reference, 3 DQR complexity is compared to centralised SP routing and Hierarchical Shortest Path (H-SP) routing (i.e., using SP routing at both overlay and domain levels). E2 EP calculation using 3 DQR, in general, features much higher complexity than the other baseline routing schemes. For the increasing number of domains, however, as the operations are distributed across multiple SDNCs, the overall complexity rapidly diminishes. For a low number of computed candidate paths (\(k=4\)) and the relatively small number of domains considering real-life networks (i.e., \(|\mathfrak{v}|=8\)), 3 DQR has almost the same complexity as single-controller SP. Whilst H-SP complexity always surpasses 3 DQR, it does so at the cost of worse performance in terms of load distribution and flow acceptance rate as described in Section 6.1. ## 6 Evaluation

3 DQR in the most common case comprising LEO NTN nodes (a subset of Starlink satellites) and synthetic TN mesh-like topologies are evaluated. As LEO satellites constitute the extreme mobility case, the conclusions can be extended over 3D networks due to the typically slow mobility of aerial stratum nodes. The evaluation was conducted using the proprietary event-driven simulator implemented in Python 3.10 and based on SimPy 4.1.1 [55] (hierarchical multi-domain SDN), PyTorch 2.5.0, and PyTorch Geometric 2.6.1 [56] libraries (DRL-based routing). To implement GIMMF, the Skyfield 1.48 library [57] and publicly available Two-Line Element (TLE) files (satellite orbits' descriptors) [58] were used. The 3 DQR tests covered three different scopes (cf. Table 1):

* Performance--showing gains of 3 DQR compared to three baseline methods: (i) the most-common SP routing using link delay as the weight metric at both overlay and domain levels, further referred to as H-SP; (ii) a combination of SP for overlay routing and NTNs and classic DDQN for TNs (DNN-based architecture), and 3 DQR-Uncoordinated (3 DQR-U)--domain DGAs and SP-routing at the overlay level (cf.