main-content

## Über dieses Buch

The book is composed of two main parts: mathematical background and queueing systems with applications. The mathematical background is a self containing introduction to the stochastic processes of the later studies queueing systems. It starts with a quick introduction to probability theory and stochastic processes and continues with chapters on Markov chains and regenerative processes. More recent advances of queueing systems are based on phase type distributions, Markov arrival processes and quasy birth death processes, which are introduced in the last chapter of the first part.

The second part is devoted to queueing models and their applications. After the introduction of the basic Markovian (from M/M/1 to M/M/1//N) and non-Markovian (M/G/1, G/M/1) queueing systems, a chapter presents the analysis of queues with phase type distributions, Markov arrival processes (from PH/M/1 to MAP/PH/1/K). The next chapter presents the classical queueing network results and the rest of this part is devoted to the application examples. There are queueing models for bandwidth charing with different traffic classes, slotted multiplexers, ATM switches, media access protocols like Aloha and IEEE 802.11b, priority systems and retrial systems.

An appendix supplements the technical content with Laplace and z transformation rules, Bessel functions and a list of notations. The book contains examples and exercises throughout and could be used for graduate students in engineering, mathematics and sciences.

## Inhaltsverzeichnis

### Chapter 1. Introduction to Probability Theory

Abstract
In this chapter we summarize the most important notions and facts of probability theory that are necessary for an elaboration of our topic. In the present summary, we will apply the more specific mathematical concepts and facts – mainly measure theory and analysis – only to the necessary extent while, however, maintaining mathematical precision.
László Lakatos, László Szeidl, Miklós Telek

### Chapter 2. Introduction to Stochastic Processes

Abstract
When considering technical, economic, ecological, or other problems, in several cases the quantities $$\left \{{X}_{t},\;t \in \mathcal{T}\right \}$$ being examined can be regarded as a collection of random variables. This collection describes the changes (usually in time and in space) of considered quantities. If the set $$\mathcal{T}$$ is a subset of the set of real numbers, then the set $$\left \{t \in \mathcal{T}\right \}$$ can be interpreted as time and we can say that the random quantities X t vary in time. In this case the collection of random variables $$\left \{{X}_{t},\;t \in \mathcal{T}\right \}$$ is called a stochastic process. In mathematical modeling of randomly varying quantities in time, one might rely on the highly developed theory of stochastic processes.
László Lakatos, László Szeidl, Miklós Telek

### Chapter 3. Markov Chains

Abstract
In the early twentieth century, Markov (1856–1922) introduced in [67] a new class of models called Markov chains, applying sequences of dependent random variables that enable one to capture dependencies over time. Since that time, Markov chains have developed significantly, which is reflected in the achievements of Kolmogorov, Feller, Doob, Dynkin, and many others. The significance of the extensive theory of Markov chains and the continuous-time variant called Markov processes is that it can be successfully applied to the modeling behavior of many problems in, for example, physics, biology, and economics, where the outcome of one experiment can affect the outcome of subsequent experiments. The terminology is not consistent in the literature, and many authors use the same name (Markov chain) for both discrete and continuous cases. We also apply this terminology.
László Lakatos, László Szeidl, Miklós Telek

### Chapter 4. Renewal and Regenerative Processes

Abstract
Let $$\{N(t),\;t \geq 0\}$$ be a nonnegative-integer-valued stochastic process that counts the occurrences of a given event. That is, N(t) is the number of events in the time interval $$[0,t)$$. For example, N(t) can be the number of bulb replacements in a lamp that is continuously on, and the dead bulbs are immediately replaced
László Lakatos, László Szeidl, Miklós Telek

### Chapter 5. Markov Chains with Special Structures

Abstract
The previous chapter presented methods for analyzing stochastic models where some of the distributions were other than exponential. In these cases the analysis of the models is more complex than the analysis of Markov models. In this chapter we introduce a methodology to extend the set of models that can be analyzed by Markov models while the distributions can be other than exponential.
László Lakatos, László Szeidl, Miklós Telek

### Chapter 6. Introduction to Queueing Systems

Abstract
The theory of queueing systems dates back to the seminal work of A. K. Erlang (1878–1929), who worked for the telecom company in Copenhagen and studied telephone traffic in the early twentieth century. To this day the terminology of queueing theory is closely related to telecommunications (e.g., channel, call, idle/busy, queue length, utilization).
László Lakatos, László Szeidl, Miklós Telek

### Chapter 7. Markovian Queueing Systems

Abstract
Queueing systems whose underlying stochastic process is a continuous-time Markov chain (CTMCs) are the simplest and most often used class of queueing systems. The analysis of these systems is based on the essential results available for the analysis of CTMCs. As a consequence, several interesting properties of these queueing systems can be described by simple closed-form analytical expressions both in transient (as a function of time and initial state) and in steady state.
László Lakatos, László Szeidl, Miklós Telek

### Chapter 8. Non-Markovian Queueing Systems

Abstract
The MG ∕ 1 queueing system (Fig.8.1) is similar to the MM ∕ 1 queueing system and the only difference is that the service time distribution is no exponential. First we mention some idea, most of which were described in the previous chapter in connection with an MM ∕ 1 system.
László Lakatos, László Szeidl, Miklós Telek

### Chapter 9. Queueing Systems with Structured Markov Chains

Abstract
In the previous chapters we studied queueing systems with different interarrival and service time distributions. Chapter 7 is devoted to the analysis of queueing systems with exponential interarrival and service time distributions. The number of customers in these queueing systems is characterized by CTMCs with a generally nonhomogeneous birth-and-death structure. In contrast, Chap. 8 is devoted to the analysis of queueing systems with nonexponential interarrival and service time distributions. It turns out that far more complex analysis approaches are required for the analysis of queues with nonexponential interarrival and service time distributions. In this chapter we introduce queueing systems whose interarrival and service time distributions are nonexponential, but they can be analyzed with CTMCs. Indeed in this chapter we demonstrate the use of the results of Chap. 5 for the analysis of queueing systems with phase-type (PH) distributed interarrival and service times or with arrival and service processes that are MAPs. The main message of this chapter is that in queueing models the presence of PH or MAP processes instead of exponential distributions results in a generalization of the underlying CTMCs from birth-and-death processes to quasi-birth-and-death (QBDs) processes.
László Lakatos, László Szeidl, Miklós Telek

### Chapter 10. Queueing Networks

Abstract
Up to now, we have overviewed the main methods for the analysis of individual queueing systems. But the analysis of large telecommunication systems or computer systems executing complex interrelated tasks (e.g., transaction processing systems, Web server farms) requires the application of systems models that contain several servers (potentially of different kinds) where customers are traveling among these servers for consecutive services.
László Lakatos, László Szeidl, Miklós Telek

### Chapter 11. Applied Queueing Systems

Abstract
Traditional telephone networks were designed to implement a single type of communication service, i.e., the telephone service. Today’s telecommunication networks implement a wide range of communication services. In this section we introduce Markov models of communication services that compete for the bandwidth of a finite-capacity communication link.
László Lakatos, László Szeidl, Miklós Telek

### Backmatter

Weitere Informationen