Abstract:
Methods, using a hardware processor, for online server workload management are provided, comprising: receiving information regarding client device requests; determining, using a hardware processor, a workload distribution for the requests based on electricity cost and carbon footprint of one or more data centers using Lyapunov optimization; sending the workload distribution to the one or more data centers; and causing servers in the one or more data center to be active or inactive based on the workload distribution. Systems are provided, comprising at least one hardware processor configured to: receive information regarding client device requests; determine a workload distribution for the requests based on electricity cost and carbon footprint of one or more data centers using Lyapunov optimization; send the workload distribution to the one or more data centers; and cause servers in the one or more data center to be active or inactive based on the workload distribution.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims the benefit of U.S. Provisional Patent Application No. 62/000,841, filed May 20, 2014, which is hereby incorporated by reference herein in its entirety. 
     
    
     STATEMENT REGARDING GOVERNMENT FUNDED RESEARCH 
       [0002]    This invention was made with government support under CRI project #0855277, grant #0834797, and grant #1218505 awarded by the National Science Foundation. The government has certain rights in the invention. 
     
    
     BACKGROUND 
       [0003]    Internet data centers are typically distributed across the world in order to provide timely and reliable Internet service to users. It is estimated that data centers consume 2% of the U.S. electrical grid capacity, resulting in a $2 billion monthly utility bill. Furthermore, it is estimated that the carbon dioxide (CO 2 ) emissions from data centers will exceed emissions from the airline industry by the year 2020. Data centers will soon be required to abide by carbon capping policies that impose carbon footprint limits to encourage brown energy conservation. However, given the scale and distribution of data centers, workload scheduling of data centers based on electricity cost and carbon footprint reduction is not easy to implement. 
         [0004]    Accordingly, it is desirable to provide systems, methods, and media for online server workload management. 
       SUMMARY 
       [0005]    In some embodiments, methods, using a hardware processor, for online server workload management, the method comprising: receiving information regarding client device requests; determining, using a hardware processor, a workload distribution for the requests based on electricity cost and carbon footprint of one or more data centers using Lyapunov optimization; sending the workload distribution to the one or more data centers; and causing servers in the one or more data center to be active or inactive based on the workload distribution. 
         [0006]    In some embodiments, systems for online server workload management are provided, the systems comprising at least one hardware processor configured to: receive information regarding client device requests; determine a workload distribution for the requests based on electricity cost and carbon footprint of one or more data centers using Lyapunov optimization; send the workload distribution to the one or more data centers; and cause servers in the one or more data center to be active or inactive based on the workload distribution. 
         [0007]    In some embodiments, non-transitory computer readable media containing computer-executable instructions that, when executed by a processor, cause the processor to perform methods for online server workload management are provided, the methods comprising: receiving information regarding client device requests; determining a workload distribution for the requests based on electricity cost and carbon footprint of one or more data centers using Lyapunov optimization; sending the workload distribution to the one or more data centers; and causing servers in the one or more data center to be active or inactive based on the workload distribution. 
     
    
     
       BRIEF DESCRIPTION 
         [0008]      FIG. 1  is a schematic diagram illustrating an example of hardware suitable for the implementation of mechanisms described herein for online server workload management in accordance with some embodiments. 
           [0009]      FIG. 2  is a schematic diagram of an example of a server, and/or a computing device of  FIG. 1  that can be used in accordance with some embodiments. 
           [0010]      FIG. 3  is a flowchart illustrating an example of steps performed for online server workload management in accordance with some embodiments in the present application. 
       
    
    
     DETAILED DESCRIPTION 
       [0011]    In accordance with some implementations of the disclosed subject matter, mechanisms for online server workload management are provided. These mechanisms can be used for a variety of applications, such as large scale Internet applications that are deployed to a cloud of data centers across the world. In some implementations, these mechanisms can provide a workload routing and server management protocol for geo-distributed data centers that can minimize the data center operational electricity cost and carbon footprint. 
         [0012]    In some embodiments, there can be N geographically distributed data centers, each containing at most Y i  servers. The servers can have two power states: active and inactive, with zero (or nearly zero) power consumption in the inactive state and the servers in a data center can be homogeneous in terms of their service rate and power consumption, in accordance with some embodiments. Requests of client devices can first arrive at the front-end proxy servers. The proxy servers can distribute the requests to data centers according a workload distribution determined by a management server. In some embodiments, there can be M such front-end proxy servers. 
         [0013]    In some embodiments, a discrete-time model can be used. For example, a budgeting period (e.g., which can be year, a month, or any other suitable period of time) can be divided into S time slots, each of which can have any suitable duration (e.g., a duration that is short enough to capture the electricity cost variation, yet long enough to prevent computation and network overhead from overly impacting use of the model). At each slot, the workload management solution can reconcile a number of competing objectives, such as reducing the electricity cost, maintaining a maximum delay requirement for the requests, meeting a cloud carbon footprint cap, and/or any other suitable number and/or form of competing objectives, in accordance with some embodiments. In some embodiments, the mechanisms described herein determine: (i) the workload distribution of data centers, denoted by λ i,j (t), i.e., the workload arrival rate from front-end j to data center i, and (ii) the number of active servers at each data center i, denoted by y i (t) (the rest of the servers i.e., Y i -y i (t) can be set to inactive to save the unnecessary idle power). In some embodiments, the Internet workload for data centers can be delay sensitive and the data centers can power their servers from both the onsite renewable energy, denoted by r i , and the grid energy, denoted by g i . 
         [0014]    Turning to  FIG. 1 , an example  100  of a generalized schematic diagram of a system on which the mechanisms for online server workload management as described herein can be implemented in accordance with some implementations, is shown. As illustrated, system  100  can include one or more client devices  118 . Client devices  118  can be local to each other or remote from each other. Client devices  118  can be connected by one or more communications links  116  to a communications network  114  that can be linked via a communications link  112  to a proxy server  102 . 
         [0015]    System  100  can include one or more proxy servers  102 . Each of proxy servers  102  can be any suitable proxy server, such as a processor, a computer, a data processing device, or any suitable combination of such devices. In some embodiments, each proxy server can be any suitable front-end server responsible for receiving and routing requests made by the client devices. Any suitable number of proxy servers can be provided. For example, the number of proxy servers can be based on the number of data centers and/or the number of client devices. 
         [0016]    System  100  can include one or more data centers  106 . In some embodiments, each data center  106  is associated with carbon emission and a total carbon footprint during a time slot. 
         [0017]    Each of data centers  106  can include one or more general servers  108 . Each general server  108  can be any suitable server, such as a processor, a computer, a data processing device, or any suitable combination of such devices. 
         [0018]    Referring to  FIG. 1 , system  100  can include a centralized management server  104 . In some embodiments, management server  104  can be any suitable server, such as a processor, a computer, a data processing device, or any suitable combination of such devices. 
         [0019]    In some implementations, each of the client devices  118  and servers  102 ,  104 , and  108  can be any of a general purpose device such as a computer or a special purpose device such as a client, a server, etc. Any of these general or special purpose devices can include any suitable components such as a hardware processor (which can be a microprocessor, digital signal processor, a controller, etc.), memory, communication interfaces, display controllers, input devices, etc. For example, client device  118  can be implemented as a personal computer, a laptop computer, a digital media receiver, a tablet computer, any other suitable computing device, or any suitable combination thereof. 
         [0020]    Communications network  114  can be any suitable computer network or combination of such networks including the Internet, an intranet, a wide-area network (WAN), a local-area network (LAN), a wireless network, a digital subscriber line (DSL) network, a frame relay network, an asynchronous transfer mode (ATM) network, a virtual private network (VPN), etc. Communications links  110 ,  112  and  116  can be any communications links suitable for communicating data among client devices  118 , proxy server  102 , management server  104 , and data center  106 , such as network links, dial-up links, wireless links, hard-wired links, any other suitable communications links, or any suitable combination of such links. Client devices  118  can enable use of any of the techniques described herein that can allow the features of the mechanisms to be used. Client devices  118  and proxy server  102 , management server  104 , and data center  106  can be located at any suitable location. 
         [0021]      FIG. 2  illustrates an example  200  of hardware that can be used to implement proxy server  102 , management server  104 , general server  108 , and/or one or more of client devices  118  depicted in  FIG. 1  in accordance with some implementations of the disclosed subject matter. For example, as illustrated in example hardware  200  of  FIG. 2 , such hardware can include hardware processor  202 , memory and/or storage  204 , an input device controller  206 , an input device  208 , display/audio drivers  210 , display and audio output circuitry  212 , communication interface(s)  214 , an antenna  216 , and a bus  218 . 
         [0022]    Hardware processor  202  can include any suitable hardware processor, such as a microprocessor, a micro-controller, digital signal processor(s), dedicated logic, and/or any other suitable circuitry for controlling the functioning of a general purpose computer or a special purpose computer in some embodiments. 
         [0023]    Memory and/or storage  204  can be any suitable memory and/or storage for storing programs, data, media content, and/or any other suitable information in some embodiments. For example, memory and/or storage  204  can include random access memory, read-only memory, flash memory, hard disk storage, optical media, and/or any other suitable memory. 
         [0024]    Input device controller  206  can be any suitable circuitry for controlling and receiving input from one or more input devices  208  in some embodiments. For example, input device controller  206  can be circuitry for receiving input from a touch screen, from one or more buttons, from a voice recognition circuit, from a microphone, from a camera, from an optical sensor, from an accelerometer, from a temperature sensor, from a near field sensor, and/or any other type of input device. 
         [0025]    Display/audio drivers  210  can be any suitable circuitry for controlling and driving output to one or more display/audio output circuitries  212  in some embodiments. For example, display/audio drivers  210  can be circuitry for driving an LCD display, a speaker, an LED, or any other type of output device. 
         [0026]    Communication interface(s)  214  can be any suitable circuitry for interfacing with one or more communication networks, such as network  114  as shown in  FIG. 1 . For example, interface(s)  214  can include network interface card circuitry, wireless communication circuitry, and/or any other suitable type of communication network circuitry. 
         [0027]    Antenna  216  can be any suitable one or more antennas for wirelessly communicating with a communication network in some embodiments. In some embodiments, antenna  216  can be omitted when not needed. 
         [0028]    Bus  218  can be any suitable mechanism for communicating between two or more components  202 ,  204 ,  206 ,  210 , and  214  in some embodiments. 
         [0029]    Any other suitable components can be included in hardware  200  in accordance with some embodiments. 
         [0030]    In some implementations, proxy server  102 , management server  104 , and/or general server  108  can be implemented in one server or can be distributed as any suitable number of servers. For example, multiple servers can be implemented in various locations to increase reliability and/or increase the speed at which the server can communicate with client devices  118 . 
         [0031]    Turning to  FIG. 3 , an example  300  of a process for managing online server workload in accordance with some embodiments of the disclosed subject matter is shown. 
         [0032]    At  302 , client devices  118  can send client device requests during a pre-defined time slot. Client device requests can be any suitable type of requests such as content media requests (e.g., video, audio, and/or text), advertisement requests, web requests, email requests and/or any suitable combination of requests. In some embodiments, the pre-defined time slot can be a period of one hour during a budgeting period. 
         [0033]    At  304  the client device requests can be received by one or more proxy servers  102 . In some embodiments, client device requests can be received in any suitable manner. For example, client device requests can be received using communication links  110  and  116  via communication network  114  and can be transmitted in any suitable protocol using any suitable type of communication interface, such as TCP/IP and/or HTTP respectively. 
         [0034]    At  306 , proxy server  102  can send information on the client device requests to a management server  104  via communication link  110 . Any suitable information can be sent, such as any suitable information useful to determine a workload distribution as described herein. 
         [0035]    In accordance with some embodiments, management server  104  can compute, using a hardware processor  202 , at  308 , a workload distribution for the client device requests. 
         [0036]    At  310 , the workload distribution of the client device requests can then be sent to the proxy server  102  via communication link  110 , which can subsequently distribute, at  312 , the workload distribution to data centers  106 . After data centers  106  receive the workload distribution of the client device requests, the data centers can set one or more general servers  108  to active or inactive at  314  according to the workload distribution. 
         [0037]    At  316 , process  300  can determine whether there are additional client device requests. If not, the general servers of the data centers can be set to inactive and then process  300  can loop back to  316 . Otherwise, process  300  can loop back to  302 . 
         [0038]    In some embodiments, the workload distribution can be determined as follows: 
         [0039]    In some embodiments, the service delay (which, along with network delay, can be one of the delays experienced when processing a client device request) can be modeled by using a M/M/n queuing theory model to determine on a number of active servers in a data center in such a way that the average service delay is bounded. For example, a slack can be added to the number of active servers to avoid any sudden increase in service delay due to the input workload spikes during a slot. In the M/M/n model, given that all requests are queued, the average service delay,  d , can be defined as follows: 
         [0000]    
       
         
           
             
               
                 d 
                 _ 
               
               = 
               
                 1 
                 
                   λ 
                   - 
                   
                     n 
                      
                     
                         
                     
                      
                     μ 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where n denotes the number of servers, μ denotes the servers&#39; service rate, and λ denotes the workload arrival rate. 
         [0040]    In some embodiments, λ j  can be the time-varying average workload arrival rate at each front-end j. Workload distributions, i.e., λ i,j (t), can be determined based on the following constraints and/or any other suitable form of constraints, where d′ ref , denotes the reference average service delay, d i,j ″(t) denotes the average network delay, n denotes the number of active servers to guarantee d′ ref , 0≦y slack ≦1 denotes the slack, and y denotes the total number of active servers including the slack: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         Σ 
                         i 
                       
                        
                       
                         
                           λ 
                           
                             i 
                             , 
                             j 
                           
                         
                          
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                     = 
                     
                       
                         λ 
                         j 
                       
                        
                       
                         ( 
                         t 
                         ) 
                       
                     
                   
                   , 
                   
                     ∀ 
                     j 
                   
                   , 
                   
                     t 
                      
                     
                       [ 
                       service 
                       ] 
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     
                       
                         
                           n 
                           i 
                         
                          
                         
                           ( 
                           t 
                           ) 
                         
                       
                        
                       
                         μ 
                         i 
                       
                     
                     &gt; 
                     
                       
                         Σ 
                         j 
                       
                        
                       
                         
                           λ 
                           
                             i 
                             , 
                             j 
                           
                         
                          
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                   
                   , 
                   
                     ∀ 
                     i 
                   
                   , 
                   
                     t 
                      
                     
                       [ 
                       
                         queuing 
                          
                         
                             
                         
                          
                         stability 
                       
                       ] 
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     
                       1 
                       
                         
                           
                             
                               n 
                               i 
                             
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                            
                           μ 
                         
                         - 
                         
                           
                             Σ 
                             j 
                           
                            
                           
                             
                               λ 
                               
                                 i 
                                 , 
                                 j 
                               
                             
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                       
                     
                     ≤ 
                     
                       d 
                       
                         ′ 
                          
                         ref 
                       
                     
                   
                   , 
                   
                     ∀ 
                     i 
                   
                   , 
                   
                     t 
                      
                     
                       [ 
                       
                         service 
                          
                         
                             
                         
                          
                         delay 
                       
                       ] 
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     ( 
                     
                       
                         
                           
                             d 
                             ref 
                           
                           - 
                           
                             
                               ( 
                               
                                 
                                   d 
                                   
                                     ′ 
                                      
                                     ref 
                                   
                                 
                                 + 
                                 
                                   
                                     d 
                                     
                                       i 
                                       , 
                                       j 
                                     
                                     ″ 
                                   
                                    
                                   
                                     ( 
                                     t 
                                     ) 
                                   
                                 
                               
                               ) 
                             
                              
                             
                               
                                 λ 
                                 
                                   i 
                                   , 
                                   j 
                                 
                               
                                
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                         
                         ≥ 
                         0 
                       
                       , 
                       
                         ∀ 
                         i 
                       
                       , 
                       j 
                       , 
                       
                         t 
                          
                         
                           [ 
                           
                             total 
                              
                             
                                 
                             
                              
                             delay 
                           
                           ] 
                         
                       
                       , 
                       
                         
 
                       
                        
                       
                         
                           
                             y 
                             i 
                           
                            
                           
                             ( 
                             t 
                             ) 
                           
                         
                         = 
                         
                           
                             
                               ( 
                               
                                 1 
                                 + 
                                 
                                   y 
                                   i 
                                   slack 
                                 
                               
                               ) 
                             
                              
                             
                               
                                 n 
                                 i 
                               
                                
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           ≤ 
                           
                             Y 
                             i 
                           
                         
                       
                       , 
                       
                         ∀ 
                         i 
                       
                       , 
                       
                         
                           t 
                            
                           
                             [ 
                             
                               data 
                                
                               
                                   
                               
                                
                               center 
                                
                               
                                   
                               
                                
                               capacity 
                             
                             ] 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0041]    In the above, the “service” constraint guarantees providing service for all requests, the “queuing stability” constraint ensures the queuing model convergence, the “service delay” constraint estimates the service delay using the M/M/n queuing model and guarantees maintaining a reference average service delay, and the “total delay” asserts that the sum of service and network delay is below the reference, d ref . The equations can be in linear form, specifically by bounding both the service delay and the total delay. 
         [0042]    The model can determine the number of active servers based on the input workload in order to use the active servers, on average, near their peak utilization. The average one slot energy consumption of an active server, denoted by p i , can be obtained by profiling (p i  can be estimated by including the per-server data center cooling energy). Then y i (t)p i  estimates the total one-slot energy consumed by active servers in data center i, denoted by p i   tot . The power draw from the grid, g i (t), and the available renewable energy, r i (t), can supply the total power demand: 
         [0000]        p   i   tot ( t )= g   i ( t )+ r   i ( t ),∀ i  and  t.   (2)
 
         [0043]    Each data center i is associated with carbon emission intensities for the power source from the grid (ε i   g ) and its on-site renewable energy source (ε i   r ) measured in units of CO 2  g/J. The total carbon footprint of the cloud (i.e., from all of the data centers), within slot t can be written as: 
         [0000]      η( t )=Σ i =η i ( t )=Σ i ε i   g ( t ) g   i ( t )+ε i   r ( t ) r   i ( t ).  (3)
 
         [0044]    The cloud can follow a long-term carbon capping target, denoted by a sum, which is typically expressed for a year of operation of a data center. For example, for 
         [0000]    
       
         
           
             
               
                 η 
                 _ 
               
               = 
               
                 Σ 
                 S 
               
             
             , 
           
         
       
     
         [0000]    the long term carbon capping constraint can be written as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       1 
                       S 
                     
                      
                     
                       Σ 
                       
                         t 
                         = 
                         0 
                       
                       
                         S 
                         - 
                         1 
                       
                     
                      
                     
                       η 
                        
                       
                         ( 
                         t 
                         ) 
                       
                     
                   
                   ≤ 
                   
                     η 
                     _ 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0045]    The focus can be on the electricity operational costs rather than the capital costs (e.g., building data centers, renewable energy installation cost), and the renewable energy operational cost can be set to zero, since the primary cost for solar panels and wind turbines is the construction cost. Further, data centers can maximize the utilization of the on-site renewable energy, in accordance with some embodiments. At each slot t, the operation cost is power procurement cost across all the data centers, i.e., cost(t)=Σ i g i (t)α i (t), where α denotes the electricity cost. Finally, offline workload distribution strategy over the cloud can minimize the long-term average electricity cost of the cloud, which is demonstrated in the following optimization problem, P1: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         minimize 
                         
                           g 
                           , 
                           r 
                           , 
                           y 
                           , 
                           λ 
                         
                       
                     
                     
                       
                         
                           
                             cost 
                             _ 
                           
                           = 
                           
                             
                               1 
                               S 
                             
                              
                             
                               Σ 
                               
                                 t 
                                 = 
                                 0 
                               
                               
                                 S 
                                 - 
                                 1 
                               
                             
                              
                             
                               Σ 
                               i 
                             
                              
                             
                               
                                 g 
                                 i 
                               
                                
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                              
                             
                               
                                 α 
                                 i 
                               
                                
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                         
                         , 
                       
                     
                   
                   
                     
                       
                         subject 
                          
                         
                             
                         
                          
                         to 
                          
                         
                           : 
                         
                       
                     
                     
                       
                         
                           ( 
                           1 
                           ) 
                         
                         , 
                         
                           ( 
                           2 
                           ) 
                         
                         , 
                         
                           and 
                            
                           
                               
                           
                            
                           
                             
                               ( 
                               4 
                               ) 
                             
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0046]    In some embodiments, some of the variables are real (i.e., g i  and λ i,j ) and some are integers (i.e., y i ). It can be shown that the NP-hard Fixed-Charge-Min-Cost-Flow problem can be reduced to P1. However, relaxing y to a real variable can have a very negligible impact on the electricity cost. Therefore, P1 can be solved where all its decision variables are real. In this way, P1 can be solved using linear programming or any other suitable type of programming. Carbon capping constraint (4) couples the solution of P1 over slots. In some embodiments, when solving P1, the following assumptions can be: 
         [0047]    Boundedness assumption: The cloud carbon footprint on every slot is upper-bounded by η max  which implies that the workload arrival rate and the carbon intensity associated with the cloud are finite for t=0, . . . , S−1, that is true due to the finite number of servers in data centers. 
         [0048]    Feasibility assumption: There exists at least one sequence of workload distribution policy over slots t=0, . . . , S−1 that satisfy P1&#39;s constraints. 
         [0049]    Periodicity assumption: There exits θ number of continuous slots, θ&lt;&lt;S, during which, if carbon footprint is minimized (i.e., ∀kεθ: η(k)=η min (k), where η min (k) is the minimum possible carbon footprint for slot k which can be achieved by any workload distribution policy), then the average carbon footprint over 0 becomes lower than that of average carbon cap  η . The parameter θ depends on the cycle variation of the cloud carbon footprint as well as the tightness of  η , i.e., the proximity of the  η  to the minimum feasible average carbon footprint. 
         [0050]    In some embodiments, Lyapunov optimization can be used to provide online control of such optimization problems with coupling and/or any other suitable online problem solving technique, such as a Metrical Task System (MTS). In some such embodiments, a (virtual) queue with occupancy X(t) can be constructed to include the total excess carbon footprint beyond the average carbon footprint until the time slot t. Using X(0)=0, the values X(t) can be propagated over slots as follows: 
         [0000]        X ( t+ 1)=max[ X ( t )−  η ,0]+Σ i η i ( t )  (7)
 
         [0051]    OnlineCC, as given in Algorithm 1 (below), can be used to solve the cost minimization in an online way, in accordance with some embodiments. 
         [0000]    
       
         
               
             
               
             
           
               
                   
               
               
                 Algorithm 1 Online CC Algorithm: 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Initialize the virtual queue X 
               
               
                 for every slot t = 1 ...S (beginning of the slot) do 
               
               
                     Predict the system parameters over slot t 
               
               
                     Solve the following problem, namely P2: 
               
               
                     Minimize: 
               
               
                         cost OnlineCC  = V Σ i  g i (t)α i (t) + X(t) Σ i η i (t)   (6) 
               
               
                     Subject to: (1), and (2) 
               
               
                     Update the virtual queue X using (7). 
               
               
                 end for 
               
               
                   
               
             
          
         
       
     
         [0052]    OnlineCC, solving the optimization problem P2 in Algorithm 1, requires only the hour-ahead information for the inputs (i.e., λ j (t), r i (t), α i (t), ε i   g (t) and ε i   r (t)), since the problem P2 removes the coupling property of P1 (i.e., removing the constraint (4)). OnlineCC can use the control parameter V that can be adjusted in any suitable form (see Alg. 1) to adjust the cost minimization and carbon capping trade-off 
         [0053]    Lemma 1 (below) can be used to help to prove the worst-case carbon capping violation of OnlineCC. It can be seen that OnlineCC minimizes the weighted sum of electricity cost and carbon footprint, weighted by V and X(t), respectively. 
         [0054]    The following lemma presents a condition under which the second term of (6) outweighs its first term such that minimizing carbon footprint yields lesser value for the OnlineCC objective function. Such condition is related to the parameter X lim  which is a bound of the electricity cost difference over the carbon footprint difference across data centers for the entire time period. Mathematically, it is represented as: 
         [0000]    
       
         
           
             
               
                 X 
                 lim 
               
               = 
               
                 
                   
                     c 
                     max 
                   
                   - 
                   
                     c 
                     min 
                   
                 
                 b 
               
             
             , 
             
               
 
             
              
             
               where 
                
               
                 : 
               
             
           
         
       
       
         
           
             
               
                 c 
                 max 
               
               = 
               
                 
                   max 
                   
                     i 
                     , 
                     t 
                   
                 
                  
                 
                   ( 
                   
                     
                       
                         p 
                         i 
                       
                       
                         μ 
                         i 
                       
                     
                      
                     
                       
                         α 
                         i 
                       
                        
                       
                         ( 
                         t 
                         ) 
                       
                     
                   
                   ) 
                 
               
             
             , 
             
               
 
             
              
             
               
                 c 
                 min 
               
               = 
               
                 
                   min 
                   
                     i 
                     , 
                     t 
                   
                 
                  
                 
                   ( 
                   
                     
                       
                         p 
                         i 
                       
                       
                         μ 
                         i 
                       
                     
                      
                     
                       
                         α 
                         i 
                       
                        
                       
                         ( 
                         t 
                         ) 
                       
                     
                   
                   ) 
                 
               
             
             , 
             
               
 
             
              
             
               b 
               = 
               
                 
                   min 
                   
                     i 
                     , 
                     k 
                     , 
                     t 
                     , 
                     
                       i 
                       ≠ 
                       k 
                     
                   
                 
                  
                 
                   
                     ( 
                     
                       
                         
                           
                             
                               p 
                               i 
                             
                             
                               μ 
                               i 
                             
                           
                            
                           
                             
                               ɛ 
                               i 
                               g 
                             
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                         - 
                         
                           
                             
                               p 
                               k 
                             
                             
                               μ 
                               k 
                             
                           
                            
                           
                             
                               ɛ 
                               k 
                               g 
                             
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                       
                       | 
                       
                         
                           
                             
                               p 
                               i 
                             
                             
                               μ 
                               i 
                             
                           
                            
                           
                             
                               ɛ 
                               i 
                               g 
                             
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                         ≠ 
                         
                           
                             
                               p 
                               k 
                             
                             
                               μ 
                               k 
                             
                           
                            
                           
                             
                               ɛ 
                               k 
                               g 
                             
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                       
                     
                     ) 
                   
                   . 
                 
               
             
           
         
       
     
         [0055]    Lemma 1. 
         [0056]    Suppose data centers require non-zero active servers, and for a given slot t, X(t)≧VX lim , then OnlineCC minimizes carbon footprint for the current slot. 
         [0057]    Building upon Lyapunov optimization, Theorem 1 (below) presents the performance analysis of OnlineCC. 
         [0058]    Theorem 1. 
         [0059]    (Performance Bound Analysis): Suppose X(0)=0, and that power demands and input workloads of data centers are bounded. Then given any fixed control parameter V&gt;0, the online algorithm, OnlineCC achieves the following: 
         [0060]    1) The carbon footprint capping constraint is approximately satisfied with a bounded deviation as follows: 
         [0000]      Σ t=0   S-1 Σ i η i ( t )≦Σ+ VX   lim +max(θ−2,0)(η max −  η )+η max   (8)
 
         [0061]    2) Assume data center parameters are independent and identically distributed over every slot, the time averaged cost under the online algorithm is within B/V of the offline optimal time averaged cost value, cost: 
         [0000]    
       
         
           
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           lim 
                            
                           
                               
                           
                            
                           
                             sup 
                             
                               t 
                               -&gt; 
                               ∞ 
                             
                           
                            
                           
                             1 
                             t 
                           
                            
                           
                             Σ 
                             
                               τ 
                               = 
                               0 
                             
                             
                               t 
                               - 
                               1 
                             
                           
                            
                            
                            
                           
                             { 
                             
                               
                                 cost 
                                 OnlineCC 
                               
                                
                               
                                 ( 
                                 τ 
                                 ) 
                               
                             
                             } 
                           
                         
                         ≤ 
                         
                           
                             cost 
                             * 
                           
                           + 
                           
                             B 
                             V 
                           
                         
                       
                       , 
                       
                         
 
                       
                        
                       
                           
                       
                        
                       
                         where 
                          
                         
                           : 
                         
                       
                     
                      
                     
                       
 
                     
                      
                     
                         
                     
                      
                     
                       B 
                       = 
                       
                         
                           1 
                           2 
                         
                          
                         
                           ( 
                           
                             
                               η 
                               max 
                               2 
                             
                             + 
                             
                               
                                 η 
                                 _ 
                               
                               2 
                             
                           
                           ) 
                         
                       
                     
                      
                     
                       
 
                     
                      
                     
                       
                         
                           cost 
                           OnlineCC 
                         
                          
                         
                             
                         
                          
                         refers 
                          
                         
                             
                         
                          
                         to 
                          
                         
                             
                         
                          
                         the 
                          
                         
                             
                         
                          
                         value 
                          
                         
                             
                         
                          
                         of 
                          
                         
                             
                         
                          
                         
                           ( 
                           6 
                           ) 
                         
                          
                         
                             
                         
                          
                         as 
                          
                         
                             
                         
                          
                         shown 
                          
                         
                             
                         
                          
                         in 
                          
                         
                             
                         
                          
                         
                           Alg 
                           . 
                           
                               
                           
                            
                           1 
                         
                       
                       , 
                       and 
                     
                      
                     
                       
 
                     
                      
                     
                         
                     
                      
                     
                       
                         
                           co 
                            
                           st 
                         
                         * 
                       
                        
                       
                           
                       
                        
                       is 
                        
                       
                           
                       
                        
                       the 
                        
                       
                           
                       
                        
                       optimal 
                        
                       
                           
                       
                        
                       solution 
                        
                       
                           
                       
                        
                       to 
                        
                       
                           
                       
                        
                       
                         P1 
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0062]    The results of Lemma 1 and (8) are important since they can provide a deterministic bound on the maximum carbon capping violation of OnlineCC. The intuition behind (8) is that the carbon cap violation is bounded by the maximum value that X can get which is equal to the sum of VX lim  (e.g., the upper bound value of X to minimize carbon footprint) and the total carbon footprint backlog accumulated when minimizing carbon footprint in the worst case (i.e., over θ). 
         [0063]    These results can also be used to adjust the value of V. OnlineCC uses a control parameter V&gt;0 that affects the distance from optimality. Particularly, according to Theorem 1, the algorithm achieves an average cost no more than O(I/V) distance above the optimal average cost, while the large value of V comes at the expense of an O(V) trade-off in achieving the carbon cap. According to (7), the aggregated carbon violation until time t equals max(X(t)−  η ). If V=V min  were chosen, where  η =V min X lim , then according to Lemma 1, OnlineCC minimizes carbon footprint whenever either the carbon footprint over a slot exceeds  η  (due to peak workload) or the sum of backlog and the slot carbon footprint exceed  η . This means that choosing V=V min , OnlineCC most of the time yields a lesser value than that of  η , since the offline solution does not always minimize the carbon footprint when the workload is at its peak (e.g., for loose  η ). This is particularly true because VX lim  is an upper-bound value for OnlineCC to minimize the carbon footprint. Choosing the right value for V such that OnlineCC achieves near or very close to the carbon cap (Σ) depends on the variability of the electricity cost (α i (t)) and the carbon emission (η i (t)) of data centers over time. 
         [0064]    The right V value also depends on θ. Depending on the electricity cost, the optimal offline solution may violate the average carbon cap in some slots, which can be compensated in future slots (depending on θ). One heuristic solution to imitate this behavior, is to choose V such that on average around 
         [0000]    
       
         
           
             
               θ 
               2 
             
              
             
               η 
               _ 
             
           
         
       
     
         [0000]    violation nom average carbon cap is allowed, i.e., V such that 
         [0000]    
       
         
           
             
               
                 θ 
                 2 
               
                
               
                 η 
                 _ 
               
             
             = 
             
               
                 
                   VX 
                   lim 
                 
                  
                 
                     
                 
                  
                 or 
                  
                 
                     
                 
                  
                 
                   θ 
                   2 
                 
                  
                 
                   η 
                   _ 
                 
               
               = 
               
                 
                   θ 
                   2 
                 
                  
                 
                   
                     X 
                     min 
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    Further, in some embodiments, V can be chosen by considering how tight the bound X lim  is, which can be approximately calculated using the data center input parameters (i.e., peak to mean ratio of the electricity cost and the carbon intensities). 
         [0065]    In some embodiments, any suitable computer readable media can be used for storing instructions for performing the processes described herein. For example, in some embodiments, computer readable media can be transitory or non-transitory. For example, non-transitory computer readable media can include media such as magnetic media (such as hard disks, floppy disks, etc.), optical media (such as compact discs, digital video discs, Blu-ray discs, etc.), semiconductor media (such as flash memory, electrically programmable read only memory (EPROM), electrically erasable programmable read only memory (EEPROM), etc.), any suitable media that is not fleeting or devoid of any semblance of permanence during transmission, and/or any suitable tangible media. As another example, transitory computer readable media can include signals on networks, in wires, conductors, optical fibers, circuits, and any suitable media that is fleeting and devoid of any semblance of permanence during transmission, and/or any suitable intangible media. 
         [0066]    Although the invention has been described and illustrated in the foregoing illustrative embodiments, it is understood that the present disclosure has been made only by way of example, and that numerous changes in the details of implementation of the invention can be made without departing from the spirit and scope of the invention, which is limited only by the claims that follow. Features of the disclosed embodiments can be combined and rearranged in various ways.