Yue / Takahashi / Takagi Advances in Queueing Theory and Network Applications

1. Auflage 2009
ISBN: 978-0-387-09703-9
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 316 Seiten

Advances in Queueing Theory and Network Applications presents several useful mathematical analyses in queueing theory and mathematical models of key technologies in wired and wireless communication networks such as channel access controls, Internet applications, topology construction, energy saving schemes, and transmission scheduling. In sixteen high quality chapters, this work provides novel ideas, new analytical models, and simulation and experimental results by experts in the field of queueing theory and network applications. The text serves as a state-of-the-art reference for a wide range of researchers and engineers engaged in the fields of queueing theory and network applications, and can also serve as supplemental material for advanced courses in operations research, queueing theory, performance analysis, traffic theory, as well as theoretical design and management of communication networks.

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.

Autoren/Hrsg.

Yue, Wuyi

Takahashi, Yutaka

Takagi, Hideaki

Inhaltsverzeichnis

1;Contents;6
2;Preface;8
2.1;Part I: Queueing Processes;8
2.2;Part II: Single-Server Queues;9
2.3;Part III: Multiple Queues;10
2.4;Part IV: Finite-Buffer Queues;10
2.5;Part V: Network Applications;11
3;Part I: Queueing Processes;13
3.1;Chapter 1;14
3.1.1;Two Sided DQBD Process and Solutions to the Tail Decay Rate Problem and Their Applications to the Generalized Join Shortest Queue;14
3.1.1.1;1.1 Introduction;14
3.1.1.2;1.2 Two Sided DQBD Process;17
3.1.1.3;1.3 Eigenvectors of Rate Matrices;23
3.1.1.4;1.4 Answers to Decay Rate Problem;26
3.1.1.5;1.5 Generalized Join Shortest Queue;31
3.1.1.6;1.6 Remarks on Existence Results;39
3.1.1.7;1.7 Conclusions;40
3.1.1.8;Appendix 1;40
3.1.1.9;Appendix 2;42
3.1.1.10;References;43
3.2;Chapter 2;45
3.2.1;Analytical Model of On-Demand Streaming Services Based on Renewal Reward Theory;45
3.2.1.1;2.1 Introduction;45
3.2.1.2;2.2 Streaming Services and Renewal Model;48
3.2.1.3;2.3 Mean Download Rate and Optimal Strategy;49
3.2.1.4;2.4 Download Rate Distribution;52
3.2.1.5;2.5 Conclusions;55
3.2.1.6;References;55
4;Part II: Single - Server Queues;56
4.1;Chapter 3;57
4.1.1;A Pure Decrement Service Geom/G/1 Queue with Multiple Adaptive Vacations;57
4.1.1.1;3.1 Introduction;57
4.1.1.2;3.2 Model Description;58
4.1.1.3;3.3 Analysis of System Performance Measures;60
4.1.1.3.1;3.3.1 Number of Customers at the Beginning of a Service Period;60
4.1.1.3.2;3.3.2 Stationary Queue Length and Waiting Time;62
4.1.1.4;3.4 Special Cases;66
4.1.1.5;3.5 Numerical Results;68
4.1.1.6;3.6 Conclusions;70
4.1.1.7;References;71
4.2;Chapter 4;72
4.2.1;Performance Analysis of an M/M/1 Working Vacation Queue with Setup Times;72
4.2.1.1;4.1 Introduction;72
4.2.1.2;4.2 Model Description and Preliminary;73
4.2.1.3;4.3 Queue Length Distribution;76
4.2.1.4;4.4 Waiting Time Analysis;79
4.2.1.5;4.5 Numerical Results;80
4.2.1.6;4.6 Conclusions;82
4.2.1.7;References;83
4.3;Chapter 5;84
4.3.1;Modeling of Production System with Nonrenewal Batch Input, Early Setup, and Extra Jobs;84
4.3.1.1;5.1 Introduction;84
4.3.1.2;5.2 System Model;86
4.3.1.3;5.3 Preliminaries;87
4.3.1.4;5.4 Waiting Time Distribution;88
4.3.1.4.1;5.4.1 Obtaining Yidle(z);88
4.3.1.4.2;5.4.2 Obtaining the LST of the Waiting Time of the Customer Who Arrives During the Idle Period;92
4.3.1.5;5.5 Mean Waiting Time;99
4.3.1.6;5.6 Numerical Example;101
4.3.1.7;5.7 Conclusions and Summary;102
4.3.1.8;Appendix 1;103
4.3.1.9;Appendix 2: Derivation of (5.23);105
4.3.1.10;Appendix 3: Derivation of (5.16);106
4.3.1.11;References;108
4.4;Chapter 6;110
4.4.1;Performance Analysis of an M/Ek/1 Queue with Balking and Two Service Rates Based on a Single Vacation Policy;110
4.4.1.1;6.1 Introduction;110
4.4.1.2;6.2 System Model and Equilibrium Condition;112
4.4.1.2.1;6.2.1 System Model;112
4.4.1.2.2;6.2.2 Equilibrium Condition;113
4.4.1.3;6.3 Steady-State Probability Vector;115
4.4.1.4;6.4 Performance Measures and Cost Model;117
4.4.1.4.1;6.4.1 Performance Measures;117
4.4.1.4.2;6.4.2 Cost Model;118
4.4.1.5;6.5 Sensitivity Analysis;119
4.4.1.6;6.6 Conclusions;122
4.4.1.7;References;122
5;Part III: Multiple Queues;124
5.1;Chapter 7;125
5.1.1;Markovian Polling Systems: Functional Computation for MeanWaiting Times and its Computational Complexity;125
5.1.1.1;7.1 Introduction;125
5.1.1.2;7.2 Model Description;127
5.1.1.3;7.3 Expressions for W0j(·),H0j(·),Fj(·), and Related Quantities;131
5.1.1.3.1;7.3.1 Expressions for W0j(·),H0j(·), andFj(·);131
5.1.1.3.2;7.3.2 System State at the Next Polling Instant;133
5.1.1.3.3;7.3.3 Unified Forms: Linear Functional Expressions;133
5.1.1.4;7.4 The Linear Functional Expression;135
5.1.1.5;7.5 Steady-State Values;137
5.1.1.6;7.6 Computational Complexity;139
5.1.1.6.1;7.6.1 Reduction of Calculations of h10(·);140
5.1.1.6.2;7.6.2 Reduction of Calculations of Steady-State Values;144
5.1.1.6.3;7.6.3 Evaluation of Computational Complexity;146
5.1.1.6.4;7.6.4 Comparison of Computational Times by Examples;147
5.1.1.7;7.7 Conclusions;149
5.1.1.8;Appendix: Proof of Proposition 7.2;150
5.1.1.9;References;151
5.2;Chapter 8;153
5.2.1;Performance Analysis of a Two-Station MTO/MTS Production System;153
5.2.1.1;8.1 Introduction;153
5.2.1.2;8.2 Model Description;156
5.2.1.3;8.3 Numerical Results;163
5.2.1.4;8.4 Conclusions;167
5.2.1.5;References;167
6;Part IV: Finite - Buffer Queues;169
6.1;Chapter 9;170
6.1.1;Analysis of anM/M/c/N Queueing System with Balking, Reneging, and Synchronous Vacations;170
6.1.1.1;9.1 Introduction;170
6.1.1.2;9.2 System Model;172
6.1.1.3;9.3 Steady-State Probability;173
6.1.1.3.1;9.3.1 Steady-State Equations;173
6.1.1.3.2;9.3.2 Matrix Solution;174
6.1.1.3.3;9.3.3 Some Special Cases;178
6.1.1.4;9.4 Conditional Distributions of Queue Lengthand Waiting Time;179
6.1.1.5;9.5 Conclusions;182
6.1.1.6;Appendix;182
6.1.1.7;References;184
6.2;Chapter 10;186
6.2.1;Analysis of Mixed Loss-Delay M/M/m/K Queueing Systems with State-Dependent Arrival Rates;186
6.2.1.1;10.1 Introduction;186
6.2.1.2;10.2 Equilibrium State Probability Equations;188
6.2.1.3;10.3 Analysis of Blocking Probability andWaiting Time;190
6.2.1.3.1;10.3.1 Blocking Probability of Loss Calls;190
6.2.1.3.2;10.3.2 Blocking Probability of Delay Calls;191
6.2.1.3.3;10.3.3 Waiting and Nonwaiting Probabilities of Accepted Delay Calls;192
6.2.1.3.4;10.3.4 Waiting Time Distribution of Accepted Delay Calls;192
6.2.1.4;10.4 Numerical Examples;194
6.2.1.4.1;10.4.1 Equilibrium State Probabilities;194
6.2.1.4.2;10.4.2 Blocking Probabilities of Loss and Delay Calls;194
6.2.1.4.3;10.4.3 Mean Waiting Time;195
6.2.1.5;References;199
6.3;Chapter 11;200
6.3.1;Asymptotic Behavior of Loss Rate for Feedback Finite Fluid Queue with Downward Jumps;200
6.3.1.1;11.1 Introduction;200
6.3.1.2;11.2 MAP (Markov Additive Process) with Downward Jumps;202
6.3.1.3;11.3 FIFQ (Feedback Infinite Fluid Queue) with Downward Jumps;206
6.3.1.4;11.4 FFFQ (Feedback Finite Fluid Queue) with Downward Jumps;208
6.3.1.5;11.5 Asymptotic Behavior of Loss Rate for FFFQ with Downward Jumps;209
6.3.1.6;11.6 Numerical Examples;212
6.3.1.7;11.7 Conclusions;213
6.3.1.8;Appendix;213
6.3.1.9;References;216
6.4;Chapter 12;217
6.4.1;Explicit Probability Density Function for the Length of a Busy Period in an M/M/1/K Queue;217
6.4.1.1;12.1 Introduction;217
6.4.1.2;12.2 Busy Period;218
6.4.1.3;12.3 First Passage Time to the System Capacity;226
6.4.1.4;12.4 Regeneration Cycle;228
6.4.1.5;12.5 Conclusions;229
6.4.1.6;References;230
7;Part V: Network Applications;231
7.1;Chapter 13;232
7.1.1;Performance Analysis of ARQ Schemes in Self-Similar Traffic;232
7.1.1.1;13.1 Introduction;232
7.1.1.2;13.2 System Model and Notation;234
7.1.1.3;13.3 Performance Analysis;235
7.1.1.4;13.4 Performance Analysis for Different Kinds of ARQ Schemes;239
7.1.1.4.1;13.4.1 Performance Measures;239
7.1.1.4.2;13.4.2 Performance Analysis for ARQ Schemes;240
7.1.1.5;13.5 Numerical Results;243
7.1.1.6;13.6 Conclusions;248
7.1.1.7;References;248
7.2;Chapter 14;250
7.2.1;Modeling of P2P File Sharing with a Level-Dependent QBD Process;250
7.2.1.1;14.1 Introduction;250
7.2.1.2;14.2 Related Work;252
7.2.1.3;14.3 Peer-to-Peer File Sharing Model;253
7.2.1.3.1;14.3.1 Upload Queue Management and File Segmentation;253
7.2.1.3.2;14.3.2 Download Bandwidth;254
7.2.1.4;14.4 Analytical P2P File Sharing Model;255
7.2.1.4.1;14.4.1 Level-Dependent QBD;255
7.2.1.4.1.1;14.4.1.1 Level-Dependent QBD Generator Description;256
7.2.1.4.1.2;14.4.1.2 Probability of Extinction;258
7.2.1.4.2;14.4.2 Level-Dependent QBD with Catastrophes;259
7.2.1.5;14.5 Numerical Evaluation;262
7.2.1.6;14.6 Conclusions;265
7.2.1.7;References;265
7.3;Chapter 15;267
7.3.1;Performance Analysis of a Decentralized Content Delivery System with FEC Recovery;267
7.3.2;15.1 Introduction;267
7.3.3;15.2 Model and Analysis;269
7.3.4;15.3 Numerical Results;270
7.3.4.1;15.3.1 Impact of Background Traffic;270
7.3.4.2;15.3.2 Impact of Service Rate at Bottleneck Router;272
7.3.4.3;15.3.3 Impact of System Capacity;274
7.3.4.4;15.3.4 Impact of Number of Video Servers;276
7.3.5;15.4 Conclusions;278
7.3.6;Appendix: Derivation of Probability p(l)(k |M(l));278
7.3.7;References;280
7.4;Chapter 16;282
7.4.1;Blocking Probabilities of Multiple Classes in IP Networks with QoS Routing;282
7.4.1.1;16.1 Introduction;282
7.4.1.2;16.2 Bandwidth Allocation Schemes;284
7.4.1.2.1;16.2.1 Problem Definition;285
7.4.1.2.2;16.2.2 First Phase: A Precomputation Scheme for Network Optimization;285
7.4.1.2.3;16.2.3 Second Phase: An Online Routing Scheme with End-to-End QoS Guarantees;287
7.4.1.3;16.3 Blocking Probability with Predetermined Optimal Solutions;289
7.4.1.3.1;16.3.1 M/G/K/K Blocking Probability Model and System Performance;290
7.4.1.3.2;16.3.2 GI/M/K/K Blocking Probability Model and System Performance;293
7.4.1.4;16.4 Numerical Results;296
7.4.1.4.1;16.4.1 Predetermined Optimal Solutions;297
7.4.1.4.2;16.4.2 Blocking Probabilities Under M/G/K/K Model;298
7.4.1.5;16.5 Conclusions;301
7.4.1.6;References;301
8;About the Editors and Authors;303
9;Index;312