Queueing analysis is a vital tool used in the evaluation of system performance. Applications of queueing analysis cover a wide spectrum from bank automated teller machines to transportation and communications data networks.Fully revised, this second edition of a popular book contains the significant addition of a new chapter on Flow & Congestion Control and a section on Network Calculus among other new sections that have been added to remaining chapters. An introductory text, Queueing Modelling Fundamentals focuses on queueing modelling techniques and applications of data networks, examining the underlying principles of isolated queueing systems. This book introduces the complex queueing theory in simple language/proofs to enable the reader to quickly pick up an overview to queueing theory without utilizing the diverse necessary mathematical tools. It incorporates a rich set of worked examples on its applications to communication networks.Features include:Fully revised and updated edition with significant new chapter on Flow and Congestion Control as-well-as a new section on Network CalculusA comprehensive text which highlights both the theoretical models and their applications through a rich set of worked examples, examples of applications to data networks and performance curvesProvides an insight into the underlying queuing principles and features step-by-step derivation of queueing resultsWritten by experienced Professors in the fieldQueueing Modelling Fundamentals is an introductory text for undergraduate or entry-level post-graduate students who are taking courses on network performance analysis as well as those practicing network administrators who want to understand the essentials of network operations. The detailed step-by-step derivation of queueing results also makes it an excellent text for professional engineers.
Author(s): Professor Chee-Hock Ng, Professor Soong Boon-Hee
Edition: 2
Year: 2008
Language: English
Pages: 292
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
