Table of Contents
Preface to the Second Edition v
1 Basic Tools of Probabilistic Modelling 1
1.1 General background 1
1.2 Markov processes. The exponential distribution 3
1.3 Poisson arrival streams. Important properties 9
1.4 Steady-state. Balance diagrams. The "Birth and Death" process 13
1.5 The M/M/1, M/M/c and related queueing systems 20
1.6 Little's result. Applications. The M/G/1 system 28
1.7 Operational identities 34
1.8 Priority queueing 37
References 42
2 The Queue with Server of Walking Type and Its Applications to Computer System Modelling 43
2.1 Introduction 43
2.2 The queue with server of walking type with Poisson arrivals, and the M/G/1 queue 44
2.3 Evaluation of secondary memory device performance 58
2.4 Analysis of multiplexed data communication systems 68
References 71
3 Queueing Network Models 73
3.1 General remarks 73
3.2 Feedforward networks and product-form solution 76
3.3 Jackson networks 80
3.4 Other scheduling strategies and service time distributions 90
3.5 The BCMP theorem 98
3.6 The computation of performance measures 106
References 114
4 Queueing Networks with Multiple Classes of Positive and Negative Customers and Product Form Solution 117
4.1 Introduction 117
4.2 The model 119
4.3 Main results 121
4.4 Existence of the solution to the traffic equations 132
4.5 Conclusion 134
References 134
5 Markov-Modulated Queues 137
5.1 A multiserver queue with breakdowns and repairs 139
5.2 Manufacturing blocking 141
5.3 Phase-type distributions 142
5.4 Checkpointing and recovery in the presence of faults 143
5.5 Spectral expansion solution 144
5.6 Balance equations 146
5.7 Batch arrivals and/or departures 151
5.8 A simple approximation 153
5.9 The heavy traffic limit 155
5.10 Applications and comparisons 158
5.11 Remarks 163
References 164
6 Diffusion Approximation Methods for General Queueing Networks 165
6.1 Introduction 165
6.2 Diffusion approximation for a single queue 166
6.3 Diffusion approximations for general networks of queues with one customer class 185
6.4 Approximate behaviour of a single queue in a network with multiple customer classes 201
6.5 Conclusion 206
References 207
7 Approximate Decomposition and Iterative Techniques for Closed Model Solution 211
7.1 Introduction 211
7.2 Subsystem isolation 211
7.3 Decomposition as an approximate solution method 215
7.4 An electric circuit analogy for queueing network solution 224
References 229
8 Synthesis Problems in Single-Resource Systems: Characterisation and Control of Achievable Performance 231
8.1 Problem formulation 231
8.2 Conservation laws and inequalities 233
8.3 Characterisation theorems 242
8.4 The realisation of pre-specified performance vectors. Complete families of scheduling strategies 249
8.5 Optimal scheduling strategies 259
References 268
9 Control of Performance in Multiple-Resource Systems 269
9.1 Some problems arising in multiprogrammed computer systems 269
9.2 The modelling of system resources and program behaviour 271
9.3 Control of the degree of multiprogramming 274
9.4 The page fault rate control policy (RCP) 281
9.5 Control of performance by selective memory allocation 287
9.6 Towards a characterisation of achievable performance in terminal systems 292
References 294
10 A Queue with Server of Walking Type 297
10.1 Introduction 297
10.2 Properties of the waiting time process 299
10.3 Application to a paging drum model 307
References 307
Index 309