Queueing Modelling Fundamentals: With Applications in Communication Networks, Second Edition

Queueing Modelling Fundamentals......Page 2
Contents......Page 10
List of Tables......Page 14
List of Illustrations......Page 16
Preface......Page 20
1.1 PROBABILITY THEORY......Page 24
1.1.1 Sample Spaces and Axioms of Probability......Page 25
1.1.2 Conditional Probability and Independence......Page 28
1.1.3 Random Variables and Distributions......Page 30
1.1.4 Expected Values and Variances......Page 35
1.1.5 Joint Random Variables and Their Distributions......Page 39
1.1.6 Independence of Random Variables......Page 44
1.2 z-TRANSFORMS – GENERATING FUNCTIONS......Page 45
1.2.1 Properties of z-Transforms......Page 46
1.3 LAPLACE TRANSFORMS......Page 51
1.3.1 Properties of the Laplace Transform......Page 52
1.4.1 Matrix Basics......Page 55
1.4.2 Eigenvalues, Eigenvectors and Spectral Representation......Page 57
1.4.3 Matrix Calculus......Page 59
Problems......Page 62
2: Introduction to Queueing Systems......Page 66
2.1 NOMENCLATURE OF A QUEUEING SYSTEM......Page 67
2.1.1 Characteristics of the Input Process......Page 68
2.1.2 Characteristics of the System Structure......Page 69
2.1.3 Characteristics of the Output Process......Page 70
2.2 RANDOM VARIABLES AND THEIR RELATIONSHIPS......Page 71
2.3 KENDALL NOTATION......Page 73
2.4 LITTLE’S THEOREM......Page 75
2.4.1 General Applications of Little’s Theorem......Page 77
2.4.2 Ergodicity......Page 78
2.5 RESOURCE UTILIZATION AND TRAFFIC INTENSITY......Page 79
2.6 FLOW CONSERVATION LAW......Page 80
2.7.1 The Poisson Process – A Limiting Case......Page 82
2.7.2 The Poisson Process – An Arrival Perspective......Page 83
2.8.1 Superposition Property......Page 85
2.8.2 Decomposition Property......Page 86
2.8.4 Memoryless (Markovian) Property of Inter-arrival Times......Page 87
2.8.5 Poisson Arrivals During a Random Time Interval......Page 89
Problems......Page 92
3: Discrete and Continuous Markov Processes......Page 94
3.1 STOCHASTIC PROCESSES......Page 95
3.2 DISCRETE-TIME MARKOV CHAINS......Page 97
3.2.1 Definition of Discrete-time Markov Chains......Page 98
3.2.2 Matrix Formulation of State Probabilities......Page 102
3.2.3 General Transient Solutions for State Probabilities......Page 104
3.2.4 Steady-state Behaviour of a Markov Chain......Page 109
3.2.5 Reducibility and Periodicity of a Markov Chain......Page 111
3.2.6 Sojourn Times of a Discrete-time Markov Chain......Page 113
3.3.1 Definition of Continuous-time Markov Chains......Page 114
3.3.2 Sojourn Times of a Continuous-time Markov Chains......Page 115
3.3.3 State Probability Distribution......Page 116
3.3.4 Comparison of Transition-rate and Transition-probability Matrices......Page 118
3.4 BIRTH-DEATH PROCESSES......Page 119
Problems......Page 123
4: Single-Queue Markovian Systems......Page 126
4.1 CLASSICAL M/M/1 QUEUE......Page 127
4.1.1 Global and Local Balance Concepts......Page 129
4.1.2 Performance Measures of the M/M/1 System......Page 130
4.2 PASTA – POISSON ARRIVALS SEE TIME AVERAGES......Page 133
4.3 M/M/1 SYSTEM TIME (DELAY) DISTRIBUTION......Page 134
4.4 M/M/1/S QUEUEING SYSTEMS......Page 141
4.4.1 Blocking Probability......Page 142
4.4.2 Performance Measures of M/M/1/S Systems......Page 143
4.5 MULTI-SERVER SYSTEMS – M/M/m......Page 147
4.5.1 Performance Measures of M/M/m Systems......Page 149
4.5.2 Waiting Time Distribution of M/M/m......Page 150
4.6 ERLANG’S LOSS QUEUEING SYSTEMS – M/M/m/m SYSTEMS......Page 152
4.6.1 Performance Measures of the M/M/m/m......Page 153
4.7 ENGSET’S LOSS SYSTEMS......Page 154
4.7.1 Performance Measures of M/M/m/m with Finite Customer Population......Page 156
4.8 CONSIDERATIONS FOR APPLICATIONS OF QUEUEING MODELS......Page 157
Problems......Page 162
5: Semi-Markovian Queueing Systems......Page 164
5.1.1 The Imbedded Markov-Chain Approach......Page 165
5.1.2 Analysis of M/G/1 Queue Using Imbedded Markov-Chain Approach......Page 166
5.1.3 Distribution of System State......Page 169
5.1.4 Distribution of System Time......Page 170
5.2 THE RESIDUAL SERVICE TIME APPROACH......Page 171
5.2.1 Performance Measures of M/G/1......Page 173
5.3 M/G/1 WITH SERVICE VOCATIONS......Page 178
5.3.1 Performance Measures of M/G/1 with Service Vacations......Page 179
5.4.1 M/G/1 Non-preemptive Priority Queueing......Page 181
5.4.2 Performance Measures of Non-preemptive Priority......Page 183
5.4.3 M/G/1 Pre-emptive Resume Priority Queueing......Page 186
5.5 THE G/M/1 QUEUEING SYSTEM......Page 188
5.5.1 Performance Measures of GI/M/1......Page 189
Problems......Page 190
6: Open Queueing Networks......Page 192
6.1 MARKOVIAN QUEUES IN TANDEM......Page 194
6.1.1 Analysis of Tandem Queues......Page 198
6.1.2 Burke’s Theorem......Page 199
6.2 APPLICATIONS OF TANDEM QUEUES IN DATA NETWORKS......Page 201
6.3 JACKSON QUEUEING NETWORKS......Page 204
6.3.1 Performance Measures for Open Networks......Page 209
6.3.2 Balance Equations......Page 213
Problems......Page 216
7.1 JACKSON CLOSED QUEUEING NETWORKS......Page 220
7.2 STEADY-STATE PROBABILITY DISTRIBUTION......Page 222
7.3 CONVOLUTION ALGORITHM......Page 226
7.4 PERFORMANCE MEASURES......Page 230
7.5 MEAN VALUE ANALYSIS......Page 233
7.6 APPLICATIONS OF CLOSED QUEUEING NETWORKS......Page 236
Problems......Page 237
8: Markov-Modulated Arrival Process......Page 240
8.1.1 Definition and Model......Page 241
8.1.2 Superposition of MMPPs......Page 246
8.1.3 MMPP/G/1......Page 248
8.1.4 Applications of MMPP......Page 249
8.2.1 Source Model and Definition......Page 250
8.2.2 Superposition of N Identical MMBPs......Page 251
8.2.3 ΣMMBP/D/1......Page 252
8.2.4 Queue Length Solution......Page 254
8.3.1 Model and Queue Length Analysis......Page 256
8.4 NETWORK CALCULUS......Page 259
8.4.1 System Description......Page 260
8.4.2 Input Traffic Characterization – Arrival Curve......Page 262
8.4.3 System Characterization – Service Curve......Page 263
8.4.4 Min-Plus Algebra......Page 264
9.1 INTRODUCTION......Page 266
9.2 QUALITY OF SERVICE......Page 268
9.3.1 A Simple Virtual Circuit Model......Page 269
9.3.2 Sliding Window Model......Page 270
9.4 RATE BASED ADAPTIVE CONGESTION CONTROL......Page 280
References......Page 282
Index......Page 288