QUEUEING NETWORKS WITH BLOCKING
Exact and Approximate Solutions

Harry G. Perros

Oxford Press, 1994,
ISBN: 0-19-508580-9



Table of Contents

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