Systems with multiserver jobs, inspired by modern datacenters, present a challenge in terms of the analysis of their performance and, in particular, the determination of their processing capacity as some servers may remain idle even though there are jobs queued for service. We consider a generalization of the multiserver jobs model to a resource of not necessarily integer quantity and jobs of different classes requiring arbitrary fractions of that resource. We present a simple approach to the analysis of such a system in steady state. Our approach relies on a suitably chosen state description and the use of conditional probabilities. The limiting values of these conditional probabilities allow us to determine the asymptotic maximum job processing capacity without having to obtain the full solution for the system.

Current architecture of many computer systems relies on dynamic allocation of a pool of resources according to workload conditions to meet specific performance objectives while minimizing cost (e.g., energy or billing). In such systems, different levels of operation may be defined, and switching between operating levels occurs at certain thresholds of system congestion. To avoid rapid oscillations between levels of service, “hysteresis” is introduced by using different thresholds for increasing and decreasing workload levels, respectively. We propose a model of such systems with general arrivals, arbitrary number of servers and operating levels where each higher operating level may correspond to an arbitrary number of additional servers and soft (i.e., non-deterministic) thresholds to account for “inertia” in switching between operating levels. In our model, request service times are assumed to be memoryless and server processing rates may be a function of the current operating level and of the number of requests (users) in the system. Additionally, we allow for delays in the activation of additional operating levels. We use simple mathematics to obtain a semi-numerical solution of our model. We illustrate the versatility of our model using several case study examples inspired by features of real systems. In particular, we explore optimal thresholds as a tradeoff between performance and energy consumption.

In this paper we consider the problem of combining calibrated performance models of system components in order to predict overall system performance. We focus on open workload system models, in which, under certain conditions, obtaining and validating the overall system performance measures can be a simple application of Little's law. We discuss the conditions of applicability of such a simple validation methodology, including examples of successful application, as well as examples where this approach fails. Additionally, we propose to analyze the deviations between the model predictions and system measurements, so as to decide if they correspond to "measurement noise" or if an important system component has not been correctly represented. This approach can be used as an aid in the design of validated system performance models.

Cloud providers need to size their systems to determine the right amount of resources to allocate as a function of customer's needs so as to meet their SLAs (Service Level Agreement), while at the same time minimizing their costs and energy use. Queueing theory based tools are a natural choice when dealing with performance aspects of the QoS (Quality of Service) part of the SLA and forecasting resource utilization. The characteristics of a cloud center lead to a queueing system with multiple servers (nodes) in which there is potentially a very large number of servers and both the arrival and service process can exhibit high variability. We propose to use a G/G/c-like model to represent a cloud system and assess expected performance indices. Given the potentially high number of servers in a cloud system, we present an efficient, fast and easy-to-implement approximate solution. We have extensively validated our approximation against discrete-event simulation for several QoS performance metrics such as task response time and blocking probability with excellent results. We apply our approach to examples of system sizing and our examples clearly demonstrate the importance of taking into account the variability of the tasks arrivals and thus expose the risk of under- or over-provisioning if one relies on a model with Poisson assumptions.

A large number of real-life systems can be viewed as instances of the classical M/G/c/N queue. The exact analytical solution of this queueing model is not known, and a frequently-used approach is to replace the general service time distribution by a phase-type distribution. The advantage of this approach is that the resulting M/Ph/c/N queue can be described by familiar balance equations. The downside is that the size of the resulting state space suffers from the "dimensionality curse", i.e., exhibits combinatorial growth as the number of servers and/or phases increases. To circumvent this complexity issue, we propose to use, instead of the classical full state description, a reduced state description in which the state of only one server is represented explicitly, while the other servers are accounted for through their rate of completions. The accuracy of the resulting approximation is generally good and, moreover, tends to improve as the number of servers in the system increases. Its computational complexity in terms of the number of states grows only linearly in the number of servers and phases, thus making the numerical solution of such queues with hundreds of servers and a reasonable number of phases computationally affordable.

We propose a simple approximation to assess the steady-state probabilities of the number of customers in Ph/Ph/1 and Ph/Ph/1/N queues, as well as probabilities found on arrival, including the probability of buffer overflow for the Ph/Ph/1/N queue. The phase-type distributions considered are assumed to be acyclic. Our method involves iteration between solutions of an M/Ph/1 queue with state-dependent arrival rate and a Ph/M/1 queue with state-dependent service rate. We solve these queues using simple and efficient recurrences. By iterating between these two simpler models our approximation divides the state space, and is thus able to easily handle phase-type distributions with large numbers of stages (which might cause problems for classical numerical solutions). The proposed method converges typically within a few tens of iterations, and is asymptotically exact for queues with unrestricted queueing room. Its overall accuracy is good: generally within a few percent of the exact values, except when both the inter-arrival and the service time distributions exhibit low variability. In the latter case, especially under moderate loads, the use of our method is not recommended.

