Computer System Performance Modeling in Perspective

The following sections are included:

• Preface

• Contents

Please refer to full text.

Queuing network models have been applied to the analysis of computer system performance since the early 1970s. Shortly after their introduction, a number of major extensions to the underlying mathematical theory were developed by a worldwide community of researchers. Among the most important of these new extensions was the ability to represent priority scheduling at CPUs. Sevcik's shadow server approximation, which appeared in 1977, provided the first computationally viable technique for analyzing the effect of CPU priority scheduling within a queuing network model. The shadow server approximation is based on a powerful and intuitively appealing heuristic. It provided a solution to an important open problem and contributed substantially to the practical success of commercial modeling tools based on the theory of queuing networks.

Kenneth Sevcik's pioneering result in stochastic scheduling theory seems to be the first dynamic allocation index policy for problems of bandit type. The Sevcik rank was the precursor of the much celebrated Gittins index that appeared about a year later. We present the main result, put it in the context of the research on these problems in the late sixties to mid seventies, and give a number of illustrations extending those of Sevcik.

Operational analysis is a branch of queueing network models. It derives the basic equations for calculating throughput, response time, and congestion from fully operational assumptions. These assumptions, applicable in any finite observation period, require that all variables be directly measurable and all modeling assumptions be directly testable. In this framework, the steady-state stochastic limit theorems become operational laws that hold in every observation period. The resulting model applies in many cases where stochastic models do not. Operational analysis was created during the late 1970s to explain why Markovian queueing network models worked so well for real computer and network systems, even though the systems violated almost all the assumptions of the Markovian model. Operational analysis considerably simplifies the theory needed to deal with practical queueing systems and gives an indisputable edge to teaching, understanding, and communicating about queueing networks.

This paper discusses the function approximation properties of the “Gelenbe” random neural network (GNN).^5,6,9 We use two extensions of the basic model: the bipolar GNN (BGNN)⁷ and the clamped GNN (CGNN). We limit the networks to being feedforward and consider the case where the number of hidden layers does not exceed the number of input layers. With these constraints we show that the feedforward CGNN and the BGNN with s hidden layers (total of s + 2 layers) can uniformly approximate continuous functions of s variables.

The following sections are included:

• Introduction

• The Current Status of Model Building

• System Multilevel Description

• The Multilevel Model Building Method

• Comparison with Existing Approaches

• Conclusions

• Acknowledgment

• References

Network simulation is a widely used tool in wireless network research. However, this widespread use of simulation has also resulted in the creation of new problems. In this study, we consider two of these problems and investigate their impact on the study of network behavior.

The first problem arises due to the large number of parameters typically found in a simulation model. Simulation models abound in the wireless domain and the parameters vary from model to model. Moreover, there is no consensus on values for these parameters across models, even on common parameters. This makes the task of analyzing simulation results complex. We propose a framework to address this issue. Our framework is based on reducing the large parameter space into a smaller set of a few, essential parameters. We also propose a new metric, steady state utilization, to capture the inherent capacity of a network and show how this can be used in the comparison of results across models.

The second problem arises due to the assumption of homogeneity in various aspects of modeling and simulation. Homogeneity is often resorted to in order to simplify the task of implementing a simulation and interpreting the subsequent results. We show that this can often hide subtle details that affect the network performance and can result in erroneous interpretations if the analysis of results is not done properly.

Asymmetric links are common in wireless networks for a variety of physical, logical, operational, and legal considerations. An asymmetric link supports unidirectional communication between a pair of mobile stations and requires a set of relay stations for the transmission of packets in the other direction. We evaluate m-limited forwarding, a technique to disseminate information in location- and power-aware networks with symmetric and/or asymmetric links. Then we introduce a network and a MAC layer protocol for wireless networks with asymmetric links. The network layer protocol takes advantage of the location information to reduce the number of retransmissions and thus reduces the power consumption via the m-limited forwarding technique. The MAC layer protocol requires fewer nodes to maintain silence during a transmission than the protocols proposed in Refs. 1 and 2. We present a set of metrics characterizing the ability of a medium access control protocol to silence nodes which can cause collisions.

