Queueing networks and markov chains

Queueing Networks

and

Markov Chains

Queueing Networks

and

Markov Chains

Modeling and Performance

Evaluation with Computer

Science Applications

Gunter Belch, Stefan Greiner,

Hermann de Meer, and Kishor S. Trivedi

A Wiley-Interscience Publication

JOHN WILEY & SONS, INC.

New York / Chichester / Weinheim / Brisbane / Singapore / Toronto

Copyright  1998 by John Wiley & Sons, Inc. All rights reserved.

No part of this publication may be reproduced, stored in a retrieval system or transmitted in

any form or by any means, electronic or mechanical, including uploading, downloading,

printing, decompiling, recording or otherwise, except as permitted under Sections 107 or 108 of

the 1976 United States Copyright Act, without the prior written permission of the Publisher.

Requests to the Publisher for permission should be addressed to the Permissions Department,

John Wiley & Sons, Inc., 605 Third Avenue, New York, NY 10158-0012, (212) 850-6011, fax

(212) 850-6008, E-Mail: [email protected].

This publication is designed to provide accurate and authoritative information in regard to the

subject matter covered. It is sold with the understanding that the publisher is not engaged in

rendering professional services. If professional advice or other expert assistance is required, the

services of a competent professional person should be sought.

ISBN 0-471-20058-1.

This title is also available in print as ISBN 0-471-19366-6

For more information about Wiley products, visit our web site at www.Wiley.com.

Library of Congress Cataloging in Publication Data:

Queueing networks and Markov chains: modeling and performance

evaluation with computer science applications / Gunter Bolch ... [et

al.].

p. cm.

“A Wiley-Interscience publication.”

Includes bibliographical references and index.

ISBN 0-471-19366-6

1. Electronic digital computers — Evaluation. 2. Markov processes.

3. Queuing theory. I. Bolch, Gunter.

QA76.9.E94Q48 1998

004.20

40

01519233 — dc21 97-11959

CIP

Printed in the United States of America.

10 9 8 7 6 5 4 3 2

Contents

Preface xv

1 Introduction 1

1.1 Motivation 1

1.2 Basics of Probability and Statistics 5

1.2.1 Random Variables 5

1.2.1.1 Discrete Random Variables 5

1.2. 1.2 Continuous Random Variables 7

1.2.2 Multiple Random Variables 19

1.2.2.1 Independence 20

1.2.2.2 Conditional Probability 22

1.2.2.3 Important Relations 23

1.2.2.4 The Central Limit Theorem 24

1.2.3 Transforms 25

1.2.3.1 z - Transform 25

1.2.3.2 Laplace Transform 26

1.2.4 Parameter Estimation 27

1.2.4.1 Method of Moments 28

1.2.4.2 Maximum-Likelihood Estimation 29

1.2.4.3 Confidence Intervals 29

1.2.5 Order Statistics 30

vi CONTENTS

1.2.6 Distribution of Sums 31

2 Markov Chains 35

2.1 Markov Processes 35

2.1. I Stochastic and Markov Processes 35

2, I .2 Markov Chains 37

2. I .2.1 Discrete- Time Markov Chains 37

2.1.2.2 Continuous- Time Markov Chains 49

2.1.2.3 Recapitulation 55

2.2 The Modeling Process 56

2.2.1 Modeling Life-cycle Phases 56

2.2.2 Performance Measures 61

2.2.2.1 A Simple Example 61

2.2.2.2 Markov Reward Models 64

2.2.2.3 A Case Study 70

2.2.3 Generation Methods 80

2.2.3.1 Petri Nets 81

2.2.3.2 Generalized Stochastic Petri Nets 86

2.2.3.3 Stochastic Reward Nets 87

2.2.3.4 GSPN/SRN Analysis 91

2.2.3.5 A Larger Example 98

3 Steady-State Solutions of Markov Chains 103

3.1 Symbolic Solution: Birth-Death Process 105

3.2 Hessenberg Matrix: Non-Markovian Queues 106

3.2.1 Non-Exponential Service Times 107

3.2.2 Server with Vacations 112

3.2.2.1 Polling Systems 113

3.2.2.2 Analysis 114

3.3 Numerical Solution: Direct Methods 118

3.3.1 Gaussian Elimination 119

3.3.2 The Grassmann Algorithm 125

3.4 Numerical Solution: Iterative Methods 132

3.4.1 Convergence of Iterative Methods 132

3.4.2 Power Method 133

3.4.3 Jacobi’s Method 136

3.4.4 Gauss-Seidel Method 139

3.4.5 The Method of Successive Over-Relaxation 140

CONTENTS vii

3.4.5.1 The Relaxation Parameter

3.4.5.2 The Test of Convergence

3.4.5.3 Overflow and Underflow

3.4.5.4 The Algorithm

3.5 Comparison of Numerical Solution Methods

3.5.1 Case Studies

141

143

143

144

144

146

4 Steady-State Aggregation/ Disaggregation Methods 153

4.1 Courtois’s Approximate Method 153

