## 5 Algorithm
### DRL Problem Setup  
The multi-controller hierarchical SDN can be treated as the combination of standard Reinforcement Learning (RL) settings, i.e., a set of stochastic environments--each modelledas Markov Decision Process (MDP) represented by tuples \(M=(S;A;T;R)\), where \(S\) denotes states, \(A\) actions that can be taken by the agent, \(T\) the transition function, and \(R\) the reward function. As the environment details are unknown, including transition probability between states and dynamics, the dynamic programming methods [50] cannot effectively solve the given MDP. Moreover, the network environment is a non-linear system (due to complex traffic patterns, bursty behaviour, in-DP buffering, etc. ), making the exploitation of well-established methods inapplicable [51]. Hence, the proposed DQR algorithm utilises a model-free DRL due to its suitability for operation in environments in unknown or not-well-understood dynamics. **State:** For each arriving flow allocation request, the DRL agent is to evaluate \(k\) candidate paths and select the one that maximises the reward. To improve the reasoning of agents, the environment state is obtained as follows. Once the network information is pulled from SDN controllers (i.e., edge/node properties listed in Section 5.1), the graph is extended with more features provided by GIMMF and calculated internally by the router (i.e., state enrichment phase). Additional features include the edge/node expiry \(\xi_{ij},\xi_{i}\in\langle 0,1\rangle\) (probability of node/edge activity in the defined time horizon: 0 for active, 1 for inactive), \(\chi(v)\in\mathbb{N}\) (node type, e.g., satellite, gateway, relay, etc. ), and \(deg(v_{i})\) (node centrality). The obtained graph constitutes the environment state \(s_{t}^{\Phi}=(G^{\Phi},X^{\Phi},F^{\Phi})\) in the DQR and \(s_{t}^{\Psi}=(G^{\Phi},X^{\Psi},F^{\Psi})\) in the M-QR case, where \((X,F)\) are node and edge features:  
\[ \begin{split} F^{\Phi}&=\{f_{ij}^{\Phi}=(c_{ij},d_{ij },\xi_{ij},b_{ij}^{\text{GFRR}},b_{ij}^{\text{MFRR}},u_{ij},\zeta_{ij},\zeta_{ ij})|(i,j)\in E^{\Phi}\}\\ X^{\Phi}&=\{x_{i}^{\Psi}=(c_{i},b_{i}^{\text{GFRR}},b_ {i}^{\text{MFRR}},u_{i},\zeta_{i},deg(v_{i}),\chi(v_{i}))|v_{i}\in V^{\Phi}\}\\ F^{\Psi}&=\{f_{ij}^{\Phi}=(c_{ij}^{\Psi},d_{ij}^{ \Psi},\phi_{ij}^{\Psi},b_{ij}^{\Psi},b_{ij}^{\Psi},b_{ij}^{\Psi},b_{ij}^{\Psi },b_{ij}^{\Psi},W_{ij}^{\Psi},W_{ij}^{\Psi},\zeta_{ij},\zeta_{ij})|(i,j)\in E^{ \Psi}\}\\ X^{\Psi}&=\{x_{i}^{\Psi}=(c_{i},b_{i}^{\text{GFRR}},b_ {i}^{\text{MFRR}},u_{i},\zeta_{i},deg(v_{i}),\chi(v_{i}))|v_{i}\in V^{\Psi}\} \end{split}  \tag{11}\]  
Before feeding the above state into the DRL agent, a virtual path allocation of the flow for each of the candidate paths is performed (cf. Section 4 and Figure 2 for details). To improve the reasoning of the agent, in addition to the features listed above, flags indicating if the node/edge is a part of the path are included--\(r^{p},e^{p}\in 0,1\). Hence, the state evaluated by DGA for \(k\)-th allocation is defined as \(s_{t}^{\Phi,k}=(G^{\Phi},X^{\Phi,k},F^{\Psi,k})\) for domain graphs, and \(s_{t}^{\Psi,k}=(G^{\Psi},X^{\Psi,k},F^{\Psi,k})\) for the overlay graph:  
\[ \begin{split} F^{\Phi,k}&=\{f_{ij}^{\Phi,k}=(c_{ij}, d_{ij},\delta_{ij},b_{ij}^{\text{k,GFRR}},b_{ij}^{\text{k,MFRR}},u_{ij}^{k}, \zeta_{ij},\zeta_{ij},c_{ij}^{p})|(i,j)\in E^{\Phi}\}\\ X^{\Phi,k}&=\{x_{i}^{\Psi,k}=(c_{i},b_{i}^{\text{ KGFR}},b_{i}^{\text{k,MFRR}},u_{i}^{k},\zeta_{i},deg(v_{i}),v^{p},\chi(v_{i}))|v_{i} \in V^{\Phi}\}\\ F^{\Psi,k}&=\{f_{ij}^{\Psi,k}=(c_{ij}^{\Psi},d_{ij}^{ \Psi},\delta_{ij}^{\Psi},b_{ij}^{\Psi},b_{ij}^{\Psi,\Psi},b_{ij}^{\Psi,\Psi}, w_{ij}^{\Psi},\zeta_{ij},c_{ij}^{p})|(i,j)\in E^{\Psi}\}\\ X^{\Psi,k}&=\{x_{i}^{\Psi,k}=(c_{i},b_{i}^{\text{ KGFR}},b_{i}^{\text{k,MFRR}},u_{i}^{k},\zeta_{i},deg(v_{i}),v^{p},\chi(v_{i}))|v_{i} \in V^{\Psi}\}\end{split}  \tag{12}\]  
**Action:** The action \(a_{t}\) is defined as the path (a list of network nodes) calculated for the flow. IDP is denoted as \(a_{t}^{\Phi}\) and E2 EP as \(a_{t}^{\Psi}\).