Advances in Queueing Theory and Network Applications (eBook)

Wuyi Yue is a Doctor of Engineering in Applied Mathematics and Physics. She has worked for years in research and as a professor in her field. She is currently a professor at Konan University in Kobe, Japan, in the Department of Information Sciences and Systems Enginnering and the Faculty of Science and Engineering. She is also the Director of Intelligent Information and Communications Techonology. She has served as the organizing chair of many committees and international conferences, as well as published numerous monographs and journal articles. Yutaka Takahashi has actively worked in the field of computer science, communication networks, operations research and systems science. He pioneered a technique for a nalzying the performance of queuing networks and was the founding co-chairman of the IFIP WG6.3 for Performance Evaluation of Communication Systems. He has organized and served on committees of hundreds of international conferences, and he has edited several books in his field. Hideaki Takagi is a professor at the Institute of Policy and Planning Sciences at the University of Tsukuba, Japan. He received his doctorate of Physics from the University of California, Los Angeles, which he attended with the support of the IBM Japan Overseas Scholarship Program and a contract with the Defense Advanced Research Projects Agency. He has worked in research and academia for years, and is curently the editor of the Performance Evaluation journal and the Queueing Systems journal.

Contents 6
Preface 8
Part I: Queueing Processes 8
Part II: Single-Server Queues 9
Part III: Multiple Queues 10
Part IV: Finite-Buffer Queues 10
Part V: Network Applications 11
Part I: Queueing Processes 13
Chapter 1 14
Two Sided DQBD Process and Solutions to the Tail Decay Rate Problem and Their Applications to the Generalized Join Shortest Queue 14
1.1 Introduction 14
1.2 Two Sided DQBD Process 17
1.3 Eigenvectors of Rate Matrices 23
1.4 Answers to Decay Rate Problem 26
1.5 Generalized Join Shortest Queue 31
1.6 Remarks on Existence Results 39
1.7 Conclusions 40
Appendix 1 40
Appendix 2 42
References 43
Chapter 2 45
Analytical Model of On-Demand Streaming Services Based on Renewal Reward Theory 45
2.1 Introduction 45
2.2 Streaming Services and Renewal Model 48
2.3 Mean Download Rate and Optimal Strategy 49
2.4 Download Rate Distribution 52
2.5 Conclusions 55
References 55
Part II: Single - Server Queues 56
Chapter 3 57
A Pure Decrement Service Geom/G/1 Queue with Multiple Adaptive Vacations 57
3.1 Introduction 57
3.2 Model Description 58
3.3 Analysis of System Performance Measures 60
3.3.1 Number of Customers at the Beginning of a Service Period 60
3.3.2 Stationary Queue Length and Waiting Time 62
3.4 Special Cases 66
3.5 Numerical Results 68
3.6 Conclusions 70
References 71
Chapter 4 72
Performance Analysis of an M/M/1 Working Vacation Queue with Setup Times 72
4.1 Introduction 72
4.2 Model Description and Preliminary 73
4.3 Queue Length Distribution 76
4.4 Waiting Time Analysis 79
4.5 Numerical Results 80
4.6 Conclusions 82
References 83
Chapter 5 84
Modeling of Production System with Nonrenewal Batch Input, Early Setup, and Extra Jobs 84
5.1 Introduction 84
5.2 System Model 86
5.3 Preliminaries 87
5.4 Waiting Time Distribution 88
5.4.1 Obtaining Yidle(z) 88
5.4.2 Obtaining the LST of the Waiting Time of the Customer Who Arrives During the Idle Period 92
5.5 Mean Waiting Time 99
5.6 Numerical Example 101
5.7 Conclusions and Summary 102
Appendix 1 103
Appendix 2: Derivation of (5.23) 105
Appendix 3: Derivation of (5.16) 106
References 108
Chapter 6 110
Performance Analysis of an M/Ek/1 Queue with Balking and Two Service Rates Based on a Single Vacation Policy 110
6.1 Introduction 110
6.2 System Model and Equilibrium Condition 112
6.2.1 System Model 112
6.2.2 Equilibrium Condition 113
6.3 Steady-State Probability Vector 115
6.4 Performance Measures and Cost Model 117
6.4.1 Performance Measures 117
6.4.2 Cost Model 118
6.5 Sensitivity Analysis 119
6.6 Conclusions 122
References 122
Part III: Multiple Queues 124
Chapter 7 125
Markovian Polling Systems: Functional Computation for MeanWaiting Times and its Computational Complexity 125
7.1 Introduction 125
7.2 Model Description 127
7.3 Expressions for W0j(·),H0j(·),Fj(·), and Related Quantities 131
7.3.1 Expressions for W0j(·),H0j(·), andFj(·) 131
7.3.2 System State at the Next Polling Instant 133
7.3.3 Unified Forms: Linear Functional Expressions 133
7.4 The Linear Functional Expression 135
7.5 Steady-State Values 137
7.6 Computational Complexity 139
7.6.1 Reduction of Calculations of h10(·) 140
7.6.2 Reduction of Calculations of Steady-State Values 144
7.6.3 Evaluation of Computational Complexity 146
7.6.4 Comparison of Computational Times by Examples 147
7.7 Conclusions 149
Appendix: Proof of Proposition 7.2 150
References 151
Chapter 8 153
Performance Analysis of a Two-Station MTO/MTS Production System 153
8.1 Introduction 153
8.2 Model Description 156
8.3 Numerical Results 163
8.4 Conclusions 167
References 167
Part IV: Finite - Buffer Queues 169
Chapter 9 170
Analysis of anM/M/c/N Queueing System with Balking, Reneging, and Synchronous Vacations 170
9.1 Introduction 170
9.2 System Model 172
9.3 Steady-State Probability 173
9.3.1 Steady-State Equations 173
9.3.2 Matrix Solution 174
9.3.3 Some Special Cases 178
9.4 Conditional Distributions of Queue Lengthand Waiting Time 179
9.5 Conclusions 182
Appendix 182
References 184
Chapter 10 186
Analysis of Mixed Loss-Delay M/M/m/K Queueing Systems with State-Dependent Arrival Rates 186
10.1 Introduction 186
10.2 Equilibrium State Probability Equations 188
10.3 Analysis of Blocking Probability andWaiting Time 190
10.3.1 Blocking Probability of Loss Calls 190
10.3.2 Blocking Probability of Delay Calls 191
10.3.3 Waiting and Nonwaiting Probabilities of Accepted Delay Calls 192
10.3.4 Waiting Time Distribution of Accepted Delay Calls 192
10.4 Numerical Examples 194
10.4.1 Equilibrium State Probabilities 194
10.4.2 Blocking Probabilities of Loss and Delay Calls 194
10.4.3 Mean Waiting Time 195
References 199
Chapter 11 200
Asymptotic Behavior of Loss Rate for Feedback Finite Fluid Queue with Downward Jumps 200
11.1 Introduction 200
11.2 MAP (Markov Additive Process) with Downward Jumps 202
11.3 FIFQ (Feedback Infinite Fluid Queue) with Downward Jumps 206
11.4 FFFQ (Feedback Finite Fluid Queue) with Downward Jumps 208
11.5 Asymptotic Behavior of Loss Rate for FFFQ with Downward Jumps 209
11.6 Numerical Examples 212
11.7 Conclusions 213
Appendix 213
References 216
Chapter 12 217
Explicit Probability Density Function for the Length of a Busy Period in an M/M/1/K Queue 217
12.1 Introduction 217
12.2 Busy Period 218
12.3 First Passage Time to the System Capacity 226
12.4 Regeneration Cycle 228
12.5 Conclusions 229
References 230
Part V: Network Applications 231
Chapter 13 232
Performance Analysis of ARQ Schemes in Self-Similar Traffic 232
13.1 Introduction 232
13.2 System Model and Notation 234
13.3 Performance Analysis 235
13.4 Performance Analysis for Different Kinds of ARQ Schemes 239
13.4.1 Performance Measures 239
13.4.2 Performance Analysis for ARQ Schemes 240
13.5 Numerical Results 243
13.6 Conclusions 248
References 248
Chapter 14 250
Modeling of P2P File Sharing with a Level-Dependent QBD Process 250
14.1 Introduction 250
14.2 Related Work 252
14.3 Peer-to-Peer File Sharing Model 253
14.3.1 Upload Queue Management and File Segmentation 253
14.3.2 Download Bandwidth 254
14.4 Analytical P2P File Sharing Model 255
14.4.1 Level-Dependent QBD 255
14.4.1.1 Level-Dependent QBD Generator Description 256
14.4.1.2 Probability of Extinction 258
14.4.2 Level-Dependent QBD with Catastrophes 259
14.5 Numerical Evaluation 262
14.6 Conclusions 265
References 265
Chapter 15 267
Performance Analysis of a Decentralized Content Delivery System with FEC Recovery 267
15.1 Introduction 267
15.2 Model and Analysis 269
15.3 Numerical Results 270
15.3.1 Impact of Background Traffic 270
15.3.2 Impact of Service Rate at Bottleneck Router 272
15.3.3 Impact of System Capacity 274
15.3.4 Impact of Number of Video Servers 276
15.4 Conclusions 278
Appendix: Derivation of Probability p(l)(k |M(l)) 278
References 280
Chapter 16 282
Blocking Probabilities of Multiple Classes in IP Networks with QoS Routing 282
16.1 Introduction 282
16.2 Bandwidth Allocation Schemes 284
16.2.1 Problem Definition 285
16.2.2 First Phase: A Precomputation Scheme for Network Optimization 285
16.2.3 Second Phase: An Online Routing Scheme with End-to-End QoS Guarantees 287
16.3 Blocking Probability with Predetermined Optimal Solutions 289
16.3.1 M/G/K/K Blocking Probability Model and System Performance 290
16.3.2 GI/M/K/K Blocking Probability Model and System Performance 293
16.4 Numerical Results 296
16.4.1 Predetermined Optimal Solutions 297
16.4.2 Blocking Probabilities Under M/G/K/K Model 298
16.5 Conclusions 301
References 301
About the Editors and Authors 303
Index 312