4.1.1 Decomposition 154

4.1.2 Applicability 160

4.1.3 Analysis of the Substructures 162

4.1.4 Aggregation and Unconditioning 163

4.1.5 The Algorithm 165

4.2 Takahashi’s Iterative Method 166

4.2.1 The Fundamental Equations 167

4.2.2 Applicability 169

4.2.3 The Algorithm 170

4.2.4 Application 170

4.2.4.1 Aggregation 172

4.2.4.2 Disaggregation 173

4.2.5 Final Remarks 174

5 Transient Solution of Markov Chains 177

5. I Transient Analysis Using Exact Methods 178

5.1.1 A Pure Birth Process 178

5.1.2 A Two-State CTMC 181

5.1.3 Solution Using Laplace Transforms 184

5.1.4 Numerical Solution Using Uniformixation 184

5.1.4.1 The Instantaneous Case 184

5.1.4.2 Stiffness Tolerant Uniformization 186

5.1.4.3 The Cumulative Case 187

5.1.5 Other Numerical Methods 189

5.1.5.1 Ordinary Differential Equations 189

5.1.5.2 Weak Lumpability 189

5.2 Aggregation of Stiff Markov Chains 190

5.2.1 Outline and Basic Definitions 191

5.2.2 Aggregation of Fast Recurrent Subsets 192

. . . VIII CONTENTS

52.3

5.2.4

5.2.5

5.2.6

5.2.7

Aggregation of Fast Transient Subsets

Aggregation of Initial State Probabilities

Disaggregations

5.2.5.1 Fast Transient States

5.2.5.2 Fast Recurrent States

The Algorithm

An Example: Server Breakdown and

Repair

6 Single Station Queueing Systems 209

6.1 Kendall’s Notation 210

6.2 Performance Measures 212

6.3 The M/M/l System 214

6.4 The M/M/m System 217

6.5 The M/M/m System 218

6.6 The M/M/l/K Finite Capacity System 219

6.7 Machine Repairman Model 221

6.8 Closed Tandem Network 222

6.9 The M/G/l System 223

6.10 The GI/M/l System 225

6.11 The GI,M/m System 228

6.12 The GI/G/l System 229

6.13 The M/G/m System 230

6.14 The GI/G/m System 233

6.15 Priority Queueing 237

6.15.1 System without Preemption 239

6.15.2 Conservation Laws 242

6.15.3 System with Preemption 242

6.15.4 System with Time-Dependent Priorities 243

6.16 The Asymmetric System 248

6.16.1 Approximate Analysis 248

6.16.2 Exact Analysis 249

195

196

197

197

197

198

200

6.16.2.1 Analysis of M/M/m Loss Systems 250

6.16.2.2 Extending to Non-Lossy System 251

6.16.3 Exact Analysis of an Asymmetric M/M/2

System 253

6.17 Systems with Batch Service 258

7 Queueing Networks 263

7.1 Definitions and Notation 265

7.1.1 Single Class Networks 265

7.1.2 Multiclass Networks 267

7.2 Performance Measures 268

7.2.1 Single Class Networks 268

7.2.2 Multiclass Networks 271

7.3 Product-Form Queueing Networks 273

7.3.1 Global Balance 274

7.3.2 Local Balance 277

7.3.3 Product-Form 283

7.3.4 Jackson Networks 284

7.3.5 Gordon/Newell Networks 288

7.3.6 BCMP Networks 295

7.3.6.1 The Concept of Chains 296

7.3.6.2 BCMP Theorem 300

8 Algorithms for Product-Form Networks 311

8.1 The Convolution Algorithm 313

8.1 .l Single Class Closed Networks 313

8. I. 2 Multiclass Closed Networks 320

8.2 The Mean Value Analysis 326

8.2.~ Single Class Closed Networks 327

8.2.2 Multiclass Closed Networks 335

8.2.3 Mixed Networks 342

CONTENTS ix

8.2.4 Networks with Load-Dependent Service 347

8.2.4.1 Closed Networks 348

8.2.4.2 Mixed Networks 352

8.3 The RECAL Method 360

8.4 Flow Equivalent Server Method 368

8.4.1 FES Method for a Single Node 368

8.4.2 FES Method for Multiple Nodes 373

8.5 Summary 376

9 Approximation Algorithms for Product-Form Networks 379

9.1 Approximations Based on the MVA 380

9.1.1 Bard-Schweitzer Approximation 380

9.1.2 Self- Correcting Approximation Technique 385

9.1.2.1 Single Server Nodes 385

X CONTENTS

9.1.2.2 Multiple Server Nodes 389

9.1.2.3 Extended SCAT Algorithm 393

9.2 Summation Method 397

9.2.1 Single Class Networks 400

9.2.2 Multiclass Networks 403

9.3 Bottapprox Method 405

9.3.1 Initial Value of X 405

9.3.2 Single Class Networks 405

9.3.3 Multiclass Networks 408

9.4 Bounds Analysis 410

