Introduction To Queueing Theory And Stochastic Teletra C .

3y ago
38 Views
3 Downloads
1.72 MB
300 Pages
Last View : 10d ago
Last Download : 4m ago
Upload by : Randy Pettway
Transcription

Introduction to Queueing Theory andStochastic Teletraffic ModelsMoshe ZukermanEE DepartmentCity University of Hong Kongemail: moshezu@gmail.comCopyright M. Zukerman c 2000–2021.This book can be used for educational and research purposes under the condition that it(including this first page) is not modified in any way.PrefaceThe aim of this textbook is to provide students with basic knowledge of stochastic modelswith a special focus on queueing models, that may apply to telecommunications topics, suchas traffic modelling, performance evaluation, resource provisioning and traffic management.These topics are included in a field called teletraffic. This book assumes prior knowledge of aprogramming language and mathematics normally taught in an electrical engineering bachelorprogram.The book aims to enhance intuitive and physical understanding of the theoretical concepts itintroduces. The famous mathematician Pierre-Simon Laplace is quoted to say that “Probabilityis common sense reduced to calculation” [18]; as the content of this book falls under the fieldof applied probability, Laplace’s quote very much applies. Accordingly, the book aims to linkintuition and common sense to the mathematical models and techniques it uses. It mainlyfocuses on steady-state analyses and avoids discussions of time-dependent analyses.A unique feature of this book is the considerable attention given to guided homework assignments involving computer simulations and analyzes. By successfully completing these assignments, students learn to simulate and analyze stochastic models, such as queueing systemsand networks, and by interpreting the results, they gain insight into the queueing performanceeffects and principles of telecommunications systems modelling. Although the book, at times,provides intuitive explanations, it still presents the important concepts and ideas required forthe understanding of teletraffic, queueing theory fundamentals and related queueing behaviorof telecommunications networks and systems. These concepts and ideas form a strong basefor the more mathematically inclined students who can follow up with the extensive literatureon probability models and queueing theory. A small sample of it is listed at the end of this

Queueing Theory and Stochastic Teletraffic Modelsc Moshe Zukerman2book.The first two chapters provide background on probability and stochastic processes topics relevant to the queueing and teletraffic models of this book. These two chapters provide a summaryof the key topics with relevant homework assignments that are especially tailored for understanding the queueing and teletraffic models discussed in later chapters. The content of thesechapters is mainly based on [18, 38, 94, 99, 100, 101]. Students are encouraged to also studythe original textbooks for more explanations, illustrations, discussions, examples and homeworkassignments.Chapter 3 discusses general queueing notation and concepts. Chapter 4 aims to assist thestudent to perform simulations of queueing systems. Simulations are useful and importantin the many cases where exact analytical results are not available. An important learningobjective of this book is to train students to perform queueing simulations. Chapter 5 providesanalyses of deterministic queues. Many queueing theory books tend to exclude deterministicqueues; however, the study of such queues is useful for beginners in that it helps them betterunderstand non-deterministic queueing models. Chapters 6 – 14 provide analyses of a widerange of queueing and teletraffic models most of which fall under the category of continuoustime Markov-chain processes. Chapter 15 provides an example of a discrete-time queue thatis modelled as a discrete-time Markov chain. In Chapter 16, various aspects of a single serverqueue with Poisson arrivals and general service times are studied, mainly focussing on meanvalue results as in [17]. Then, in Chapter 17, some selected results of a single server queuewith a general arrival process and general service times are provided. Chapter 18 focusses onmulti access applications, and in Chapter 19, we extend our discussion to queueing networks.Finally, in Chapter 20, stochastic processes that have been used as traffic models are discussedwith special focus on their characteristics that affect queueing performance.Throughout the book there is an emphasis on linking the theory with telecommunications applications as demonstrated by the following examples. Section 1.19 describes how propertiesof Gaussian distribution can be applied to link dimensioning. Section 6.11 shows, in the context of an M/M/1 queueing model, how optimally to set a link service rate such that delayrequirements are met and how the level of multiplexing affects the spare capacity required tomeet such delay requirement. An application of M/M/ queueing model to a multiple accessperformance problem [17] is discussed in Section 7.5. Then later in Chapter 18 more multiaccess models are presented. In Sections 8.8 and 9.5, discussions on dimensioning and relatedutilization issues of a multi-channel system are presented. Especially important is the emphasis on the insensitivity property of models such as M/M/ , M/M/k/k, processor sharing andmulti-service that lead to practical and robust approximations as described in Chapters 7, 8,13, and 14. Section 19.3 guides the reader to simulate a mobile cellular network. Section 20.6describes a traffic model applicable to the Internet.Last but not least, the author wishes to thank all the students and colleagues that providedcomments and questions that helped developing and editing the manuscript over the years.

