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
