  Infrastructure-as-a-Service (IaaS) providers need to offer richer services to
be competitive while optimizing their resource usage to keep costs down. Richer
service offerings include new resource request models involving bandwidth
guarantees between virtual machines (VMs). Thus we consider the following
problem: given a VM request graph (where nodes are VMs and edges represent
virtual network connectivity between the VMs) and a real data center topology,
find an allocation of VMs to servers that satisfies the bandwidth guarantees
for every virtual network edge---which maps to a path in the physical
network---and minimizes congestion of the network.
  Previous work has shown that for arbitrary networks and requests, finding the
optimal embedding satisfying bandwidth requests is $\mathcal{NP}$-hard.
However, in most data center architectures, the routing protocols employed are
based on a spanning tree of the physical network. In this paper, we prove that
the problem remains $\mathcal{NP}$-hard even when the physical network topology
is restricted to be a tree, and the request graph topology is also restricted.
We also present a dynamic programming algorithm for computing the optimal
embedding in a tree network which runs in time $O(3^kn)$, where $n$ is the
number of nodes in the physical topology and $k$ is the size of the request
graph, which is well suited for practical requests which have small $k$. Such
requests form a large class of web-service and enterprise workloads. Also, if
we restrict the requests topology to a clique (all VMs connected to a virtual
switch with uniform bandwidth requirements), we show that the dynamic
programming algorithm can be modified to output the minimum congestion
embedding in time $O(k^2n)$.
