Sample-Path Analysis of Queueing Systems

by El-Taha, Muhammad; Stidham, Shaler, Jr.

• ISBN13: 9780792382102
• ISBN10: 0792382102
• Format: Hardcover
• Copyright: 1999-01-01
• Publisher: Kluwer Academic Pub

Summary

Sample-Path Analysis of Queueing Systems uses a deterministic (sample-path) approach to analyze stochastic systems, primarily queueing systems and more general input-output systems. Among other topics of interest it deals with establishing fundamental relations between asymptotic frequencies and averages, pathwise stability, and insensitivity. These results are utilized to establish useful performance measures. The intuitive deterministic approach of this book will give researchers, teachers, practitioners, and students better insights into many results in queueing theory. The simplicity and intuitive appeal of the arguments will make these results more accessible, with no sacrifice of mathematical rigor. Recent topics such as pathwise stability are also covered in this context. The book consistently takes the point of view of focusing on one sample path of a stochastic process. Hence, it is devoted to providing pure sample-path arguments. With this approach it is possible to separate the issue of the validity of a relationship from issues of existence of limits and/or construction of stationary framework. Generally, in many cases of interest in queueing theory, relations hold, assuming limits exist, and the proofs are elementary and intuitive. In other cases, proofs of the existence of limits will require the heavy machinery of stochastic processes. The authors feel that sample-path analysis can be best used to provide general results that are independent of stochastic assumptions, complemented by use of probabilistic arguments to carry out a more detailed analysis. This book focuses on the first part of the picture. It does however, provide numerous examples that invoke stochastic assumptions, which typically are presented at the ends of the chapters.

Table of Contents

