Shared data centers and clouds are gaining popularity because of their ability to reduce costs by increasing the utilization of server farms. In a shared server environment, a careful assignment of workload streams (all work-requests from a customer may constitute a stream) to servers is necessary to ensure good “end user” performance. In this work, we investigate the assignment of streams to servers in order to minimize an objective function, while ensuring that load is balanced across all the servers. The objective functions we optimize in this work include the overall expected waiting-time, overall probability of the wait exceeding a given value, and weighted versions of these measures. We obtain the optimal algorithm for a farm with 2 servers, if sharing of streams among servers is allowed. Based on the insights obtained, we design an efficient algorithm for the multiserver case. By rounding off this solution, we obtain a solution to the case where sharing of streams is not allowed. Our trace-driven evaluation study shows that our algorithms significantly outperform baseline methods. Our work enables high performance for web hosting services as well as emerging Application as a Service (AaaS) clouds. We also show that solutions in areas such as task-level scheduling and file assignment fall within our framework.

Markov chains with small transition probabilities occur while modeling the reliability of systems where the individual components are highly reliable and quickly repairable. Complex inter-component dependencies can exist and the state space involved can be huge, making these models analytically and numerically intractable. Naive simulation is also difficult because the event of interest (system failure) is rare, so that a prohibitively large amount of computation is needed to obtain samples of these events. An earlier paper (Juneja et al., 2001) proposed an importance sampling scheme that provides large efficiency increases over naive simulation for a very general class of models including reliability models with general repair policies such as deferred and group repairs. However, there is a statistical penalty associated with this scheme when the corresponding Markov chain has high probability cycles as may be the case with reliability models with general repair policies. This paper develops a splitting-based importance-sampling technique that avoids this statistical penalty by splitting paths at high probability cycles and thus achieves bounded relative-error in a stronger sense than in previous attempts.

With the ever-increasing complexity and requirements of highly dependable systems, their evaluation during design and operation is becoming more crucial. Realistic models of such systems are often not amenable to analysis using conventional analytic or numerical methods. Therefore, analysts and designers turn to simulation to evaluate these models. However, accurate estimation of dependability measures of these models requires that the simulation frequently observes system failures, which are rare events in highly dependable systems. This renders ordinary Simulation impractical for evaluating such systems. To overcome this problem, simulation techniques based on importance sampling have been developed, and are very effective in certain settings. When importance sampling works well, simulation run lengths can be reduced by several orders of magnitude when estimating transient as well as steady-state dependability measures. This paper reviews some of the importance-sampling techniques that have been developed in recent years to estimate dependability measures efficiently in Markov and nonMarkov models of highly dependable systems.

This paper develops methods for computationally efficient calculation of value-at-risk (VAR) in the presence of heavy-tailed risk factors. The methods model market risk factors through a multivariate t-distribution, which has both heavy tails and empirical support. Our key mathematical result is a transform analysis of a quadratic form in multivariate t random variables. Using this result, we develop two computational methods. The first uses Fourier transform inversion to develop a heavy-tailed delta-gamma approximation; this method is extremely fast, but like any delta-gamma method is only as accurate as the quadratic approximation. For greater accuracy, we therefore develop an efficient Monte Carlo method; this method uses our heavy-tailed delta-gamma approximation as a basis for variance reduction. Specifically, we use the numerical approximation to design a combination of importance sampling and stratified sampling of market scenarios that can produce enormous speed-ups compared with standard Monte Carlo.

Service providers typically define quality of service problems using threshold tests, such as "are HTTP operations greater than 12 per second on server XYZ?" This paper explores the feasibility of predicting violations of threshold tests. Such a capability would allow providers to take corrective actions in advance of service disruptions. Our approach estimates the probability of threshold violations for specific times in the future. We modeled the threshold metric (e.g., HTTP operations per second) at two levels: (1) nonstationary behavior (as is done in workload forecasting for capacity planning) and (2) stationary, time-serial dependencies. Using these models, we compute the probability of threshold violations. We asses our approach using measurements of HTTP operations per second collected from a production Web server. These assessments suggest that our approach works well if: (a) the actual values of predicted metrics are sufficiently distant from their thresholds; and/or (b) the prediction horizon is not too far into the future.

