## 5 Algorithm
### E2E Operation and DGA Architecture
To enable time-variant and size-variant graph input for the agent, a GNN-based approach is adopted. The Q-network architecture is comprised of the following layers:

* Standard MPNN--used to obtain the embeddings \(\phi\) of nodes using both edge and node features. The standard MPNN model is used [53], which defines two phases of a forward operation: message passing (Equation (21)) and readout phases, where \(M_{t}\)--a message function, \(U_{t}\)--vertex update function, \(h_{v}^{t}\)--hidden state, \(m_{v}^{t+1}\)--message, and \(T\)--passing step. \[m_{v}^{t+1}=\sum_{w\in N(v)}M_{t}(h_{v}^{t},h_{w}^{t},e_{ww})\] (21) \[h_{v}^{t+1}=U_{t}(h_{v}^{t},m_{v}^{t+1})\] Both message \(M_{t}\) and vertex update functions \(U_{t}\) are implemented using concatenation, Multi-Layer Perceptron (MLP) with ReLu activation, and sum as the aggregation operator (cf. Equations (22) and (23)). \[M_{t}=MLP(h_{v}||h_{v});\,w\in N(v)\] (22) \[U_{t}=MLP(h_{v}^{T}||m_{v}^{t+1})\] (23)
* Global Attention Pooling (GAP)--global attention pooling [54] for aggregating node embeddings using attention mechanisms to obtain attention scores and calculate graph embedding \(\Phi\). GAP plays the role of MPNN's readout phase. * Linear Layer (LL)--final linear layer that compresses the graph embedding vector into a singular output, which defines the Q-value of the allocation. The above approach allows us to aggregate the node/edge information based on the neighbourhood. The role of GAP is to pick the nodes that contribute the most to the graph embedding values, i.e., the traffic concentration nodes. This enables the agent to learn about the relative relationship of the nodes and edges and focus on the nodes/edges that accommodate the highest traffic volume and are at risk of congestion. Combined with the proposed reward and DDQN principles, the agents are encouraged to prioritiise the allocations that omit the most loaded edges and nodes, if possible, and load balance across traffic concentration points. Moreover, time is introduced into the model by embedding predictions on node/edge expiry in the network state. A common approach is to combine GNNs with time-series prediction units, e.g., Long Short-Term Memory (LSTM). Hereby, a more generic model is used. While the orbital period of LEO satellites is approximately constant, the periodicity of satellite topology (as visible from the point on the ground) is harder to deduct due to the impact of Earth's rotation and orbital inclination of nodes. This requires careful consideration of the training time window and can potentially lead to progressively lowered model performance as time passes. Moreover, coupling the reasoning with time as is does not take into account random events like interface misalignments, occlusions, or weather conditions that can impact the topology shape and can be predicted by GIMMF-like systems. The 3 DQR approach also enables encapsulating the specific NTN/TN events and time-driven topology changes, leading to a more generic model that can be reused across different 3D systems. ### Complexity Analysis

To evaluate the theoretical complexity of 3 DQR E2 EP establishment, a popular Shortest Path (SP) implementation is considered that uses priority queues and features time complexity \(O(VlogV+E)\). As described in Section 4.2, the E2 EP establishment involves a number of operations at the overlay and domain levels, which contribute to the overall 3 DQR complexity:

1. Rough E2 EP computation by M-SDNC using overlay network graph \(G^{\Psi}(V^{\Psi},E^{\Psi})\);
2. IDP computation by designated SDNCs; using domain network graph \(G^{\Psi}(V^{\Psi},E^{\Psi})\);
3. Verification of E2 EP and IDPs feasibility in terms of QoS requirements. Following the getPath procedure definition (cf. Algorithm 1), the complexity is impacted by the calculation of \(k\) candidate paths (\(k\) shortest paths), the virtual path allocation procedure, and comparison of paths.