## 5 Description of the Heuristics
### Second Phase: Maximum Edge Disjoint Path Problem (MEDPP)--Greedy Heuristics
For routines \(\mathit{make\_feasible}\) and \(\mathit{improve}\), the worst running-time complexity is \(\mathcal{O}(|F|\times H\times(|V|+|L|))\), while for the _perturbation_ routine it is \(\mathcal{O}(rInst\times rStot\times nTries\times|F|\times H\times(|V|+|L|))\). This results in a computational complexity of Algorithm 7 of \(\mathcal{O}((|F|\times H\times(|V|+|L|))\times(1+MAX\_ITERS\times(rInst\times rStot \times nTries+1))\). As there are many tuning parameters for this third phase, the toolbox IRACE [39] is used to optimize them. ## 6 Experimental Evaluation

In this section, several experiments with the different heuristic approaches are presented and compared for synthetic sets of problems with different characteristics. The experiments were carried out on a personal computer with Ubuntu Server 20.04 with processor Intel I7-10700 running at 2.9 GHz and 64 GB of RAM. All the implementations are written in the C++ programming language. As mentioned in previous sections, flows are periodic with real-time constraints. It is enough to evaluate the behaviour of the system up to the hyperperiod (\(H\)), which is given by the least common multiple of all the periods. As the system schedules for each slot the flows to be transmitted and their allocation to different paths, the size of the problem to be solved is proportional to the amount of servers, network switches, links, flows and the hyperperiod. In the evaluation, the periods were selected to set \(H\) to 300 slots in order to keep the simulation time at reasonable values. This is a discretionary value that has no real impact in the comparison metric but does in the time necessary to compute the solutions. It is assumed that switches can be turned on and off on demand and that all of them have identical electrical characteristics and can process flows at the same speed. In this scenario, it is sufficient to compare how many elements are active at each slot. The worst case, or maximum energy demand, is given if during the whole hyperperiod all elementsare active. In case there are less elements active, those without traffic can be turned off and with this during that slot some energy is saved. In a fat-tree topology, the number of switches is a function of the number of servers. When all switches are active the energy demand of the infrastructure during the hyperperiod is considered nominal, Enom, and its value is used as reference to compute the savings. In the same way, once the scheduling of flows have been computed, only the active switches in each slot demand energy and the actual energy consumed by the infrastructure during the hyperperiod can be computed, \(E_{\text{consumed}}\). The relation between both values represents the energy saved; see Equation (15). \[Saving=100(1-\frac{E_{\text{consumed}}}{E_{\text{nom}}}) \tag{15}\]

However, this value has to be normalized to be useful in comparisons. When the system schedules only a few flows or activations, only a subset of the switches would be active and the rest of the infrastructure can be turned off. The normalization is done by incorporating, in Equation (15), the relation between the number of scheduled flows to the total number of flows when the scheduling is done based on flows or the relation between activations when it is done per activation. \[ \begin{split} N\_Saving\_F&=Saving\frac{\text{ Flows\_Scheduled}}{\text{Total\_Flows}}\\ N\_Saving\_A&=Saving\frac{\text{Act\_Scheduled}}{ \text{Total\_Act}}\end{split}  \tag{16}\]

As mentioned in Section 5, the IRACE package, for automatic configuration of optimization algorithms [39], was used to tune the input parameters of the algorithms. The experiments were performed with several sets of instances. Systems with 8, 16, 32, 64 and 12 eight servers were generated in fat-tree DCN topologies. For each set different amounts of flows were simulated with bandwidth demands between 0.2 and 1 for each server. Results are presented only for 8 and 12 eight servers as they represent the most significant cases.