On the problem of mapping virtual machines to physical machines for delay sensitive services

Server virtualization is usually used to consolidate multiple virtual machines in the same physical server for power consumption and cost reduction purposes. On the other hand, several virtual machines´ killer applications are delay sensitive since they interact with the user in real time such as IP telephony signalling, thin clients and video. Therefore, server virtualization can be exploited to run VMs on servers that provide the lowest delay to their users. In this paper, we consider the case of a virtualized IP Multimedia Subsystems. As a first optimization objective, assigning VMs to lowest delay servers will consolidate them in very few servers serving high density regions. However, it will create overloaded hot spot servers. Thus, in order to provide a globally higher number of VMs to servers mappings, we allow delay-sensitive applications to tolerate a delay up to a given threshold. Consequently, we will be able to provide an option to optimize a second objective that consists of load balancing over a higher number of servers. We show that this optimization problem is NP complete. We formulate the problem using a weighted bipartite matching graph and then we solve it using a modified Hungarian method. Results show that our proposed algorithms provide near-optimal solutions in short time.