Retrial Queueing Systems

A Computational Approach

verfasst von: Jesús R. Artalejo, Antonio Gómez-Corral

Verlag: Springer Berlin Heidelberg

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The application of auto-repeat facilities in telephone systems, as well as the use of random access protocols in computer networks, have led to growing interest in retrial queueing models. Since much of the theory of retrial queues is complex from an analytical viewpoint, with this book the authors give a comprehensive and updated text focusing on approximate techniques and algorithmic methods for solving the analytically intractable models.

Retrial Queueing Systems: A Computational Approach also

Presents motivating examples in telephone and computer networks. Establishes a comparative analysis of the retrial queues versus standard queues with waiting lines and queues with losses. Integrates a wide range of techniques applied to the main M/G/1 and M/M/c retrial queues, and variants with general retrial times, finite population and the discrete-time case. Surveys basic results of the matrix-analytic formalism and emphasizes the related tools employed in retrial queues. Discusses a few selected retrial queues with QBD, GI/M/1 and M/G/1 structures. Features an abundance of numerical examples, and updates the existing literature.

The book is intended for an audience ranging from advanced undergraduates to researchers interested not only in queueing theory, but also in applied probability, stochastic models of the operations research, and engineering. The prerequisite is a graduate course in stochastic processes, and a positive attitude to the algorithmic probability.

Inhaltsverzeichnis

Frontmatter

An Introduction to Retrial Queueing Systems

1. Introduction and Motivating Examples

The general structure of a retrial queue is shown in Figure 1.1. It is clear from the picture that retrial queues can also be regarded as a special type of queueing networks. In their basic form, these networks contain two nodes: the main node where blocking is possible and a delay node for repeated trials. To describe specific retrial queues with a certain structure and queueing discipline more nodes have to be introduced.

Our aim in this book is to discuss algorithmic solutions for queueing systems with retrials. We are interested in obtaining the limiting distribution of the system state because important system descriptors, such as the blocking probability and the mean number of customers making repeated attempts, can be expressed in terms of this limiting law. In a few simple models, it is possible to derive closed-form expressions but very often it is difficult or even impossible to determine the limiting distribution of the system state. Algorithmic methods and approximate techniques are powerful tools for solving the analytically intractable problems. We complete the performance analysis of retrial queues by studying a variety of quality measures including waiting time, busy period and other specific descriptors arising due to the retrial feature. The main focus of this book is on the application of algorithmic methods in studying the M/G/1 retrial queue and the M/M/c retrial queue, as well as the use of matrix-analytic techniques [464, 544, 546] to solve some selected retrial queues with QBD, GI/M/1 and M/G/1 structures. For analytical solutions given in terms of generating functions and Laplace-Stieltjes transforms, we refer interested readers to the textbook by Falin and Templeton [288].

2. A General Overview

In Section 2.1, we present the framework we will use for modelling a retrial queue. To keep the discussion simple, we limit ourselves to the M/M/c and M/G/1 retrial queues, even though the material in this section may be readily adapted to advanced retrial queues. In Section 2.2, we establish a comparative analysis of the standard M/M/c and M/G/1 models versus their retrial counterparts. Short descriptions of several variants and generalizations of these retrial queues are given in Section 2.3 and, finally, Section 2.4 is devoted to bibliographical notes.

Computational Analysis of Performance Descriptors

3. Limiting Distribution of the System State

This chapter deals with the computational analysis of the limiting distribution of the system state in some basic retrial queues. In Section 3.1, we present recursive schemes (embedded Markov chain approach and regenerative approach) and an alternative approach based on maximum entropy techniques for the computation of the limiting probabilities in the main M/G/1 retrial queue. Sections 3.2 and 3.3 extend the study to models with general retrial times and the discrete-time case, respectively. Section 3.4 discusses approximations for the main M/M/c retrial queue based on finite and infinite models (see Subsections 3.4.1 and 3.4.2). In Subsections 3.4.3-3.4.5, other approximating assumptions are introduced. We then discuss numerically the goodness of these approximations. In Section 3.5, we show how to deal with a multiserver model with finite population. The bibliographical comments are given in Section 3.6.

We stress that the mathematical descriptions and notations regarding to the M/G/1 and M/M/c retrial queues were given in Section 2.1.

4. Busy Period

