System Modeling and Analysis: Foundations of System Performance Evaluation

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