14
$\begingroup$

Can someone recommend a good self-study textbook for queueing theory and performance modeling? My interest is in applying this to understanding the behavior of some real-world server networks, predicting what loads they can handle, etc.

I have a strong background in probability theory, stats, and graphical models, and familiarity with survival models, Poisson processes, and Markov chains, but don't know a lot about queueing theory, renewal processes, or how to efficiently simulate queueing networks.

$\endgroup$
7
$\begingroup$

Unfortunately, much of the performance analysis and transient approximations for time-varying systems with non-Markovian (non-exponential) properties are not easily obtained in book form (see note at bottom).

This answer lists some books that don't require measure theory.

Some Queueing & Renewal theory books: (non-measure theoretic)

  • Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling by William J. Stewart (Princetion University Press).[1]

    Includes an impressive amount on various queues & queueing networks.

  • Introduction to Probability Models by Sheldon M. Ross (Academic Press).[2]

    Ross is anything but an "introduction" but is widely used for its body of examples. Unfortunately, the type-setting is terrible and makes it difficult to distinguish between key points, theorems, examples, etc., at a glance. Includes queues, queueing networks, & renewal processes.

  • Stochastic Processes by Sheldon M. Ross (Wiley).[3]

    This covers renewal theory in greater depth. (Full text)

Some relevant Simulation books:

  • Simulation Modeling & Analysis by Averill M. Law (McGraw-Hill).[4]
  • Simulation by Sheldon M. Ross (Academic Press).[5]

Note: If relevant to the OP, I can add resources for time-varying systems with non-Markovian (non-exponential) properties, to include recent surveys.

Reference
[1] ISBN: 978-1400832811 or here
[2] ISBN: 978-0128143469
[3] ISBN: 978-0471120629 or (full text)
[4] ISBN: 978-0073401324 or here
[5] ISBN: 978-0124158252

$\endgroup$
  • $\begingroup$ Thanks, this is useful. I do expect to be dealing with arrivals whose rate exhibits a spiky behavior -- a moderate background rate of arrivals punctuated by short spikes of much higher arrival rate -- and I can handle measure theory, so I would be interested in the additional resources you mentioned. $\endgroup$ – Kevin S. Van Horn Aug 15 '19 at 18:51
4
$\begingroup$

I have used Stochastic Modeling: Analysis and Simulation by Barry Nelson and found it to be a pretty gentle introduction. It covers stochastic processes, queuing, and simulation.

$\endgroup$
4
$\begingroup$

I enjoyed Performance Modeling and Design of Computer Systems: Queueing Theory in Action (Amazon link) by Mor Harchol-Balter, which sounds like it fits your bill pretty well. I have it on my desk.

ISBN-13: 978-1107027503

$\endgroup$
2
$\begingroup$

Introduction to queueing theory and stochastic teletraffic models$^1$.

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 modeling, performance evaluation, resource provisioning, and traffic management. These research areas are included in a field called teletraffic.

Introduction to queueing theory$^2$.

This book is one of the best introductory books in the field, the good thing about this book is, the video lectures of Prof. Cooper can be found on the net and you can easily follow the book base on the lectures.

An introduction to queueing theory: modeling and analysis in applications$^3$.

With an emphasis on modeling and analysis this book deals with topics such as identification of models, collection of data, and tests for stationarity and independence of observations. It provides a rigorous treatment of basic models commonly used in applications with references for advanced topics. It gives a comprehensive discussion of statistical inference techniques usable in the modeling of queueing systems and an introduction to decision problems in their management. The book also includes a chapter, written by computer scientists, on the use of computational tools and simulation in solving queueing theory problems.

Markov Chains: Models, Algorithms and Applications$^4$.

The mentioned two chapters are very good examples of modeling: Chapter 2 discusses the applications of continuous-time Markov chains to model queueing systems and discrete-time Markov chain for computing the PageRank, the ranking of websites on the Internet. Chapter 3 studies Markovian models for manufacturing and re-manufacturing systems and presents closed-form solutions and fast numerical algorithms for solving the captured systems.

Queues A Course in Queueing Theory$^5$.

The first three chapters focus on the needed preliminaries, including exposition distributions, Poisson processes and generating functions, renewal theory, and Markov chains, Then, rather than switching to first-come-first-served memoryless queues here as most texts do, Haviv discusses the M/G/1 model instead of the M/M/1, and then covers priority queues. Later chapters cover the G/M/1 model, thirteen examples of continuous-time Markov processes, open networks of memoryless queues and closed networks, queueing regimes with insensitive parameters, and then concludes with two-dimensional queueing models which are quasi birth and death processes. Each chapter ends with exercises.

References:

1) Zukerman, Moshe. "Introduction to queueing theory and stochastic teletraffic models." arXiv preprint arXiv:1307.2968 (2013).

2) Cooper, Robert B. Introduction to queueing theory. North Holland, 1981.

3) Bhat, U. Narayan. An introduction to queueing theory: modeling and analysis in applications. Birkhäuser, 2015.

4) Ching, Wai-Ki, and Michael K. Ng. "Markov chains." Models, algorithms and applications (2006).

5) Haviv, Moshe. Queues: A Course in Queueing Theory. Vol. 191. Springer Science & Business Media, 2013.

$\endgroup$
2
$\begingroup$

I learned from Quantitative System Performance Computer System Analysis Using Queueing Network Models by Lazowska, et.al. Unfortunately, it is no longer published, but it is available for free online. It may seem a bit out of date today but it is considered the classic for queueing network analysis of computer performance.

It does not really cover the areas of simulation much (it focuses on MVA rather than either convolution or simulation), or general operations research, but once you've read this, you should be able to easily move to and apply it to those.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.