Preface
This book covers fundamental concepts in queueing and loss models, as wellas simulation methods, with their application to modeling and analysis of computer
systems and communication networks. Modeling and analysis are essential components in the process of designing and dimensioning a computer system or network.
The aim of the book is to provide the reader with state-of-the-art analytical andcomputational tools to evaluate the performance and operating characteristics oftoday’s computer systems and communication networks. The theory and methodologies discussed in this book may be applied to other ﬁelds such as manufacturing,operations research, and industrial engineering.
This volume is an updated and expanded version of an earlier book by theﬁrst author entitled Modeling and Analysis: An Introduction to System Performance Evaluation Methodology published by Addison-Wesley in 1978. The present
book includes more advanced and recent materials on queueing and traﬃc models
in the context of both computing systems and networks. For instance, the generalized Erlang and Engset loss models and loss network theory are discussed for theﬁrst time in a cohesive manner. The book also features an up-to-date treatment ofsimulation methodologies for systems and networks, including an introduction tonetwork simulation packages and recent developments on random number generation.
ORGANIZATION OF THE BOOK
Chapter 1 provides an overview of the scope of the performance evaluation methodologies to be covered in the book. We start with a discussion of the signiﬁcant rolestochastic modeling has played in science and engineering, followed by a brief review of successful “modeling and analysis” eﬀorts in the development of computing
systems and communication networks. The art of performance modeling is illustrated by means of several examples taken from today’s computing systems andnetworks. State-of-the-art practice in performance evaluation is reviewed and thestrengths and limitations of these techniques are discussed.
The remainder of the book is organized into four parts. Part I, “Basic Queueing and Loss Models”, covers the principles of queueing and loss analysis and teletraﬃc theory. Chapter 2 starts with Little’s formula, the most fundamental anduseful formula in queueing analysis, followed by a review of Poisson processes, whichleads to formulation of birth-and-death (BD) queueing models. M/M/1, M/M/∞,and other Markovian queueing models are derived as special cases of the BD queueing models. Chapter 3 introduces the classical loss models studied by Erlang andEngset in telephone engineering a century ago, but they still capture the essenceof connection-oriented network services, be they over wired, wireless, or opticalchannels. Chapter 4 begins with various ways of representing general distributionsof either service time or interarrival time, followed by discussion of the embeddedv

vi

PrefaceMarkov chain technique due to Kendall, as applied to queues in which either thearrival process or the service process is non-Markovian, i.e., M/G/1 and G/M/mqueueing models. Chapter 5 discusses a class of queueing models whose departure
process is shown to be Poisson when the arrival process is Poisson. This importantclass of models is derived by using the notions of quasi-reversibility and symmetricqueues introduced by Kelly. Loss servers (as in the Erlang and Engset loss models), M/G/∞ and M/G/1 with PS (processor-sharing) scheduling, and M/G/1 withLCFS (last-come, ﬁrst-served) with PR (preemptive resume) scheduling fall in thisclass.
In Part II, “Queueing and Loss Networks”, we provide a cohesive treatmentof queueing network models, loss network models, and computational algorithms
associated with these models. Chapter 6 starts with the classical Jackson networkthat has the so-called product-form solution for the joint queue distribution, andthen introduces a more general model, often referred to as the BCMP (Baskett–Chandy–Muntz–Palacios) model. Multiple classes of customers and general routing
behavior are also incorporated into these generalized Jackson-type networks. Chapter 7 addresses the loss system counterparts of the results presented in Chapter 6;
it can also be viewed as a generalization of the classical loss models discussed in
Chapter 3. Chapter 8 provides a comprehensive treatment of eﬃcient computational algorithms to numerically evaluate performance measures associated withqueueing and loss networks.
Part III, “Advanced Queueing Models”, consists of several advanced topics.
Chapter 9 begins with a discussion of some conservation laws due to Kleinrock.
Then, priority queues and the so-called server vacation models are discussed, thelatter being suited for modeling scheduling algorithms involving polling and token passing. Chapter 10 discusses the classical theory of the G/G/1 queue due
to Lindley, followed by the more recent work of Neuts and others on phase-type(PH) distributions and their application to a numerically treatable subset of G/G/1queues, known as PH/PH/1 queues. The notion of quasi-birth-and-death (QBD)
is also discussed.
Queueing theory is generally formulated in the continuous-time setting. However, in such systems as time-slotted and synchronous systems, discrete-time modeling is more appropriate. In Chapter 11, we present Geo/Geo/1 (the discretetime analog of M/M/1), Geo/G/1, discrete-time M/G/∞, and discrete-time G/G/1
models.
In Chapter 12 we treat two diﬀerent types of traﬃc model in which interarrival
times are not independent: one is the class of Markovian traﬃc models, the other isthe class of long-range dependent (LRD) traﬃc models. Empirical studies reported
in the literature have suggested that some Internet and LAN traﬃc exhibit the selfsimilar property, and the theory of fractional Brownian motion (fBM) developedby Mandelbrot provides a mathematical characterization of such non-Markovian
traﬃc.
Chapter 13 is devoted to ﬂuid models and their applications. While the diffusion process approximation characterizes the queue process in terms of the ﬁrst
and second moments of the arrival and departure processes, the ﬂuid approximation
uses only the ﬁrst moment. It is equivalent to treating the movement of customers

