Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Internet hosting centers serve multiple service sites from a common hardware base. This paper presents the design and implementation of an architecture for resource management in a hosting center operating system, with an emphasis on energy as a driving resource management issue for large server clusters. The goals are to provision server resources for co-hosted services in a way that automatically adapts to offered load, improve the energy efficiency of server clusters by dynamically resizing the active server set, and respond to power supply disruptions or thermal events by degrading service in accordance with negotiated Service Level Agreements (SLAs).Our system is based on an economic approach to managing shared server resources, in which services "bid" for resources as a function of delivered performance. The system continuously monitors load and plans resource allotments by estimating the value of their effects on service performance. A greedy resource allocation algorithm adjusts resource prices to balance supply and demand, allocating resources to their most efficient use. A reconfigurable server switching infrastructure directs request traffic to the servers assigned to each service. Experimental results from a prototype confirm that the system adapts to offered load and resource availability, and can reduce server energy usage by 29% or more for a typical Web workload. <s> BIB001 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Online dynamic power management (DPM) strategies refer to strategies that attempt to make power-mode-related decisions based on information available at runtime. In making such decisions, these strategies do not depend upon information of future behavior of the system, or any a priori knowledge of the input characteristics. In this paper, we present online strategies, and evaluate them based on a measure called the competitive ratio that enables a quantitative analysis of the performance of online strategies. All earlier approaches (online or predictive) have been limited to systems with two power-saving states (e.g., idle and shutdown). The only earlier approaches that handled multiple power-saving states were based on stochastic optimization. This paper provides a theoretical basis for the analysis of DPM strategies for systems with multiple power-down states, without resorting to such complex approaches. We show how a relatively simple "online learning" scheme can be used to improve the competitive ratio over deterministic strategies using the notion of "probability-based" online DPM strategies. Experimental results show that the algorithm presented here attains the best competitive ratio in comparison with other known predictive DPM algorithms. The other algorithms that come close to matching its performance in power suffer at least an additional 40p wake-up latency on average. Meanwhile, the algorithms that have comparable latency to our methods use at least 25p more power on average. <s> BIB002 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> In this paper we examine the somewhat controversial subject of energy consumption of networking devices in the Internet, motivated by data collected by the U.S. Department of Commerce. We discuss the impact on network protocols of saving energy by putting network interfaces and other router & switch components to sleep. Using sample packet traces, we first show that it is indeed reasonable to do this and then we discuss the changes that may need to be made to current Internet protocols to support a more aggressive strategy for sleeping. Since this is a position paper, we do not present results but rather suggest interesting directions for core networking research. The impact of saving energy is huge, particularly in the developing world where energy is a precious resource whose scarcity hinders widespread Internet deployment. <s> BIB003 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Competitive analysis is concerned with comparing the performance of on-line algorithms with that of optimal off-line algorithms. In some cases randomization can lead to algorithms with improved performance ratios on worst-case sequences. In this paper we present new randomized on-line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approachinge/(eź1) ź 1.58 against an oblivious adversary. These ratios are optimal and are a surprising improvement over the best possible ratio in the deterministic case, which is 2. We also consider the situation when the request sequences for these problems are generated according to an unknown probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have competitive factors approachinge/(eź1). Finally, we obtain randomized algorithms for the 2-server problem on a class of isosceles triangles. These algorithms are optimal against an oblivious adversary and have competitive ratios that approache/(eź1). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle. <s> BIB004 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α. There are two natural versions of this problem, both considered extensively in recent work: minimize the total power consumption (including computation time), or minimize the number of "gaps" in execution. For both versions in a multiprocessor system, we develop a polynomial-time algorithm based on sophisticated dynamic programming. In a generalization of the power-saving problem, where each task can execute in any of a specified set of time intervals, we develop a (1 + 2 3 α)-approximation, and show that dependence on α is necessary. In contrast, the analogous multi-interval gap scheduling problem is set-cover hard (and thus not o(lg n)-approximable), even in the special cases of just two intervals per job or just three unit intervals per job. We also prove several other hardness-of-approximation results. Finally, we give an O(√n)-approximation for maximizing throughput given a hard upper bound on the number of gaps. <s> BIB005 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> We consider the problem of selecting threshold times to transition a device to low-power sleep states during an idle period. The two-state case, in which there is a single active and a single sleep state, is a continuous version of the ski-rental problem. We consider a generalized version in which there is more than one sleep state, each with its own power-consumption rate and transition costs. We give an algorithm that, given a system, produces a deterministic strategy whose competitive ratio is arbitrarily close to optimal. We also give an algorithm to produce the optimal online strategy given a system and a probability distribution that generates the length of the idle period. We also give a simple algorithm that achieves a competitive ratio of $3 + 2\sqrt{2} \approx 5.828$ for any system. <s> BIB006 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Exponential bandwidth scaling has been a fundamental driver of the growth and popularity of the Internet. However, increases in bandwidth have been accompanied by increases in power consumption, and despite sustained system design efforts to address power demand, significant technological challenges remain that threaten to slow future bandwidth growth. In this paper we describe the power and associated heat management challenges in today's routers. We advocate a broad approach to addressing this problem that includes making power-awareness a primary objective in the design and configuration of networks, and in the design and implementation of network protocols. We support our arguments by providing a case study of power demands of two standard router platforms that enables us to create a generic model for router power consumption. We apply this model in a set of target network configurations and use mixed integer optimization techniques to investigate power consumption, performance and robustness in static network design and in dynamic routing. Our results indicate the potential for significant power savings in operational networks by including power-awareness. <s> BIB007 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Energy conservation is drawing increasing attention in data networking. One school of thought believes that a dominant amount of energy saving comes from turning off network elements. The difficulty is that transitioning between the active and sleeping modes consumes considerable energy and time. This results in an obvious trade-off between saving energy and provisioning performance guarantees such as end-to-end delays. We study the following routing and scheduling problem in a network in which each network element either operates in the full-rate active mode or the zero-rate sleeping mode. For a given network and traffic matrix, routing determines the path along which each traffic stream traverses. For frame-based periodic scheduling, a schedule determines the active period per element within each frame and prioritizes packets within each active period. For a line topology, we present a schedule with close-to-minimum delay for a minimum active period per element. For an arbitrary topology, we partition the network into a collection of lines and utilize the near-optimal schedule along each line. Additional delay is incurred only when a path switches from one line to another. By minimizing the number of switchings via routing, we show a logarithmic approximation for both energy consumption and end-to-end delays. If routing is given as input, we present two schedules one of which has active period proportional to the traffic load per network element, and the other proportional to the maximum load over all elements. The end-to-end delay of the latter is much improved compared to the delay for the former. This demonstrates the trade-off between energy and delay. <s> BIB008 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Current network infrastructures exhibit poor power efficiency, running network devices at full capacity all the time regardless of the traffic demand and distribution over the network. Most research on router power management are at component level or link level, treating routers as isolated devices. A complementary approach is to facilitate power management at network level by routing traffic through different paths to adjust the workload on individual routers or links. Given the high path redundancy and low link utilization in today's large networks, this approach can potentially allow more network devices or components to go into power saving mode. This paper proposes an intra-domain traffic engineering mechanism, GreenTE, which maximizes the number of links that can be put into sleep under given performance constraints such as link utilization and packet delay. Using network topologies and traffic data from several wide-area networks, our evaluation shows that GreenTE can reduce line-cards' power consumption by 27% to 42% under constraints that the maximum link utilization is below 50% and the network diameter remains the same as in shortest path routing. <s> BIB009 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Networks are a shared resource connecting critical IT infrastructure, and the general practice is to always leave them on. Yet, meaningful energy savings can result from improving a network's ability to scale up and down, as traffic demands ebb and flow. We present ElasticTree, a network-wide power1 manager, which dynamically adjusts the set of active network elements -- links and switches--to satisfy changing data center traffic loads. ::: ::: We first compare multiple strategies for finding minimum-power network subsets across a range of traffic patterns. We implement and analyze ElasticTree on a prototype testbed built with production OpenFlow switches from three network vendors. Further, we examine the trade-offs between energy efficiency, performance and robustness, with real traces from a production e-commerce website. Our results demonstrate that for data center workloads, ElasticTree can save up to 50% of network energy, while maintaining the ability to handle traffic surges. Our fast heuristic for computing network subsets enables ElasticTree to scale to data centers containing thousands of nodes. We finish by showing how a network admin might configure ElasticTree to satisfy their needs for performance and fault tolerance, while minimizing their network power bill. <s> BIB010 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Today, backbone networks of telecom operators deploy a large number of devices and links. This is mainly due to both redundancy purposes for network service reliability and resource overdimensioning for maintaining quality of service during rush hours. Unfortunately, current network devices do not have power management primitives, and have constant energy consumption independent of their actual workloads. Starting from these considerations, we propose a viable approach to introduce and support standby modes in backbone network devices. This approach can be effectively used to almost halve the energy requirements of the whole telecom core network. Our main idea consists of periodically reconfiguring nodes and links to meet incoming traffic volumes and operational constraints of real-world networks, such as reliability, stability, quality of service, and reconvergence times. To this purpose, the approach we propose directly exploits the main features of both backbone device architectures and the network protocol stack. <s> BIB011 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining satisfactory level of performance. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the paper, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses one unit of energy per one unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O(n^5)-time algorithm. In addition we provide an O(n^4)-time algorithm for computing the minimum energy schedule when all jobs have unit length. <s> BIB012 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Energy consumption of the Information and Communication Technology (ICT) sector has grown exponentially in recent years. A major component of the today’s ICT is constituted by the data centers which have experienced an unprecedented growth in their size and population, recently. The Internet giants like Google, IBM and Microsoft house large data centers for cloud computing and application hosting. Many studies, on energy consumption of data centers, point out to the need to evolve strategies for energy efficiency. Due to large-scale carbon dioxide (\(\mathrm{CO}_2\)) emissions, in the process of electricity production, the ICT facilities are indirectly responsible for considerable amounts of green house gas emissions. Heat generated by these densely populated data centers needs large cooling units to keep temperatures within the operational range. These cooling units, obviously, escalate the total energy consumption and have their own carbon footprint. In this survey, we discuss various aspects of the energy efficiency in data centers with the added emphasis on its motivation for data centers. In addition, we discuss various research ideas, industry adopted techniques and the issues that need our immediate attention in the context of energy efficiency in data centers. <s> BIB013 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Power consumption imposes a significant cost for data centers implementing cloud services, yet much of that power is used to maintain excess service capacity during periods of low load. This paper investigates how much can be saved by dynamically "right-sizing" the data center by turning off servers during such periods and how to achieve that saving via an online algorithm. We propose a very general model and prove that the optimal offline algorithm for dynamic right-sizing has a simple structure when viewed in reverse time, and this structure is exploited to develop a new "lazy" online algorithm, which is proven to be 3-competitive. We validate the algorithm using traces from two real data-center workloads and show that significant cost savings are possible. Additionally, we contrast this new algorithm with the more traditional approach of receding horizon control. <s> BIB014 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> In this paper, we investigate the problem of online task scheduling of jobs such as MapReduce jobs, Monte Carlo simulations and generating search index from web documents, on cloud computing infrastructures. We consider the virtualized cloud computing setup comprising machines that host multiple identical virtual machines (VMs) under pay-as-you-go charging, and that booting a VM requires a constant setup time. The cost of job computation depends on the number of VMs activated, and the VMs can be activated and shutdown on demand. We propose a new bi-objective algorithm to minimize the maximum task delay, and the total cost of the computation. We study both the clairvoyant case, where the duration of each task is known upon its arrival, and the more realistic non-clairvoyant case. <s> BIB015 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> Power management aims in reducing the energy consumed by computer systems while maintaining a good level of performance. One of the mechanisms used to save energy is the shut-down mechanism which puts the system into a sleep state when it is idle. No energy is consumed in this state, but a fixed amount of energy is required for a transition from the sleep state to the active state which is equal to L times the energy required for the execution of a unit-time task. In this paper, we focus on the off-line version of this problem where a set of unit-time tasks with release dates and deadlines have to be scheduled in order to minimize the overall consumed energy during the idle periods of the schedule. Here we focus on the case where the tasks have agreeable deadlines. For the single processor case, an O(n^3) algorithm has been proposed in Gururaj et al. (2010) for unit-time tasks and arbitrary L. We improve this result by introducing a new O(n^2) polynomial-time algorithm for tasks with arbitrary processing times and arbitrary L. For the multiprocessor case we also improve the complexity from O(n^3m^2) Gururaj et al. (2010) to O(n^2m) in the case of unit-time tasks and unit L. <s> BIB016 </s> Green Data Centers: A Survey, Perspectives, and Future Directions <s> B. Power-Down Mechanism (PDM) <s> We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems. ::: ::: First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59. ::: ::: Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(h-k) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm. <s> BIB017
In this scheme, devices are transitioned into a low-power standby or sleep mode while they are idle to save energy. One must determine when idle periods exist that are of sufficient duration to outweigh the costs incurred by the scheme (such as the cost for transitioning from the sleep state and the delay cost) and decide when to wake the devices from the powersaving mode to satisfy the workload demand. When a single device is considered and the transition delay is ignored, the problem of managing power in a two-state situation (active state and sleep state) is equivalent to the ski-rental problem. A competition analysis of this problem was presented by  , BIB004 . Irani et al. BIB002 extended the study to devices with multiple states. The authors presented a deterministic algorithm that achieved 2-competitive performance when the transition energies were assumed to be additive. In BIB006 , the authors investigated the generalized case in which the state transition energies could take arbitrary values and achieved a competitiveness of 3 + 2 √ 2. With preemptions allowed and the process of waking up assumed to require a certain fixed amount of energy, Baptiste et al. BIB012 provided an O(n 5 )-time algorithm for offline operation. For the case in which the tasks have agreeable deadlines, i.e., later-released tasks also have later deadlines,  and BIB016 proposed algorithms to improve the time complexity. Given a single processor, tasks with arbitrary processing time and unit transition costs,  proposed an O(n log n) greedy algorithm. Later, Angel et al. BIB016 proposed an O(n 2 ) algorithm for tasks with arbitrary processing time and arbitrary transition costs in a single-processor environment. For tasks with unit processing time and unit transition cost in the multiprocessor case, the authors of BIB016 also provided an O(n 2 m) algorithm. In BIB005 , Demaine et al. considered the powersaving problem in which each task must be executed within a specified set of time intervals and proposed a (1 + 2 3 L c )-approximation algorithm, where L c is the transition cost. In BIB017 , the authors studied the problem of online dynamic power management in a three-state situation (busy state, standby state and off state). They first considered the case in which the set of tasks that could feasibly be scheduled on a single processor was known in advance (packable) and, for this case, proposed a 4-competitive online algorithm that used at most two processors. The competitive ratio was improved to 3.59 for tasks with unit processing time. For the general case of tasks with unit processing time and multiple processors, an O(1)-competitive algorithm was provided. In Table IV , we summarize all the algorithmic results mentioned above regarding power-down mechanisms; the definitions of the symbols are the same as those given in Table III. For large hosting centers, several studies recommend energyproportional computing BIB001 , BIB014 , BIB015 , BIB007 , BIB011 , BIB008 , BIB009 , BIB010 . Here, "proportional" refers to the concept that the size of the data center should be proportional to its workload demand BIB013 . In BIB001 , the authors proposed energy-conscious provisioning to concentrate the request load on a minimal active set of servers appropriate to the current aggregate load level. The excess servers would be transitioned into a power-saving state to reduce the energy cost during periods of light load. These authors reported that their system could reduce server energy usage by 29% or more for a typical Web workload. Lin et al. BIB014 investigated the energy-saving problem by dynamically "right-sizing" the target data center by turning off servers during lighter periods in both offline and online cases. They BIB017 modeled the cost of toggling a server back and forth between the active and power-saving modes as a switching cost. The authors reported a 50% energy savings for a peak-to-mean ratio (PMR) of 5. Azar et al. BIB015 considered turning off machines to save on computation costs. The authors accounted for the delay cost as the duration required to turn the machines on or off. They proposed a bi-objective algorithm to address the problem of minimizing both the maximum task delay and the total cost. On the network-device level, power-down mechanisms redirect network traffic to aggregate traffic on only a few network devices and links while allowing idle devices to sleep for energy conservation BIB003 . In BIB007 , the authors investigated poweraware network design and routing to dynamically power on/off line cards and chassis. They modeled the minimization of network-wide power consumption as a mixed-integer optimization problem and solved it using a branch-and-cut solver that incorporated several practical considerations (such as the network structure). They demonstrated that their results were within 11% of the optimal result. Bolla et al. BIB011 used energyaware traffic engineering on backbone networks to manage the standby and wakeup behavior of network devices with respect to the IP layer. The basic concept driving their work was to periodically reconfigure the network nodes and links to accommodate incoming traffic volumes and operational constraints (e.g., quality of service and reconvergence times). The authors noted that the energy savings depended on the level of traffic load; specifically, the energy savings was approximately 40% when the traffic load was less than 50%. Andrews et al. BIB008 studied routing and scheduling in a power-down model and captured the trade-off between energy savings and provisioning performance guarantees such as end-to-end delays. The authors proposed scheduling algorithms for line and arbitrary topologies. In the case of periodic scheduling, the schedule determined the active period per element within each frame and prioritized the packets within each active period. Zhang et al. BIB009 proposed GreenTE, an intra-domain energy-aware traffic engineering mechanism that maximizes the number of links that can be placed in sleep mode while satisfying performance constraints (e.g., link utilization and packet delay). The authors reported an energy savings of 27-42% for a maximum link utilization below 50%. ElasticTree BIB010 dynamically adjusts the set of active network elements to achieve a trade-off between energy efficiency and performance. The authors used methods including a formal model, a greedy bin-packer, a topologyaware heuristic and prediction to determine which subset of links and switches to use. The authors reported a network energy savings of 50%.