# Router Activation Heuristics for Energy-Saving ECMP and Valiant Routing in Data Center Networks
## 5 Heuristic Algorithm for Energy-Aware Routing  
The solutions of the optimization problems formulated in the above section are switches' energy states and the optimal routing, assuming fixed flows. The energy consumption in a data center network is minimized by placing into low power mode (sleeping mode) as many relay nodes (switches) as possible, assuming transmission of all flows from the set \(M\). Unfortunately, calculating routing by solving the above optimization tasks (1), (7), and (10) has some limitations.  
* To solve the optimization problems, the central server has to continuously collect data about the state of all network nodes and links.
* The traffic forecasts have to be known. These forecasts can be based on declarations from DC users or calculated by the central server.
* Disabling many DCN relay nodes can negatively affect service quality. It can lead to significant packet losses in unexpected traffic growth. Moreover, enabling a lacking relay node takes additional time for waking up and running services to handle network traffic. Taking this delay into account significantly complicates the optimization problem.
* Solving the optimization task for a large computing center is time-consuming, especially when nonlinear energy consumption models for data transmission are considered (\(DELhtm\) problem). The update of the routing tables is not immediate. In the period between updates, the network load may change significantly.  
Considering the limitations above, and the optimization problem dimensionality estimation (Table 1), the presented mathematical models can be used for network management in simple scenarios. Moreover, they assume constant load and neglect various details of network operation to limit complexity. Therefore, we developed and investigated a few heuristics for network nodes activity control and energy-aware multipath routing calculation. We aimed to design efficient and fast algorithms and computing schemes for energy-aware DCN management with effectiveness close to that determined by solving the optimization tasks defined in Section 4.1.  
Consider a DCN composed of network nodes \(n\in N\) that can operate in two modes, i.e., active or inactive, and links \(l\in L\). We assume ECMP routing and use the Valiant algorithm to calculate the transmission paths. Therefore, the algorithm for determining the path from the source server \(s\) to the destination server \(d\) is implemented in two steps:  
1. Select the pivot \(q\) through which the flow from the node \(s\) to the node \(d\) will be sent.
2. Designate subsequent nodes of the path so that the path contains the node \(q\).  
The path calculation process depends on the current node availability. If possible, a path is created based on currently active switches. Otherwise, it is necessary to enable additional nodes. Unfortunately, the node waking up takes some time, which should be considered  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & & \multicolumn{6}{c}{**Number of Switch Ports**} \\ \cline{2-7}  & **4*** & **4** & **8** & **16** & **32** & **48** \\ \hline N & 20 & 20 & 80 & 320 & 1280 & 2880 \\ L & 32 & 32 & 256 & 2048 & 16,384 & 55,296 \\ \(M=S\) & 8 & 16 & 128 & 1024 & 8192 & 27,648 \\ Number of variables & 276 & 532 & 32,848 & \(2.0975\times 10^{6}\) & \(1.3422\times 10^{8}\) & \(1.5288\times 10^{8}\) \\ Number of constraints & 520 & 1008 & 31,104 & 986,112 & \(3.1482\times 10^{7}\) & \(2.3896\times 10^{8}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Dimensionality of the optimization problem (1)–(6). The column marked with 4\({}^{*}\) refers to number of servers reduced to one per switch.  
in the path generation process, especially if we assume that unused switches are shut down. Three main problems must be solved: (i) next hop selection, (ii) pivot selection, and (iii) nodes for activation and deactivation selection.