Prefacevii(e.g., packets) as the ﬂow of a ﬂuid, ignoring random ﬂuctuations associated with
the irregularity of interarrival and service times. We will ﬁnd ﬂuid models usefulin the analysis of statistical multiplexer models.
The analytic solution of G/G/1 based on Lindley’s theory presented in Chapter 10 requires spectrum decomposition, which in practice may present great diﬃculty except for special cases. Alternatives to the numerical solution technique via
the PH/PH/1 formulation are some bounding and approximation techniques, which
are often extremely simple and insightful. In Chapter 14 we discuss exponentiallytight bounds on both the waiting time distribution and the mean waiting time. The
latter argument can be generalized to the G/G/m queue as well. Heavy traﬃc approximation and diﬀusion process approximation are closely related. Both require
only the ﬁrst two moments of service time and interarrival time distributions. Also
covered in this chapter are diﬀusion approximation of a queueing network, reduced
load approximation in a loss network, and the concept of eﬀective bandwidth.
The last topic of Part III is time-dependent solutions of some queueing models.
The time-dependent solution is generally hard to come by: a closed-form solution
for the time-dependent queue distribution of the M/M/1, the simplest queueing
model, involves modiﬁed Bessel functions! In Chapter 15 we present several diﬀerent
methods for transient analysis of Markovian models—the matrix representation
method, the spectral expansion method, the eigenvector method, and the Laplacetransform method. These solution methods can be shown to be mathematicallyequivalent or closely related to each other. We also show that the diﬀusion andﬂuid approximations often lend themselves to simpler transient analysis.
Part IV, “Simulation Modeling and Analysis”, focuses on implementation
methodologies for discrete-event simulators, and statistical tools for the design andanalysis of simulation experiments. In Chapter 16, basic concepts of discrete-event
simulation are discussed, including the formulation of simulation models and random number generation. Then, simulation languages and environments for more
complex simulation tasks are discussed. We discuss two popular packages for network simulation: a commercial package OPNET and the public-domain software
ns-2. Then three case studies—a single server queue, a queueing network, anda loss network—are presented to illustrate how discrete-event simulators can bedeveloped.
Chapter 17 discusses how a simulation experiment ought to be designed andhow its output data should be analyzed. Basic concepts such as signiﬁcance level
and conﬁdence interval are reviewed. The chapter also discusses some useful practices in analyzing a simulation run. Finally, the chapter discusses a very importantbut seldom practiced technique in simulation experiments, i.e., how to minimize
the simulation run time while maintaining the accuracy of the simulation estimate
at a required level. Eﬃcient simulation is very critical when we model rare events
such as buﬀer overﬂow or packet loss. Various variance reduction techniques as wellas the importance sampling method are discussed.
Appendix A provides a brief exposition of concepts in number theory that areneeded to follow the theory behind the various random number generation methods
discussed in Section 16.5.

viiiPreface

SUGGESTED COURSE PLANS
We assume that the readers or students are familiar with calculus, linear algebra (ormatrix theory), and statistics at the undergraduate level, and probability, randomvariables, and random processes at the ﬁrst-year graduate level. In Appendix A,
we provide a brief review of concepts in number theory, which are pertinent to thetopic of random number generation discussed in Chapter 17.
The book is suitable as a graduate-level textbook, but should also be of interest to researchers concerned with the performance evaluation of computer systems
and networks. As a text the book can be used for a two-semester course sequenceon system performance evaluation. The ﬁrst semester could cover the fundamental
material in Chapters 2 through 8, as well as Chapter 16 on simulation methodology.
The second semester could then cover a selection of material of the advanced topics
from Chapters 9 through 15, as well Chapter 17 on simulation experiments and data
analysis. Alternatively, portions of the book can be covered in a one-semester course.
For example, a one-semester course emphasizing computational methods could comprise Chapters 2 through 8, with selected material from Chapters 9 through 15. A
course emphasizing simulation methods could comprise Chapters 2 through 7, withselected material from Chapters 16 and 17.
At Princeton, the materials in Chapters 2 through 8 and some selected topics of Chapters 9 through 15 have been taught as a part of a graduate course“ELE 531: Communication Networks”. Syllabi for these courses are availableat www.princeton.edu/kobayashi. The students are expected to have taken“ELE525: Random Processes for Information Systems”. Syllabi for these courses
are available at www.princeton.edu/kobayashi. At George Mason University, draft
copies of the book were used in a graduate course “ECE 642: Design and Analysis of Computer Networks”, and the course syllabus can be found at ece.gmu.
edu/~bmark.

Princeton, New Jersey
Fairfax, Virginia
March 2008

Hisashi Kobayashi
Brian L. Mark