## 6 Heuristic
We then apply [PERSON]'s algorithm on the extracted subgraph, in order to determine the shortest path from the node associated to the source satellite in the unprocessed state during the service generation cycle to the node representing the ground station in the processed state at service delivery deadline cycle (Line 5). While applying [PERSON]'s algorithm, distances are related to energy consumption due to crossing edges between couples of nodes, but since we are interested in minimizing the energy consumption in ground stations, while calculating path distances we only consider energy to be paid to process data on ground stations, and we zero any contribution given by crossing a link different from a processing link of the _vGS_ node. Then, if a path has been found, the path is added to the list of paths (Line 7); thus, in Lines 8-11, first the matrix tracking the link occupancy is updated to consider the hosting of the current service on the crossed links by means of the following expression:  
\[\Lambda^{i}_{\{i,\tilde{u},\tilde{p}\},\{\tilde{u},\tilde{p}\}}=\Lambda^{i}_{\{ i,\tilde{u},\tilde{p}\},\{\tilde{u},\tilde{p}\}}+f^{h}_{\{\tilde{p}_{1}/2\}} \tag{25}\]  
second, similarly, the matrix tracking the node energy usage in time is updated to consider the hosting of the current service on nodes crossed by the service with the following expression:  
\[\Psi^{i}_{\tilde{u}}=\Psi^{i}_{\tilde{l}_{i}}+\gamma^{i}_{\tilde{l}_{i},\tilde {p}_{i}}.\cdot f^{h}_{\{p_{i}/2\}} \tag{26}\]  
and, finally, the current service is removed from the buffer tracking the services still to be handled by the algorithm (Lines 12-14); otherwise, the current service is included into the set of rejected services, i.e., services which cannot be handled because of lack of resources (Lines 15-17). As far as the _Extract Subgraph_ algorithm illustrated in Algorithm 2 is concerned, it first allows for extracting from the graph only the nodes which can potentially be traversed by the current service, i.e., all nodes between the service generation time cycle and the service delivery deadline one (Lines 8-9). Furthermore, this algorithm also allows for the following [PERSON]'s algorithm application dealing with the fact that links have a finite capacity and nodes have a finite amount of energy. In particular, in Lines 7-15, the first condition to be verified to include an edge between a couple of nodes in the subgraph is that the edge has enough capacity to handle the current service, by checking the following condition:  
\[\Lambda^{f}_{\{i,\tilde{u},p\},\{\tilde{u},p\}}+f^{h}_{\{p/2\}}\leq C^{f}_{\{ i,\tilde{u},p\},\{\tilde{u},p\}} \tag{27}\]  
Then, a transmission edge between two nodes in the unprocessed (processed) state is included in the subgraph only if the transmitting node has enough energy to transmit the unprocessed (processed) service plus a margin. This is checked by means of the following expression:  
\[\Psi^{i}_{\tilde{l}_{i}}+f^{h}_{\{p/2\}}\cdot\gamma^{i,p,p}_{i_{i},p}+\mu^{i}_ {\tilde{l}_{i}}\cdot\left(1-\delta_{i_{\tilde{u},}N_{5}-1}\right)\leq\varepsilon _{i_{i}} \tag{28}\]  
Please notice that, in the case of memory links, since we assume no energy is required to store data, this energy condition is automatically verified. Instead, a processing edge is included in the subgraph only if the node has enough energy to process the service plus a margin, and we assume that processing on a node can happen only in the first cycle during which it has enough capacity and energy to accomplish it (Lines 16-18).