Queueing Theory and Stochastic Teletraffic Modelsc Moshe Zukerman3Contents1 Background on Relevant Probability Topics1.1 Events, Sample Space, and Random Variables . . . . . . . . . . . . . . . . .1.2 Probability, Conditional Probability and Independence . . . . . . . . . . . .1.3 Probability and Distribution Functions . . . . . . . . . . . . . . . . . . . . .1.4 Joint Distribution Functions . . . . . . . . . . . . . . . . . . . . . . . . . . .1.5 Conditional Probability for Random Variables . . . . . . . . . . . . . . . . .1.6 Independence between Random Variables . . . . . . . . . . . . . . . . . . . .1.7 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.8 Selected Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . .1.8.1 Non-parametric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.8.2 Bernoulli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.8.3 Geometric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.8.4 Binomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.8.5 Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.8.6 Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.8.7 Discrete Uniform . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.9 Continuous Random Variables and their Distributions . . . . . . . . . . . . .1.10 Selected Continuous Random Variables . . . . . . . . . . . . . . . . . . . . .1.10.1 Uniform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.10.2 Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.10.3 Relationship between Exponential and Geometric Random Variables1.10.4 Hyper-Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.10.5 Erlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.10.6 Hypo-Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.10.7 Gaussian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.10.8 Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.11 Moments and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.11.1 Mean (or Expectation) . . . . . . . . . . . . . . . . . . . . . . . . . .1.11.2 Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.11.3 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.11.4 Conditional Mean and the Law of Iterated Expectation . . . . . . . .1.11.5 Conditional Variance and the Law of Total Variance . . . . . . . . . .1.12 Mean and Variance of Specific Random Variables . . . . . . . . . . . . . . .1.13 Sample Mean and Sample Variance . . . . . . . . . . . . . . . . . . . . . . .1.14 Covariance and Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . .1.15 Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.15.1 Z-transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.15.2 Laplace Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.16 Multivariate Random Variables and Transform . . . . . . . . . . . . . . . . .1.17 Probability Inequalities and Their Dimensioning Applications . . . . . . . .1.18 Limit Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.19 Link Dimensioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.19.1 Case 1: Homogeneous Individual Sources . . . . . . . . . . . . . . . .1.19.2 Case 2: Non-homogeneous Individual Sources . . . . . . . . . . . . .1.19.3 Case 3: Capacity Dimensioning for a Community . . . . . . . . . . 36364041434451555658616366666869707172