Distributed application systems are often implemented as layers of software services. The services provide functions, which we refer to as service entries, that can have significantly different demands on resources such as CPUs and on requests for service from other service entries. Significantly different demands within service entries lead to high service time variation for a service. Such services are typically deployed within application server containers each having some bound on its level of concurrency refered to as its maximum threading level. We have modeled such systems using a layered queueing network approach. Each queue represents a first-come-first-served multi-threaded server with multiple entries that may have high service time variation. This chapter describes a simple and intuitive residence time expression for such queues. Simulation results show that the technique is both fast and accurate when compared with other techniques from the literature.

Fast response times and the satisfaction of response time quantile targets are important performance criteria for almost all transaction processing, computer-communication and other operational systems. However, response time quantiles tend to be difficult to obtain in stochastic models, even when the mean value of the response time has a relatively simple mathematical expression. Expressions have been obtained for the Laplace transform of the probability density function of sojourn times in many queueing models, including some complex single queues and networks of simple queues. These can sometimes be inverted analytically, giving an explicit expression for the density as a function of time, but more often numerical inversion is necessary. More generally, interesting sojourn times can be expressed in terms of passage times between states in continuous time Markov and semi-Markov chains. Quantiles for these can be computed in principle but can require extensive computational resources, both in terms of processing time and memory. Consequently, until recently, only trivial problems could be solved by this direct method. With recent technological advances, including the widespread use of clusters of workstations and limited availability of parallel supercomputers, very large Markov and semi-Markov chains can be solved directly for passage time densities, allowing many realistic systems to be investigated. This chapter reviews the various approaches taken to compute sojourn time quantiles in systems ranging from simple queues to arbitrary semi-Markov chains, by the authors and others, over the past twenty years and more.

The following sections are included:

• Introduction

• Poisson Approximation for the Number of Failed Routers

• Asymptotics of Lost Bandwidth

• References

In an Optical Burst Switched (OBS) network, depending on the maximum burst size, the minimum link lengths and the data rate, bursts may span two, three and even more links simultaneously as they travel from their source to their destination. Bursts dynamically move from occupying one set of links to the next by releasing a wavelength on one link and occupying a wavelength on the next link along their route. This behavior greatly differs from the widely studied packet-switched and circuit-switched networks and thus it requires the development of new performance models. In this chapter, we consider bursts, which are assumed to be long enough to occupy wavelengths on two successive links simultaneously but our analysis can be extended for bursts that hold any number of links. The burst arrival process is modeled by a two-state Markov process, called IDLE/ON, which accurately captures the burst transmission at the edge of the OBS network. We present a new queueing model which captures the dynamic simultaneous link possession and allows us to evaluate the burst loss probabilities of a path in an OBS network. Decomposition and state-dependent arrivals are used in order to analyze the queueing network. The approximate results were verified by simulation for a variety of input parameters and the approximation algorithm was found to have a good accuracy.

We derive an exact matrix-analytic analysis of a general stochastic model of parallel processing systems under dynamic spacesharing, which yields a closed-form solution for certain model instances. An analysis of a general nearly completely decomposable model of parallel program memory reference behavior is also derived, which provides measures of the distribution of the memory overhead incurred by a parallel program as a function of its server allocation. These theoretical results can be exploited to investigate the design and performance space of parallel processing systems with respect to fundamental tradeoffs related to the server and memory allocation strategies and their interactions.

This chapter addresses issues of task clustering — the coalition of several tasks into single coarser grain tasks called task clusters — and task cluster scheduling on distributed processors. It considers a special scheduling method referred to as periodic task cluster scheduling. With this method, processor queues are rearranged only at the end of predefined intervals called epochs. The objective is to find an epoch that minimizes the number of queue rearrangements, and that also results in good overall performance, and in fairness in individual job service. Simulation models are used to compare the performance of this method with other task cluster scheduling policies. Simulated results indicate that periodic task cluster scheduling is a good policy to use.