Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service

Details Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service

2012-02-16

arxiv.org/abs/1202.3683v1

Computer Science

Networking and Internet Architecture

Scientific paper

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)$.

Affiliated with

Also associated with

No associations

Rating

Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-34940