c Moshe ZukermanQueueing Theory and Stochastic Teletraffic Models2 Relevant Background on Stochastic Processes2.1 General Concepts . . . . . . . . . . . . . . . . . . . . . . .2.2 Two Orderly and Memoryless Point Processes . . . . . . .2.2.1 Bernoulli Process . . . . . . . . . . . . . . . . . . .2.2.2 Poisson Process . . . . . . . . . . . . . . . . . . . .2.3 Markov Modulated Poisson Process . . . . . . . . . . . . .2.4 Discrete-time Markov chains . . . . . . . . . . . . . . . . .2.4.1 Definitions and Preliminaries . . . . . . . . . . . .2.4.2 Transition Probability Matrix . . . . . . . . . . . .2.4.3 Chapman-Kolmogorov Equation . . . . . . . . . . .2.4.4 Marginal Probabilities . . . . . . . . . . . . . . . .2.4.5 Properties and Classification of States . . . . . . .2.4.6 Steady-state Probabilities . . . . . . . . . . . . . .2.4.7 Birth and Death Process . . . . . . . . . . . . . . .2.4.8 Reversibility . . . . . . . . . . . . . . . . . . . . . .2.4.9 Multi-dimensional Markov Chains . . . . . . . . . .2.5 Continuous Time Markov chains . . . . . . . . . . . . . . .2.5.1 Definitions and Preliminaries . . . . . . . . . . . .2.5.2 Birth and Death Process . . . . . . . . . . . . . . .2.5.3 First Passage Time . . . . . . . . . . . . . . . . . .2.5.4 Transition Probability Function . . . . . . . . . . .2.5.5 Steady-State Probabilities . . . . . . . . . . . . . .2.5.6 Multi-Dimensional Continuous-time Markov Chains2.5.7 Solutions by Successive Substitutions . . . . . . . .2.5.8 The Curse of Dimensionality . . . . . . . . . . . . .2.5.9 Simulations . . . . . . . . . . . . . . . . . . . . . .2.5.10 Reversibility . . . . . . . . . . . . . . . . . . . . . .2.6 Renewal Process . . . . . . . . . . . . . . . . . . . . . . .3 General Queueing and Teletraffic Concepts3.1 Notation . . . . . . . . . . . . . . . . . . . .3.2 Utilization . . . . . . . . . . . . . . . . . . .3.3 Little’s Formula . . . . . . . . . . . . . . . .3.4 Delay and Loss Systems . . . . . . . . . . .3.5 Traffic . . . . . . . . . . . . . . . . . . . . .3.6 Offered and Carried Traffic . . . . . . . . . .3.7 Work Conservation . . . . . . . . . . . . . .3.8 PASTA . . . . . . . . . . . . . . . . . . . . .3.9 Bit-rate Versus Service Rate . . . . . . . . .3.10 Queueing Models . . . . . . . . . . . . . . 101102102103105.108. 108. 109. 110. 113. 113. 115. 116. 116. 118. 1194 Simulations1214.1 Confidence Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1214.2 Simulation of a G/G/1 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1245 Deterministic Queues1275.1 D/D/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

