An Enhanced Approximation Algorithm Using Red Black Tree and HashMap for Virtual Machine Placement Problem

The virtual machine placement problem (VMPP) is an np-hard optimization problem in cloud computing that involves efficiently allocating virtual machines (VMs) to physical hosts in such a way that the resource wastage is minimized, and resource usage is optimal while ensuring adequate performance. This paper proposes a modified best-fit approximation algorithm using Red Black Tree (RBT) and HashMap for addressing the VMPP with enhanced computational efficiency in such a way that the active hosts in a given data center remains minimum possible. The proposed algorithm builds up on the existing best-fit approximation algorithm by using RBT and HashMap. The proposed approach considers various attributes such as CPU utilization, memory requirements, and network bandwidth while allocating virtual machines. To evaluate the performance the simulation is done in cloudsim environment with PlanetLab workload. Test cases are considered in both homogeneous and heterogeneous environments and results are taken. Comparative analyses were performed against existing benchmark algorithms in terms of time complexity and resource usage in terms of active hosts. The results demonstrate that the proposed algorithm outperforms the existing algorithms and guarantees time complexity of O(log n) and give better results compared to other algorithms.