# Router Activation Heuristics for Energy-Saving ECMP and Valiant Routing in Data Center Networks
## 3 Related Work in Energy-Efficient Routing  
Recent hardware used to build data center network infrastructure is more energy-effective than several years ago. The savings are achieved thanks to advancements in semiconductors technology and low-level control techniques such as smart standby and dynamic power scaling. However, control mechanisms implemented at the network devices level can be augmented by network-wide control strategies to further energy benefit. Managing the network as a whole, it is possible to switch off or operate at a lower rate some of the redundant or underutilized links. Many of these mechanisms are centralized (see, e.g., [PERSON] et al. (2019); [PERSON] et al. (2019); [PERSON] et al. (2019); [PERSON] et al. (2020)) and try to define and solve energy-efficient network design problems. Typically, mixed-integer linear solvers are used [PERSON] et al. (2019); [PERSON] et al. (2019); [PERSON] et al. (2020) and, as the fully formulated problem is NP-complete, heuristics are proposed to speed up calculations [PERSON] et al. (2019); [PERSON] et al. (2019); [PERSON] et al. (2019). The reason for NP-completeness of a task is the interdependence of paths which should be aggregated to move traffic out of some links. Moreover, the energy consumption functions are nonconvex due to the presence of integer variables. As long as a centralized control scheme seems to be simple and attractive, it lacks reliability and scalability, which distributed mechanisms, primarily extensions of routing protocols [PERSON] et al. (2019); [PERSON] et al. (2019); [PERSON] et al. (2019); [PERSON] et al. (2019), may easily provide. Most proposed algorithms use relatively simple heuristics, which are especially suitable for data center networks due to their regularity and hierarchical topology [PERSON] et al. (2019). The critical feature is multipath routing, allowing the relaxation of some constraints in classic network tasks. Multiple paths provide reliability and boost bandwidth and are widely accepted in cluster interconnect networks, e.g., in the ECMP routing algorithm. While small and simple switched networks may rely on spanning-tree protocol [PERSON] et al. (2019), larger and highly redundant ones employ IP routing at least at higher levels of hierarchy to create data tunnels and alleviate multipathing and load balancing. Proposed topologies are fat-tree and flattened butterfly, presented in Section 2.1, or B-Cube [PERSON] et al. (2019) and others, less or more complex. All of them tend to provide total bisection bandwidth and high fault tolerance via several layers of usually symmetrically wired nodes, which, to reduce investment, may be cheaper-commodity devices [PERSON] et al. (2019). As such, architecture seems reasonable when the network load is high; running it in quiet periods results in unjustifiable power consumption. The detailed study of possible energy savings and proposition of elastic-tree systems for bandwidth allocation and node activity control may be found in [PERSON] et al. (2019). In a reactive manner, most proposed energy-saving algorithms apply relatively simple heuristics that select network devices or their parts--line cards or single ports--to be switched off. An example of such a scheme may be [PERSON] et al. (2019), where the blocking island paradigm is used to limit routing protocol search depth to allow switching off some of fat-tree network links. In [PERSON] et al. (2019), authors propose the fill preferred link first algorithm, which tries to consolidate network traffic on links with utilization below a certain level. Importantly, the algorithm is highly integrated with the network control subsystem via OpenFlow protocol allowing the automatic building of network topology and sensing traffic. Authors of [PERSON] et al. (2019) proposed a complete network model and used traffic matrix prediction to solve the resulting multicommodity flow problem using reinforcement learning. In addition, the algorithm described in [PERSON] et al. (2019) is based on a mathematical network model.