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.
Breitgand and Epstein @cite_6 , building on @cite_3 , suggest an algorithm for stochastic bin packing that takes advantage of this smoothing effect. The algorithm assumes all bins have equal capacity. The algorithm first sorts the processes by their variance to mean ratio (VMR), i.e., @math . Then the algorithm finds the largest prefix of the sorted list such that allocating that set of services to the first bin makes the probability the first bin overflows at most @math . The algorithm then proceeds bin by bin, each time allocating a prefix of the remaining services on the sorted list to the next bin. @cite_6 show that if we allow solutions, i.e., we allow splitting services between bins, the algorithm finds an optimal solution, and also show an online, integral version that gives a @math -approximation to the optimum.
@cite_3 @cite_6
2110458625 1998448657
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. Current trends in virtualization, green computing, and cloud computing require ever increasing efficiency in consolidating virtual machines without degrading quality of service. In this work, we consider consolidating virtual machines on the minimum number of physical containers (e.g., hosts or racks) in a cloud where the physical network (e.g., network interface or top of the rack switch link) may become a bottleneck. Since virtual machines do not simultaneously use maximum of their nominal bandwidth, the capacity of the physical container can be multiplexed. We assume that each virtual machine has a probabilistic guarantee on realizing its bandwidth Requirements-as derived from its Service Level Agreement with the cloud provider. Therefore, the problem of consolidating virtual machines on the minimum number of physical containers, while preserving these bandwidth allocation guarantees, can be modeled as a Stochastic Bin Packing (SBP) problem, where each virtual machine's bandwidth demand is treated as a random variable. We consider both offline and online versions of SBP. Under the assumption that the virtual machines' bandwidth consumption obeys normal distribution, we show a 2-approximation algorithm for the offline version and improve the previously reported results by presenting a (2 +∈)-competitive algorithm for the online version. We also observe that a dual polynomial-time approximation scheme (PTAS) for SBP can be obtained via reduction to the two-dimensional vector bin packing problem. Finally, we perform a thorough performance evaluation study using both synthetic and real data to evaluate the behavior of our proposed algorithms, showing their practical applicability.