Perturbation analysis (PA) of discrete event dynamic systems (DEDS) enables parameter sensitivities of DEDS to be obtained by observing a single sample path of the system. A simple GI/G/1 system is used to give an introduction to PA and illustrate the basic theoretical issues involved in this technique. The application of PA to networks of queues is covered briefly, and then some of the recent extensions to PA are discussed. It is shown that many interesting open questions remain for PA, and areas for research are indicated.>

A rigorous extension of the recent perturbation analysis approach to more general discrete event systems is given. First, a general class of systems and performance measures is defined, and some basic reprsentational and linearity properties are derived. Next a sample gradient of performance with respect to a parameter of the system is defined. Then, for certain parameters of such systems, an infinitesimal perturbation analysis algorithm is derived. It is proved that this algorithm gives exact values for the sample gradients of performance with respect to the parameters, by observing only one sample path of the DEDS. (However, the sample gradient may or may not be a good estimate of the gradient of the performance measure; this point is elaborated in the body of the paper.) The computational complexity of this algorithm is bound to be linear in the number of events. These results offer the potential for very efficient calculation of the gradients—a fact that can be used for design/operation of computer systems, communication networks, manufacturing systems, and many other real-world systems, particularly since restrictive assumptions (e.g., exponential distributions) are not required of the system.

Perturbation Analysis (P/A) of Discrete Event Systems is a technique that enables parameter sensitivities to be determined while observing a single experiment on the system. In the context of automated manufacturing systems, P/A enables system managers to obtain answers to many "what-if" questions about their system just by observing its current operation. Thus, for a Flexible Manufacturing System (FMS), the FMS manager could obtain estimates of the effects of adding pallets/fixtures, adding carts or AGVs, changing machine cycle times, and so on, simply by observing the current FMS operations and applying the P/A algorithms to these observations. An over view of the P/A approach, along with a literature survey and discussion of the benefits of P/A over other techniques, is given in Ho et al. [1] Application to FMS, and some related implementation issues, are discussed by Suri and Dille [2]. Recently there have been many theoretical results on the consistency and convergence of P/A: an example is Suri and Zazanis [3]. A bibliography of such results can he found in [1] and [3]. One of the advantages of the P/A approach versus other analysis techniques is that it reduces the modelling assumptions, in the sense that it operates on actual data obtained from observing a system. There are two main steps involved in applying P/A: i) perturbation generation, which relates the change in a parameter to changes in "neighboring" events, and ii) perturbation propagation which relates the effects of perturbations in one event to (possibly) all other events in the system. In many cases, both these steps are determined completely by the data being observed. In some cases however, the perturbation generation step requires an assumption of the probability distribution for an observed random variable. For example, suppose a parameter of a machine is its mean time to repair (MTTR). Now suppose we are interested in knowing, what would be the effect of improving the efficiency of our repair team. so that MTTR is reduced by 10 minutes? In order for P/A to answer this, we need to know more about the relation between the parameter MTTR and the actual (observed) repair times. Thus, one of the criticisms of P/A has been that while it reduces some modelling assumptions, it still requires assuming many probability distributions. This criticism, it turns out, is not entirely fair. First, we can show that for many practical cases, very little needs to be assumed about the distributions mentioned. Second, for a simple system which is analytically tractable, namely the M/G/1 queue, we can derive analytic bounds on the errors introduced even when incorrect assumptions are made. Finally, for more complex systems, we show experimental results indicating again that errors in such assumptions have small effects on the P/A estimates. All these results can be found in [4] which is being submitted for journal publication, The sum of these results is that, when used in practical systems, the P/A technique is going to be robust with respect to the assumptions made. Intuitively, this can be explained quite simply: The propagation part of the algorithm depends only on the observations, and also, the errors introduced at the generation stage tend to be small. This is but one more argument for promoting P/A as a practical analysis technique for actual automated manufacturing systems.

We introduce the concept of approximate disaggregation which enables us to replace a station by a subnetwork, i.e. a set of stations, such that the performance of the derived network is close to the performance of the initial network. We use this concept to disaggregate any multiple-server station into a set single-server stations. Using two different disaggregations, we are able to bound the performance of the initial network by the performance of a “lower” and an “upper” network each consisting of single-server stations, whose performance can in turn be bounded by the Balanced Job Bounds (or other known bounds). Several examples show the useful information provided by these bounds at a very low cost: for Κ stations and Ν customers, the computational complexity here is Ο(Κ) which is significantly less than the Ο(ΚΝ2) operations required for exact solution. Indeed, despite the multiple server stations, the computational complexity of our bounds is the same as that of Balanced Job Bounds.

