## 5 Description of the Heuristics
### Second Phase: Maximum Edge Disjoint Path Problem (MEDPP)--Greedy Heuristics
```

```
```
```  
```
```
```

```
```
```  
```
```
```

```
```
```  
```
```
```
```
```


```
0: Network \(R\), sequence of set of pairs (source, destination) servers \(S=\langle S_{1},\ldots,S_{H}\rangle\) with priorities \(\overline{P}=\langle\overline{P_{1}},\ldots,\overline{P_{H}}\rangle\), where \(\overline{P_{h}}\) indicates the set of disjoint paths in \(R\) followed in slot \(h\) by the flows delivered in that slot \(\overline{P}\leftarrow\langle\rangle\) for\(h=1,\ldots,H\)do \(S_{o}\gets sort\_by\_priorities(S_{h})\) \(\overline{P}\gets add\_back(disjoint\_paths(R,S_{o}))\) endfor return\(\overline{P}\)
```
**Algorithm 4** Simple Greedy Heuristic. #### 5.2.2 Multistart

The second heuristic proposed in this phase is also greedy and can be seen in Algorithm 5. It consists in repeating the previous one several times permuting the order in \(S_{h}\) randomly without repetition. From all the alternatives, the best solution is chosen. Through preliminary experimentation, it was observed that after 20 iterations the best solution rarely improves. Based on this, the \(MAX\_ITER\) value was set at 20 for the following experiments. #### 5.2.3 Multistart-Adhoc

The last heuristic in this phase is presented in Algorithm 6. It is implemented in two steps. In the first one, a similar procedure to the Multistart one is used. In this case, the number of times that a flow \(f=(source,destination)\) could be allocated is counted in \(assigned\_count\). In the second step, the flows are ordered increasingly in relation to this value and a new simple heuristic is run to choose the best allocation between both steps, prioritizing flows that were assigned less frequently. The idea behind this is that flows that are assigned less overall might have their few available paths taken by other so not restricted flows. ```
0: Network \(R\), sequence of set of (source, destination) flows \(S=\langle S_{1},\ldots,S_{H}\rangle\) with priorities \(MAX\_ITER\in\mathbb{N}\) \(\overline{P}=\langle\overline{P_{1}},\ldots,\overline{P_{H}}\rangle\), where \(\overline{P_{h}}\) indicates the set of disjoint paths in \(R\) followed in slot \(h\) by the flows delivered in that slot \(\overline{P}\leftarrow\langle\rangle\) for\(h=1,\ldots,H\)do \(\mathit{inters\gets MAX\_ITER}\) \(S\leftarrow sort\_by\_priorities(S_{h})\) \(best\_AR\leftarrow disjoint\_paths(R,S)\) while\(\mathit{inters}>0\)do \(S\gets shuffle(S_{h})\) \(assign\_result\leftarrow disjoint\_paths(R,S)\) if\(assign\_result\) is better than \(best\_AR\)then \(best\_AR\leftarrow assign\_result\) endif \(\mathit{inters}\leftarrow\mathit{inters}-1\) endwhile \(\overline{P}\leftarrow add\_back(best\_AR)\) endfor return\(\overline{P}\)
```
**Algorithm 5** Multistart Greedy Heuristic. The worst running-time complexity is \(\mathcal{O}(\sum_{h\in H}|S_{h}|\times(\log|S_{h}|+MAX\_ITER\times(|V|+|L|)))\). ### Third Phase: Feasibility Schedule

The second phase provides a schedule but depending on the approach or whole flows are left out in case they can not meet the deadlines or some activations of that flow are left out. In any case, flows or instances may be not fully sent. From a hard real-time point of view the system as a whole (all flows with all activations transmitted on time) is not feasible or at least a feasible solution considering all the flows and their activations were not found. However, in soft real-time where some deadlines may be missed, the scheduling on time of as many flows or instances as possible, is important and constitutes a figure of merit of the system. In this last phase, flows are moved in search of enough space to add discarded flows or instances in a first round, and later a minimization of the used switches is done to reduce the energy cost. Algorithm 7 presents the pseudo-code for this phase. This phase uses, as input, the set of paths found in the previous stage and attempts at first to complete those flows or activations that have not been completely scheduled.