System Modeling and Analysis

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