  Efficient embedding virtual clusters in physical network is a challenging
problem. In this paper we consider a scenario where physical network has a
structure of a balanced tree. This assumption is justified by many real- world
implementations of datacenters. We consider an extension to virtual cluster
embedding by introducing replication among data chunks. In many real-world
applications, data is stored in distributed and redundant way. This assumption
introduces additional hardness in deciding what replica to process. By
reduction from classical NP-complete problem of Boolean Satisfia- bility, we
show limits of optimality of embedding. Our result holds even in trees of edge
height bounded by three. Also, we show that limiting repli- cation factor to
two replicas per chunk type does not make the problem simpler.
