For courses in Performance Analysis and Design of Communication Networks (PC) offered in departments of Electrical and Computer Engineering. Also appropriate for courses in Systems Engineering and Operations Research.   Kobayashi and Mark present the most up-to-date analytical models, simulation techniques, and computational algorithms useful for performance evaluation of complex systems – including computer systems, communication networks, transportation systems, and manufacturing systems. Broader in scope than other texts, this book provides more in-depth coverage of topics such as computational algorithms and approximations. It appeals to students with a background or interest in a wide range of areas, including systems analysis or telecommunication networks.

Table of Contents:
1 Introduction 1 1.1 Role of Modeling and Analysis . . . . . . . . . . . . . . . . . . . . . 1 1.2 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Modeling Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Examples of Performance Modeling . . . . . . . . . . . . . . . . . . . 16 1.5 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 38 I Basic Queueing and Loss Models 39 2 Basic Queueing Models 40 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2 Little’s Formula and Its Generalization . . . . . . . . . . . . . . . . . 46 2.3 Birth-and-Death Processes . . . . . . . . . . . . . . . . . . . . . . . . 52 2.4 Birth-and-Death Queueing Models . . . . . . . . . . . . . . . . . . . 68 2.5 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 93 3 Basic Loss Models 95 3.1 Erlang Loss Model: M/M/m(0) or M/M/m/m . . . . . . . . . . . 95 3.2 Engset Loss Model: M(K)/M/m(0) or M/M/m/m/K . . . . . . . 103 3.3 Insensitivity and Generalization of Loss Models . . . . . . . . . . . . 111 3.4 Application Example: Blocking Analysis of Cellular Communication Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 3.5 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 123 4 Non-Markovian Queues 124 4.1 Renewal Process and Residual Life . . . . . . . . . . . . . . . . . . . 124 4.2 Representations of General Distributions . . . . . . . . . . . . . . . . 129 4.3 M/G/1 Queueing Model . . . . . . . . . . . . . . . . . . . . . . . . . 139 4.4 G/M/1 Queueing Model . . . . . . . . . . . . . . . . . . . . . . . . . 159 4.5 G/G/1 Queue and Waiting Time Distribution . . . . . . . . . . . . . 169 4.6 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 175 5 Quasi-Reversibility and Queues with Product-Form Solutions 177 5.1 Markov Processes and Markov Chains . . . . . . . . . . . . . . . . . 177 5.2 Departure Processes, Reversibility and Quasi-Reversibility . . . . . . 188 5.3 M/G/1 Queueing Model . . . . . . . . . . . . . . . . . . . . . . . . 208 5.4 M/G/1 with Processor Sharing . . . . . . . . . . . . . . . . . . . . . 213 5.5 M/G/1 with LCFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 5.6 M/G/1 with LCFS-PR . . . . . . . . . . . . . . . . . . . . . . . . . . 220 5.7 Multiple Customer Classes and Quasi-Reversible Stations . . . . . . 221 5.8 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 233 II Queueing and Loss Networks 235 6 Queueing Networks 236 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 6.2 Jackson Networks: Queueing Networks with Exponential Servers . . 238 6.3 Networks with Quasi-Reversible Stations and Multiple Classes of Customers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 6.4 Higher-Order Markov Routing . . . . . . . . . . . . . . . . . . . . . . 287 6.5 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 295 7 Loss Networks and Generalized Loss Models 297 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 7.2 Generalized Loss Stations . . . . . . . . . . . . . . . . . . . . . . . . 298 7.3 Loss Networks with Fixed Routing . . . . . . . . . . . . . . . . . . . 310 7.4 Queueing-Loss Networks . . . . . . . . . . . . . . . . . . . . . . . . . 334 7.5 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 336 8 Computational Algorithms for Product-Form Networks 338 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 8.2 Computational Algorithms for Queueing Networks . . . . . . . . . . 338 8.3 Parametric Decomposition of a Queueing Network . . . . . . . . . . 354 8.4 Computational Algorithms for Loss Networks . . . . . . . . . . . . . 356 8.5 Reduced Load Approximation of a Loss Network . . . . . . . . . . . 376 8.6 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 379 III Advanced Queueing Models 383 9 Conservation Laws, Priority Queues, and Polling Models 384 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 9.2 Work-Conserving Queue Disciplines and Conservation Laws . . . . . 384 9.3 M/G/1 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . 391 9.4 M/G/1 with Server Vacations and Polling Models . . . . . . . . . . 397 9.5 Rate Conservation Law (RCL) . . . . . . . . . . . . . . . . . . . . . 405 9.6 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 409 10 Phase-Type Process and Matrix Geometric Method 411 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 10.2 Phase-Type (PH) Distribution . . . . . . . . . . . . . . . . . . . . . 412 10.3 Phase-Type (PH) Renewal Process . . . . . . . . . . . . . . . . . . . 418 10.4 PH Renewal Service Process . . . . . . . . . . . . . . . . . . . . . . . 426 10.5 PH/PH/1 Queue and Quasi-Birth-and-Death (QBD) Process . . . . 428 10.6 Stationary Distribution of QBD and Performance Measures . . . . . 432 10.7 Algorithms for the Rate Matrix R . . . . . . . . . . . . . . . . . . . 437 10.8 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 439 11 Discrete-Time Queues 442 11.1 Geo/G/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442 11.2 Geo/Geo/1: Discrete-Time M/M/1 . . . . . . . . . . . . . . . . . . . 450 11.3 Discrete-Time M/G/1 . . . . . . . . . . . . . . . . . . . . . . . . . 454 11.4 Discrete-Time G/G/1 System . . . . . . . . . . . . . . . . . . . . . . 455 11.5 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 457 12 Traffic Modeling 458 12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458 12.2 Second-order Properties of Arrival Processes . . . . . . . . . . . . . . 459 12.3 Markovian Traffic Models . . . . . . . . . . . . . . . . . . . . . . . . 467 12.4 Long-Range Dependent (LRD) Traffic Models . . . . . . . . . . . . . 480 12.5 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 492 13 Fluid Models 494 13.1 Fluid Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 13.2 Markov Fluid Model of Statistical Multiplexer . . . . . . . . . . . . . 495 13.3 Two Limiting Cases: Buffer Overflows and Infinite Sources . . . . . 509 13.4 Markov Fluid Model with Multiple Types of Sources . . . . . . . . . 513 13.5 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 517 14 Approximation and Bounding Techniques 519 14.1 Inequalities and Bounds . . . . . . . . . . . . . . . . . . . . . . . . . 519 14.2 Exponential Bounds on G/G/1 Waiting Time Distribution . . . . . . 527 14.3 Bounds for Mean Waiting Time in G/G/1 . . . . . . . . . . . . . . . 540 14.4 Bounds for Mean Waiting Time in G/G/m . . . . . . . . . . . . . . 542 14.5 Heavy Traffic Approximation for G/G/1 Queue . . . . . . . . . . . . 544 14.6 Diffusion Process Approximations for G/G/1 Queue . . . . . . . . . 546 14.7 Diffusion Approximation of a Queueing Network . . . . . . . . . . . 560 14.8 Bounds and Approximations for Bandwidth Allocation . . . . . . . . 566 14.9 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 577 15 Time-Dependent Solutions of Queues 579 15.1 Time-Dependent Solution for M/G/1 . . . . . . . . . . . . . . . . . 579 15.2 Time-Dependent Solution of a Markov Process Model . . . . . . . . 581 15.3 Eigenvectors of the BD Process . . . . . . . . . . . . . . . . . . . . . 587 15.4 Generating Function Method . . . . . . . . . . . . . . . . . . . . . . 594 15.5 Uniformization of Continuous Time Markov Chain . . . . . . . . . . 610 15.6 Time-Dependent Solution of a Fluid Flow Model . . . . . . . . . . . 616 15.7 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 621 IV Simulation Modeling and Analysis 623 16 Formulation and Implementation of Simulation Models 624 16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624 16.2 Self-Driven Simulation vs. Trace-Driven Simulation . . . . . . . . . . 626 16.3 Formulation of Simulation Models . . . . . . . . . . . . . . . . . . . 628 16.4 Implementation of Simulators . . . . . . . . . . . . . . . . . . . . . . 634 16.5 Techniques for Generating Random Variables . . . . . . . . . . . . . 641 16.6 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663 16.7 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 685 17 Simulation Experiments and Statistical Data Analysis 690 17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690 17.2 Experiments and Statistical Inference . . . . . . . . . . . . . . . . . 690 17.3 Analyzing a Simulation Run . . . . . . . . . . . . . . . . . . . . . . . 695 17.4 Efficient Statistical Simulation . . . . . . . . . . . . . . . . . . . . . 708 17.5 Fast Simulation of Rare Events . . . . . . . . . . . . . . . . . . . . . 714 17.6 Discussion and Further Reading . . . . . . . . . . . . . . . . . . . . . 729 A Number Theory 731 Bibliography 737