How Hard Can It Be? Understanding the Complexity of Replica Aware Virtual Cluster Embeddings

∗ authors contributed equally to this work Abstract—Virtualized datacenters offer great flexibilities in terms of resource allocation. In particular, by decoupling ap-plications from the constraints of the underlying infrastructure, virtualization supports an optimized mapping of virtual machines as well as their interconnecting network to their physical coun-terparts: essentially a graph embedding problem. However, existing embedding algorithms such as Oktopus and Proteus often ignore a crucial dimension of the embedding problem, namely data locality: the input to a cloud application such as MapReduce is typically stored in a distributed, and sometimes redundant, file system. Since moving data is costly, an embedding algorithm should be data locality aware, and allocate computational resources close to the data; in case of redundant storage, the algorithm should also optimize the replica selection. This paper initiates the algorithmic study of data locality aware virtual cluster embeddings on datacenter topologies. We show that despite the multiple degrees of freedom in terms of embedding, replica selection and assignment, many problems can be solved efficiently. We also highlight the limitations of such optimizations, by presenting several NP-hardness proofs; interestingly, our hardness results also hold in uncapacitated networks of small diameter. I