Queueing Modelling Fundamentals

Chee-Hock Ng, Nanyang Technological University, SingaporeChee-Hock Ng is currently an Associate Professor in the School of Electrical & Electronic Engineering, Nanyang Technological University (NTU). He is also serving as an external examiner and assessor to the SIM University for its computer science programmes. The author of the first edition of "Queueing Modelling Fundamentals", Chee-Hock Ng runs short courses to the industry and other statuary bodies in the area of networking.? A Chartered Engineer and a Senior Member of IEEE, he has also published many papers in international journals and conferences in the areas of networking. Boon-Hee Soong, Nanyang Technological University, SingaporeSoong Boon-Hee is currently an Associate Professor with the School of Electrical and Electronic Engineering, Nanyang Technological University. Previously a Visiting Research Fellow at the Department of Electrical and Electronic Engineering, Imperial College, London, under the Commonwealth Fellowship Award, he has served as a consultant for many companies including Mobile IP in a recent technical field trial of Next-Generation Wireless LAN initiated by IDA (InfoComm Development Authority, Singapore). Boon-Hee Soong was awarded the Tan Chin Tuan Fellowship in 2004. Author of over 100 international journals, book chapters and conference papers, he is currently a Senior member of IEEE and a member of ACM.

• List of Tables xiList of Illustrations xiiiPreface xvii1. Preliminaries 11.1 Probability Theory 11.1.1 Sample Spaces and Axioms of Probability 21.1.2 Conditional Probability and Independence 51.1.3 Random Variables and Distributions 71.1.4 Expected Values and Variances 121.1.5 Joint Random Variables and Their Distributions 161.1.6 Independence of Random Variables 211.2 z-Transforms – Generating Functions 221.2.1 Properties of z-Transforms 231.3 Laplace Transforms 281.3.1 Properties of the Laplace Transform 291.4 Matrix Operations 321.4.1 Matrix Basics 321.4.2 Eigenvalues, Eigenvectors and Spectral Representation 341.4.3 Matrix Calculus 36Problems 392. Introduction to Queueing Systems 432.1 Nomenclature of a Queueing System 442.1.1 Characteristics of the Input Process 452.1.2 Characteristics of the System Structure 462.1.3 Characteristics of the Output Process 472.2 Random Variables and their Relationships 482.3 Kendall Notation 502.4 Little’s Theorem 522.4.1 General Applications of Little’s Theorem 542.4.2 Ergodicity 552.5 Resource Utilization and Traffic Intensity 562.6 Flow Conservation Law 572.7 Poisson Process 592.7.1 The Poisson Process – A Limiting Case 592.7.2 The Poisson Process – An Arrival Perspective 602.8 Properties of the Poisson Process 622.8.1 Superposition Property 622.8.2 Decomposition Property 632.8.3 Exponentially Distributed Inter-arrival Times 642.8.4 Memoryless (Markovian) Property of Inter-arrival Times 642.8.5 Poisson Arrivals During a Random Time Interval 66Problems 693. Discrete and Continuous Markov Processes 713.1 Stochastic Processes 723.2 Discrete-time Markov Chains 743.2.1 Definitions of Discrete-time Markov Chains 753.2.2 Matrix Formulation of State Probabilities 793.2.3 General Transient Solutions for State Probabilities 813.2.4 Steady-state Behaviour of a Markov Chain 863.2.5 Reducibility and Periodicity of a Markov Chain 883.2.6 Sojourn Times of a Discrete-time Markov Chain 903.3 Continuous-time Markov Chains 913.3.1 Definition of Continuous-time Markov Chains 913.3.2 Sojourn Times of a Continuous-time Markov Chain 923.3.3 State Probability Distribution 933.3.4 Comparison of Transition-rate and Transitionprobability Matrices 953.4 Birth-Death Processes 96Problems 1004. Single-Queue Markovian Systems 1034.1 Classical M/M/1 Queue 1044.1.1 Global and Local Balance Concepts 1064.1.2 Performance Measures of the M/M/1 System 1074.2 PASTA – Poisson Arrivals See Time Averages 1104.3 M/M/1 System Time (Delay) Distribution 1114.4 M/M/1/S Queueing Systems 1184.4.1 Blocking Probability 1194.4.2 Performance Measures of M/M/1/S Systems 1204.5 Multi-server Systems – M/M/m 1244.5.1 Performance Measures of M/M/m Systems 1264.5.2 Waiting Time Distribution of M/M/m 1274.6 Erlang’s Loss Queueing Systems – M/M/m/m Systems 1294.6.1 Performance Measures of the M/M/m/m 1304.7 Engset’s Loss Systems 1314.7.1 Performance Measures of M/M/m/m with Finite Customer Population 1334.8 Considerations for Applications of Queueing Models 134Problems 1395. Semi-Markovian Queueing Systems 1415.1 The M/G/1 Queueing System 1425.1.1 The Imbedded Markov-chain Approach 1425.1.2 Analysis of M/G/1 Queue Using Imbedded Markov-chain Approach 1435.1.3 Distribution of System State 1465.1.4 Distribution of System Time 1475.2 The Residual Service Time Approach 1485.2.1 Performance Measures of M/G/ 1 1505.3 M/G/1 with Service Vocations 1555.3.1 Performance Measures of M/G/1 with Service Vacations 1565.4 Priority Queueing Systems 1585.4.1 M/G/1 Non-preemptive Priority Queueing 1585.4.2 Performance Measures of Non-preemptive Priority 1605.4.3 M/G/1 Pre-emptive Resume Priority Queueing 1635.5 The G/M/1 Queueing System 1655.5.1 Performance Measures of GI/M/ 1 166Problems 1676. Open Queueing Networks 1696.1 Markovian Queries in Tandem 1716.1.1 Analysis of Tandem Queues 1756.1.2 Burke’s Theorem 1766.2 Applications of Tandem Queues in Data Networks 1786.3 Jackson Queueing Networks 1816.3.1 Performance Measures for Open Networks 1866.3.2 Balance Equations 190Problems 1937. Closed Queueing Networks 1977.1 Jackson Closed Queueing Networks 1977.2 Steady-state Probability Distribution 1997.3 Convolution Algorithm 2037.4 Performance Measures 2077.5 Mean Value Analysis 2107.6 Application of Closed Queueing Networks 213Problems 2148. Markov-Modulated Arrival Process 2178.1 Markov-modulated Poisson Process (MMPP) 2188.1.1 Definition and Model 2188.1.2 Superposition of MMPPs 2238.1.3 MMPP/G/ 1 2258.1.4 Applications of MMPP 2268.2 Markov-modulated Bernoulli Process 2278.2.1 Source Model and Definition 2278.2.2 Superposition of N Identical MMBPs 2288.2.3 ΣMMBP/D/ 1 2298.2.4 Queue Length Solution 2318.2.5 Initial Conditions 2338.3 Markov-modulated Fluid Flow 2338.3.1 Model and Queue Length Analysis 2338.3.2 Applications of Fluid Flow Model to ATM 2368.4 Network Calculus 2368.4.1 System Description 2378.4.2 Input Traffic Characterization–Arrival Curve 2398.4.3 System Characterization – Service Curve 2408.4.4 Min-Plus Algebra 2419. Flow and Congestion Control 2439.1 Introduction 2439.2 Quality of Service 2459.3 Analysis of Sliding Window Flow Control Mechanisms 2469.3.1 A Simple Virtual Circuit Model 2469.3.2 Sliding Window Model 2479.4 Rate Based Adaptive Congestion Control 257References 259Index 265

"The book is well written and nicely illustrated. I recommend it as an introduction for graduate students and telecommunications engineers." (Computing Reviews, November 24, 2008) "This book would serve ideally as a text for an undergraduate course on network performance analysis." (Computing Reviews, July 2008)