Queueing Theory for Telecommunications - Discrete Time Modelling of a Single Node System

Preface

Acknowledgements

Contents

Chapter 1

Introduction

1.1 Introduction

1.2 A single node queue

1.3 A tandem queueing systems

1.4 A network system of queues

1.5 Queues in Communication networks

1.6 Why are queueing systems of interest?

1.7 Discrete time vs Continuous time analyses

1.7.1 Time

Chapter 2

Markov Processes

2.1 Introduction

2.2 Stochastic Processes

2.3 Markov Processes

2.4 Discrete Time Markov Chains

2.4.1 Examples

2.4.2 State of DTMC at arbitrary times

2.4.2.1 Example

2.4.2.2 Chapman Kolmogorov Equations

2.4.3 Classification of States

2.4.4 Classification of Markov Chains

2.5 First Passage Time

2.5.1 Examples

2.5.2 Some Key Information Provided by First Passage

2.5.3 Example

2.5.4 Mean first recurrence time

2.6 Absorbing Markov Chains

2.6.1 Characteristics of an absorbing Markov chain

2.7 Transient Analysis

2.7.1 Direct Algebraic Operations

2.7.1.1 Naive repeated application of P

2.7.1.2 Matrix decomposition approach

2.7.2 Transient Analysis Based on the z-Transform

2.8 Limiting Behaviour of Markov Chains

2.8.1 Ergodic Chains

2.8.2 Non-Ergodic Chains

2.8.3 Mean First Recurrence Time and Steady State Distributions

2.9 Numerical Computations of the Invariant Vectors

2.9.1 Finite State Markov Chains

2.9.1.1 Direct Methods

2.9.1.2 Iterative Methods:

2.9.2 Bivariate Discrete Time Markov Chains

2.9.3 Computing Stationary Distribution for the Finite Bivariate DTMC

2.9.4 Special Finite State DTMC

2.9.5 Infinite State Markov Chains

2.9.6 Some Results for Infinite State Markov Chains with Repeating Structure

2.9.7 Matrix-Analytical Method for Infinite State Markov Chains

2.9.7.1 The GI/M/1 Type

2.9.7.2 Key Measures

2.9.7.3 Computing matrix R

2.9.7.4 Some Special Structures of the Matrix R often Encountered

2.9.7.5 The M/G/1 Type:

2.9.7.6 Stationary distribution

2.9.7.7 Computing Matrix G

2.9.7.8 Some Special Structures of the Matrix G often Encountered

2.9.7.9 QBD

2.9.7.10 Computing the matrices R and G

2.9.7.11 Some Special Structures of the Matrix R and the matrix G

2.9.8 Other special QBDs of interest

2.9.8.1 Level-dependent QBDs:

2.9.8.2 Tree structured QBDS

2.9.9 Re-blocking of transition matrices

2.9.9.1 The non-skip-free M/G/1 type

2.9.9.2 The non-skip-free GI/M/1 type

2.9.9.3 Time-inhomogeneous Discrete Time Markov Chains

2.9.9.4 Time-inhomogeneous and spatially-homogeneous QBD

2.10 Software Tools for Matrix-Analytic Methods

Chapter 3

Characterization of Queueing Systems

3.1 Introduction

3.1.1 Factors that affect the measures

3.2 Arrival and Service Processes

3.2.1 Renewal Process

3.2.1.1 Number of renewals

3.3 Special Arrival and Service Processes in Discrete Time

3.3.1 Geometric Distribution

3.3.1.1 Lack of Memory Property:

3.3.2 Phase Type Distribution

3.3.2.1 Two very important closure properties of phase type distributions:

3.3.2.2 Minimal coefficient of variation of a discrete PH distribution

3.3.2.3 Examples of special phase type distributions

3.3.2.4 Analogy between PH and Geometric distributions

3.3.2.5 Phase Renewal Process:

3.3.3 The infinite phase distribution (IPH)

3.3.4 General Inter-event Times

3.3.4.1 Remaining Time Representation

3.3.4.2 Elapsed Time Representation

3.3.5 Markovian Arrival Process

3.3.5.1 Platoon Arrival Process (PAP)

3.3.5.2 Batch Markovian Arrival Process (BMAP)

3.3.6 Marked Markovian Arrival Process

3.3.7 Semi Markov Processes

3.3.8 Data Fitting for PH and MAP

Chapter 4

Single Node Queuing Models

4.1 Introduction

4.2 Birth-and-Death Process

4.3 Discrete time B-D Process

4.4 Geo/Geo/1 Queues

