Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s) which indicates the power consumption level given a particular speed. We assume that P(s) is convex, nondecreasing, and nonnegative for s ≥ 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio. <s> BIB001 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> We present the design and evaluation of two forms of power management schemes that reduce the energy consumption of networks. The first is based on putting network components to sleep during idle times, reducing energy consumed in the absence of packets. The second is based on adapting the rate of network operation to the offered workload, reducing the energy consumed when actively processing packets. ::: ::: For real-world traffic workloads and topologies and using power constants drawn from existing network equipment, we show that even simple schemes for sleeping or rate-adaptation can offer substantial savings. For instance, our practical algorithms stand to halve energy consumption for lightly utilized networks (10-20%). We show that these savings approach the maximum achievable by any algorithms using the same power management primitives. Moreover this energy can be saved without noticeably increasing loss and with a small and controlled increase in latency (<10ms). Finally, we show that both sleeping and rate adaptation are valuable depending (primarily) on the power profile of network equipment and the utilization of the network itself. <s> BIB002 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> In this paper we extend the study of flow-energy scheduling to a model that allows both sleep management and speed scaling. Our main result is a sleep management algorithm called IdleLonger, which works online for a processor with one or multiple levels of sleep states. The design of IdleLonger is interesting; among others, it may force the processor to idle or even sleep even though new jobs have already arrived. IdleLonger works in both clairvoyant and non-clairvoyant settings. We show how to adapt two existing speed scaling algorithms AJC [15] (clairvoyant) and LAPS [9] (non-clairvoyant) to the new model. The adapted algorithms, when coupled with IdleLonger, are shown to be O(1)-competitive clairvoyant and non-clairvoyant algorithms for minimizing flow plus energy on a processor that allows sleep management and speed scaling. ::: ::: The above results are based on the traditional model with no limit on processor speed. If the processor has a maximum speed, the problem becomes more difficult as the processor, once overslept, cannot rely on unlimited extra speed to catch up the delay. Nevertheless, we are able to enhance IdleLonger and AJC so that they remain O (1)-competitive for flow plus energy under the bounded speed model. Non-clairvoyant scheduling in the bounded speed model is left as an open problem. <s> BIB003 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> In this paper we consider online deadline scheduling on a processor that can manage its energy usage by scaling the speed dynamically or entering a sleep state. A new online scheduling algorithm called SOA is presented. Assuming speed can be scaled arbitrarily high (the infinite speed model), SOA can complete all jobs with reduced energy usage, improving the competitive ratio for energy from 2^2^@a^-^[email protected]^@a+2^@a^-^1+2 (Irani et al. (2007) [17]) to @a^@a+2, where @a is the constant involved in the speed-to-power function, commonly believed to be 2 or 3. More importantly, SOA is the first algorithm that works well even if the processor has a fixed maximum speed and the system is overloaded. In this case, SOA is 4-competitive for throughput and (@a^@[email protected]^24^@a+2)-competitive for energy. Note that the throughput ratio cannot be better than 4 even if energy is not a concern. <s> BIB004 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> Energy consumption of the Internet is already substantial and it is likely to increase as operators deploy faster equipment to handle popular bandwidth-intensive services, such as streaming and video-on-demand. Existing work on energy saving considers local adaptation relying primarily on hardware-based techniques, such as sleeping and rate adaptation. We argue that a complete solution requires a network-wide approach that works in conjunction with local measures. However, traditional traffic engineering objectives do not include energy. This paper presents Energy-Aware Traffic engineering (EATe), a technique that takes energy consumption into account while achieving the same traffic rates as the energy-oblivious approaches. EATe uses a scalable, online technique to spread the load among multiple paths so as to increase energy savings. Our extensive ns-2 simulations over realistic topologies show that EATe succeeds in moving 21% of the links to the sleep state, while keeping the same sending rates and being close to the optimal energy-aware solution. Further, we demonstrate that EATe successfully handles changes in traffic load and quickly restores a low overall energy state. Alternatively, EATe can move links to lower energy levels, resulting in energy savings of 8%. Finally, EATe can succeed in making 16% of active routers sleep. <s> BIB005 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> In this work we focus on a stochastic optimization based approach to make distributed routing and server management decisions in the context of large-scale, geographically distributed data centers, which offers significant potential for exploring power cost reductions. Our approach considers such decisions at different time scales and offers provable power cost and delay characteristics. The utility of our approach and its robustness are also illustrated through simulation-based experiments under delay tolerant workloads. <s> BIB006 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> We consider an energy-efficient scheduling problem where n jobs J 1 , J 2 , ?, J n need to be executed such that the total energy usage by these jobs is minimized while ensuring that each job is finished within its deadline. The processor executing these jobs can be in either active or sleep state at any point of time. The speed of the processor in an active state can be arbitrary. If the processor is running at a speed s ? 0 , the required power P ( s ) is assumed to be equal to s α + g where α 1 , g 0 are constants. On the other hand, the required power is zero when the processor is in the sleep state. However, L 0 amount of wake-up energy is needed to wake-up the processor from the sleep state to the active state.In this paper, we work in an online setting where a job is known only at its arrival time, along with its processing volume and deadline. In such a setting, the currently best-known algorithm by Han et al. (2010) 3] provides a competitive ratio max ? { 4 , 2 + α α } of energy usage. We present a new online algorithm SqOA which provides a competitive ratio max ? { 4 , 2 + ( 2 - 1 / α ) α 2 α - 1 } of energy usage. For α ? 2.34 , the competitive ratio of our algorithm is better than that of any other existing algorithm for this problem. <s> BIB007 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> We study an energy conservation problem where a variable-speed processor is equipped with a sleep state. Executing jobs at high speeds and then setting the processor asleep is an approach that can lead to further energy savings compared to standard dynamic speed scaling. We consider classical deadline-based scheduling, i.e. each job is specified by a release time, a deadline and a processing volume. For general convex power functions, Irani et al. [12] devised an offline 2-approximation algorithm. Roughly speaking, the algorithm schedules jobs at a critical speed Scrit that yields the smallest energy consumption while jobs are processed. For power functions P(s) = sα + γ, where s is the processor speed, Han et al. [11] gave an (αα + 2)-competitive online algorithm. ::: ::: We investigate the offline setting of speed scaling with a sleep state. First we prove NP-hardness of the optimization problem. Additionally, we develop lower bounds, for general convex power functions: No algorithm that constructs Scrit-schedules, which execute jobs at speeds of at least scrit, can achieve an approximation factor smaller than 2. Furthermore, no algorithm that minimizes the energy expended for processing jobs can attain an approximation ratio smaller than 2. ::: ::: We then present an algorithmic framework for designing good approximation algorithms. For general convex power functions, we derive an approximation factor of 4/3. For power functions P(s) = βsα + γ, we obtain an approximation of 137/117 < 1.171. We finally show that our framework yields the best approximation guarantees for the class of Scrit-schedules. For general convex power functions, we give another 2-approximation algorithm. For functions P(s) = βsα + γ, we present tight upper and lower bounds on the best possible approximation factor. The ratio is exactly eW−1(−e−1−1/e)/(eW−1(−e−1−1/e) + 1) < 1.211, where W--1 is the lower branch of the Lambert W function. <s> BIB008 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> We study classical deadline-based preemptive scheduling of jobs in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each job is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed scaling alone, the addition of a sleep state makes it sometimes beneficial to accelerate the processing of jobs in order to transition the processor to the sleep state for longer amounts of time and incur further energy savings. The goal is to output a feasible schedule that minimizes the energy consumption. Since the introduction of the problem by Irani et al. [17], its exact computational complexity has been repeatedly posed as an open question (see e.g. [2,9,16]). The currently best known upper and lower bounds are a 4/3-approximation algorithm and NP-hardness due to [2] and [2, 18], respectively. ::: ::: We close the aforementioned gap between the upper and lower bound on the computational complexity of speed scaling with sleep state by presenting a fully polynomial-time approximation scheme for the problem. The scheme is based on a transformation to a non-preemptive variant of the problem, and a discretization that exploits a carefully defined lexicographical ordering among schedules. <s> BIB009 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> Power consumption in data centers has been growing significantly in recent years. To reduce power, servers are beingequipped with increasingly sophisticated power management mechanisms. Different mechanisms offer dramatically different trade-offs between power savings and performance penalties. Considering the complexity, variety, and temporallyvarying nature of the applications hosted in a typical data center, intelligently determining which power management policy to use and when is a complicated task. In this paper we analyze a system model featuring both performance scaling and low-power states. We reveal the interplay between performance scaling and low-power states via intensive simulation and analytic verification. Based on the observations, we present SleepScale, a runtime power management tool designed to efficiently exploit existing power control mechanisms. At run time, SleepScale characterizes power consumption and quality-of-service (QoS) for each lowpower state and frequency setting, and selects the best policy for a given QoS constraint. We evaluate SleepScale using workload traces from data centers and achieve significant power savings relative to conventional power management strategies <s> BIB010 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> C. Hybrid Technology <s> The power consumption of enormous network devices in data centers has emerged as a big concern to data center operators. Despite many traffic-engineering-based solutions, very little attention has been paid on performance-guaranteed energy saving schemes. In this paper, we propose a novel energy-saving model for data center networks by scheduling and routing "deadline-constrained flows" where the transmission of every flow has to be accomplished before a rigorous deadline, being the most critical requirement in production data center networks. Based on speed scaling and power-down energy saving strategies for network devices, we aim to explore the most energy efficient way of scheduling and routing flows on the network, as well as determining the transmission speed for every flow. We consider two general versions of the problem. For the version of only flow scheduling where routes of flows are pre-given, we show that it can be solved polynomially and we develop an optimal combinatorial algorithm for it. For the version of joint flow scheduling and routing, we prove that it is strongly NP-hard and cannot have a Fully Polynomial-Time Approximation Scheme (FPTAS) unless P=NP. Based on a relaxation and randomized rounding technique, we provide an efficient approximation algorithm which can guarantee a provable performance ratio with respect to a polynomial of the total number of flows. <s> BIB011
Various studies of hybrid technology have also been reported that have explored both speed scaling and power-down mechanisms to fully exploit the potential for energy savings. In a standard speed scaling setting, there is a tendency to use low speed levels, subject to prescribed deadline constraints. By contrast, in combination with the power-down approach, it can be beneficial to speed up the processing of tasks to generate idle intervals in which devices can be transitioned to the power-saving mode. Irani et al. BIB001 performed the first theoretical analysis of reducing energy usage by combining placing the system in a sleep state if it is idle with varying the speed at which tasks are processed. Assuming that all tasks could be preempted and resumed at no cost, the authors proposed a 2-approximation offline algorithm and a constantcompetitive-ratio online algorithm. Several subsequent studies presented algorithms that improved on these result BIB004 , BIB007 , BIB008 , BIB009 . In BIB004 , the authors considered online scheduling of a processor to manage its energy consumption using both speed scaling and a sleep state. They proposed an algorithm called SOA to improve the competitive ratio for energy minimization from 2 2α−2 α α + 2 α−1 + 2 BIB001 to max {4, α α + 2}, under the assumption that the speed could be arbitrarily high. They also showed that when the maximum speed of the processor was bounded, their algorithm was 4-competitive for throughput and (α α + α 2 4 α + 2)-competitive for energy. In BIB007 , the authors presented an algorithm called SqOA to further improve the competitive ratio of SOA BIB004 in the unbounded-speed setting to max {4, (2 − 1/α) α 2 α−1 + 2}. The authors of BIB008 designed superior approximation algorithms for the offline case. They proposed a 4/3-approximation algorithm for general convex power and a 137/117-approximation algorithm for power functions of the form P(s) = βs α + γ. Recently, Antoniadis et al. BIB009 closed the gap in the approximation factor by presenting a fully polynomial-time approximation scheme for the deadline-based preemptive offline scheduling problem. In BIB003 , the authors extended the study of this strategy to minimize the sum of energy and flow on a processor with one or multiple levels of sleep states. They designed O(1)-competitive clairvoyant and non-clairvoyant algorithms in the unlimited-speed setting (note: the terms "clairvoyant" and "non-clairvoyant" indicate that the sizes of the tasks are either known or not known, respectively, when the tasks arrive). Under a maximum-speed constraint, they enhanced their algorithm to again achieve O(1)-competitive performance. Chen et al.  proposed a framework to allow the employment of both approaches to enhance energy savings in hosting centers. Their solutions were based on queuing models and control theory and did not require compromise in enduser Service Level Agreements (SLAs). In BIB006 , the authors considered reducing the power consumed in geographically distributed data centers. They proposed an approach that incorporated selecting the number of active servers and their service rates to minimize the time-averaged power cost incurred when handling delay-tolerant workloads. Liu et al. BIB010 developed SleepScale, a power management tool to manage data centers for power efficiency while fulfilling quality-of-service (QoS) agreements. They exploited the low-power states and operating frequency that are built into modern CPUs and proposed a joint optimization of speed scaling and sleep-state selection to reduce energy consumption. BIB002 , BIB005 and BIB011 presented studies of network elements. Nedevschi et al. BIB002 explored the use of hybrid technology to reduce network energy consumption by putting network components to sleep during idle periods and adapting the rate of network operation to the requested workload. They showed that the effect depended on the power profile of the network equipment and the utilization of the network itself. Using real-world traffic workloads, topologies and power constants, they reported an energy savings of 50% for a network utilization of 10-20%, accompanied by a very slight increase in latency. The developers of EATe BIB005 formulated a method of online traffic management to spread the load across multiple paths while minimizing energy consumption. Their approach leveraged the rate adaptation and power-down of links and routers to configure an energy-proportional network hardware structure. Extensive ns-2 simulations demonstrated that EATe could place 21% of the links in the sleep state, lower the link energy levels to achieve 8% energy savings and put 16% of the active routers to sleep. Wang et al. BIB011 studied the problem of flow scheduling and routing while meeting flow deadlines in data center networks. They combined speed scaling and power-down mechanisms to determine routing paths and schedules as well as the transmission rate for each flow.