TeAM YYePG
Digitally signed by TeAM YYePG
DN: cn=TeAM YYePG, c=US, o=TeAM YYePG,
ou=TeAM YYePG, email=
Reason: I attest to the accuracy and integrity of
this document
Date: 2005.05.26 21:14:08 +08'00'
QUEUEING THEORY WITH
APPLICATIONS TO PACKET
TELECOMMUNICATION
This page intentionally left blank
QUEUEING THEORY WITH
APPLICATIONS TO PACKET
TELECOMMUNICATION
JOHN N. DAIGLE
Prof. of Electrical Engineering
The University of Mississippi
University, MS 38677
Springer
eBook ISBN: 0-387-22859-4
Print ISBN: 0-387-22857-8
Print ©2005 Springer Science + Business Media, Inc.
All rights reserved
No part of this eBook may be reproduced or transmitted in any form or by any means, electronic,
mechanical, recording, or otherwise, without written consent from the Publisher
Created in the United States of America
Boston
©2005 Springer Science + Business Media, Inc.
Visit Springer's eBookstore at:
and the Springer Global Website Online at:

CDMA-Based Cellular Data
1.3
Summary
2.
REVIEW OF RANDOM PROCESSES
2.1
Statistical Experiments and Probability
2.1.1
2.1.2
Statistical Experiments
Conditioning Experiments
2.2
2.3
2.4
2.5
Random Variables
Exponential Distribution
Poisson Process
Markov Chains
3.
ELEMENTARY CTMC-BASED QUEUEING MODELS
3.1
M/M/1 Queueing System
3.1.1
3.1.2
3.1.3
Time-Dependent M/M/1 Occupancy Distribution
Stochastic Equilibrium M/M/1 Distributions
Busy Period for M/M/1 Queueing System
1

3.5
3.6
Balance Equations Approach for Systems in Equilibrium
Probability Generating Function Approach
Supplementary Problems
4.
ADVANCED CTMC-BASED QUEUEING MODELS
4.1
Networks
4.1.1
4.1.2
4.1.3
Feedforward Networks: Fixed Routing
Arbitrary Open Networks
Closed Networks of Single Servers
4.2
Phase-Dependent Arrivals and Service
4.2.1
4.2.2
4.2.3
4.2.4
Probability Generating Function Approach
Matrix Geometric Method
Rate Matrix Computation via Eigenanalysis
Generalized State-Space Methods
4.3
4.4
Phase-Type Distributions
Supplementary Problems
5.

M/G/1 Under LCFS-PR Discipline
M/G/1 System Exceptional First Service
M/G/1 under HOL Priority
81
83
84
88
91
98
101
107
108
109
110
111
122
124
138
143
146
152
156
159
161
165
167
167
170
170
180

7.6
7.7
The M/G/1 and G/M/1 Paradigms
G/M/1 Solution Methodology
M/G/1 Solution Methodology
Application to Statistical Multiplexing
Generalized State Space Approach: Complex Boundaries
Summary
Supplementary Problems
8.
CLOSING REMARKS
References
Index
About the Author
238
241
244
246
248
249
253
254
259
261
265
278
290
294
297
301

length as a parameter.
Comparison between a system serving a fixed number
of 16 units per frame and a system serving a binomial
number of units with an average of 16 at a traffic inten-
sity of 0.9.
Distribution function for the random variable defined
in Example 2.4.
Survivor function for system occupancy for several val-
ues of
Schematic diagram of a single-server queueing system.
Schematic diagram of a simple network of queues.
Sequence of busy and idle periods.
Sequence of service times during a generic busy period.
2
3
4
6
11
14
15
16
29
63
65
76
76
77
xii
QUEUEING THEORY FOR TELECOMMUNICATIONS
3.6

Survivor functions with deterministic, Erlang-2, expo-
nential, branching Erlang and gamma service-time dis-
tributions at
Survivor functions for system occupancy with message
lengths drawn from truncated geometric distributions
at
Survivor functions for system having exponential ordi-
nary and exceptional first service
and as a parameter.
Survivor functions with unit deterministic service and
binomially distributed arrivals with N as a parameter
at
Survivor functions with unit-mean Erlang-10 service
and Poisson arrivals with C as a parameter at a traffic
load of 0.9.
Survivor functions with unit-mean Erlang-K service
and Poisson arrivals with K as a parameter at a traf-
fic load of 0.9.
Survivorfunctions with and Pade(2, 2) ser-
vice, Poisson arrivals, and a traffic load of 0.9.
Survivor functions for deterministic (16) batch sizes
with Pade deterministic service and
Poisson arrivals at a traffic load of 0.9 for various choices
of
79
86
90
92
92
95

proximated by a Pade(32, 32) approximation and Pois-
son arrivals at a traffic load of 0.9.
A sample of service times.
An observed interval of a renewal process.
HOL service discipline.
Survivor functions for occupancy distributions for sta-
tistical multiplexing system with 0.5 to 1.0 speed con-
version at
Survivor functions for occupancy distributions for sta-
tistical multiplexing system with equal line and trunk
capacities at
Survivor functions for occupancy distributions for sta-
tistical multiplexing system with and without line-speed
conversion at
Survivor functions for occupancy distributions for wire-
less communication link with on time as a parameter.
207
208
211
212
237
273
277
278
291
This page intentionally left blank
List of Tables
5.1
5.2
5.3

