Queueing Modelling Fundamentals: With Applications in Communication Networks

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 Calculus A 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 curves Provides an insight into the underlying queuing principles and features step-by-step derivation of queueing results Written by experienced Professors in the field Queueing 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.

Table of Contents:
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