Load Balancing in Cloud Computing: Challenges and Algorithms

Cloud computing opens a new chapter in information technology, by enabling global access to shared pools of resources such as services, data, servers, and computer networks. It drives new digital businesses across enterprises. In the last few years, an unprecedented amount of data center capacity has been built to support cloud computing services' growth. Therefore, optimizing the energy budget of data centers, without harming service level agreements, would result in massive savings for their operators, and significantly contribute to greater environmental sustainability. A key challenge in optimizing cloud computing services is their online nature. That is, they require immediate and irrevocable decisions to be made, based on incomplete input.        

In this talk, I will discuss my work on a major optimization aspect of cloud services: virtual machine placement. Specifically, I will present our results for online vector load balancing problems, a well-studied model for virtual machine placement in cloud services. In those problems, jobs have vector loads and the goal is to balance the load on all dimensions simultaneously. First, I will present algorithms and matching lower bounds for those problems.

Unfortunately, for many practical applications, those bounds are unsatisfactory. Accordingly, by adding restricting, yet practical, assumptions, and by using various novel techniques, we show how to improve those bounds significantly