You are here

Fundamentals of Queueing Theory

Donald Gross, John F. Shortle, James M. Thompson, and Carl M. Harris
Publisher: 
John Wiley
Publication Date: 
2008
Number of Pages: 
500
Format: 
Hardcover
Edition: 
4
Series: 
Wiley Series in Probability and Statistics
Price: 
110.00
ISBN: 
9780471791270
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee considers this book essential for undergraduate mathematics libraries.

[Reviewed by
William J. Satzer
, on
03/19/2009
]

This classic mathematical introduction to queueing theory is now in its fourth edition. It has been honed and polished over the years and differs from the third edition only in modest additions and some reorganization. The text is aimed at advanced undergraduates or graduate students in applied probability or operations research. A comparable introduction for engineers or computer scientists is Kleinrock’s Queueing Systems, which focuses more on results than development and is a bit dated now.

Queueing theory is known for its rather distinctive notation. A queueing process is described by a series of symbols and slashes such as A/B/C/D/E where A indicates an inter-arrival time probability distribution, B identifies the distribution for service (or waiting) time, C the number of parallel service channels, D the restrictions on service capacity, and E the queue discipline. So the notation M/D/2/∞/FCFS refers to a queueing process with exponential (the M is for Markov) arrival times, deterministic service time, two parallel service channels, no restrictions on capacity, and first-come, first-served queue discipline. It sounds complicated, but is actually logical and useful. Of course, the most commonly used queueing model is just M/M/1 with exponentially distributed inter-arrival and waiting times. Just imagine waiting to pay for your groceries in a store with only one cashier.

The basics of queueing theory are introduced in the first two chapters. Chapter 1 establishes the background and terminology, provides some tools, and discusses basic (and quite powerful) results like Little’s formula. Simple Markovian queueing models of increasing complexity are taken up in Chapter 2. There is an amusing discussion here of modeling “queues with impatience”. These arise, for example, when a customer is reluctant to join a queue on arrival, doesn’t want to stay in line after joining and waiting, or chooses to jockey between lines when each of a number of parallel lines has its own queue. We have all probably practiced many forms of queue impatience.

The chapter on queues in series is quite an important one. The questions that come up are often difficult but important. The internet is a gigantic combination of queues in tandem, and understanding its performance — even estimating the end-to-end delay for a single packet traveling from your keyboard to its distant destination — is very challenging. The authors describe the major approaches in this field, but they can really only scratch the surface.

This is an accessible and attractive textbook with good writing al the way through. It has the advantage of years of classroom testing. The exercises are extensive and creative.


 

Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.



Dedication.

Preface.

1. Introduction.

1.1 Description of the Queueing Problem.

1.2 Characteristics of Queueing Processes.

1.3 Notation.

1.4 Measuring System Performance.

1.5 Some General Results.

1.6 Simple Data Bookkeeping for Queues.

1.7 Poisson Process and the Exponential Distribution.

1.8 Markovian Property of the Exponential Distribution.

1.9 Stochastic Processes and Markov Chains.

Problems.

2. Simple Markovian Queueing Models.

2.1 Birth Death Processes.

2.2 Single-Server Queues (M/M/1).

2.3 Multi-Server Queues (M/M/c).

2.4 Choosing the Number of Servers.

2.5 Queues with Truncation (M/M/c/K).

2.6 Erlang?s Loss Formula (M/M/c/c).

2.7 Queues with Unlimited Service (M/M/1).

2.8 Finite Source Queues.

2.9 State-Dependent Service.

2.10 Queues with Impatience.

2.11 Transient Behavior.

2.12 Busy-Period Analysis.

Problems.

3. Advanced Markovian Queueing Models.

3.1 Bulk Input (M[X]/M/1).

3.2 Bulk Service (M/M[Y ]/1).

3.3 Erlangian Models.

3.4 Priority Queue Disciplines.

3.5 Retrial Queues.

4. Networks, Series, and Cyclic Queues.

4.1 Series Queues.

4.2 Open Jackson Networks.

4.3 Closed Jackson Networks.

4.4 Cyclic Queues.

4.5 Extensions of Jackson Networks.

4.6 Non-Jackson Networks.

5. General Arrival or Service Patterns.

5.1 General Service, Single Server (M/G/1).

5.2 General Service, Multi-Server (M/G/c/ú, M/G/1).

5.3 General Input (G/M/1, G/M/c).

6. More General Models and Theoretical Topics.

6.1 G/Ek/1, G[k]/M/1, and G/PHk/1.

6.2 General Input, General Service (G/G/1) .

6.3 Multichannel Queues with Poisson Input and Constant Service (M/D/c).

6.4 Semi-Markov and Markov Renewal Processes in Queueing.

6.5 Other Queue Disciplines.

6.6 Design and Control of Queues.

6.7 Statistical Inference in Queueing.

7. Bounds and Approximations.

7.1 Bounds.

7.2 Approximations.

7.3 Network Approximations.

Problems.

8. Numerical Techniques and Simulation.

8.1 Numerical Techniques.

8.2 Numerical Inversion of Transforms.

8.3 Discrete-Event Stochastic Simulation.

Problems.

Bibliography.

Appendix 1. Symbols and Abbreviations.

Appendix 2. Tables.

Appendix 3. Transforms and Generating Functions.

A3.1 Laplace Transforms.

A3.2 Generating Functions.

Appendix 4. Differential and Difference Equations.

A4.1 Ordinary Differential Equations.

A4.2 Difference Equations.

Appendix 5. QTSPlus Software.

A5.1 Instructions for Downloading.