## 5 Description of the Heuristics
### Second Phase: Maximum Edge Disjoint Path Problem (MEDPP)--Greedy Heuristics  
In this second phase, three greedy heuristics are proposed. The output of the previous stage is divided in slots and considered independently. For each slot \(h\), the set of flows to be allocated is maximized using the approach proposed in Maximum Edge Disjoint Path Problem (MEDPP) [38] but with the additional objective of minimizing the number of active switches or, equivalently, minimizing the energy demand. Thus, when we compare two solutions for the MEDPP, we say the best one shall be the one with the most amount of flows allocated and the one that sends that quantity with the least energy consumption. Note that for this stage, a flow is defined by a pair origin-destination servers, unlike for the rest of the article where a flow also has associated a duration and a period. ```
\(h\gets 0\)\(\triangleright\) Initialize the slot counter \(sort\_by\_period(F)\)\(\triangleright\) The set of flows is sorted by period while\(h<H\)do\(\triangleright\) For each slot until reaching the end of the hyperperiod for\(f\) in \(F\)do\(\triangleright\) For each flow (starting from the one with lower period) if\(slots\_left[f]>0\)then\(\triangleright\) If the current flow \(f\) is not transmitted if\(h>deadline[f]\)then\(\triangleright\) If the current flow \(f\) is overdue \(reduce\_priority(f)\)\(\triangleright\) Reduce the priority of current flow else if\(feasible(f,h)\)then\(\triangleright\) If it is feasible to transmit \(f\) in slot \(h\)\(allocate(f,h)\)\(\triangleright\) Allocate current flow to slot \(h\)\(slots\_left[f]\gets slots\_left[f]-1\)\(\triangleright\) Reduce counter endif else if\(h>deadline[f]-1\)then\(\triangleright\) If it is the last slot for current instance \(slots\_left[f]\gets size[f]\)\(\triangleright\) Update counter \(deadline[f]\gets deadline[f]+period[f]\)\(\triangleright\) Update deadline slot endif endfor \(h\gets h+1\) endwhile
```  
**Algorithm 1** First phase scheduling algorithm: first approach. The three heuristics use the _disjoint_paths_ routine based on Breadth-first search algorithm to look for disjoint paths between source and destination servers. This routine, in addition to the network \(R=(V,L)\), receives, as input, an ordered list \(S\) of pairs (source, destination) servers and returns a set of disjoint paths in \(R\) for as many pairs as possible. It takes each pair (origin, destination) of servers from \(S\) following the order and, using \(bfs\_shortest\_path\) routine, looks for a path \(C\) between them that uses as few switches as possible in the remaining network. If there is such a path, it marks the edges in \(C\) as used, blocking them for the other flows. The pseudo-code is shown in Algorithm 3, and its complexity is \(\mathcal{O}(|S|*(|V|+|L|))\). ```
**Algorithm 2** First phase scheduling algorithm: second approach. ``` \(sort\_by\_period(F)\)\(\triangleright\) The set of flows is sorted by period for\(f\) in \(F\)do\(\triangleright\) For each flow (starting from the one with lower period) \(inst\gets 0\)\(\triangleright\) Initialize the instance counter \(h\gets 0\)\(\triangleright\) Initialize the slot counter while\(inst<\frac{H}{p_{f}}\)do\(\triangleright\) For each instance of current flow \(f\) \(left\gets t_{f}\)\(\triangleright\) Number of slot left \(dl\leftarrow(inst+1)*p_{f}\)\(\triangleright\) Deadline of current instance while\(h<dl\And left>0\)do\(\triangleright\) While there are slots left and instance is not overdue if\(feasible(f,h)\)then\(\triangleright\) If it is feasible to allocate flow \(f\) to slot \(h\)\(\triangleright\) Allocate \(left\gets left-1\)\(\triangleright\) Decrease slot counter endif \(h\gets h+1\)\(\triangleright\) Next slot endwhile \(inst\leftarrow inst+1\)\(\triangleright\) Next instance of flow \(f\) \(h\gets dl+1\)\(\triangleright\) Next slot is the first of next period endwhile endfor ```
**Algorithm 3** disjoint_paths routine.