An Introduction to Queueing Systems

by Sanjay K. Bose

Overview

Queueing is an aspect of modern life that we encounter at every step in our daily activities. Whether it happens at the checkout counter in the supermarket or in accessing the Internet, the basic phenomenon of queueing arises whenever a shared facility needs to be accessed for service by a ]arge number of jobs or customers. The study of queueing is important as it gravides both a theoretical background to the kind of service that we may expect from such a facility and the way in which the facility itself may be designed to provide some specified grade of service to its customers. Our study of queueing was basically motivated by its use in the study of communication systems and computer networks. The various computers, routers and switches in such a network may be modelled as individual queues. The whole system may itself be modelled as a queueing network providing the required service to the messages, packets or cells that need to be carried. Application of queueing theory provides the theoretical framework for the design and study of such networks. The purpose of this book is to support a course on queueing systems at the senior undergraduate or graduate Ievels. Such a course would then provide the theoretical background on which a subsequent course on the performance modeHing and analysis of computer networks may be based.

Product Details

ISBN-13:	9780306467349
Publisher:	Springer US
Publication date:	12/31/2001
Edition description:	2002
Pages:	288
Product dimensions:	6.14(w) x 9.21(h) x 0.03(d)

Table of Contents

	List of Figures	xv
1.	Introduction	1
1.1	Queueing Model Parameters	2
1.2	A Simple Queueing Model	3
1.3	Some Basic Queueing Models	7
1.4	A Summary of the Contents	7
2.	Basic Queueing Theory: Fundamentals of Analyzing Single Queues	9
2.1	Markov Processes and Markov Chains	9
2.2	Birth-Death Processes	15
2.3	Kendall's Notation for Queues	20
2.4	Little's Result	22
2.5	Equilibrium Solutions for M/M/-/- Queues	23
2.6	Delay Analysis for FCFS M/M/1/[infinity] and M/M/m/[infinity] Queues	34
2.7	Departure Process from a M/M/m/[infinity] Queue	38
2.8	Time Reversibility Property of Irreducible, Aperiodic Markov Chains	40
2.9	The Method of Stages for Solving a M/-/1/[infinity] FCFS Queue	41
2.10	Queues with Bulk (or Batch) Arrivals	45
	Problems	49
3.	Analysis of the M/G/1 Queue in Equilibrium: Performance Analysis Using Residual Life and Imbedded Markov Chain Approaches	55
3.1	The Residual Life Approach for Analysing the M/G/1 Queue	57
3.2	The Imbedded Markov Chain Approach for Analysing the M/G/1 Queue	64
3.3	Distributions of Time Spent in System and the Waiting Time Prior to Service in a FCFS M/G/1 Queue	70
3.4	Busy Period Analysis of a M/G/1 Queue	72
3.5	Delay Analysis for a LCFS M/G/1 Queue	76
3.6	The M/D/1 Queue	79
3.7	Alternative Derivation for the Delays in a FCFS M/G/1 Queue	81
	Problems	86
4.	Advanced Queueing Theory: Vacations, Bulk Arrivals and Priorities in a M/G/1 Queue and the Geo/G/1 Queue	89
4.1	M/G/1 Queue with Vacations	90
4.2	M/G/1 Queue with Only One Vacation after Idle	97
4.3	M/G/1 Queue with Exceptional First Service	98
4.4	M[superscript [X]/G/1 Queue - Single Server Queue with Batch Arrivals	101
4.5	Single Server M/G/1 Priority Queues	106
4.6	The Discrete Time Geo/G/1 and Geo[superscript [X]/G/1 Queues	127
	Problems	140
5.	Fundamentals of Queueing Networks: Open and Closed Networks with Product-Form Solutions	143
5.1	Classification of Different Types of Queueing Networks	145
5.2	Probabilistic Routing in a Queueing Network	148
5.3	Open Networks of M/M/m Type Queues and Jackson's Theorem	150
5.4	Extensions to Jackson's Theorem for Other Open Networks	161
5.5	Closed Queueing Networks	164
5.6	Convolution Algorithm for Finding the Normalisation Constant for a Closed Queueing Network	172
5.7	Mean Value Analysis (MVA) Algorithm for a Closed Queueing Network	174
5.8	Analysis of a Sample Closed Network Using Convolution and MVA Algorithms	181
5.9	Norton's Theorem for Closed Queueing Networks	184
	Problems	189
6.	Advanced Queueing Networks: Approximation Techniques for Open and Closed Queueing Networks	193
6.1	Mixed Queueing Networks	193
6.2	The GI/G/m Approximation for the Approximate Analysis of Open Queueing Networks (the QNA Technique)	198
6.3	Fork/Join Queues in Open and Closed Networks of Infinite Capacity Queues	211
6.4	Models of Blocking in Open and Closed Networks of Finite Capacity Queues	218
6.5	Approximate Analytical Methods for Solving Closed Networks of Finite Capacity Queues	221
6.6	Approximate Analytical Methods for Solving Open Networks of Finite Capacity Queues	234
Appendix 6.1	The Generalised Exponential Distribution	254
7.	Simulation Techniques for Queues and Queueing Networks: Basic Principles for the Design of Queueing Simulators	257
7.1	Simulation Model of a Real World System	258
7.2	Discrete Event Simulation	263
7.3	Collecting and Processing Simulator Outputs for Queues	268
7.4	Estimation of Confidence Intervals and Confidence Levels	271
7.5	Transient Behaviour and the Warm-up Interval	274
7.6	Data Collection in Steady State Conditions	275
Appendix 7.1	Generating Random Numbers	280
	References	283
	Index	285

Editorial Reviews

Bose (Indian Institute of Technology, India) intends this work to be used as a textbook for a senior undergraduate or graduate course on queuing systems. Such a course would provide a theoretical background for a subsequent course on the performance modeling and analysis of computer networks. Chapters cover the equilibrium solutions of basic queues that may be analyzed using birth-death models, single server queues with Poisson arrivals and general service time distributions, and queuing algorithms. Annotation c. Book News, Inc., Portland, OR (booknews.com)