Algorithms for load balancing in electricity markets and data centers
Permanent URL:
http://hdl.handle.net/2047/D20289361
Aslam, Javed (Committee member)
Balakrishnan, Narayanaswamy (Committee member)
Rajaraman, Rajmohan (Committee member)
First, we study the temporal load balancing problem in electricity markets where peak demand and supply-demand imbalance are major problems. It is often suggested that exposing consumers to real-time pricing will incentivize them to change their usage and mitigate the problem. However, we show that risk-averse electricity consumers react to price fluctuations by scaling back on their total demand, leading to the unintended consequence of an overall decrease in production/consumption and reduced economic efficiency. Compared with the relatively fixed production mode of electric- ity power (the supply), the consumption pattern of end users (the demand) is more variable and potentially changeable. This makes temporally shifting consumers electricity load possible. We propose SmartShift, a new scheme that allows households to move their demands from peak hours in exchange for greater electricity consumption in non-peak hours. We show that our scheme not only enables increased consumption and consumer welfare but also allows the distribution company to increase profits.
We next consider the fault-tolerant spatial load balancing problem in data centers where com- putational loads get balanced by being assigned on different locations (machines - computational resources). k-HA (high-availability), a fault tolerance property of virtual machine (VM) placement in clouds, represents the ability to tolerate up to k host failures by relocating VMs from failed hosts without disrupting other VMs. It has long been assumed that deciding the existence of a k-HA placement is P3 -complete. We show that k-HA reduces to multiple knapsack and hence is NP- complete. We propose a stochastic model for multiple knapsack that not only captures real-world workloads but also provides a uniform basis for comparing the efficiencies of different polynomial- time heuristics. We prove, using the central limit theorem and linear programming, that, in an important special case, there exists a best polynomial-time heuristic. We turn to industry practice and discuss the drawbacks of commonly used heuristics - First-fit, Best-fit, Worst-fit, MTHM and CSP. Based on a large real-world dataset of cluster workloads from industry we show that the natural load-balancing heuristic - Water-filling - has several excellent properties. We compare and contrast Water-filling with MTHM using our stochastic model and find that Water-filling is a heuristic of choice.
Finally, we extend our study on load balancing from the single dimensional case to multidi- mensional resources. This is inspired by multiple questions from both electricity markets and data centers. For example, what is the best way to assign VMs to data centers to minimize the disruption caused when data centers are powered down for maintenance? How companies distribute the load to hybrid clouds? These related problems can be modeled as the Uncapacitated Multidimensional Load Assignment problem, where items (load demand) and buckets (supply capacity) are character- ized by a d-dimensional vector. Additional affinity constraints may restrict the subset of buckets a specific item may be placed in. The cost of a bucket is obtained by aggregating the assigned items according to some metric, with different metrics (max, min, second-max, etc) representing different application scenario for either electric markets or data centers. The goal is to minimize the total cost across all buckets. The temporal load balancing in electricity market and the spatial load balancing in data centers become the two applied scenarios of this problem. We provide hardness results and approximation algorithms for this problem in a variety of settings.
mechanism design
multidimensional load balancing
spatial load balancing
temporal load balancing
Copyright restrictions may apply.