In this paper, we explore the impact of reference node, or "landmark", placement on the accuracy of the coordinate systems built using topology-based localization techniques. Such techniques employ landmarks to which each node computes its hop-count distance. A node's coordinates is given by the hop-count distance to all landmarks. To our knowledge, our paper is the first to study the impact of landmark placement on the accuracy of the resulting coordinate system. We show that placing landmarks on the periphery of the topology yields more accurate coordinate systems when compared to placing landmarks in the interior of the topology. Nevertheless, our simulation results also show that, in general, if enough landmarks are used, random landmark placement yields comparative performance to placing landmarks on the boundary randomly or equally spaced. This is an important result since boundary placement (especially at equal distances) may turn out to be infeasible and/or prohibitively expensive (in terms of power consumption as well as processing and communication overhead). This is also the first study to consider not only uniform, synthetic topologies, but also, non-uniform topologies resembling more concrete deployments.

We propose a novel approach to the decomposition of large probabilistic models. The goal of our method is to avoid the evaluation of the subnetworks obtained by decomposition for all values of the state description vector, as would be necessary with a standard aggregation and decomposition approach. Instead, we propose a fixed-point iteration that requires the evaluation of the subnetwork for a subset of the population levels only. Outside the evaluated points, simple upper and lower linear approximations are used resulting in bounds for overall system performance measures. We concentrate the evaluation of the subnetworks in the regions where the difference between the lower and upper bound is most likely to impact the accuracy of the result.

This note is devoted to a few remarks on the performance evaluation of systems with service interruptions such as priority queues for lower priority customers, systems subject to breakdowns, etc. Recent work on priority queues has shown that a popular approximation method, the “reduced occupancy approximation”, can be exceedingly inaccurate for a range of parameter values. We identify a cause of inaccuracy and, hence, propose a simple correction that provides a substantial improvement in the results. Using the example of a simple model with service interruptions, we show also that conditional probabilities can be of value in deriving recurrent solutions to some problems.

Queueing network models of multiprogramming systems with memory constraints and multiple classes of jobs are important in representing large commercial computer systems. Typically, an exact analytical solution of such models is unavailable, and, given the size of their state space, the solution of models of this type is approached through simulation and/or approximation techniques. Recently, a computationally efficient iterative technique has been proposed by Brandwajn, Lazowska and Zahorjan for models of systems in which each job is subject to a separate memory constraint, i.e., has its own memory domain. In some important applications, it is not unusual, however, to have several jobs of different classes share a single memory “domain” (e.g., IBM's Information Management System). We present a simple approximate solution to the shared domain problem. The approach is inspired by the recently proposed technique which is complemented by a few approximations to preserve the conceptual simplicity and computational efficiency of this technique. The accuracy of the results is generally in fair agreement with simulation.

The recently introduced Extended Architecture (XA) of large IBM computer systems includes, in the disk I/O area, the ability for an access to be resumed and completed on a path different from the one on which it has been initiated. The expected disk performance improvement due to this feature - known as Dynamic Path Reconnection - is investigated in this note.

A throughput-driven approach to the performance analysis of direct access storage devices (DASD's), i.e., disks, is presented for a model of a block-multiplexor channel system with multiple transfer paths. The approach relies on a step-wise analysis of shared components within the data transfer path: head of string, control unit, channel, referred to as blocking points. In order to derive the service time of an I/O request, each blocking point is analyzed separately, using essentially a classical loss-system model. The advantages of the method are its relative simplicity and applicability to a large number of configurations. Transient and boundary effects, including the miss probability on second and subsequent reconnection attempts, and the device reconnection window (lead time), are also discussed. The inclusion of the approach in a larger system model, as well as its relationship with previous work on DASD analysis is considered. Numerical results illustrate the accuracy of the method.

This paper deals with the following mechanism for controlling the multiprogramming set in a demand paging system: processes are dynamically divided into several categories according to the number of page faults generated during their residence in main memory. A process is admitted into the multiprogramming set only if there is enough space free in the main memory to contain the number of pages corresponding to the current category of the process. Using a queueing network model of an interactive system with such a control mechanism we study the effectivenesss of the control considered, and, more particularly, its ability to partition the memory space according to the locality of processes.

ARCADE is a research project in computer architecture. We first discuss its motivations and goals, wich are primarily the design of a dynamically adaptive system, and the use of performance evaluation methods as a design tool. The resulting system is intended to serve as a support for education in computer architecture and operating systems. Then, we present the overall structure of the system, and finally, we consider in more detail hardware tools that will be provided for the dynamic adaptation to varying load conditions.

This paper presents a queueing model of a multiprogrammed computer system with virtual memory. Two system organizations are considered: (i) all the processes present in the system share primary storage; (ii) processes which have generated a file request (slow I/O) lose their memory space until the I/O is completed. Our model assumes balanced memory allocation among processes, and accounts for the memory sharing effect through the use of lifetime functions. The model explicitly takes into account the fact that, if a written-onto page is to be replaced at the moment of a page fault, it first has to be saved in the secondary memory. An approximate closed form solution is obtained by using an equivalence and decomposition approach. A procedure for evaluating the accuracy of the approximation is presented. The numerical examples illustrate the influence of the system and program behavior parameters taken into account in our model.