Delayed and Network Queues

Preface xi

1 Preliminaries 1

1.1 Basics of Probability, 1

1.1.1 Introduction, 1

1.1.2 Conditional Probability, 2

1.2 Discrete Random Variables and Distributions, 4

1.3 Discrete Moments, 8

1.4 Continuous Random Variables, Density, and Cumulative Distribution Functions, 13

1.5 Continuous Random Vector, 17

1.6 Functions of Random Variables, 19

1.7 Continuous Moments, 23

1.8 Difference Equations, 25

1.8.1 Introduction, 25

1.8.2 Basic Definitions and Properties, 25

1.9 Methods of Solving Linear Difference Equations with Constant Coefficients, 27

1.9.1 Characteristic Equation Method, 27

1.9.2 Recursive Method, 29

1.9.3 Generating Function Method, 30

1.9.4 Laplace Transform Method, 32

Exercises, 36

2 Stochastic Processes 39

2.1 Introduction and Basic Definitions, 39

2.2 Markov Chain, 43

2.2.1 Classification of States, 53

2.3 Markov Process, 58

2.3.1 Markov Process with Discrete Space State, 58

2.4 Random Walk, 61

2.5 Up-and-Down Biased Coin Design as a Random Walk, 69

Exercises, 75

3 Birth and Death Processes 77

3.1 Overviews of the Birth and Death Processes, 77

3.2 Finite B-D Process, 86

3.3 Pure Birth Process (Poisson Process), 94

3.4 Pure Death Process (Poisson Death Process), 96

Exercises, 97

4 Standard Queues 101

4.1 Introduction of Queues (General Birth and Death Process), 101

4.1.1 Mechanism, Characteristics, and Types of Queues, 103

4.2 Remarks on Non-Markovian Queues, 108

4.2.1 Takacs's Waiting Time Paradox, 108

4.2.2 Virtual Waiting Time and Takacs's Integro-Differential Equation, 109

4.2.3 The Unfinished Work, 113

4.3 Stationary M/M/1 Queueing Process, 116

4.4 A Parallel M/M/C/K with Baking and Reneging, 119

4.5 Stationary M/M/1/K Queueing Process, 120

4.6 Busy Period of an M/M/1/K Queue, 122

4.7 Stationary M/M/1 and M/M/1/K Queueing Processes with Feedback, 124

4.7.1 Stationary Distribution of the Sojourn Time of a Task, 126

4.7.2 Distribution of the Total Time of Service by a Task, 128

4.7.3 Stationary Distribution of the Feedback Queue Size, 129

4.7.4 Stationary Distribution of ?n (Sojourn Time of the nth task), 130

4.8 Queues with Bulk Arrivals and Batch Service, 131

4.9 A Priority Queue with Balking and Reneging, 133

4.10 Discrete Time M/M/1 Queueing Process, Combinatorics Method (Lattice Paths), 137

4.10.1 The Basic Ballot Problem, 138

4.10.2 Ballot Problem (based on Takacs 1997), 140

4.10.3 Transient Solution of the M/M/1 by Lattice Path Method, 149

4.11 Stationary M/M/C Queueing Process, 153

4.11.1 A Stationary Multiserver Queue, 154

Exercises, 156

5 Queues With Delay 159

5.1 Introduction, 159

5.2 A Queuing System with Delayed Service, 163

5.3 An M/G/1 Queue with Server Breakdown and with Multiple Working Vacation, 172

5.3.1 Mathematical Formulation of the Model, 173

5.3.2 Steady-State Mean Number of Tasks in the System, 173

5.3.3 A Special Case, 183

5.4 A Bulk Queuing System Under N-Policy with Bilevel Service Delay Discipline and Start-Up Time, 185

5.4.1 Analysis of the Model, 186

5.5 Interrelationship between N-Policy M/G/1/K and F-Policy G/M/1/K Queues with Start-up Time, 188

5.5.1 N-Policy M/G/1/K Queuing System with Exponential Start-up Time, 189

5.5.2 F-Policy G/E/1/K Queuing System with Exponential Start-up Time, 195

5.6 A Transient M/M/1 Queue Under (M, N)-Policy, Lattice Path Method, 199

5.6.1 Solution in Discrete Time, 200

5.6.2 Solution in Continuous Time, 206

5.7 Stationary M/M/1 Queuing Process with Delayed Feedback, 208

5.7.1 Distribution of the Queue Length, 209

5.7.2 Mean Queue Length and Waiting Time, 213

5.8 Single-Server Queue with Unreliable Server and Breakdowns with an Optional Second Service, 222

5.9 A Bulk Arrival Retrial Queue with Unreliable Server, 229

5.9.1 The Model, 231

5.9.2 Model Analysis, 233

5.9.3 Steady-State System Analysis, 237

5.9.4 Performance Measures, 244

5.9.5 Numerical Illustration, 248

5.10 Multiserver Queue with Retrial Feedback Queuing System with Two Orbits, 253

5.11 Steady-State Stability Condition of a Retrial Queuing System with Two Orbits, Reneging, and Feedback, 258

5.11.1 Necessary Stability Condition for the Steady-State System, 259

5.12 Batch Arrival Queue with General Service in Two Fluctuating Modes and Reneging During Vacation and Breakdowns, 263

5.12.1 The Model, 263

5.12.2 Analysis, 265

Exercises, 266

6 Networks of Queues with Delay 267

6.1 Introduction to Networks of Queues, 267

6.2 Historical Notes on Networks of Queues, 270

6.3 Jackson's Network of Queues, 272

6.3.1 Jackson's Model, 273

6.4 Robustness of Networks of Queues, 298

6.5 A MAP Single-Server Queueing System with Delayed Feedback as a Network of Queues, 302

6.5.1 Description of the Model, 304

6.5.2 Service Station, 307

6.5.3 Stepwise Explicit Joint Distribution of the Number of Tasks in the System: General Case When Batch Sizes Vary Between a Minimum k and a Maximum K, 319

6.6 Unreliable Networks of Queueing System Models, 336

6.6.1 Unreliable Network Model of Goodman and Massey, 337

6.6.2 Unreliable Network of Queues Model of Mylosz and Daduna, 340

6.6.3 Unreliable Network of Queues Model of Gautam Choudhury, Jau-Chuan Ke, and Lotfi Tadj: A Queueing System with Two Network Phases of Services, Unreliable Server, Repair Time Delay under N-Policy, 348

6.7 Assessment of Reliability of a Network of Queues, 363

6.8 Effect of Network Service Breakdown, 365

6.8.1 The Model (CoginfoCom System), 366

6.8.2 Analysis, 368

6.8.3 Numerical Example, 370

Exercises, 374

References 377

Index 391