Online Placement of Virtual Machines with Prior Data

The cloud computing market has a wide variety of customers that deploy various applications from deep learning to classical web services. Each application may have different computing, memory and networking requirements, and each customer may be willing to pay a different price for the service. When a request for a VM arrives, the cloud provider decides online whether to serve it or not and which resources to allocate for this purpose. The goal is to maximize the revenue while obeying the constraints imposed by the limited physical infrastructure and its layout.Although requests arrive online, cloud providers are not entirely in the dark; historical data is readily available and may contain strong indications regarding future requests. Thus, standard theoretical models that assume the online player has no prior knowledge are inadequate. In this paper, we adopt a recent theoretical model for the design and analysis of online algorithms that allows taking such historical data into account. We develop new competitive online algorithms for multidimensional resource allocation and analyze their guaranteed performance. Moreover, using extensive simulation over real data from Google and AWS, we show that our new approach yields much higher revenue to cloud providers than currently used heuristics.