To migrate or to wait: Delay-cost tradeoff for cloud data centers

To upgrade the systems or fix the security issues, some physical machines (PMs) in data centers are required to undergo a maintenance process, which might disable the continuous services of the virtual machines (VMs) run on them for a few time slots. To reduce the waiting delay, one may migrate the VMs to other active PMs. However, it will incur extra migration cost, e.g., bandwidth or memory used to move data. To balance the tradeoff between delay and migration cost, we formulate a two-objective optimization problem, which minimizes both delay and migration cost according to a certain weightage, so as to decide whether the VMs should be migrated to other active PMs or should wait their own maintained PMs to be back. We first prove that the proposed problem is NP-hard. For a special case, where each VM requires the same size of resource, we show that the defined problem can be converted to minimum weighted bipartite matching problem in an auxiliary bipartite graph. A lower bound of the delay is derived for a specific setting. For the general case of the problem, we also design an efficient heuristic algorithm. Finally, simulation results demonstrate the effectiveness of the proposed scheme.