# Router Activation Heuristics for Energy-Saving ECMP and Valiant Routing in Data Center Networks
## 4 Mathematical Models for Energy-Aware Routing Calculation
### Optimization Problems Formulation  
The problem of calculating energy-aware routing and energy-aware states of network nodes may be defined in the form of the optimization task. Let us consider a data center network composed of nodes \(n\in N\), i.e., source and destination servers and switches that play the role of relay nodes in the transmission between servers. We assume that switches can operate in several modes, which differ in power usage. To simplify the considerations, we limit the number of states to active--a high-power mode, and inactive (sleeping)--a low-power mode. We also use the terms enable and disable to describe these states.  
All pairs of network nodes are connected by links \(l\in L\), working in a full-duplex mode. We model the energy consumption of each network node using the same linear model. \(M\) is a set of flows transmitted in the network. Each flow \(m\) denotes a standard, constant in-time packet stream transmission between a given pair of servers. It is described by two parameters: \(w_{m}\)--the size of the \(m\)-th flow (in Mb/s) and \(c_{l}\)--the capacity of the \(l\)-th link (in Mb/s). We do not consider the time and energy necessary for state transition. First, we assume that the transitions are relatively rare as they depend on the routing algorithm. Second, as far as possible, we tend not to switch nodes off completely but to use  
Figure 2: Network (a fat-tree example) without energy-saving capabilities (**a**) uses all network devices even in periods of low utilization. Using energy-aware algorithms (**b**), it is possible to calculate routing allowing to switch off devices and links. Colored links represent active transmissions, and gray links and nodes are switched off or (better) in energy-saving standby mode.  
a low-power standby state. Hence, we do not consider momentary microsleep as discussed in works [39; 40], as the intervention rate is in the range of minutes, and we also avoid switching the nodes off to provide a quick switch-on. In such a case, the transition energy may be neglected, resulting in a simpler mathematical model.  
The aim is to minimize the total power utilized by network nodes for transmitting all flows from the set \(M\) while ensuring end-to-end quality of service (QoS). We tackle the energy saving in a network by placing it into low-energy states or deactivating currently unused DCN switches. In our approach, we propose to use the Valiant routing algorithm to calculate the transmission paths and traffic load balancing. Let \(Q\subset N\) denote a set of pivot nodes, i.e., randomly selected switches. In Valiant routing, a path to transmit each flow \(m\in M\) must contain at leastone pivot node.  
We consider various formulations of a DCN-wide energy-saving problem. They differ in the energy used by network node modeling.  
* Same-energy-usage problem (linear model): a formulation stated in terms of the assumption of the same energy usage by all DCN nodes, i.e., energy usage independent of the transmitted traffic (linear model of energy consumption).
* Different-energy-usage problem (linear model): a formulation stated in terms of the assumption of different energy usage by DCN nodes, i.e., energy usage depends on transmitted traffic (linear model of energy consumption).
* Different-energy-usage problem (nonlinear model): a formulation stated in terms of the assumption of different energy usage by DCN nodes (nonlinear model of energy consumption).