Introduction to Queueing Theory and Stochastic Teletraffic Models
by Moshe Zukerman
Copyright M. Zukerman c ° 2000–2008
Preface
The aim of this textbook is to provide students with basic knowledge of stochastic models that
may apply to telecommunications research areas such as traffic modelling, resource provisioning
and traffic management. These study areas are often collectively called teletraffic. This book
assumes prior knowledge of a programming language, mathematics, probability and stochastic
processes normally taught in an electrical engineering course. For students who have some but
not sufficiently strong background in probability and stochastic processes, we provide, in the
first few chapters, a revision of the relevant concepts in these areas.
The book aims to enhance intuitive and physical understanding of the theoretical concepts it
introduces. The famous mathematician Pierre-Simon Laplace is quoted to say that “Probability
is common sense reduced to calculation” [12]; as the content of this book falls under the field
of applied probability, Laplace’s quote very much applies. Accordingly, the book aims to link
intuition and common sense to the mathematical models and techniques it uses.
A unique feature of this book is the considerable attention given to guided projects involving
computer simulations and analyzes. By successfully completing the programming assignments,
students learn to simulate and analyze stochastic models such as queueing systems and net-
works and by interpreting the results, they gain insight into the queueing performance effects
and principles of telecommunications systems modelling. Although the book, at times, pro-
vides intuitive explanations, it still presents the important concepts and ideas required for the
understanding of teletraffic, queueing theory fundamentals and related queueing behavior of
telecommunications networks and systems. These concepts and ideas form a strong base for
the more mathematically inclined students who can follow up with the extensive literature on
probability models and queueing theory. A small sample of it is listed at the end of this book.
As mentioned above, the first two chapters provide a revision of probability and stochastic
processes topics relevant to the queueing and teletraffic models of this book. The content
of these chapters is mainly based on [12, 20, 52, 54, 55, 56]. These chapters are intended for
students who have some background in these topics. Students with no background in probability
and stochastic processes are encouraged to study the original textbooks that include far more
explanations, illustrations, discussions, examples and homework assignments. For students with
background, we provide here a summary of the key topics with relevant homework assignments
that are especially tailored for understanding the queueing and teletraffic models discussed in
later chapters. Chapter 3 discusses general queueing notation and concepts and it should beQueueing Theory and Stochastic Teletraffic Models c ° Moshe Zukerman 2
studied well. Chapter 4 aims to assist the student to perform simulations of queueing systems.
Simulations are useful and important in the many cases where exact analytical results are not
available. An important learning objective of this book is to train students to perform queueing
simulations. Chapter 5 provides analyses of deterministic queues. Many queueing theory books
tend to exclude deterministic queues; however, the study of such queues is useful for beginners
in that it helps them better understand non-deterministic queueing models. Chapters 6 – 12
provide analyses of a wide range of queueing and teletraffic models that fall under the category
of continuous-time Markov-chain processes. Chapter 13 provides an example of a discrete-time
queue that is modelled as a discrete-time Markov-chain. In Chapter 14, various aspects of a
single server queue with Poisson arrivals and general service times are studied, mainly focussing
on mean value results as in [11]. Then, in Chapter 15, some selected results of a single server
queue with a general arrival process and general service times are provided. Next, queueing
networks are discussed in Chapter 16. Finally, in Chapter 17, stochastic processes that have
been used as traffic models are discussed with special focus on their characteristics that affect
queueing performance.
Throughout the book there is an emphasis on linking the theory with telecommunications
applications as demonstrated by the following examples. Section 1.18 describes how properties
of Gaussian distribution can be applied to link dimensioning. Section 6.4 shows, in the context of
an M/M/1 queueing model, how optimally to set a link service rate such that delay requirements
are met and how the level of multiplexing affects the spare capacity required to meet such delay
requirement. An application of M/M/∞ queueing model to a multiple access performance
problem [11] is discussed in Section 7.5. In Sections 8.5 and 9.4, discussions on dimensioning
and related utilization issues of a multi-channel system are presented. Section 16.3 guides the
reader to simulate a mobile cellular network. Section 17.6 describes a traffic model applicable
to the Internet.