Shadow-Routing Based Dynamic Algorithms for Virtual Machine Placement in a Network Cloud

We consider a shadow routing based approach to the problem of real-time adaptive placement of virtual machines (VM) to large data centers (DC) in a network cloud. Such placement in particular has to respect vector packing constraints on the allocation VMs to host physical machines (PM) within a DC, because each PM can potentially serve multiple VMs simultaneously. Shadow routing is attractive in that it allows a large variety of system objectives and/or constraints to be treated within a common framework (as long as the underlying optimization problem is convex). Perhaps even more attractive feature is that a shadow routing algorithm is very simple to implement, it runs continuously, and adapts automatically to changes in the VM demand rates, additions and removals of constraints, changes in system parameters, etc., without the need to re-solve the underlying optimization problem "from scratch". In this paper we concentrate on the min-max-DC-load problem. Namely, we propose a combined VM-to-DC routing and VM-to-PM assignment algorithm, which minimizes the maximum of DC utilizations; a DC utilization is defined as the fraction of non-idle PMs. We prove that the proposed scheme is asymptotically optimal (as one of its parameters goes to 0). Simulation confirm good performance and high adaptivity of the algorithm. We also propose a simplified - "more distributed" - version of the shadow routing algorithm, which performs almost as well in simulations.