Cloud Computing and Graph Coloring

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 two major online optimization problems for cloud services: switch routing and virtual machine placement. I will show how these problems relate to graph coloring, one of the most well-known, popular and extensively-researched areas in the field of graph theory. First, I will present tight bounds for online edge coloring in bipartite graphs, which leads to an optimal switch routing scheduler. I will then discuss vector balancing problems, a well-studied model for virtual machine placement in cloud services. In these problems, jobs have vector loads and the goal is to balance the load on all dimensions simultaneously. For this purpose, I will first consider two natural relaxations of the vertex coloring problem, and show new online lower bounds for them. I will then show how to port these bounds back to vector balancing, and prove that the bounds are tight by presenting matching upper bounds. In addition, for practical applications, these bounds are unsatisfactory, so I will also discuss how to improve the upper bounds by adding restricting, yet practical, assumptions.