Appendix B

Elements of queuing theory and queuing networks

Abstract

This appendix serves the purpose of providing a simple, yet self-contained primer on queuing systems and networks. Initially, the basic notions and notation of queuing systems are introduced, followed by the notions of discrete/continuous Markov chains and birth-death Markov systems. Then, simple but useful single-server or multiserver queuing systems in equilibrium are presented, followed by fundamental elements of queuing networks and their analysis methodologies that are of interest in this book. This appendix aspires to cover the required knowledge for understanding and exploit the techniques that are based on queuing theory and are presented in the main part of the book. Multiple references to more targeted and detailed treatises on queuing theory, practical systems, and their applications are provided for the more interested reader.

Queuing systems; Discrete Markov chains; Continuous Markov processes; Birth-death systems; Reversibility; Queues in tandem; Queuing networks

B.1. Introduction

The term queuing is defined as the time delay experienced by various entities, e.g. customers, network packets, and cars, in the different facets of life and operations they participate in. Queuing emerges frequently in natural and artificial systems in diverse application settings, e.g. waiting lines, toll stations, and packet routers in computer networks. Queuing theory is the branch of stochastic processes [66,71,88,174,187] that provides formal methodologies and techniques for analyzing queuing phenomena, as the ones described above.
In this book, elements from queuing theory have been used extensively in Chapter 4 to analyze malware diffusion by quantifying the time spent by legitimate nodes in various states, e.g. susceptible and infected. The purpose of this primer is to provide the fundamental knowledge required to understand the contents of Chapter 4. In addition, the primer aspires to aid in the understanding of the methodologies presented in other parts of the book that are relevant to Markov processes, such as techniques in Chapter 5. Appendix B focuses only on the analysis of simple Markovian systems and simple open/closed queuing networks. More advanced treatments may be found in dedicated monographs and books available in the literature, such as [25,33,36,90,142,209,211,229].
The rest of Appendix B is organized as follows. Initially, it explains the basic components of queues, notation, elementary arrival-service processes, and Little’s law. Then, it reviews simple queuing models, namely, birth-death Markov systems in equilibrium, followed by some elementary analysis of queues-in-tandem. The latter leads to the notion of reversibility, which together with Burke’s theorem pave the way for a brief overview of open and closed Jackson networks. The latter consists of the most essential knowledge required to understand the methodologies presented in Chapter 4.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.227.52.11