Certified Bounds on the Live Migrations Needed to Reclaim Servers Fragmented by Online Vector Bin Packing on a Production Cloud Trace

Abstract

Background. Online allocators place virtual machines (VMs) without knowing their life-times; departures leave servers fragmented, and reclaiming them takes costly live migrations. We bound how many servers a migration budget reclaims in a public production trace.
Methods. We prove the minimum-migration problem strongly NP-hard and, unless P = NP, inapproximable, and bracket the servers that a budget reclaims between a greedy drain and an elementary lower bound on migrations; column generation brackets the static optimum. Re-playing the Azure VM packing trace under five online policies, we test, under a plan frozen before opening the second week, whether a budget of 1% of the live VMs reclaims more than 1% of the servers over 167 hourly instants, with validity checks, 1,200 multiverse speci-fications, an external replication and exact baselines.
Results. Under Best Fit, a budget of 1% of the live VMs reclaimed for certain 5.62% of the servers in use on average (one-sided 95% lower bound 5.38%), valid under the plan, while no algorithm could reclaim more than 6.89%, the whole excess over the size-sum bound; at the 7 daily checkpoints the static optimum lay within 2 servers of the size-sum bound. The drain achieved on average 0.83 of the certified maximum, below the planned 0.9; 69% of the multiverse specifications exceeded the threshold, including every one with a budget of 2% or more; the replication was positive for all three machine shapes; and on small instances both bounds matched the exact minimum. Exploratory: with 0.1% of the VMs the bounds coin-cided at every instant; with 5% the drain stopped short of the excess before exhausting the budget.
Conclusions. Certified bounds make the migration cost of reclaiming fragmented servers measurable at production scale; on this trace under Best Fit, a budget of 1% of the live VMs reclaims 5.6% of the servers on average.