List of Tables xi
List of Illustrations xiii
Preface xvii
1. Preliminaries 1
1.1 Probability Theory 1
1.1.1 Sample Spaces and Axioms of Probability 2
1.1.2 Conditional Probability and Independence 5
1.1.3 Random Variables and Distributions 7
1.1.4 Expected Values and Variances 12
1.1.5 Joint Random Variables and Their Distributions 16
1.1.6 Independence of Random Variables 21
1.2 z-Transforms – Generating Functions 22
1.2.1 Properties of z-Transforms 23
1.3 Laplace Transforms 28
1.3.1 Properties of the Laplace Transform 29
1.4 Matrix Operations 32
1.4.1 Matrix Basics 32
1.4.2 Eigenvalues, Eigenvectors and Spectral Representation 34
1.4.3 Matrix Calculus 36
Problems 39
2. Introduction to Queueing Systems 43
2.1 Nomenclature of a Queueing System 44
2.1.1 Characteristics of the Input Process 45
2.1.2 Characteristics of the System Structure 46
2.1.3 Characteristics of the Output Process 47
2.2 Random Variables and their Relationships 48
2.3 Kendall Notation 50
2.4 Little’s Theorem 52
2.4.1 General Applications of Little’s Theorem 54
2.4.2 Ergodicity 55
2.5 Resource Utilization and Traffic Intensity 56
2.6 Flow Conservation Law 57
2.7 Poisson Process 59
2.7.1 The Poisson Process – A Limiting Case 59
2.7.2 The Poisson Process – An Arrival Perspective 60
2.8 Properties of the Poisson Process 62
2.8.1 Superposition Property 62
2.8.2 Decomposition Property 63
2.8.3 Exponentially Distributed Inter-arrival Times 64
2.8.4 Memoryless (Markovian) Property of Inter-arrival Times 64
2.8.5 Poisson Arrivals During a Random Time Interval 66
Problems 69
3. Discrete and Continuous Markov Processes 71
3.1 Stochastic Processes 72
3.2 Discrete-time Markov Chains 74
3.2.1 Definitions of Discrete-time Markov Chains 75
3.2.2 Matrix Formulation of State Probabilities 79
3.2.3 General Transient Solutions for State Probabilities 81
3.2.4 Steady-state Behaviour of a Markov Chain 86
3.2.5 Reducibility and Periodicity of a Markov Chain 88
3.2.6 Sojourn Times of a Discrete-time Markov Chain 90
3.3 Continuous-time Markov Chains 91
3.3.1 Definition of Continuous-time Markov Chains 91
3.3.2 Sojourn Times of a Continuous-time Markov Chain 92
3.3.3 State Probability Distribution 93
3.3.4 Comparison of Transition-rate and Transitionprobability Matrices 95
3.4 Birth-Death Processes 96
Problems 100
4. Single-Queue Markovian Systems 103
4.1 Classical M/M/1 Queue 104
4.1.1 Global and Local Balance Concepts 106
4.1.2 Performance Measures of the M/M/1 System 107
4.2 PASTA – Poisson Arrivals See Time Averages 110
4.3 M/M/1 System Time (Delay) Distribution 111
4.4 M/M/1/S Queueing Systems 118
4.4.1 Blocking Probability 119
4.4.2 Performance Measures of M/M/1/S Systems 120
4.5 Multi-server Systems – M/M/m 124
4.5.1 Performance Measures of M/M/m Systems 126
4.5.2 Waiting Time Distribution of M/M/m 127
4.6 Erlang’s Loss Queueing Systems – M/M/m/m Systems 129
4.6.1 Performance Measures of the M/M/m/m 130
4.7 Engset’s Loss Systems 131
4.7.1 Performance Measures of M/M/m/m with Finite Customer Population 133
4.8 Considerations for Applications of Queueing Models 134
Problems 139
5. Semi-Markovian Queueing Systems 141
5.1 The M/G/1 Queueing System 142
5.1.1 The Imbedded Markov-chain Approach 142
5.1.2 Analysis of M/G/1 Queue Using Imbedded Markov-chain Approach 143
5.1.3 Distribution of System State 146
5.1.4 Distribution of System Time 147
5.2 The Residual Service Time Approach 148
5.2.1 Performance Measures of M/G/ 1 150
5.3 M/G/1 with Service Vocations 155
5.3.1 Performance Measures of M/G/1 with Service Vacations 156
5.4 Priority Queueing Systems 158
5.4.1 M/G/1 Non-preemptive Priority Queueing 158
5.4.2 Performance Measures of Non-preemptive Priority 160
5.4.3 M/G/1 Pre-emptive Resume Priority Queueing 163
5.5 The G/M/1 Queueing System 165
5.5.1 Performance Measures of GI/M/ 1 166
Problems 167
6. Open Queueing Networks 169
6.1 Markovian Queries in Tandem 171
6.1.1 Analysis of Tandem Queues 175
6.1.2 Burke’s Theorem 176
6.2 Applications of Tandem Queues in Data Networks 178
6.3 Jackson Queueing Networks 181
6.3.1 Performance Measures for Open Networks 186
6.3.2 Balance Equations 190
Problems 193
7. Closed Queueing Networks 197
7.1 Jackson Closed Queueing Networks 197
7.2 Steady-state Probability Distribution 199
7.3 Convolution Algorithm 203
7.4 Performance Measures 207
7.5 Mean Value Analysis 210
7.6 Application of Closed Queueing Networks 213
Problems 214
8. Markov-Modulated Arrival Process 217
8.1 Markov-modulated Poisson Process (MMPP) 218
8.1.1 Definition and Model 218
8.1.2 Superposition of MMPPs 223
8.1.3 MMPP/G/ 1 225
8.1.4 Applications of MMPP 226
8.2 Markov-modulated Bernoulli Process 227
8.2.1 Source Model and Definition 227
8.2.2 Superposition of N Identical MMBPs 228
8.2.3 ΣMMBP/D/ 1 229
8.2.4 Queue Length Solution 231
8.2.5 Initial Conditions 233
8.3 Markov-modulated Fluid Flow 233
8.3.1 Model and Queue Length Analysis 233
8.3.2 Applications of Fluid Flow Model to ATM 236
8.4 Network Calculus 236
8.4.1 System Description 237
8.4.2 Input Traffic Characterization–Arrival Curve 239
8.4.3 System Characterization – Service Curve 240
8.4.4 Min-Plus Algebra 241
9. Flow and Congestion Control 243
9.1 Introduction 243
9.2 Quality of Service 245
9.3 Analysis of Sliding Window Flow Control Mechanisms 246
9.3.1 A Simple Virtual Circuit Model 246
9.3.2 Sliding Window Model 247
9.4 Rate Based Adaptive Congestion Control 257
References 259
Index 265
