## 5 Description of the Heuristics
### Second Phase: Maximum Edge Disjoint Path Problem (MEDPP)--Greedy Heuristics
Five different sets of flows or problem instances were generated in a random way for a system with eight servers and 10 switches. Each instance has 30 flows to be scheduled between the different servers. The utilization factors for all them were set to 1.6, 3.2, 4.8, 6.4 and 8. As a uniform distribution was used for the generation of the flows, on average, this means that each server has a bandwidth demand of 0.2, 0.4, 0.6, 0.8 and 1. The interferences between flows from different source servers in the same destination server can produce priority inversions causing deadline misses on one hand and on the other, as it is a random generation, some servers may be overloaded. Both things make that the systems generated may not be able to schedule all the flows on time. It is for this that, in the experiments, the percentage of successfully scheduled flows is considered together with the energy saving in the networks as a figure of merit. In Tables 4 and 5, the results are presented for this first set of instances for the case in which the scheduling is made per flows and per activations, respectively. In the first section of the table, the result obtained with CPLEX with the ILP model is shown. Even for a small system like this, with only a few servers and flows, the exact solution is not obtained within the time limit. However, as CPLEX provides additional information, such \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Parameter** & **Domain** & **Best Value Flows** & **Best Value Activations** \\ \hline First phase approach & 1, 2 & 1 & 2 \\ _rRemove_ & 0, 0.1, 0.5 & 0 & 0 \\ _rInst_ & 0.3, 0.5, 0.8, 1 & 0.3 & 0.3 \\ _rSlot_ & 0.3, 0.5, 0.8, 1 & 0.3 & 0.5 \\ _nTries_ & \(10,30,50\) & 10 & 10 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Configuration of input parameters. as upper and lower bounds, we know that there is a solution and that the actual gap to the optimal value is not large. In the case of maximizing the amount of flows, a solution is found fast when \(U<1\). However, for \(U=1\), it can not find an optimal solution in 1800 [s]. The result presented in Table 4 is the best value obtained up to that instant. In the case of maximizing the amount of activations, the solver can not find an optimal solution in 1800 [s] when \(U>0.6\). As before, the results presented in Table 5 are the best values. With respect to the second objective, minimizing the energy demand, neither approach finds an optimal solution within 1800 [s]. The results shown are then the best values obtained within that time limit. In the following columns, the results obtained with the Simple proposed heuristic for the second stage are presented for the cases in which, in the last phase, 0, 20 or 50 iterations are performed trying to improve the result obtained. This first experiment shows several important issues. In the case of scheduling flows, as the utilization factor increases to 1 for the servers, there is a reduction in the number of feasible flows and an important reduction in the savings obtained. Both things are within the expected response of the model. As explained in Section 3, there may be interference between flows in different servers because they share the same destination, and this eventually produces a priority inversion that makes the flow not schedulable. Considering the solution obtained by CPLEX as benchmark we can see that the results obtained with the heuristics with 0, 20 or 50 iterations in the third phase, are quite similar. In Figure 4, the relative results are presented. As can be seen, the response of the heuristic in its different versions is good. On the left axis, the percentage of scheduled flows is shown with respect to the CPLEX solution, and on the right axis the energy saved with respect to the CPLEX solution. The results show that the heuristic results are within 90% of the ones obtained with the CPLEX solver but they demand about four orders of magnitude less execution time.