Queueing Theory with Applications to Packet Telecommunication

✍ Scribed by John N. Daigle

• Publisher: Springer
• Year: 2004
• Tongue: English
• Leaves: 341
• Edition: 1
• Category: Library

✦ Synopsis

Queueing Theory with Applications to Packet Telecommunication is an efficient introduction to fundamental concepts and principles underlying the behavior of queueing systems and its application to the design of packet-oriented electrical communication systems. In addition to techniques and approaches found in earlier works, the author presents a thoroughly modern computational approach based on Schur decomposition. This approach facilitates solution of broad classes of problems wherein a number of practical modeling issues may be explored. Key features of communication systems, such as correlation in packet arrival processes at IP switches and variability in service rates due to fading wireless links are introduced. Numerous exercises embedded within the text and problems at the end of certain chapters that integrate lessons learned across multiple sections are also included. In all cases, including systems having priority, developments lead to procedures or formulae that yield numerical results from which sensitivity of queueing behavior to parameter variation can be explored.  In several cases multiple approaches to computing distributions are presented. Queueing Theory with Applications to Packet Telecommunication is intended both for self study and for use as a primary text in graduate courses in queueing theory in electrical engineering, computer science, operations research, and mathematics.  Professionals will also find this work invaluable because the author discusses applications such as statistical multiplexing, IP switch design, and wireless communication systems.  In addition, numerous modeling issues, such as the suitability of Erlang-k and Pade approximations are addressed.

✦ Table of Contents

Contents......Page 8
List of Figures......Page 12
List of Tables......Page 16
Preface......Page 18
Acknowledgments......Page 24
1. TERMINOLOGY AND EXAMPLES......Page 26
1.1 The Terminology of Queueing Systems......Page 27
1.2.1 Cellular Telephony......Page 34
1.2.2 Multiplexing Packets......Page 36
1.2.3 CDMA-Based Cellular Data......Page 39
1.3 Summary......Page 42
2. REVIEW OF RANDOM PROCESSES......Page 44
2.1.1 Statistical Experiments......Page 45
2.1.2 Conditioning Experiments......Page 47
2.2 Random Variables......Page 52
2.3 Exponential Distribution......Page 58
2.4 Poisson Process......Page 64
2.5 Markov Chains......Page 70
3. ELEMENTARY CTMC-BASED QUEUEING MODELS......Page 82
3.1.1 Time-Dependent M/M/1 Occupancy Distribution......Page 83
3.1.2 Stochastic Equilibrium M/M/1 Distributions......Page 85
3.1.3 Busy Period for M/M/1 Queueing System......Page 101
3.2 Dynamical Equations for General Birth-Death Process......Page 106
3.3 Time-Dependent Probabilities for Finite-State Systems......Page 108
3.3.1 Classical Approach......Page 109
3.3.2 Jensen’s Method......Page 113
3.4 Balance Equations Approach for Systems in Equilibrium......Page 116
3.5 Probability Generating Function Approach......Page 123
3.6 Supplementary Problems......Page 126
4. ADVANCED CTMC-BASED QUEUEING MODELS......Page 132
4.1 Networks......Page 133
4.1.1 Feedforward Networks: Fixed Routing......Page 134
4.1.2 Arbitrary Open Networks......Page 135
4.1.3 Closed Networks of Single Servers......Page 136
4.2 Phase-Dependent Arrivals and Service......Page 147
4.2.1 Probability Generating Function Approach......Page 149
4.2.2 Matrix Geometric Method......Page 163
4.2.3 Rate Matrix Computation via Eigenanalysis......Page 168
4.2.4 Generalized State-Space Methods......Page 171
4.3 Phase-Type Distributions......Page 177
4.4 Supplementary Problems......Page 181
5. THE BASIC M/G/1 QUEUEING SYSTEM......Page 184
5.1 M/G/1 Transform Equations......Page 186
5.1.1 Sojourn Time for M/G/1......Page 190
5.1.3 Busy Period for M/G/1......Page 192
5.2.1 Discrete Fourier Transform Approach......Page 195
5.2.2 Recursive Approach......Page 205
5.2.3 Generalized State-Space Approach......Page 208
5.3.1 Expected Waiting and Renewal Theory......Page 235
5.3.2 Busy Periods and Alternating Renewal Theory......Page 241
5.4 Supplementary Problems......Page 244
6. THE M/G/1 QUEUEING SYSTEM WITH PRIORITY......Page 250
6.1 M/G/1 Under LCFS-PR Discipline......Page 251
6.2 M/G/1 System Exceptional First Service......Page 254
6.3 M/G/1 under HOL Priority......Page 261
6.3.1 Higher Priority Customers......Page 263
6.3.2 Lower Priority Customers......Page 266
6.4 Ergodic Occupancy Probabilities for Priority Queues......Page 269
6.5 Expected Waiting Times under HOL Priority......Page 271
6.5.1 HOL Discipline......Page 273
6.5.2 HOL-PR Discipline......Page 274
7. VECTOR MARKOV CHAINS ANALYSIS......Page 278
7.1 The M/G/1 and G/M/1 Paradigms......Page 279
7.2 G/M/1 Solution Methodology......Page 284
7.3 M/G/1 Solution Methodology......Page 286
7.4 Application to Statistical Multiplexing......Page 290
7.5 Generalized State Space Approach: Complex Boundaries......Page 303
7.6 Summary......Page 315
7.7 Supplementary Problems......Page 319
8. CLOSING REMARKS......Page 322
References......Page 326
D......Page 334
L......Page 335
O......Page 336
T......Page 337
Z......Page 338
About the Author......Page 340