The Operational Analysis of Queueing Network Models* PETER J. DENNING Computer Sciences Department, Purdue Unwers~ty, West Lafayette, Indiana 47907 JEFFREY P. BUZEN BGS Systems, Inc., Box 128, Lincoln, Massachusetts 01773 Queueing network models have proved to be cost effectwe tools for analyzing modern computer systems. This tutorial paper presents the basic results using the operational approach, a framework which allows the analyst to test whether each assumption is met in a given system. The early sections describe the nature of queueing network models and their apphcations for calculating and predicting performance quantitms The basic performance quantities--such as utilizations, mean queue lengths, and mean response tunes--are defined, and operatmnal relationships among them are derwed Following this, the concept of job flow balance is introduced and used to study asymptotic throughputs and response tunes. The concepts of state transition balance, one-step behavior, and homogeneity are then used to relate the proportions of time that each system state is occupied to the parameters of job demand and to dewce charactenstms Efficmnt methods for computing basic performance quantities are also described. Finally the concept of decomposition is used to stmphfy analyses by replacing subsystems with equivalent devices. All concepts are illustrated liberally with examples Keywords and Phrases" balanced system, bottlenecks, decomposability, operational analysis, performance evaluation, performance modeling, queuelng models, queuelng networks, response tunes, saturation. CR Categorws: 8.1, 4.3 INTRODUCTION Queueing networks are used widely to an- alyze the performance of multiprogrammed computer systems. The theory dates back to the 1950s. In 1957, Jackson published an analysis of a multiple device system wherein each device contained one or more parallel servers and jobs could enter or exit the system anywhere [JACK57]. In 1963 Jackson extended his analysis to open and closed systems with local load-dependent * This work was supported in part by NSF Grant GJ-41289 at Purdue University service rates at all devices [JACK63]. In 1967, Gordon and Newell simplified the no- tational structure of these results for the special case of closed systems [GORD67]. Baskett, et al. extended the results to in- clude different queueing disciplines, multi- ple classes of jobs, and nonexponential ser- vice distributions [BASK75]. The first successful application of a net- work model to a computer system came in 1965 when Scherr used the classical ma- chine repairman model to analyze the MIT time sharing system, CTSS [SCHE67]. How- ever, the Jackson-Gordon-Newell theory PermmsIon to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copymg m by permission of the Assoclatlon for Computing Machinery. To copy otherwlse, or to republish, reqmres a fee and/or specific permission. © 1978 ACM 0010-4892/78/0900-0225 Computing Surveys, Vol. 10, No. 3, September 1978226 P. J. Denning and J. P. Buzen CONTENTS INTRODUCTION 1 THE BASIS FOR OPERATIONAL ANALYSIS Operatmnal Variables, Laws and Theorems Apphcatton Areas Prior Work m Operatmnal Analysts 2 VALIDATION AND PREDICTION 3 OPERATIONAL MEASURES OF NETWORKS Types of Networks Bamc Operatmnal Quantities 4 JOB FLOW ANALYSIS Vtslt Ratms System Response Tune Examples Bottleneck Analys~ Examples Summary 5 LOAD DEPENDENT BEHAVIOR 6 SOLVING FOR STATE OCCUPANCIES State Trap~ttmn Balance Solving the Balance Equations An Example Accuracy of the Analysm 7 COMPUTATION OF PERFORMANCE QUANTITIES Closed System with Homogeneous Service Tm~es Termmal Driven System with Homogeneous Serwce Tunes General Systems 8 DECOMPOSITON Offime Experiments Apphcatmns CONCLUSIONS ACKNOWLEDGMENTS REFERENCES lay dormant until 1971 when Buzen intro- duced the central server model and fast computational algorithms for these models [BuzE71a, BuzE71b, BUZE73]. Working independently, Moore showed that queueing network models could predict the response times on the Michigan Terminal System (MTS) to within 10% [MooR71]. Extensive validations since 1971 have veri- fied that these models reproduce observed performance quantities with remarkable accuracy [BuzE75, GIAM76, HUGH73, LII's77, ROSE78]. Good surveys are [GELE76a, KLEI75, KLEI76, and MONT75]. Many analysts have experienced puzzle- ment at the accuracy of queueing network results. The traditional approach to deriv- ing them depends on a series of assump- tions used in the theory of stochastic proc- esses: • The system is modeled by a stationary stochastic process; • Jobs are stochastically independent; • Job steps from device to device follow a Markov chain; • The system is in stochastic equilib- rium; • The service time requirements at each device conform to an exponential dis- tribution; and • The system is ergodic--i.e., long-term time averages converge to the values computed for stochastic equilibrium. The theory of queueing networks based on these assumptions is usually called "Markovian queueing network theory" [KLEI75]. The italicized words in this list of assumptions illustrate concepts that the an- alyst must understand to be able to deploy the models. Some of these concepts are difficult. Some, such as "equilibrium" or "stationarity," cannot be proved to hold by observing the system in a finite time period. In fact, most can be disproved empirically --for example, parameters change over time, jobs are dependent, device to device transitions do not follow Markov chains, systems are observable only for short pe- riods, service distributions are seldom ex- ponential. It is no wonder that many people are surprised that these models apply so well to systems which violate so many as- sumptions of the analysis! In applying or validating the results of Markovian queueing network theory, ana- lysts substitute operational (i.e., directly measured} values for stochastic parameters in the equations. The repeated successes of validations led us to investigate whether the traditional equations of Markovian queueing network theory might also be re-