In this chapter, we study the length of the busy period, denoted by L, and related performance measures for the M/G/1 and M/M/c retrial queues. This seems that the existing numerical inversion techniques would be inadequate to handle. For this reason, alternative approaches are needed, and Subsection 4.1.1 concentrates on methods based on the principle of maximum entropy and on the truncation of the orbit capacity for the M/G/1 retrial queue. Subsections 4.1.2 and 4.1.3 complete the analysis of the single server model by studying the recursive computation of the number of customers served and the maximum orbit size during a busy period. In Section 4.2, we consider the M/M/c retrial queue. In particular, Subsection 4.2.1 discusses the length of a busy period and the computation of its moments. The algorithms presented involve the approximating models X^W, X^F and X^NR, which were introduced in Section 3.4. In Subsection 4.2.2, we briefly show how to extend the analysis to the number of customers served. The exact computation of the maximal queue length is presented in Subsection 4.2.3. Finally, bibliographical remarks are given in Section 4.3.

5. Waiting Time

In this chapter, we discuss the waiting time distribution for the M/G/1 and M/M/c retrial queues under the natural assumption that customers are served in random order. In Subsection 5.1.1, maximum entropy, truncated and gamma approaches are discussed for the M/G/1 case. The numerical results give support to the truncated and gamma approximations, but the maximum entropy solution is itself of methodological interest. In Subsection 5.2.1, we provide a route for the computational investigation of the M/M/c retrial queue with finite orbit capacity, which approximates satisfactorily the original infinite capacity model. Our objective in Subsections 5.1.2 and 5.2.2 is to study for both basic models the discrete counterpart of the waiting time, namely the number of retrials made by a tagged customer before entering into service.

6. Other Descriptors

This chapter ends up the discussion on performance descriptors in retrial queues through various measures of intrinsic interest, but less studied in the literature. In Section 6.1, we give an alternative Markovian description of the M/G/1 retrial queue that replaces the state of the server by the total number of arrivals trying to enter into service since the last service completion. Our interest in Section 6.2 is to distinguish between the different events occurring along a busy period of the M/G/1 retrial queue. In particular, we study four characteristics allowing us to record the numbers of successful and blocked retrials, as well as the numbers of successful and blocked primary arrivals. Sections 6.3 and 6.4 concern the multiserver case and analyze the distribution of the server idle periods and the time to reach a certain orbit level. A brief section of bibliographical notes concludes the chapter.

Retrial Queueing Systems Analyzed Through the Matrix-Analytic Formalism

7. The Matrix-Analytic Formalism

This third part of the book deals with retrial queues analyzed by matrixanalytic methods. We begin with the present chapter on some generalities of the matrix-analytic formalism for two reasons. First and foremost, this chapter summarizes basic results of the matrix-analytic methods, presents the main tools employed in Chapters 8 and 9, and fixes some notation. In addition, it helps the reader to acquire some feeling of the constant interplay between algebraic manipulations and reasoning on the probabilistic interpretation of the underlying expressions.

Although it is assumed that the reader will have some knowledge of the basic matrix algebra, we give in Subsection 7.1.1 a short glossary of the conventions we use in Part III of this book and of some notation used earlier. In the rest of Section 7.1, we introduce the QBD processes and the Markov chains of GI/M/1- and M/G/1-types. Then, we describe a point process, namely the batch Markovian arrival process, which generalizes and unifies several Markovian processes commonly used in queueing theory. We next examine the phase-type distribution and the semi-Markov service process. In Sections 7.2 and 7.3, we study in some detail concrete results on the QBD, GI/M/1 and M/G/1 structures. Our intention is only to facilitate the understanding of the material in later chapters, hence we omit proofs. Bibliographical notes in Section 7.4 are then useful for finding the corresponding sources.

8. Selected Retrial Queues with QBD Structure

In this chapter, our interest is in a few selected retrial queues with QBD structure which are analyzed through matrix-analytic techniques. In Section 8.1, we analyze the MAP/PH/1 retrial queue and discuss the stationary distribution of the system state and the maximal queue length during a busy period. The aim in Section 8.2 is to extend the study to the multiserver case focussing on other performance characteristics. To this end, we study the busy period and the waiting time for the MAP/M/c retrial queue. Finally, in Section 8.3, we focus on a multiserver model with finite population where both the service times and the retrial times follow phase-type distributions.

9. Selected Retrial Queues with GI/M/1 and M/G/1 Structures

In this last chapter, we turn the attention to the GI/M/1 and M/G/1 structures. In order to illustrate the former, we present an exhaustive analysis of the Geo/Geo/c retrial queue, which includes the study of the stationary distribution of the system state, the busy period and the waiting time analysis. In Section 9.2, we discuss the BMAP/SM/1 retrial queue. We first analyze the system state at the departure epochs. Then, we extend the study at any arbitrary time.

Backmatter

Titel: Retrial Queueing Systems
verfasst von: Jesús R. Artalejo
Antonio Gómez-Corral
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-78725-9
Print ISBN: 978-3-540-78724-2
DOI: https://doi.org/10.1007/978-3-540-78725-9