Queueing Modelling Fundamentals With Applications in Communication Networks

by Ng, Chee-Hock; Boon-Hee, Soong

• ISBN13: 9780470519578
• ISBN10: 0470519576
• Edition: 2nd
• Format: Hardcover
• Copyright: 2008-06-09
• Publisher: Wiley

Summary

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 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 Biography

Chee-Hock Ng, Nanyang Technological University, Singapore
Chee-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, Singapore
Soong 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.

Table of Contents

List of Tables	p. xi
List of Illustrations	p. xiii
Preface	p. xvii
Preliminaries	p. 1
Probability Theory	p. 1
Sample Spaces and Axioms of Probability	p. 2
Conditional Probability and Independence	p. 5
Random Variables and Distributions	p. 7
Expected Values and Variances	p. 12
Joint Random Variables and Their Distributions	p. 16
Independence of Random Variables	p. 21
z-Transforms - Generating Functions	p. 22
Properties of z-Transforms	p. 23
Laplace Transforms	p. 28
Properties of the Laplace Transform	p. 29
Matrix Operations	p. 32
Matrix Basics	p. 32
Eigenvalues, Eigenvectors and Spectral Representation	p. 34
Matrix Calculus	p. 36
Problems	p. 39
Introduction to Queueing Systems	p. 43
Nomenclature of a Queueing System	p. 44
Characteristics of the Input Process	p. 45
Characteristics of the System Structure	p. 46
Characteristics of the Output Process	p. 47
Random Variables and their Relationships	p. 48
Kendall Notation	p. 50
Little's Theorem	p. 52
General Applications of Little's Theorem	p. 54
Ergodicity	p. 55
Resource Utilization and Traffic Intensity	p. 56
Flow Conservation Law	p. 57
Poisson Process	p. 59
The Poisson Process - A Limiting Case	p. 59
The Poisson Process - An Arrival Perspective	p. 60
Properties of the Poisson Process	p. 62
Superposition Property	p. 62
Decomposition Property	p. 63
Exponentially Distributed Inter-arrival Times	p. 64
Memoryless (Markovian) Property of Inter-arrival Times	p. 64
Poisson Arrivals During a Random Time Interval	p. 66
Problems	p. 69
Discrete and Continuous Markov Processes	p. 71
Stochastic Processes	p. 72
Discrete-time Markov Chains	p. 74
Definitions of Discrete-time Markov Chains	p. 75
Matrix Formulation of State Probabilities	p. 79
General Transient Solutions for State Probabilities	p. 81
Steady-state Behaviour of a Markov Chain	p. 86
Reducibility and Periodicity of a Markov Chain	p. 88
Sojourn Times of a Discrete-time Markov Chain	p. 90
Continuous-time Markov Chains	p. 91
Definition of Continuous-time Markov Chains	p. 91
Sojourn Times of a Continuous-time Markov Chain	p. 92
State Probability Distribution	p. 93
Comparison of Transition-rate and Transition-probability Matrices	p. 95
Birth-Death Processes	p. 96
Problems	p. 100
Single-Queue Markovian Systems	p. 103
Classical M/M/1 Queue	p. 104
Global and Local Balance Concepts	p. 106
Performance Measures of the M/M/1 System	p. 107
PASTA - Poisson Arrivals See Time Averages	p. 110
M/M/1 System Time (Delay) Distribution	p. 111
M/M/1/S Queueing Systems	p. 118
Blocking Probability	p. 119
Performance Measures of M/M/1/S Systems	p. 120
Multi-server Systems - M/M/m	p. 124
Performance Measures of M/M/m Systems	p. 126
Waiting Time Distribution of M/M/m	p. 127
Erlang's Loss Queueing Systems - M/M/m/m Systems	p. 129
Performance Measures of the M/M/m/m	p. 130
Engset's Loss Systems	p. 131
Performance Measures of M/M/m/m with Finite Customer Population	p. 133
Considerations for Applications of Queueing Models	p. 134
Problems	p. 139
Semi-Markovian Queueing Systems	p. 141
The M/G/1 Queueing System	p. 142
The Imbedded Markov-chain Approach	p. 142
Analysis of M/G/1 Queue Using Imbedded Markov-chain Approach	p. 143
Distribution of System State	p. 146
Distribution of System Time	p. 147
The Residual Service Time Approach	p. 148
Performance Measures of M/G/1	p. 150
M/G/1 with Service Vocations	p. 155
Performance Measures of M/G/1 with Service Vacations	p. 156
Priority Queueing Systems	p. 158
M/G/1 Non-preemptive Priority Queueing	p. 158
Performance Measures of Non-preemptive Priority	p. 160
M/G/1 Pre-emptive Resume Priority Queueing	p. 163
The G/M/1 Queueing System	p. 165
Performance Measures of GI/M/1	p. 166
Problems	p. 167
Open Queueing Networks	p. 169
Markovian Queries in Tandem	p. 171
Analysis of Tandem Queues	p. 175
Burke's Theorem	p. 176
Applications of Tandem Queues in Data Networks	p. 178
Jackson Queueing Networks	p. 181
Performance Measures for Open Networks	p. 186
Balance Equations	p. 190
Problems	p. 193
Closed Queueing Networks	p. 197
Jackson Closed Queueing Networks	p. 197
Steady-state Probability Distribution	p. 199
Convolution Algorithm	p. 203
Performance Measures	p. 207
Mean Value Analysis	p. 210
Application of Closed Queueing Networks	p. 213
Problems	p. 214
Markov-Modulated Arrival Process	p. 217
Markov-modulated Poisson Process (MMPP)	p. 218
Definition and Model	p. 218
Superposition of MMPPs	p. 223
MMPP/G/1	p. 225
Applications of MMPP	p. 226
Markov-modulated Bernoulli Process	p. 227
Source Model and Definition	p. 227
Superposition of N Identical MMBPs	p. 228
[Sigma]MMBP/D/1	p. 229
Queue Length Solution	p. 231
Initial Conditions	p. 233
Markov-modulated Fluid Flow	p. 233
Model and Queue Length Analysis	p. 233
Applications of Fluid Flow Model to ATM	p. 236
Network Calculus	p. 236
System Description	p. 237
Input Traffic Characterization - Arrival Curve	p. 239
System Characterization - Service Curve	p. 240
Min-Plus Algebra	p. 241
Flow and Congestion Control	p. 243
Introduction	p. 243
Quality of Service	p. 245
Analysis of Sliding Window Flow Control Mechanisms	p. 246
A Simple Virtual Circuit Model	p. 246
Sliding Window Model	p. 247
Rate Based Adaptive Congestion Control	p. 257
References	p. 259
Index	p. 265
Table of Contents provided by Ingram. All Rights Reserved.