Patent ID: 9454395
Filing Date: 2016-09-27
CPC Classification: G06F

Claim Text:
1. A method implemented by a computing device to provide traffic-aware virtual machine (VM) placement onto physical servers of a data center, the placement takes incremental VM job arrival and physical server heterogeneity into consideration, the method comprising the steps of: forming a graph including a new VM node and an existing VM node, wherein the new VM node represents a new VM to be placed on one of a plurality of physical servers and the existing VM node represents an existing VM assigned to one of the physical servers, the graph further including an edge between the new VM node and the existing VM node, wherein the edge is assigned a weight that represents a traffic demand between the new VM node and the existing VM node; marking the existing VM node as belonging to the one of the physical servers assigned to the existing VM; adding dummy VM nodes to the graph such that a total number of new VM nodes and dummy VM nodes is equal to a total number of available VM slots on the physical servers; adding pseudo VM nodes to the graph, wherein each pseudo VM node is marked as belonging to one of the physical servers, and wherein the pseudo VM nodes are added to the graph such that each of the physical servers has a same total number of VM slots and the total number of VM slots on each physical server is given by c connecting nodes that are marked as belonging to a same physical server using a pseudo edge having an infinite weight; running a balanced minimum k-cut problem algorithm on the graph to thereby divide the graph into a same number of sub-graphs as a number of physical servers; and mapping the new VM to one of the physical servers based on a sub-graph to which the new VM node that represents the new VM belongs.