QUEUEING NETWORKS WITH BLOCKING

Exact and Approximate Solutions

Harry G. Perros

Oxford Press, 1994,

ISBN: 0-19-508580-9

Exact and Approximate Solutions

Harry G. Perros

Oxford Press, 1994,

ISBN: 0-19-508580-9

BASIC CONCEPTS 1

1.1. Introduction 1

1.2. Blocking mechanisms 5

1.3. Equivalencies among blocking mechanisms 10

Open queueing networks with blocking 11

Closed queueing networks with blocking 14

1.4. The phase-type distribution 15

The Erlang distribution 16

The Coxian distribution 17

The phase-type distribution 18

Some properties of the Coxian distribution 20

The generalized exponential distribution 23

1.5. Approximating a general distribution by

a Coxian distribution 25

c^2 > 1 26

a. The method of moments 26

b. Maximum likelihood estimation 28

c. Minimum distance estimation 28

c^2 < 1 29

1.6. References 30

Blocking mechanisms 30

Equivalencies between blocking mechanisms 31

The phase-type distribution 31

Bibliography 31

NUMERICAL METHODS FOR QUEUEING NETWORKS WITH BLOCKING 35

2.1. Introduction 35

2.2. Continuous time Markov processes with

discrete states 36

2.3. An example of rate matrix generation 40

2.4. Direct and iterative numerical methods 42

2.5. The matrix-geometric procedure 46

Matrix-geometric solution of the M/PH/1 queue 48

Matrix-geometric solution of the

M/PH/1/K+1 queue 52

Matrix-geometric solution of a queueing

network with blocking 52

2.6. References 54

Bibliography 55

TWO-NODE OPEN QUEUEING NETWORKS WITH BLOCKING 57

3.1. Introduction 57

3.2. Exponential service times 57

Two limiting cases 60

a. miu1 tends to infinity 60

b. Saturated first node 61

The blocking probability 61

Condition for stability 63

Multiple servers 64

3.3. Unreliable servers 66

Exponential service times 66

Constant synchronized service times:

saturated first node 66

3.4. Phase-type services 69

A matrix-recursive procedure 69

A matrix-geometric procedure 81

3.5. References 83

Exponential service times 83

Unreliable servers 85

Phase-type services 85

Bibliography 85

APPROXIMATE ANALYSIS OF OPEN TANDEM QUEUEING

NETWORKS WITH BLOCKING 91

4.1. Introduction 91

4.2. Exponential service times 92

Single-node decomposition 93

a. Algorithm 1: Exponential effective

service times 94

b. Algorithm 2: Phase-type effective

service times 96

Algorithm 3: Two-node decomposition 102

4.3. Phase-type service times 105

Algorithm 4: Single-node decomposition 105

Algorithm 5: Two-node decomposition 110

4.4. Constant service times 114

First node has an infinite capacity 114

First node has a finite capacity 120

4.5. Synchronized servers 121

4.6. References 126

Tandem configurations with exponential

service times 127

Tandem configurations with general

service times 129

Tandem configuration with constant

service times 130

Synchronized servers 130

Bibliography 132

APPROXIMATE ANALYSIS OF ARBITRARILY LINKED

OPEN TANDEM QUEUEING NETWORKS WITH BLOCKING 91

5.1. Introduction 139

5.2. A single-node decomposition algorithm

for feed-forward configurations 139

5.3. Arbitrary configurations 146

A maximum entropy algorithm 147

5.4. References 159

Feed-forward configurations 159

Arbitrary configurations 160

Bibliography 162

CLOSED QUEUEING NETWORKS WITH BLOCKING WITH

PRODUCT-FORM SOLUTION 165

6.1. Introduction 165

6.2. Reversible Markov processes 165

6.3. Two-node closed queueing networks with blocking 167

Single class of customers 167

a. Blocking-before-service 167

b. Blocking-after-service 168

Multiple classes of customers 169

6.4. Closed queueing networks with blocking with

more than two nodes 171

Reversible routing 171

State-dependent routing 173

Multiple classes of customers 175

Calculation of the normalizing constant G 181

6.5. Other product-form solutions 183

A cyclic queueing network with blocking 183

A closed queueing network with blocking

with N = mini{mi}+1 185

6.6. References 187

Two-node closed queueing networks with blocking 187

Closed queueing networks with blocking with

more than two nodes 188

Bibliography 189

CLOSED QUEUEING NETWORKS WITH BLOCKING WITH

NON PRODUCT-FORM SOLUTION 193

7.1. Introduction 193

7.2. Some properties of closed queueing

networks with blocking 193

7.3. The throughput of cyclic queueing networks

with blocking-before-service 198

7.4. Approximate throughput analysis of cyclic

queueing networks with blocking 203

Blocking-before-service 204

Blocking-after-service 207

7.5. Symmetric cyclic queueing networks with

blocking 210

7.6. Approximate analysis of arbitrary configurations

of closed queueing networks with blocking 211

The exponentialization algorithm 212

An algorithm based on Norton's theorem 213

A maximum entropy algorithm 215

7.7. References 219

Monotonicity of the throughput of cyclic

queueing networks with blocking 220

Approximate analysis of cyclic queueing

networks with blocking 220

Approximate analysis of arbitrary configurations

of closed queueing networks with blocking 221

Bibliography 222

APPLICATIONS 225

8.1. Introduction 225

8.2. A multi-stage pull-type production/inventory

system 225

8.3. A disk I/O system 230

8.4. A multi-stage buffered Banyan switch 235

8.5. References 245

Bibliography 245

BIBLIOGRAPHY 247

TABLE OF SYMBOLS 273

INDEX 285