A new performance model for dynamic locking is proposed. It is based on a flow diagram and uses only the steady state average values of the variables. It is general enough to handle nonuniform access, shared locks, static locking, multiple transaction classes, and transactions of indeterminate length. The analysis is restricted to the case in which all conflicts are resolved by restarts. It has been shown elsewhere that, under certain conditions, this pure restart policy is as good as, if not better than, a policy that uses both blocking and restarts. The analysis is straightforward, and the computational complexity of the solution, given some nonrestrictive approximations, does not depend on the input parameters. The solution is also well defined and well behaved. The model's predictions agree well with simulation results. The model shows that data contention can cause the throughput to thrash, and gives a limit on the workload that will prevent this. It also shows that systems with a particular kind of nonuniform access and systems in which transactions share locks are equivalent to systems in which there is uniform access and only exclusive locking. Static locking has higher throughput, but longer response time, than dynamic locking. Replacing updates by queries in a multiprogramming mix may degrade performance if the queries are longer than the updates.

Analytic models based on closed queuing networks (CQNS) are widely used for performance prediction in practical systems. In using such models, there is always a prediction error, that is, a difference between the predicted performance and the actual outcome. This prediction error is due both to modeling errors and estimation errors, the latter being the difference between the estimated values of the CQN parameters and the actual outcomes. This paper considers the second class of errors; in particular, it studies the effect of small estimation errors and provides bounds on prediction errors based on bounds on estimation errors. Estimation errors may be divided into two types: (1) the difference between the estimated value and the average value of the outcome, and (2) the deviation of the actual value from its average. The analysis first studies the sum of both types of errors, then the second type alone. The results are illustrated with three examples.

An analytic model is used to study the performance of dynamic locking. The analysis uses only the steady-state average values of the variables. The solution to the model is given by a cubic, which has exactly one valid root for the range of parametric values that is of interest. The model's predictions agree well with simulation results for transactions that require up to twenty locks. The model separates data contention from resource contention, thus facilitating an analysis of their separate effects and their interaction. It shows that systems with a particular form of nonuniform access, or with shared locks, are equivalent to systems with uniform access and only exclusive locks. Blocking due to conflicts is found to impose an upper bound on transaction throughput; this fact leads to a rule of thumb on how much data contention should be permitted in a system. Throughput can exceed this bound if a transaction is restarted whenever it encounters a conflict, provided restart costs and resource contention are low. It can also be exceeded by making transactions predeclare their locks. Raising the multiprogramming level to increase throughput also raises the number of restarts per completion. Transactions should minimize their lock requests, because data contention is proportional to the square of the number of requests. The choice of how much data to lock at a time depends on which part of a general granularity curve the system sees.

An earlier paper introduced a simple performance model for studying the behaviour of locking. That paper treats a highly simplified form of locking, called the no waiting case, in which transactions restart when they request locks that are already held by others. This analysis is now extended to the more realistic waiting case, in which transactions are allowed to wait for conflicting locks, and restart only if there is a deadlock. The analysis begins with a system that has uniform access and exclusive locks only. The model's predictions for this base system agree well with simulation results. Next, a system with nonuniform access and another with shareable locks are each shown to be reducible to the base system. A comparison of the waiting and no waiting cases yields a surprising result: the throughput for the no waiting case is often better than for the waiting case, and never much worse.

Many different algorithms have been proposed for database concurrency control, and many more can be synthesized by combining locking and timestamping. The correctness of these algorithms is already well understood, their performance is not. We need a model to help us understand, compare and control the behavior of locking and timestamping we present here a model which we hope will eventually play such a role, but which we believe is simple to understand and use.

This paper is based on a recent technique called perturbation analysis of discrete event systems. The aims of the paper are two-fold. The first, is to bring this technique, which is still relatively new, to the attention of a wider audience, since the method is particularly relevant to practical systems optimization. The second, is to develop two new methods, the phantom customer method and the marked customer method, as extensions of the perturbation analysis approach. These methods enable efficient and accurate optimization of closed queueing networks with blocking and general service-time distributions. Useful practical applications of these methods would be for optimization of performance of computer systems, communication networks, and automated manufacturing complexes. The accuracy of the methods is illustrated by several numerical examples.

Analyuc models of queuing networks have been observed to give good results for systems which do not conform to the assumptions of classical queuing theory This has been explained to some extent by the recently proposed concept of operational analysis However, the use of operational analysis for prediction of system performance revolves a restrictive assumption, that of homogeneous service tnnes (HST), and practical systems often deviate from HST behavior.It is shown that the main system performance measures are surpnsmgly insensitive to violations of the HST assumption.This further explains the robustness of analyacal models for predicting performance of queuing networks Some issues regarding the operational versus stochasuc approaches are resolved, since it is clatmed that the present analysis, which is carried out m the operational framework, cannot be meaningfully carried out m the stochastic framework.