Nowadays, computing tends to be performed less and less on single computers, but rather on centralized pools of resources collectively known as virtual machines. While this concentration of resources brings undoubtedly great advantages in terms of computing power, flexibility, and availability, it also poses new problems in resource allocations that were never experienced in older architectures. It has been proved that allocating virtual machines to the underlying hardware is a nondeterministic polynomial-time (NP)-hard problem; moreover, in these environmentally conscious times, all of this must be done with the aim of lowering energy consumption. This paper presents a heuristic algorithm to solve this problem.
The general idea is to use as few hardware resources as possible to set up all of the required virtual machines. In the paper, methods currently in use are presented first, and then a new method is proposed by the authors. In this method, virtual machines are expressed in terms of resources (central processing units (CPUs), memory, bandwidth, and so on), which can be modified at will by system administrators. The method itself consists of an initial assignment of resources followed by a cycle of resource evaluation, selection, and allocation. This cycle can be repeated as many times as desired; the tricky part is knowing when to stop, or when subsequent iterations do not improve performance anymore. In the final part, the paper presents a MATLAB implementation of the algorithm and its use to test the overall performance of the model, both by itself and as compared to more traditional heuristic models (namely, simulated annealing).
Assigning virtual machines is an activity for very specialized professionals. Although the paper describes the method in mathematical terms--rigorous and to the point, but certainly not easy reading--those professionals will find precious insights here.