Resource allocation for cloud services is a complex task due to the diversity of the services and the dynamic workloads. One way to address this is by overprovisioning which results in high cost due to the unutilized resources. A much more economical approach, relying on the stochastic nature of the demand, is to allocate just the right amount of resources and use additional more expensive mechanisms in case of overflow situations where demand exceeds the capacity. In this paper we study this approach and show both by comprehensive analysis for independent normal distributed demands and simulation on synthetic data that it is significantly better than currently deployed methods.
A naive approach to such a problem is to reduce it to classical bin packing as follows: for the @math 'th service define the as the number @math such that the probability that @math is larger than @math is small; then solve the classical bin packing problem (or a variant of it) with item sizes @math . However, @cite_3 showed this approach can be quite wasteful, mostly because it adds extra space per service and not per bin. To demonstrate the issue, think about unbiased, independent coin tosses. The probability one coin toss significantly deviates from its mean is @math , while the probability @math independent coin tosses significantly deviate from the mean is exponentially small. When running independent trials there is a effect that considerably reduces the chance of high deviations. This can also be seen from the fact that the standard deviation of @math independent, identical processes is only @math times the standard deviation of one process, and so the standard deviation grows much slower than the number of processes.
@cite_3
2110458625
Recent advances in virtualization technology have made it a common practice to consolidate virtual machines(VMs) into a fewer number of servers. An efficient consolidation scheme requires that VMs are packed tightly, yet receive resources commensurate with their demands. However, measurements from production data centers show that the network bandwidth demands of VMs are dynamic, making it difficult to characterize the demands by a fixed value and to apply traditional consolidation schemes. In this work, we formulate the VM consolidation into a Stochastic Bin Packing problem and propose an online packing algorithm by which the number of servers required is within equation of the optimum for any ∈ > 0. The result can be improved to within equation of the optimum in a special case. In addition, we use numerical experiments to evaluate the proposed consolidation algorithm and observe 30 server reduction compared to several benchmark algorithms.