c Moshe ZukermanQueueing Theory and Stochastic Teletraffic Models5.25.3. . . . . . . . . . . . . . . . . . .Utilization. . . . . . . . . . . . .1281291301311311336 M/M/16.1 Steady-State Queue Size Probabilities . . . . . . . . . . . . . .6.2 State Transition Diagram of M/M/1 . . . . . . . . . . . . . .6.3 Queue Performance Measures: E[Q], E[NQ ], E[D], and E[WQ ]6.4 Using Z-Transform . . . . . . . . . . . . . . . . . . . . . . . .6.5 Mean Delay of Delayed Customers . . . . . . . . . . . . . . . .6.6 Delay Distribution . . . . . . . . . . . . . . . . . . . . . . . .6.7 The Departure Process . . . . . . . . . . . . . . . . . . . . . .6.8 Mean Busy Period and First Passage Time . . . . . . . . . . .6.9 Dimensioning Based on Meeting Required Mean Delay . . . .6.10 Effect of Rising Internet Bit-rate on Link Efficiency and QoS .6.11 Multiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.12 Dimensioning Based on Delay Distribution . . . . . . . . . . .6.13 A Markov-chain Simulation of M/M/1 . . . . . . . . . . . . .134134136137138138139141143144145147149150.153. 154. 154. 155. 156. 157. 157. 157.158. 158. 158. 161. 162. 163. 163. 164. 165. 166. 167. 172. 174. 176. 177. 1785.4D/D/k . . . . . . . . . . . . . . . . . . . . . . . .D/D/k/k . . . . . . . . . . . . . . . . . . . . . .5.3.1 The D/D/k/k Process and Its Cycles . . .5.3.2 Blocking Probability, Mean Queue-size and5.3.3 Proportion of Time Spent in Each State .Summary of Results . . . . . . . . . . . . . . . .57 M/M/ 7.1 Steady-State Equations . . . . . . . .7.2 Solving the Steady-State Equations .7.3 State Transition Diagram of M/M/ 7.4 Insensitivity . . . . . . . . . . . . . .7.5 Applications . . . . . . . . . . . . . .7.5.1 A Multi-access Model . . . . .7.5.2 Birth Rate Evaluation . . . .8 M/M/k/k and Extensions8.1 M/M/k/k: Offered, Carried and Overflow Traffic . . . . . .8.2 The Steady-State Equations and Their Solution . . . . . . .8.3 Recursion and Jagerman Formula . . . . . . . . . . . . . . .8.4 The Special Case: M/M/1/1 . . . . . . . . . . . . . . . . . .8.5 Lower bound of Ek (A) . . . . . . . . . . . . . . . . . . . . .8.6 Monotonicity of Ek (A) . . . . . . . . . . . . . . . . . . . . .8.7 The Limit k with A/k Fixed . . . . . . . . . . . . . .8.8 M/M/k/k: Dimensioning and Utilization . . . . . . . . . . .8.9 M/M/k/k under Critical Loading . . . . . . . . . . . . . . .8.10 Insensitivity and Many Classes of Customers . . . . . . . . .8.11 First Passage Time and Time Between Events in M/M/k/k8.12 A Markov-chain Simulation of M/M/k/k . . . . . . . . . . .8.13 Preemptive Priorities . . . . . . . . . . . . . . . . . . . . . .8.14 Overflow Traffic of M/M/k/k . . . . . . . . . . . . . . . . .8.15 Multi-server Loss Systems with Non-Poisson Input . . . . . .

c Moshe ZukermanQueueing Theory and Stochastic Teletraffic Models9M/M/k9.1 Steady-State Equations and Their Solution . . . .9.2 Erlang C Formula . . . . . . . . . . . . . . . . . .9.3 Mean Queue Size, Delay, Waiting Time and Delay9.4 Mean Delay of Delayed Customers . . . . . . . . .9.5 Dimensioning . . . . . . . . . . . . . . . . . . . .9.6 Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . .Factor. . . . . . . . . .10 Engset Loss Formula10.1 Steady-State Equations and Their Solution . . . . . . . . . .10.2 Blocking Probability . . . . . . . . . . . . . . . . . . . . . .10.3 Obtaining the Blocking Probability by a Recursion . . . . .10.4 Insensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . .10.5 Load Classifications and Definitions . . . . . . . . . . . . . .10.6 The Small Idle Period Limit . . . . . . . . . . . . . . . . . .10.7 The Many Sources Limit . . . . . . . . . . . . . . . . . . . .10.8 Obtaining the Blocking Probability by Successive Iterations.6.183. 183. 184. 185. 187. 187. 187.189. 189. 190. 191. 192. 192. 194. 194. 19411 State Dependent SSQ12 Queueing Models with Finite Buffers12.1 D/D/1/N . . . . . . . . . . . . . . .12.2 SLB/D/1/N . . . . . . . . . . . . . .12.3 M/M/1/N . . . . . . . . . . . . . . .12.4 M/M/k/N . . . . . . . . . . . . . . .12.5 MMPP(2)/M/1/N . . . . . . . . . .12.6 M/Em /1/N . . . . . . . . . . . . . .12.7 Saturated Queues . . . . . . . . . . .196.199. 199. 200. 200. 205. 212. 215. 21713 Processor Sharing21913.1 The M/M/1-PS queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21913.2 Insensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22214 Multi-service Loss Model14.1 Model Description . . . . . . . . . . . . . . .14.2 Attributes of the Multi-service Loss Model . .14.3 A Simple Example with I 2 and k 2 . . .14.4 Other Reversibility Criteria for Markov chains14.5 Computation . . . . . . . . . . . . . . . . . .14.6 A General Treatment . . . . . . . . . . . . . .14.6.1 Infinite Number of Servers . . . . . . .14.6.2 Finite Number of Servers . . . . . . . .14.7 Critical Loading . . . . . . . . . . . . . . . . .15 Discrete-Time Queue.22922923023123323623823824024124416 M/G/1 and Extensions24716.1 Pollaczek Khinchine Formula: Residual Service Approach [17] . . . . . . . . . . 247