4.4.1 Algebraic Approach

4.4.2 Transform Approach

4.4.3 Matrix-geometric Approach

4.4.4 Performance Measures

4.4.4.1 Mean number in system:

4.4.4.2 Mean number in queue:

4.4.4.3 Waiting time in the queue:

4.4.4.4 Waiting time in system:

4.4.4.5 Duration of a Busy Period:

4.4.4.6 Number Served During a Busy Period:

4.4.4.7 Age Process

4.4.4.8 Workload:

4.4.5 Discrete time equivalent of Little’s Law:

4.4.6 Geo/Geo/1/K Queues

4.4.6.1 Departure Process

4.5 Geo/G/1 Queues

4.5.1 Supplementary Variable Technique

4.5.1.1 Transform Approach

4.5.1.2 Matrix-analytic approach

4.5.2 Imbedded Markov Chain Approach

4.5.2.1 Distribution of number in the system

4.5.2.2 Waiting Time:

4.5.2.3 Workload:

4.5.2.4 Age Process:

4.5.2.5 Busy Period:

4.5.3 Geo/G/1/K Queues

4.6 GI/Geo/1 Queues

4.6.1 Supplementary Variable Technique

4.6.1.1 Matrix-analytic approach

4.6.2 Imbedded Markov Chain Approach

4.6.2.1 Matrix-geometric approach:

4.6.2.2 Transform approach

4.6.3 GI/Geo/1/K Queues

4.7 Geo/PH/1 Queues

4.7.1 Waiting Times

4.8 PH/Geo/1 Queues

4.8.1 Waiting Times

4.9 PH/PH/1 Queues

4.9.1 Examples

4.9.1.1 A Numerical Example

4.9.1.2 Another Example

4.9.2 Waiting Time Distirbution

4.9.2.1 Workload

4.9.2.2 Age Process

4.9.3 PH/PH/1 Queues at points of events

4.10 GI/G/1 Queues

4.10.1 The (RT,RT) representation for the GI/G/1 queue

4.10.2 New algorithm for the GI/G/1 system

4.10.3 The (ET,ET) representation for the GI/G/1 queue

4.11 GI/G/1/K Queues

4.11.1 Queue length

4.11.2 Waiting times

4.11.3 Model II

4.12 MAP/PH/1 Queues

4.13 Batch Queues

4.13.1 GeoX/Geo/1 queue

4.13.1.1 Transform Approach

4.13.1.2 Examples

4.13.1.3 Matrix-analytic Approach

4.13.2 Geo/GeoY /1 queue

Chapter 5

Advance Single Node Queuing Models

5.1 Multiserver Queues

5.1.1 Geo/Geo/k Systems

5.1.1.3 An Example

5.1.1.4 Waiting Times

5.1.2 GI/Geo/k Systems

5.1.2.1 Using MAM Same as using supplementary variables

k. 5.1.2.2 Numerical Example

5.1.3 PH/PH/k Systems

5.1.4 Geo/D/k Systems

5.1.5 MAP/D/k Systems

5.1.6 BMAP/D/k Systems

5.2 Vacation Queues

5.2.1 Geo/G/1 vacation systems

5.2.1.1 Single vacation system

5.2.1.2 Multiple vacations system

5.2.2 GI/Geo/1 vacation systems

5.2.3 MAP/PH/1 vacation systems

5.2.3.1 Exhaustive single vacation:

5.2.3.2 Stationary Distribution:

5.2.3.3 Example of the Geo/Geo/1 vacation:

5.2.3.4 Exhaustive multiple vacations

5.2.4 MAP/PH/1 vacation queues with number limited service

5.2.5 MAP/PH/1 vacation queues with time limited service

5.2.6 Random Time Limited Vacation Queues/Queues with Server Breakdowns and Repairs

5.3 Priority Queues

5.3.1 Geo/Geo/1 Preemptive

5.3.1.1 Stationary Distribution

5.3.2 Geo/Geo/1 Non-preemptive

5.3.2.1 Stationary Distribution

5.3.3 MAP/PH/1 Preemptive

5.3.3.1 Stationary Distribution

5.3.4 MAP/PH/1 Non-preemptive

5.4 Queues with Multiclass of Packets

5.4.1 Multiclass systems – with FCFS the MMAP[K]/PH[K]/1

5.4.1.1 Stationary distribution and waiting times

5.4.2 Multiclass systems – with LCFS the MMAP[K]/PH[K]/1

5.4.2.1 Stability conditions

5.4.2.2 Performance measures

References

Index