Mean and second moments of queue lengths for multi-
plexed lines with line speed conversion.
Mean and second moments of queue lengths for multi-
plexed lines with no line speed conversion.
Transition probabilities for the system of Example 7.4.
Major characteristics of the solution process for the
system of Example 7.4.
180
193
197
200
202
204
209
209
269
269
274
277
289
290
This page intentionally left blank
Preface
Soon after Samuel Morse’s telegraphing device led to a deployed electri-
cal telecommunications system in 1843, waiting lines began to form by those
wanting to use the system. At this writing queueing is still a significant factor in
designing and operating communications services, whether they are provided
over the Internet or by other means, such as circuit switched networks.
This book is intended to provide an efficient introduction to the fundamental
concepts and principles underlying the study of queueing systems as they ap-

The minimum prerequisite for this course is an understanding of calculus
and linear algebra. However, we have achieved much better results when the
students have had at least an introductory course in probability. The best re-
sults have been obtained when the students have had a traditional electrical
engineering background, including transform theory, an introductory course in
stochastic processes, and a course in computer communications.
We now present an abbreviated summary of the technical content of this
book. In Chapter 1, we introduce some general terminology from queueing
systems and some elementary concepts and terminology from the general the-
ory of stochastic processes, which will be useful in our study of queueing
systems. The waiting time process for a single-server, first-come-first-serve
(FCFS) queueing system, is discussed. We also demonstrate the application
of queueing analysis to the design of wireless communication systems and IP
switches. In the process, we demonstrate the importance of choosing queue-
ing models that are sufficiently rich to capture the important properties of the
problem under study.
In Chapter 2, we review some of the key results from the theory of ran-
dom processes that are needed in the study of queueing systems. In the first
section, we provide a brief review of probability. We begin with a definition
of the elements of a statistical experiment and conclude with a discussion of
computing event probabilities via conditioning. We then discuss random vari-
ables, their distributions, and manipulation of distributions. In the third and
fourth sections, we develop some of the key properties of the exponential dis-
tribution and the Poisson process. In the fifth section, we review discrete-
and continuous-parameter Markov chains defined on the nonnegative integers.
Our goal is to review and reinforce a subset of the ideas and principles from
the theory of stochastic processes that is needed for understanding queueing
systems. As an example, we review in detail the relationship between discrete-
time and discrete-parameter stochastic processes, which is very important to
the understanding of queueing theory but often ignored in courses on stochastic

state probability mass functions for such systems, which are of the so-called
product form type. We discuss in detail a novel technique, due to Gordon
[1990], for obtaining the normalizing constant for simple closed queueing net-
works in closed form. This technique makes use of generating functions and
contour integration, which are so familiar to many engineers.
Next, we address the solution of a two-dimensional queueing model in
which both the arrival and service rates are determined by the state of a single
independent CTMC. This type of two-dimensional Markov chain is called a
quasi-birth and death process (QBD), which is a vector version of the scalar
birth-death process discussed previously. A number of techniques for solving
such problems are developed. The first approach discussed uses the probabil-
ity generating function approach. We make extensive use of eigenvector-based
analysis to resolve unknown probabilities. Next, the matrix analytic technique
is introduced and used to solve for the state probabilities. A technique based
on solving eigensystems for finding the rate matrix of the matrix geometric
method, which reveals the entire solution, is discussed next. Finally, a gen-
eralized state space approach, which seems to have been introduced first by
Akar et. al [1998], is developed. We show how this technique can be used
efficiently to obtain the rate matrix, thereby complementing the matrix ana-
lytic approach. We then introduce distributions of the phase (PH) type, and
xx
QUEUEING THEORY FOR TELECOMMUNICATIONS
we provide the equilibrium occupancy distribution for the M/PH/1 system in
matrix geometric form. We conclude the chapter with a set of supplementary
exercises.
In Chapter 5, we introduce the M/G/1 queueing system. We begin with a
classical development of the Pollaczek-Khintchine transform equation for the
occupancy distribution. We also develop the Laplace-Stieltjes transforms for
the ergodic waiting time, sojourn time, and busy period distributions.
We next address inversion of probability generating functions. Three meth-

mainder of the chapter to study the M/G/1 queueing system with externally
assigned priorities and head-of-the-line service. Transform equations are de-
veloped for the occupancy, waiting-time and sojourn-time distributions. Inver-
sion of transform equations to obtain occupancy distribution is then discussed.
PREFACE
xxi
Finally, we develop expressions for the average waiting and sojourn times for
the M/G/1 queueing system underboth preemptive and nonpreemptive priority
disciplines.
In Chapter 7 we introduce the G/M/1 and M/G/1 paradigms, which have
been found to be useful in solving practical problems and have been discussed
at length in Neuts’ books. These paradigms are natural extensions of the or-
dinary M/G/1 and G/M/1 systems. In particular, the structure of the one-step
transition probability matrices for the embedded Markov chains for these sys-
tems are simply matrix versions of the one-step transition probability matrices
for the embedded Markov chains of the elementary systems.
In the initial part of the chapter, Markov chains of the M/G/1 and G/M/1
type are defined. The general solution procedure for models of the G/M/1
type and the M/G/1 with simple boundaries are discussed. The application
of M/G/1 paradigm ideas to analysis of statistical multiplexing systems is then
discussed by way of examples. Then, we extend our earlier development of the
generalized state space methods to the case of the Markov chains of the M/G/1
type with complex boundary conditions. The methodology presented there is
relatively new, and we believe our presentation is novel. Because generalized
state-space procedures are relatively new, we attempt to provide a thorough
introduction and reinforce the concepts through an example. Finally, additional
environments where Markov chains of the G/M1 and M/G/1 types surface are
discussed and pointers to descriptions of a variety of techniques are given.
We close in Chapter 8 with a brief discussion of a number of nontraditional
techniques for gaining insights into the behavior of queueing systems. Among

provided the appropriate encouragement to bring the manuscript to completion.
Finally, I am indebted to Katherine Daigle who read numerous drafts and
provided many valuable suggestions to improve organization and clarity. For
all errors and flaws in the presentation, I owe thanks only to myself.