Preface	ix
1. INTRODUCTION AND OVERVIEW	1	(34)
1.1 Introduction	1	(3)
1.2 Elementary Properties of Point Processes: Y = Lambda X	4	(5)
1.3 Little's Formula: L = Lambda W	9	(6)
1.4 Stability and Imbedded Properties of Input-Output Systems	15	(10)
1.4.1 Rate Stability of the G/G/c Queue	19	(1)
1.4.2 Arrival/Departure Point Frequencies	19	(2)
1.4.3 Asymptotic Frequencies of a Process with Imbedded Point Process	21	(4)
1.5 Busy-Period Analysis	25	(3)
1.6 Conditional Properties of Queues	28	(5)
1.6.1 Multiserver Queues with Finite Buffers	30	(3)
1.7 Comments and References	33	(2)
2. BACKGROUND AND FUNDAMENTAL RESULTS	35	(16)
2.1 Introduction	35	(1)
2.2 Background on Point Processes: Y = Lambda X	36	(4)
2.3 Cumulative Processes	40	(3)
2.4 Rate-Conservation Law	43	(2)
2.5 Fundamental Lemma of Maxima	45	(1)
2.6 Time-Averages and Asymptotic Frequency Distributions	46	(4)
2.7 Comments and References	50	(1)
3. PROCESSES WITH GENERAL STATE SPACE	51	(30)
3.1 Introduction	51	(1)
3.2 Relations between Frequencies for a Process with an Imbedded Point Process	52	(12)
3.2.1 Characterization of ASTA and Related Properties	55	(3)
3.2.2 Inverse-Rate Formula and Transition-Rate-Balance Equations	58	(2)
3.2.3 Forward and Backward Recurrence Times	60	(4)
3.3 Applications to the G/G/1 Queue	64	(4)
3.4 Relations between Frequencies for a Process with an Imbedded Cumulative Process (Fluid Model)	68	(2)
3.5 Martingale ASTA	70	(9)
3.5.1 Definitions and Notation	71	(1)
3.5.2 Discrete-Time Model	72	(3)
3.5.3 Continuous-Time Model	75	(4)
3.6 Comments and References	79	(2)
4. PROCESSES WITH COUNTABLE STATE SPACE	81	(36)
4.1 Introduction	81	(1)
4.2 Basic Relations	82	(12)
4.3 Networks of Queues: The Arrival Theorem	94	(4)
4.4 One-Dimensional Input-Output Systems	98	(7)
4.5 Applications to Stochastic Models	105	(8)
4.6 Relation to Operational Analysis	113	(2)
4.7 Comments and References	115	(2)
5. SAMPLE-PATH STABILITY	117	(42)
5.1 Introduction	117	(2)
5.2 Characterization of Stability	119	(6)
5.3 Rate Stability for Multiserver Models	125	(15)
5.3.1 Busy Period Fluctuations	131	(1)
5.3.2 Applications to Multiserver Queues	132	(8)
5.4 Rate Stability for Single-Server Models	140	(4)
5.4.1 Busy Period Fluctuations	141	(2)
5.4.2 Applications to Stochastic Models	143	(1)
5.5 Omega-Rate Stability	144	(12)
5.5.1 Characterization of Omega-Rate-Stability	145	(3)
5.5.2 Omega-Rate Stability Conditions	148	(4)
5.5.3 Applications	152	(4)
5.6 Comments and References	156	(3)
6. LITTLE'S FORMULA AND EXTENSIONS	159	(54)
6.1 Introduction	159	(2)
6.2 Little's Formula: L = Lambda W	161	(9)
6.3 Little's Formula for Stable Queues	170	(2)
6.3.1 The Single-Server Case	170	(1)
6.3.2 The Multiserver Case	171	(1)
6.4 Generalization of Little's Formula: H = Lambda G	172	(10)
6.4.1 Approach Based on L = Lambda W	173	(5)
6.4.2 Alternative Approach	178	(4)
6.5 Fluid Version of Little's Formula	182	(8)
6.5.1 FIFO Discipline	188	(1)
6.5.2 Fluid Version of Little's Formula for Stable Queues	189	(1)
6.6 Fluid Version of H = Lambda G	190	(3)
6.6.1 Necessary and Sufficient Conditions	192	(1)
6.7 Generalization of H = Lambda G	193	(5)
6.8 Applications to Stochastic Models	198	(13)
6.8.1 Application to Strictly Stationary Systems	198	(2)
6.8.2 Comparison Between Sample-Path and RMPP Versions of H = Lambda G	200	(2)
6.8.3 Non-Ergodic Systems: Differences between Sample-Path and RMPP Versions	202	(2)
6.8.4 Relations between Workload and Waiting Time; Mean-Value Analysis; Conservation Laws	204	(7)
6.9 Comments and References	211	(2)
7. INSENSITIVITY OF QUEUEING NETWORKS	213	(22)
7.1 Introduction	213	(1)
7.2 Preliminary Result	214	(2)
7.3 Definitions and Assumptions	216	(3)
7.4 Infinite Server Model	219	(7)
7.5 Erlang Loss Model	226	(3)
7.6 Round Robin Model	229	(3)
7.7 Comments and References	232	(3)
8. SAMPLE-PATH APPROACH TO PALM CALCULUS	235	(13)
8.1 Introduction	235	(1)
8.2 Two Basic Results	236	(4)
8.2.1 Application to Processes with Imbedded Point Processes	239	(1)
8.3 Extended Results	240	(6)
8.3.1 Imbedded Point Process	241	(4)
8.3.2 Neveu's Exchange Formula	245	(1)
8.4 Relation to Stochastic Models	246	(1)
8.5 Comments and References	247	(1)
Appendices	248	(27)
A-Ergodic Theory and Random Marked Point Processes	249	(14)
A.1 Introduction	249	(1)
A.2 Strong Law of Large Numbers	249	(2)
A.3 The Ergodic Theorem in Discrete Time	251	(3)
A.4 The Ergodic Theorem in Continuous Time	254	(2)
A.5 Stationary Marked Point Processes	256	(6)
A.6 Comments and References	262	(1)
B-Limit Theorems for Markov and Regenerative Processes	263	(6)
B.1 Markov Processes	263	(1)
B.1.1 Discrete-Time Markov Chains	263	(2)
B.1.2 Continuous-Time Markov Chain	265	(1)
B.2 Regenerative Processes	266	(1)
B.2.1 Continuous-Time Regenerative Processes	266	(1)
B.2.2 Discrete-Time Regenerative Processes	267	(2)
C-Stability in Stochastic Models	269	(6)
C.1 Introduction	269	(1)
C.2 Markov Processes	269	(1)
C.3 Regenerative Processes	270	(1)
C.4 Stationary Processes	270	(2)
C.5 Other Models and Definitions of Stability	272	(3)
References	275	(18)
Index	293