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 \(\bar{V} = \{\bar{V}_i | 1\le i \le n\}\), m cloud buckets \(B = \{B_j | 1\le j \le m\}\) with associated weights \(w_j\) and assignment constraints represented by a bipartite graph \(G=(\bar{V} \cup B, E \subseteq \bar{V} \times B)\) restricting load \(\bar{V}_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 We characterize the complexity of VITA\((\min )\), VITA\((\max )\), VITA\((\max - \min )\) and VITA\((2^{nd}\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.