Product Cover Image

System Modeling and Analysis: Foundations of System Performance Evaluation, CourseSmart eTextbook

By Hisashi Kobayashi, Brian L. Mark

Published by Prentice Hall

Published Date: May 1, 2008

More Product Info

Description

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

 

Purchase Info ?

With CourseSmart eTextbooks and eResources, you save up to 60% off the price of new print textbooks, and can switch between studying online or offline to suit your needs.

Once you have purchased your eTextbooks and added them to your CourseSmart bookshelf, you can access them anytime, anywhere.

Buy Access

System Modeling and Analysis: Foundations of System Performance Evaluation, CourseSmart eTextbook
Format: Safari Book

$87.99 | ISBN-13: 978-0-13-604169-6