Fundamentals of Queueing Networks

by Chen, Hong; Yao, David D.

• ISBN13: 9780387951669
• ISBN10: 0387951660
• Format: Hardcover
• Copyright: 2001-07-01
• Publisher: Springer Verlag

Summary

This timely and synoptic text contains the essentials of queueing networks, from the classical product-form theory to the more recent developments such as diffusion and fluid limits, stochastic comparisons, stability, dynamic scheduling, and optimization.Written by two leading experts in stochastic models and applied probability, the book is based on the authors' lecture notes accumulated over many years of teaching queueing networks. The selection of materials is well-balanced in breadth and depth, making the book an ideal graduate-level text for students in engineering, business, applied mathematics, and probability and statistics. As queueing networks have become widely used as a basic model of many physical systems in a diverse range of fields, from supply chains to communication networks, the book is also a useful reference for researchers and practitioners in industrial engineering, operations research and management, computer systems, telecommunications, and related fields.

Table of Contents

Preface	vii
List of Figures	xv
List of Tables	xvii
Birth-Death Queues	1	(14)
Basics	1	(3)
Time Reversibility	4	(4)
Stochastic Orders	8	(3)
Notes	11	(1)
Exercises	11	(4)
References	13	(2)
Jackson Networks	15	(22)
Open Network	16	(3)
Closed Network	19	(2)
Semiopen Network	21	(2)
Throughput Function	23	(2)
Throughput Computation	25	(3)
Convolution Algorithm	26	(1)
Mean Value Analysis	27	(1)
Time Reversal	28	(4)
Notes	32	(1)
Exercises	33	(4)
References	35	(2)
Stochastic Comparisons	37	(32)
Monotonicity	38	(8)
PF2 Property	38	(1)
Likelihood Ratio Ordering	39	(3)
Shifted Likelihood Ratio Ordering	42	(4)
Concavity and Convexity	46	(3)
Multiple Servers	49	(3)
Resource Sharing	52	(4)
Aggregation of Servers	52	(1)
Aggregation of Nodes	53	(3)
Arrangement and Majorization	56	(5)
Notes	61	(2)
Exercises	63	(6)
References	65	(4)
Kelly Networks	69	(28)
Quasi-Reversible Queues	70	(6)
Symmetric Queues	76	(5)
Phase-Type Distributions and Processes	76	(1)
Multiclass M / P H / 1 Queue	77	(4)
A Multiclass Network	81	(6)
Poisson Flows	87	(2)
Arrival Theorems	89	(2)
Notes	91	(2)
Exercises	93	(4)
References	95	(2)
Technical Desiderata	97	(28)
Convergence and Limits	98	(2)
Some Useful Theorems	100	(2)
Brownian Motion	102	(4)
Two Fundamental Processes	106	(2)
Limit Theorems for the Two Fundamental Processes	108	(6)
Functional Strong Law of Large Numbers	109	(1)
Functional Central Limit Theorem	110	(1)
Functional Law of the Iterated Logarithm	111	(1)
Functional Strong Approximation	112	(2)
Exponential Rate of Convergence	114	(2)
Notes	116	(1)
Exercises	117	(8)
References	123	(2)
Single-Station Queues	125	(34)
Queue-Length and Workload Processes	126	(1)
One-Dimensional Reflection Mapping	127	(8)
Fluid Limit (FSLLN)	135	(3)
Diffusion Limit (FCLT)	138	(4)
Approximating the G / G / 1 Queue	142	(2)
Functional Law of the Iterated Logarithm	144	(2)
Strong Approximation	146	(5)
Exponential Rate of Convergence	151	(2)
Notes	153	(1)
Exercises	154	(5)
References	157	(2)
Generalized Jackson Networks	159	(56)
The Queueing Network Model	160	(4)
Oblique Reflection Mapping	164	(3)
A Homogeneous Fluid Network	167	(5)
A Reflected Brownian Motion	172	(3)
Approximating the Network	175	(4)
Functional Law of the Iterated Logarithm	179	(4)
Strong Approximation	183	(3)
Fluid Limit (FSLLN)	186	(2)
Diffusion Limit (FCLT)	188	(8)
Closed Networks	196	(8)
Reflection Mapping, Fluid Model, and RBM	196	(4)
Approximating a Generalized Closed Network	200	(1)
Fluid Limit (FSLLN)	201	(1)
Diffusion Limit (FCLT)	202	(2)
Notes	204	(2)
Exercises	206	(9)
References	213	(2)
A Two-Station Multiclass Network	215	(44)
Model Description and Motivation	215	(5)
A Fluid Model with Priorities	220	(7)
Stability	227	(6)
Fluid Limit	233	(3)
Diffusion Limit	236	(7)
More Examples	243	(4)
Notes	247	(3)
Exercises	250	(9)
References	255	(4)
Feedforward Networks	259	(40)
The Single Station Model	260	(3)
FLIL: The Single Station Case	263	(4)
Strong Approximation: The Single Station Case	267	(7)
The Feedforward Network Model	274	(4)
Primitive Data and Assumptions	274	(3)
Performance Measures and Dynamics	277	(1)
FLIL: The Network Case	278	(1)
Strong Approximation: The Network Case	279	(6)
Performance Analysis and Approximations	285	(2)
Numerical Examples	287	(4)
A Single Station with Two Job Classes	287	(2)
Two Stations in Tandem	289	(2)
Notes	291	(3)
Exercises	294	(5)
References	297	(2)
Brownian Approximations	299	(38)
The Queueing Network Model	300	(5)
Natation and Conventions	300	(2)
The Primitive Processes	302	(1)
The Derived Processes	303	(2)
Two-Moment Characterization of Primitive Processes	305	(3)
The SRBM Approximation	308	(5)
Discussions and Variations	313	(5)
Issues Surrounding the SRBM	313	(2)
Kumar-Seidman Network	315	(1)
State-Space Collapse	316	(2)
Stationary Distribution of the SRBM	318	(2)
Special Cases and Numerical Results	320	(7)
A Single-Class Queue with Breakdown	320	(1)
A Variation of the Bramson Network	321	(4)
A More Complex Multiclass Network	325	(2)
Notes	327	(4)
Exercises	331	(6)
References	333	(4)
Conservation Laws	337	(38)
Polymatroid	338	(4)
Definitions and Properties	338	(2)
Optimization	340	(2)
Conservation Laws	342	(7)
Polymatroid Structure	342	(2)
Examples	344	(3)
Optimal Scheduling	347	(2)
Generalized Conservation Laws	349	(4)
Definition	349	(2)
Examples	351	(2)
Extended Polymatroid	353	(7)
Equivalent Definitions	353	(2)
Connections to Sub/Supermodularity	355	(5)
Optimization over EP	360	(4)
Notes	364	(2)
Exercises	366	(9)
References	369	(6)
Scheduling of Fluid Networks	375	(26)
Problem Formulation and Global Optimality	375	(3)
The Myopic Procedure via LP	378	(2)
Properties of the Myopic Procedure	380	(5)
Termination Rules	380	(2)
Stability and Clearing Time	382	(3)
The Single-Station Model	385	(6)
Description of the Solution Procedure	385	(3)
Summary of the Algorithm	388	(2)
Remarks	390	(1)
Proof of Global Optimality: Single-Station Model	391	(4)
Notes	395	(1)
Exercises	396	(5)
References	399	(2)
Index	401