# Dependency Analysis based Approach for Virtual Machine Placement in Software-Defined Data Center
## 2 Background and Related Work
### Virtual Machine Placement  
VM placement is a critical operation to find the best PMs to host VMs. The VM placement problem is generally formulated as an optimization problem under various constraints [29]. Existing works on VM placement can be broadly categorized into two types such as QoS-based and power-based approaches [30]. Most of the QoS-based approaches investigated network traffic-engineering for improving data center performance such as maximizing network throughput, reducing the data rate, and load-balancing. Power-based approaches focused on reducing the energy consumption of the data center by minimizing the number of concurrently running PMs. Several studies on network-aware VM placement in data center have been conducted. [PERSON] et al. [31] presented a joint optimization problem of VM placement and route scheduling. They used a traffic-engineering technique to minimize the transmission delay and maximize the network throughput. [PERSON] et al. [32] proposed a traffic-aware technique for VM placement. They formulated the VM placement as a joint optimization problem of network and server resources using the traffic matrix among VMs and the cost matrix among host machines. They used a two-tier approximation algorithm to solve the optimization problem on the scale of real data centers. [PERSON] et al. [33] studied VM placement problem in data center by modeling the problem as joint affinity aware grouping and a bin-packing method. They grouped the VMs based on the affinity between the VMs, and used a bin-packing heuristic algorithm for resource scheduling. In [34], the authors investigated the network influence on typical applications in data centers and proposed a self-adaptive network-aware virtual machine clustering and consolidation algorithm to maintain an optimal system-wide status. Moreover, recently a lot of attention has been put to the efficient placement of VMs in the context of network function virtualization (NFV). In [35], [PERSON] et al. studied how to efficiently deploy NFV middleboxes to minimize maximum link load ratio in SDN environment. They formulated traffic aware middlebox placement (TAMP) problem as a graph optimization problem,and then proposed a least-first-greatest-last (LFGL) strategy for solving the problem. [PERSON] et al. [36] designed a heuristic NFV deployment algorithm for improving data center performance. The algorithm finds the number of necessary virtual network functions (VNFs), placement location of the VNFs, and traffic dispatching strategy to the VNFs for reducing amount of east-west traffic in the data center. In [37], [PERSON] et al. proposed workload optimization approach for VM placement in the data center. They formulated an optimization model based on resource utilization with the aim of minimizing power consumption. In [27], [PERSON] et al. addressed VNF placement problem in data center. They formulated the VNF placement problem as integer linear programming (ILP) model with the aim of minimizing the number of running PMs. The proposed strategy considers both time-varying workloads and basic resource consumptions when optimizing the resource utilization of the data center. In [38], [PERSON] et al. introduced energy-efficient VNF placement strategy with the aim of minimizing data center cost. They formulated the network traffic cost function as an optimization problem and solved it by Markov approximation technique. [PERSON] et al. [39] presented a bin packing based VM placement method in cloud data centers in order to minimize the number of running PMs. They used particle swarm optimization (PSO) with variable sized bin packing (PSOLBP) algorithm for solving the optimization problem. In [40], [PERSON] et al. studied a problem of VM placement and migration to minimize resource usage and power consumption in a data center. They formulated the optimization problem of the VM placement as a joint multiple objective function and solved it by leveraging convex optimization.