9.4.1 Asymptotic Bounds Analysis 411

9.4.2 Balanced Job Bounds Analysis 414

9.5 Networks with Variabilities in Workload 418

9.6 Summary 420

10 Algorithms for Non-Product-Form Networks

10.1 Non-Exponential Distributions

10.1.1 Diffusion Approximation

10.1.1.1 Open Networks

10.1.1.2 Closed Networks

10.1.2 Maximum Entropy Method

10.1.2.1 Open Networks

10.1.2.2 Closed Networks

10.1.3 Decomposition for Open Networks

10.1.4 Methods for Closed Networks

10.1.4.1 Robustness for Closed Networks

10.1.4-Z Marie’s Method

10.1.4.3 Extended SUM and BOTT

10.1.5 Closing Method for Mixed Networks

10.2 Different Service Times at FCFS Nodes

10.3 Priority Networks

10.3.1 Extended MVA (PRIOMVA)

10.3.2 The Method of Shadow Server

10.3.2.1 The Original Shadow Technique

10.3.2.2 Extensions of the Shadow

Technique

421

423

423

424

427

430

431

433

439

448

448

452

463

464

469

470

470

478

478

10.3.3 Extended SUM

10.4 Simultaneous Resource Possession

10.4.1 Memory Constraints

480

494

497

498

CONTENTS xi

10.4.2 I/O Subsystems

10.4.3 Method of Surrogate Delays

10.4.4 Serialization

10.5 Programs with Internal Concurrency

10.6 Parallel Processing

10.6.1 Asynchronous Tasks

10.6.2 Fork Join Systems

10.6.2.1 Modeling

10.6.2.2 Performance Measures

10.6.2.3 Analysis

IO. 7 Networks with Asymmetric Nodes

10.7.1 Closed Networks

10.7.1.1 Asymmetric SUM (ASUM)

10.7.1.2 Asymmetric MVA (AMVA)

10.7.1.3 Asymmetric SCAT (ASCAT)

10.7.2 Open Networks

10.8 Networks with Blocking

10.8. I Different Blocking Types

10.8.2 Solution for Networks with Two Nodes

11 Optimization

11.1 Optimization Problems and Cost Functions

11.2 Optimization based on the Summation Method

11.2.1 Maximization of the Throughput

11.2.2 Minimization of Cost

11.2.3 Minimization of the Response Time

11.3 Optimization based on the Convolution Algorithm

11.3.1 Maximization of the Throughput

11.3.2 Optimal Design of Storage Hierarchies

12 Performance Analysis Tools 571

12.1 PEPSY 572

12.1.1 Structure of PEPSY 573

12.1.1.1 The Input File 573

12.1.1.2 The Output File 573

12.1.1.3 Control Files 574

12.1.2 Different Programs in PEPSY 574

12.1.3 Example of using PEPSY 575

501

504

505

506

507

507

517

518

519

521

533

534

534

535

536

537

547

548

549

557

558

559

560

561

562

564

564

566

xii CONTENTS

12.1.4 Graphical User Interface XPEPSY

12.2 SPNP

12.2.1 SPNP Features

12.2.2 The CSPL Language

12.2.3 iSPN

12.3 MOSES

12.3.1 The Model Description Language MOSEL

12.3.2 Examples

12.3.2.1 Central-Server Model

12.3.2.2 Fault Tolerant Multiprocessor

System

12.4 SHARPE

12.4.1 Central-Server Queueing Network

12.4.2 M/M/m/K System

12.4.3 M/M/l/K System with Server Failure

and Repair

12.5 Characteristics of Some Tools

13 Applications

13.1 Case Studies of Queueing Networks

13.1.1 Multiprocessor Systems

13.1.1.1 Tightly Coupled Systems

13.1.1.2 Loosely Coupled Systems

13.1.2 Client Server Systems

13.1.3 Communication Systems

13.1.3.1 Description of the System

13.1.3.2 Queueing Network Model

13.1.3.3 Model Parameters

13.1.3.4 Results

13.1.4 UNIX Kernel

13.1.4.1 Model of the UNIX Kernel

13.1.4.2 Analysis

13.1.5 Flexible Production Systems

13.1.5.1 An Open Network Model

13.1.5.2 A Closed Network Model

13.2 Case Studies of Markov Chains

13.2.1 Wafer Production System

13.2.2 Polling Systems

13.2.3 Client Server Systems

577

579

579

580

585

588

588

590

590

591

594

594

596

597

600

603

603

603

603

606

607

608

608

611

612

617

620

621

624

630

630

634

638

639

641

645

CONTENTS . . . XIII

13.24 ISDN Channel 650

13.2.4.1 The Baseline Model 650

13.2.4.2 Markov Modulated Poisson

Processes 653

13.2.5 ATM Network under Overload 658

i3.3 Case Studies of Hierarchical Models 665

13.3.1 A Multiprocessor with Different Cache

Strategies 666

13.3.2 Performability of a Multiprocessor System 674

Glossary 679

Bibliography 691

Index 719