Colocation, Colocation, Colocation: Optimizing Placement in the Hybrid Cloud

摘要

Today's enterprise customer has to decide how to distribute her services among multiple clouds - between on-premise private clouds and public clouds - so as to optimize different objectives, e.g., minimizing bottleneck resource usage, maintenance downtime, bandwidth usage or privacy leakage. These use cases motivate a general formulation, the uncapacitated (A defining feature of clouds is their elasticity or ability to scale with load) multidimensional load assignment problem - VITA(F) (Vectors-In-Total Assignment): the input consists of n, d-dimensional load vectors V{top}-={ V{top}-_i|1≤i≤n}, m cloud buckets B= {B_(j|)1 ≤ j ≤ m} with associated weights Wj and assignment constraints represented by a bipartite graph G = (V{top}- ∪ B, E {is contained in} V{top}- × B) restricting load V{top}-_i to be assigned only to buckets B_j with which it shares an edge (In a slight abuse of notation, we let B_j also denote the subset of vectors assigned to bucket B_j). F can be any operator mapping a vector to a scalar, e.g., max, min, etc. The objective is to partition the vectors among the buckets, respecting assignment constraints, so as to achieve {formula} We characterize the complexity of VITA(min), VITA(max), VITA(max - min) and VITA(2nd max) by providing hardness results and approximation algorithms, LP-Approx involving clever rounding of carefully crafted linear programs. Employing real-world traces from Nutanix, a leading hybrid cloud provider, we perform a comprehensive comparative evaluation versus three natural heuristics - Conservative, Greedy and Local-Search. Our main finding is that on real-world workloads too, LP-Approx outperforms the heuristics, in terms of quality, in all but one case.