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.
Renewed focus on virtualization technologies and increased awareness about management and power costs of running under-utilized servers has spurred interest in consolidating existing applications on fewer number of servers in the data center. The ability to migrate virtual machines dynamically between physical servers in real-time has also added a dynamic aspect to consolidation. However, there is a lack of planning tools that can analyze historical data collected from an existing environment and compute the potential benefits of server consolidation especially in the dynamic setting. In this paper we describe such a consolidation recommendation tool, called ReCon. Recon takes static and dynamic costs of given servers, the costs of VM migration, the historical resource consumption data from the existing environment and provides an optimal dynamic plan of VM to physical server mapping over time. We also present the results of applying the tool on historical data obtained from a large production environment. In this paper, we undertake the first study of statistical multiplexing from the perspective of approximation algorithms. The basic issue underlying statistical multiplexing is the following: in high-speed networks, individual connections (i.e., communication sessions) are very bursty, with transmission rates that vary greatly over time. As such, the problem of packing multiple connections together on a link becomes more subtle than in the case when each connection is assumed to have a fixed demand. We consider one of the most commonly studied models in this domain: that of two communicating nodes connected by a set of parallel edges, where the rate of each connection between them is a random variable. We consider three related problems: (1) stochastic load balancing, (2) stochastic bin-packing, and (3) stochastic knapsack. In the first problem the number of links is given and we want to minimize the expected value of the maximum load. In the other two problems the link capacity and an allowed overflow probability p are given, and the objective is to assign connections to links, so that the probability that the load of a link exceeds the link capacity is at most @math . In bin-packing we need to assign each connection to a link using as few links as possible. In the knapsack problem each connection has a value, and we have only one link. The problem is to accept as many connections as possible. For the stochastic load balancing problem we give an O(1)-approximation algorithm for arbitrary random variables. For the other two problems we have algorithms restricted to on-off sources (the most common special case studied in the statistical multiplexing literature), with a somewhat weaker range of performance guarantees. A standard approach that has emerged for dealing with probabilistic resource requirements is the notion of effective bandwidth---this is a means of associating a fixed demand with a bursty connection that "represents" its distribution as closely as possible. Our approximation algorithms make use of the standard definition of effective bandwidth and also a new one that we introduce; the performance guarantees are based on new results showing that a combination of these measures can be used to provide bounds on the optimal solution. We study the problems of makespan minimization (load balancing), knapsack, and bin packing when the jobs have stochastic processing requirements or sizes. If the jobs are all Poisson, we present a two approximation for the first problem using Graham's rule, and observe that polynomial time approximation schemes can be obtained for the last two problems. If the jobs are all exponential, we present polynomial time approximation schemes for all three problems. We also obtain quasi-polynomial time approximation schemes for the last two problems if the jobs are Bernoulli variables. 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. A dynamic server migration and consolidation algorithm is introduced. The algorithm is shown to provide substantial improvement over static server consolidation in reducing the amount of required capacity and the rate of service level agreement violations. Benefits accrue for workloads that are variable and can be forecast over intervals shorter than the time scale of demand variability. The management algorithm reduces the amount of physical capacity required to support a specified rate of SLA violations for a given workload by as much as 50 as compared to static consolidation approach. Another result is that the rate of SLA violations at fixed capacity may be reduced by up to 20 . The results are based on hundreds of production workload traces across a variety of operating systems, applications, and industries. There is disclosed a vehicle wash apparatus including a wash arch frame carried on tracks extending longitudinally of a wash stall in which a car to be washed is parked. Overhead arms are pivotally carried on their respective one ends from an overhead transverse horizontal pivot shaft and mount a horizontally disposed rotary top brush from the free ends thereof for selective lowering into a position for contacting the front of a vehicle to wash the grill and for travel rearwardly along the hood, top and trunk of the vehicle. Side brush arms are carried pivotally from the sides of the arch frame for rotation about vertical axes and project in a direction opposite the direction in which the top brush arms, in their retracted positions, project and are urged inwardly to wash the sides of the car as the arch carries the top brush rearwardly on the tracks. Such side arms are pivoted inwardly as the side brushes clear the rear corners of the car to carry the side brushes about the rear corners of the vehicle to wash the rear thereof as the top brush completes washing of the top of the trunk.