Introduction To Queueing Theory And Stochastic Teletra C .

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