An approximation technique is presented to evaluate the dependability of FDDI networks. This technique, based on the most likely paths to failure concept, is simple and practical. It may be applied easily to evaluate and compare the dependability of different FDDI network configurations. The effects of various network parameters on the network availability are examined. We conclude that, in order to guarantee high availability, an FDDI network backbone should be interconnected using dual-attachment concentrators. Furthermore, dual-homing configurations are required for high-availability paths between end stations and the backbone. For less stringent availability requirements, single-attachment concentrator trees with single attachment stations may suffice. We also discuss how the technique may be extended easily to more general heterogeneous networks including Token Ring and Ethernet.

In order to guarantee continuous delivery of a video stream in an on-demand video server environment, a collection of resources (referred to as a logical channel) are reserved in advance. To conserve server resources, multiple client requests for the same video can be batched together and served by a single channel. Increasing the window over which all requests for a particular video are batched results in larger savings in server capacity; however, it also increases the reneging probability of a client. A complication introduced by batching is that if a batched client pauses, a new stream (which may not be immediately available) needs to be started when the client resumes. To provide short response time to resume requests, some channels are set aside and are referred to as contingency channels. To further improve resource utilization, even when a nonbatched client pauses, the channel is released and reacquired upon resume. In this paper, we first develop an analytical model that predicts the reneging probability and expected resume delay, and then use this model to optimally allocate channels for batching, on-demand playback, and contingency. The effectiveness of the proposed policy over a scheme with no contingency channels and no batching is also demonstrated.

An approximation technique is presented to evaluate the dependability of computer networks. This technique, based on the most likely paths to failure, is simple and practical. It may easily be applied by a network designer in evaluating and comparing different network configurations. The approximation technique is applied to a variety of FDDI network configurations. The effect of certain network parameters on the network availability are examined. From these results the authors conclude that, in order to guarantee high availability, an FDDI network backbone should be interconnected using dual attachment concentrators. Furthermore, dual-homing configurations are required for high availability paths between end-stations and the backbone. For less stringent availability requirements, single attachment concentrator trees with single attachment stations may suffice.>

In an on-demand video server environment, clients make requests for movies to a centralized video server. Due to the stringent response time requirements, continuous delivery of a video stream to the client has to be guaranteed by reserving sufficient resources required to deliver a stream. Hence there is a hard limit on the number of streams that can be simultaneously delivered by a server. The server can satisfy multiple requests for the same movie using a single disk I/O stream by sending the same data pages to multiple clients (using the multicast facility if present in the system). This can be achieved by batching requests for the same movie that arrive within a short duration of time. In this paper, we consider various policies for selecting the movie to be multicast. The choice of a policy depends very much on the customer waiting time tolerance before reneging. We show that an FCFS policy that schedules the movie with the longest outstanding request can perform better than the MQL policy that chooses the movie with the maximum number of outstanding requests. Additionally, if the user behavior can be influenced by guaranteeing maximum waiting time then it may be beneficial to pre-allocate a fixed number of streams for popular movies. Finally, we demonstrate using empirical distribution for movie requests, that a substantial reduction (of the order of 60%) in required server capacity can be achieved by batching.

The authors present a unified framework for simulating Markovian models of highly dependable systems. It is shown that a variance reduction technique called importance sampling can be used to speed up the simulation by many orders of magnitude over standard simulation. This technique can be combined very effectively with regenerative simulation to estimate measures such as steady-state availability and mean time to failure. Moveover, it can be combined with conditional Monte Carlo methods to quickly estimate transient measures such as reliability, expected interval availability, and the distribution of interval availability. The authors show the effectiveness of these methods by using them to simulate large dependability models. They discuss how these methods can be implemented in a software package to compute both transient and steady-state measures simultaneously from the same sample run.>