Statistical performance evaluation has assumed an increasing amount of importance as we seek to design more and more sophisticated communi cation and information processing systems. The ability to predict a pro posed system's performance without actually having to construct it is an extremely cost effective design tool. This book is meant to be a first year graduate level introduction to the field of statistical performance evaluation. As such, it covers queueing theory (chapters 1-4) and stochastic Petri networks (chapter 5). There is a short appendix at the end of the book which reviews basic probability theory. At Stony Brook, this material would be covered in the second half of a two course sequence (the first half is a computer networks course using a text such as Schwartz's Telecommunications Networks). Students seem to be encouraged to pursue the analytical material of this book if they first have some idea of the potential applications. I am grateful to B.L. Bodnar, J. Blake, J.S. Emer, M. Garrett, W. Hagen, Y.C. Jenq, M. Karol, J.F. Kurose, S.-Q. Li, A.C. Liu, J. McKenna, H.T. Mouftah and W.G. Nichols, I.Y. Wang, the IEEE and Digital Equip ment Corporation for allowing previously published material to appear in this book.
Inhalt
1 : The Queueing Paradigm.- 1.1 Introduction.- 1.2 Queueing Theory.- 1.3 Queueing Models.- 1.4 Case Study I: File Service.- 1.5 Case Study II: Multiprocessor.- 2: Single Queueing Systems.- 2.1 Introduction.- 2.2 The M/M/l Queueing System.- 2.2.1 The Poisson Process.- 2.2.2 Foundation of the Poisson Process.- 2.2.3 Poisson Distribution Mean and Variance.- 2.2.4 The Inter-Arrival Times.- 2.2.5 The Markov Property.- 2.2.6 Exponential Service Times.- 2.2.7 Foundation of the M/M/l Queueing System.- 2.2.8 Flows and Balancing.- 2.2.9 The M/M/l Queueing System in Detail.- 2.3 Little's Law.- 2.4 Reversibility and Burke's Theorem.- 2.4.1 Introduction.- 2.4.2 Reversibility.- 2.4.3 Burke's Theorem.- 2.5 The State Dependent M/M/1 Queueing System.- 2.5.1 The General Solution.- 2.5.2 Performance Measures.- 2.6 The M/M/l/N Queueing System.- 2.7 The M/M/? Oueueing System.- 2.8 The M/M/m Oueueing System.- 2.9 The M/M/m/m Oueue: A Loss System.- 2.10 The Central Server CPU Model.- 2.11 Transient Solution of the M/M/l/. Queueing System.- 2.11.1 The Technique.- 2.11.2 The Solution.- 2.11.3 Soeeding Up the Computation.- 2.12 The M/G/l Oueueins System.- 2.12.1 Introduction.- 2.12.2 Mean Number in the Queueing System.- 2.12.3 Why We Use Departure Instants.- 2.12.4 Probability Distribution.- To Look Further.- Problems.- 3: Networks of Queues.- 3.1 Introduction.- 3.2 The Product Form Solution.- 3.2.1 Introduction.- 3.2.2 Open Networks.- 3.2.2.1 The Global Balance Equation.- 3.2.2.2 The Traffic Equations.- 3.2.2.3 The Product Form Solution.- 3.2.3 Local Balance.- 3.2.4 Closed Queueing Networks.- 3.2.5 The BCMP Generalization.- 3.3 Algebraic Topological Interpretation of P.F. Solution.- 3.3.1 Introduction.- 3.3.2 A First Look at Building Blocks.- 3.3.3 Building Block Circulatory Structure.- 3.3.4 The Consistency Condition.- 3.4 Recursive Solution of Non-Product Form Networks.- 3.4.1 Introduction.- 3.4.2 Recursive Examples.- 3.4.3 Numerical Implementation of the Equations.- 3.5 Case Study I: Queueing on a Space Division Packet Switch.- 3.5.1 Introduction.- 3.5.2 Output Queueing.- 3.5.3 Input Queueing.- 3.6 Case Study II: Queueing on a Single-Buffered Banyan Network.- 3.6.1 Introduction.- 3.6.2 The Model Assumptions.- 3.6.3 The Model and Solution.- 3.7 Case Study III: DQDB Erasure Station Location.- 3.7.1 Introduction.- 3.7.2 Optimal Location of Erasure Nodes.- To Look Further.- Problems.- 4: Numerical Solution of Models.- 4.1 Introduction.- 4.2 Closed Networks: Convolution Algorithm.- 4.2.1 Lost in the State Space.- 4.2.2 Convolution Algorithm: Single Customer Class.- 4.2.3 Performance Measures from Normalization Constants.- Example 1: State Independent Servers.- Example 2: State Independent Servers.- Example 3: State Dependent Servers.- 4.3 Mean Value Analysis.- 4.3.1 State (Load) Independent Servers.- Examples of the Use of the MVA Algorithm.- Example 1: M Cyclic Queues.- Example 2: Cyclic Queueing Network Numerical Example.- 4.4 PANACEA: Approach for Large Markovian Queueing Networks.- 4.4.1 Introduction.- 4.4.2 The Product Form Solution.- 4.4.3 Conversion to Integral Representation.- 4.4.4 Performance Measures.- 4.4.5 "Normal Usage".- 4.4.6 Some Transformations.- 4.4.7 Asymptotic Expansions.- 4.4.8 The Pseudonetworks.- 4.4.9 Error Analysis.- 4.5 Discrete Time Queueing Systems.- 4.6 Simulation of Communication Networks.- 4.6.1 Introduction.- 4.6.2 The Statistical Nature of a Simulation.- 4.6.3 Sensitivity Analysis of Simulation Results.- 4.6.4 Speeding Up a Simulation.- To Look Further.- Problems.- 5: Stochastic Petri Nets.- 5.1 Introduction.- 5.2 A Bus Oriented Multiprocessor Model.- 5.3 Toroidal MPN Lattices.- 5.4 The Dining Philosophers Problem.- 5.5 A Station Oriented CSMA Protocol Model.- 5.6 The Alternating Bit Protocol.- 5.7 Conclusion.- To Look Further.- Appendix: Probability Theory Review.- References.