TY - JOUR
T1 - Data locality and replica aware virtual cluster embeddings
AU - Fuerst, Carlo
AU - Pacut, Maciej
AU - Schmid, Stefan
PY - 2017
Y1 - 2017
N2 - Virtualized datacenters offer great flexibilities in terms of resource allocation. In particular, by decoupling applications from the constraints of the underlying infrastructure, virtualization supports an optimized mapping of virtual machines as well as their interconnecting network (the so-called virtual cluster) to their physical counterparts: a graph embedding problem.However, existing virtual cluster embedding algorithms often ignore a crucial dimension of the 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.
AB - Virtualized datacenters offer great flexibilities in terms of resource allocation. In particular, by decoupling applications from the constraints of the underlying infrastructure, virtualization supports an optimized mapping of virtual machines as well as their interconnecting network (the so-called virtual cluster) to their physical counterparts: a graph embedding problem.However, existing virtual cluster embedding algorithms often ignore a crucial dimension of the 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.
KW - Flow algorithms
KW - NP hardness
KW - Virtual network embeddings
UR - http://www.scopus.com/inward/record.url?scp=85025154012&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2017.06.025
DO - 10.1016/j.tcs.2017.06.025
M3 - Journal article
AN - SCOPUS:85025154012
SN - 0304-3975
VL - 697
SP - 37
EP - 57
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -