Tài liệu QUEUEING THEORY WITH APPLICATIONS TO PACKET TELECOMMUNICATION pptx

QUEUEING THEORY WITH

APPLICATIONS TO PACKET

TELECOMMUNICATION

This page intentionally left blank

QUEUEING THEORY WITH

APPLICATIONS TO PACKET

TELECOMMUNICATION

JOHN N. DAIGLE

Prof. of Electrical Engineering

The University of Mississippi

University, MS 38677

Springer

eBook ISBN: 0-387-22859-4

Print ISBN: 0-387-22857-8

Print ©2005 Springer Science + Business Media, Inc.

All rights reserved

No part of this eBook may be reproduced or transmitted in any form or by any means, electronic,

mechanical, recording, or otherwise, without written consent from the Publisher

Created in the United States of America

Boston

©2005 Springer Science + Business Media, Inc.

Visit Springer's eBookstore at: http://ebooks.kluweronline.com

and the Springer Global Website Online at: http://www.springeronline.com

NOTE TO INSTRUCTORS

A complete solution manual has been prepared for use by those interested in

using this book as the primary text in a course or for independent study. Inter￾ested persons should please contact the publisher or the author at

http://www.olemiss.edu/~

wcdaigle/QueueingText to obtain an electronic copy

of the solution manual as well as other support materials, such as computer

programs that implement many of the computational procedures described in

this book.

This page intentionally left blank

Contents

List of Figures

List of Tables

Preface

Acknowledgments

xi

xv

xvii

xxiii

1. TERMINOLOGY AND EXAMPLES

1.1

1.2

The Terminology of Queueing Systems

Examples of Application to System Design

1.2.1

1.2.2

1.2.3

Cellular Telephony

Multiplexing Packets

CDMA-Based Cellular Data

1.3 Summary

2. REVIEW OF RANDOM PROCESSES

2.1 Statistical Experiments and Probability

2.1.1

2.1.2

Statistical Experiments

Conditioning Experiments

2.2

2.3

2.4

2.5

Random Variables

Exponential Distribution

Poisson Process

Markov Chains

3. ELEMENTARY CTMC-BASED QUEUEING MODELS

3.1 M/M/1 Queueing System

3.1.1

3.1.2

3.1.3

Time-Dependent M/M/1 Occupancy Distribution

Stochastic Equilibrium M/M/1 Distributions

Busy Period for M/M/1 Queueing System

1

2

9

9

11

14

17

19

20

20

22

27

33

39

45

57

58

58

60

76

viii QUEUEING THEORY FOR TELECOMMUNICATIONS

3.2

3.3

Dynamical Equations for General Birth-Death Process

Time-Dependent Probabilities for Finite-State Systems

3.3.1

3.3.2

Classical Approach

Jensen’s Method

3.4

3.5

3.6

Balance Equations Approach for Systems in Equilibrium

Probability Generating Function Approach

Supplementary Problems

4. ADVANCED CTMC-BASED QUEUEING MODELS

4.1 Networks

4.1.1

4.1.2

4.1.3

Feedforward Networks: Fixed Routing

Arbitrary Open Networks

Closed Networks of Single Servers

4.2 Phase-Dependent Arrivals and Service

4.2.1

4.2.2

4.2.3

4.2.4

Probability Generating Function Approach

Matrix Geometric Method

Rate Matrix Computation via Eigenanalysis

Generalized State-Space Methods

4.3

4.4

Phase-Type Distributions

Supplementary Problems

5. THE BASIC M/G/1 QUEUEING SYSTEM

5.1 M/G/1 Transform Equations

5.1.1

5.1.2

5.1.3

Sojourn Time for M/G/1

Waiting Time for M/G/1

Busy Period for M/G/1

5.2 Ergodic Occupancy Distribution for M/G/1

5.2.1

5.2.2

5.2.3

Discrete Fourier Transform Approach

Recursive Approach

Generalized State-Space Approach

5.3 Expected Values Via Renewal Theory

5.3.1

5.3.2

Expected Waiting and Renewal Theory

Busy Periods and Alternating Renewal Theory

5.4 Supplementary Problems

6. THE M/G/1 QUEUEING SYSTEM WITH PRIORITY

6.1

6.2

6.3

M/G/1 Under LCFS-PR Discipline

M/G/1 System Exceptional First Service

M/G/1 under HOL Priority

81

83

84

88

91

98

101

107

108

109

110

111

122

124

138

143

146

152

156

159

161

165

167

167

170

170

180

183

210

210

216

219

225

226

229

236

Contents ix

6.3.1

6.3.2

Higher Priority Customers

Lower Priority Customers

6.4

6.5

Ergodic Occupancy Probabilities for Priority Queues

Expected Waiting Times under HOL Priority

6.5.1

6.5.2

HOL Discipline

HOL-PR Discipline

7. VECTOR MARKOV CHAINS ANALYSIS

7.1

7.2

7.3

7.4

7.5

7.6

7.7

The M/G/1 and G/M/1 Paradigms

G/M/1 Solution Methodology

M/G/1 Solution Methodology

Application to Statistical Multiplexing

Generalized State Space Approach: Complex Boundaries

Summary

Supplementary Problems

8. CLOSING REMARKS

References

Index

About the Author

238

241

244

246

248

249

253

254

259

261

265

278

290

294

297

301

309

315

This page intentionally left blank

List of Figures

1.1

1.2

1.3

1.4

1.5

1.6

1.7

1.8

2.1

3.1

3.2

3.3

3.4

3.5

Schematic diagram of a single-server queueing system.

Sequence of events for first customer.

Sequence of events for general customer.

Typical realization for unfinished work.

Blocking probability as a function of population size at

a load of

Queue length survivor function for an N-to-1 multi￾plexing system at a traffic intensity of 0.9 with N as a

parameter and with independent, identically distributed

arrivals.

Queue length survivor function for an 8-to-1 multiplex￾ing system at a traffic intensity of 0.9 with average run

length as a parameter.

Comparison between a system serving a fixed number

of 16 units per frame and a system serving a binomial

number of units with an average of 16 at a traffic inten￾sity of 0.9.

Distribution function for the random variable defined

in Example 2.4.

Survivor function for system occupancy for several val￾ues of

Schematic diagram of a single-server queueing system.

Schematic diagram of a simple network of queues.

Sequence of busy and idle periods.

Sequence of service times during a generic busy period.

2

3

4

6

11

14

15

16

29

63

65

76

76

77

xii QUEUEING THEORY FOR TELECOMMUNICATIONS

3.6

3.7

3.8

3.9

3.10

3.11

3.12

4.1

4.2

4.3

5.1

5.2

5.3

5.4

5.5

5.6

5.7

5.8

Busy period decompositions depending upon interar￾rival versus service times.

Time-dependent state probabilities corresponding to Ex￾ample 3.1.

Steps involved in randomization.

State diagram for M/M/1 System.

State diagram for general birth-death process.

State diagram for general birth-death process.

State diagram illustrating local balance.

Block diagram for window flow control network.

State diagram for phase process.

State diagram for system having phase-dependent ar￾rival and service rates.

Survivor functions with deterministic, Erlang-2, expo￾nential, branching Erlang and gamma service-time dis￾tributions at

Survivor functions for system occupancy with message

lengths drawn from truncated geometric distributions

at

Survivor functions for system having exponential ordi￾nary and exceptional first service

and as a parameter.

Survivor functions with unit deterministic service and

binomially distributed arrivals with N as a parameter

at

Survivor functions with unit-mean Erlang-10 service

and Poisson arrivals with C as a parameter at a traffic

load of 0.9.

Survivor functions with unit-mean Erlang-K service

and Poisson arrivals with K as a parameter at a traf￾fic load of 0.9.

Survivorfunctions with and Pade(2, 2) ser￾vice, Poisson arrivals, and a traffic load of 0.9.

Survivor functions for deterministic (16) batch sizes

with Pade deterministic service and

Poisson arrivals at a traffic load of 0.9 for various choices

of

79

86

90

92

92

95

98

117

122

123

176

178

198

199

201

203

205

206

List of Figures xiii

5.9

5.10

5.11

5.12

6.1

7.1

7.2

7.3

7.4

Survivor functions for deterministic (16) batch sizes

with Erlang-K-approximated deterministic service and

Poisson arrivals at a traffic load of 0.9 for various choices

of K.

Survivor functions for binomial (64,0.25) and deter￾ministic (16) batch sizes with deterministic service ap￾proximated by a Pade(32, 32) approximation and Pois￾son arrivals at a traffic load of 0.9.

A sample of service times.

An observed interval of a renewal process.

HOL service discipline.

Survivor functions for occupancy distributions for sta￾tistical multiplexing system with 0.5 to 1.0 speed con￾version at

Survivor functions for occupancy distributions for sta￾tistical multiplexing system with equal line and trunk

capacities at

Survivor functions for occupancy distributions for sta￾tistical multiplexing system with and without line-speed

conversion at

Survivor functions for occupancy distributions for wire￾less communication link with on time as a parameter.

207

208

211

212

237

273

277

278

291