c Moshe ZukermanQueueing Theory and Stochastic Teletraffic ine Formula: by Kendall’sSpecial Cases: M/M/1 and M/D/1 . . . .Busy Period . . . . . . . . . . . . . . . . .M/G/1-LIFO . . . . . . . . . . . . . . . .M/G/1 with m Priority Classes . . . . . .Nonpreemptive . . . . . . . . . . . . . . .Preemptive Resume . . . . . . . . . . . . .Recursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .[65]. . . . . . . . . . . . .17 Queues with General Input17.1 Reich’s Formula . . . . . . . . . . . . . . . . . . . . . . .17.2 Queue Size Versus Virtual Waiting Time . . . . . . . . .17.3 Is the Queue Overflow Probability a Good QoS Measure?17.4 G/GI/1 Queue and Its G/GI/1/k Equivalent . . . . . .18 Multi-access Modeling and Analyses18.1 ALOHA . . . . . . . . . . . . . . . . . . . . . . . . . . .18.1.1 Throughput Analysis of Slotted ALOHA . . . . .18.1.2 Throughput Analysis of Pure ALOHA . . . . . .18.2 Random-access Channel . . . . . . . . . . . . . . . . . .18.3 Binary Exponential Backoff (BEB) . . . . . . . . . . . .

the understanding of teletra c, queueing theory fundamentals and related queueing behavior of telecommunications networks and systems. These concepts and ideas form a strong base for the more mathematically inclined students who can follow up with the extensive literature on

Related Documents:

Purpose Simulation is often used in the analysis of queueing models. A simple but typical queueing model Waiting line Server Calling population Queueing models provide the analyst with a powerful tool for designing and evaluating the performance of queueing systems. Typical measures of system performance Server util

802.16 networks was conducted in [7], [8] by combining link-layer queueing with physical-layer transmission. A vacation queueing model was adopted in [9] to analyze the link-layer queueing performance of OFDM-TDMA systems with round-robin scheduling. A queueing model for OFDMA systems was used in [10] to design a scheduling scheme that balances

theory to construct the dynamic system of screening system in this paper. Queueing theory is the mathematical study of waiting lines [23]. In queueing theory, a model is constructed so that queue length

probability, operational research, telecommunication, i ndustrial engineering, com-puter science, management science publish articles on queu eing extensively. The ow of new theories and methodologies in queueing has become very hard to keep . Queueing Theory and its Applications, A Personal View 13 distrib

of Queueing Theory Applied to Emergency Care. Here is a picture of the participants at our meeting on October 25, 2012. Figure 1. Emergency Care/Queueing Seminar: (Left to Right) Jed Keesling, Trent Register, Joshua Hurwitz, Jean Larson, James Maissen, Hayriye Gulbu-dak, Evan Milliken,

have faded. But our lack of completeness is also explained by the time constraints of this survey. Queueing applications are abundant in Canada. The diverse areas where queueing analysis has been applied include: ship-ping and canals, grocery store checkout line count estimation, vehic

Components of a Queueing Model The calling population Finite or infinite (often approx. “very large”) Infinite pool: arrival rate not affected by the number of customers who have left the calling population and joined the queueing system. Finite pool: can affect arrival proce

The colonial response to these acts is really the start of the American Revolution. First Massachusetts passed a set of resolutions calling for colonists to: one, disobey the Intolerable Acts, two, stop paying taxes, and three, prepare for war. And in September 1774, a group of delegates from twelve of the thirteen colonies - Georgia! - met in Philadelphia to coordinate the resistance of the .