1
Stability Analysis of Queueing Systems based on Synchronization of the Input and Majorizing Output Flows

Larisa AFANASEVA

Department of Probability, Faculty of Mathematics and Mechanics, Lomonosov Moscow State University, Russia

This chapter is focused on the stability conditions for a multiserver queueing system with heterogeneous servers and a regenerative input flow X. The main idea is constructing an auxiliary service process Y, which is also a regenerative flow and determination of the common points of regeneration for both processes X and Y. Then the traffic rate is defined in terms of the mean of the increments of these processes on a common regeneration period. It allows us to use well-known results from the renewal theory to find the instability and stability conditions. The possibilities of the proposed approach are demonstrated by examples. We also present the applications to transport system capacity analysis.

1.1. Introduction

This chapter deals with the study of stability conditions for a heterogeneous multiserver queueing system with regenerative input flow (Afanaseva 2019).

We consider queueing systems with regenerative input flow for three reasons. First, a process describing the performance of the system under some natural conditions turns out to be a classical regenerative process (Asmussen 2003; Thorisson 2000) and the renewal theory gives very effective tools for asymptotic analysis of the system. Second, the class of regenerative flows is rather wide and includes fundamental flows from queueing theory. Finally, regenerative flow has some useful properties that allow us to investigate various applied models (Afanasyeva and Bashtova 2014).

The main objective of our study is to determine conditions under which the process describing the performance of the system is stochastically bounded and therefore, under some additional assumptions, a stable process.

Let us note that stability results for the classical homogeneous multiserver queue are very well known. We refer to the works of (Kiefer and Wolfowitz 1955) for the GI|GI|m system and the general ergodicity results of (Loynes 1962). As it was shown in Sadowsky (1995), the proposed approach could not be applied for heterogeneous systems. Instead, in the work of (Sadowsky 1995), the stability is examined from the point of view of Harris recurrent Markov chain theory. Based on the works of (Malyshev and Menshikov 1982; Meyn and Tweedie 2009; Georgiadis and Szpankowski 1992; Szpankowski 1994), the author obtained two results concerning the irreducibility and positive Harris recurrence of the corresponding process.

The heterogeneous multiserver queueing system with regenerative flow was investigated in the papers of (Afanasyeva and Tkachenko 2014, 2016, 2018). Under some assumptions, the necessary and sufficient stability condition was obtained there.

We consider m-server queueing system S with regenerative input flow X with intensity ?X. The main assumption is that the process X does not depend on the stochastic sequences and processes determining the work of the servers, such as service time, the moments of breakdowns and recovery of the servers, and the random numbers of the servers required for the service of the customers.

We construct an auxiliary system S0 with input flow X0. The latter does not depend on X and is determined by the stochastic sequence describing the work of the servers. The flow X0 is constructed in such a way that there are always customers for service. We introduce an auxiliary flow Y, which is the number of customers served in the system S0 up to time t. Then we establish the conditions of Y being the regenerative flow with the intensity ??.

The basic idea is constructing the common points of regeneration for both processes X and Y. Then we define the traffic rate of the system in terms of the first moments of increments of these processes on the common regeneration period. Under some conditions, we estimate the increments of the service process ?(t) in the original system S (that is the number of customers served in the system up to time t) with the help of increments of an auxiliary process Y (t). It allows us to prove instability results and to find conditions of stochastic boundedness of the number of customers Q(t) at the system at time t as t 8.

One more traditional approach to the analysis of stability of the queueing systems is based on the regenerative structure of the processes describing the states of the system, such as the number of customers in the system or workload process. We make assumptions providing the presence of the points of the regeneration for the processes. Then, it is required to establish the finiteness of the mean of the times between the regenerations in accordance with the theorem of (Smith 1955). It is quite a complex problem for non-Markovian processes. Exactly this approach is employed in several works of Morozov and colleagues (Morozov et al. 2011; Morozov 2004, 2007; Morozov and Dimitriou 2017; Morozov and Rumyantsev 2016) for establishing the conditions for stability of a wide circle of models. Although our approach is also based on the notions of regeneration and synchronization, it significantly differs from the approach employed in the works mentioned earlier. Our main objective is to establish necessary and sufficient conditions of the stochastic boundedness of the process, describing the system. Thus, this process does not have to be regenerative. Let us point out that a similar situation emerges in the classic models (Borovkov 1976). The analysis of the stochastic boundedness of the process is important for the applications, since precisely the existence of the stochastic boundaries manifests that the system successfully deals with the task. Our conditions may seem too restrictive to be useful in applications. Therefore, we consider four models with service interruptions as examples. In particular, in section 1.7, a discrete-time heterogeneous multiserver queueing system with a regenerative input flow and service interruptions, which are described by independent renewal processes for various servers, is discussed. It is shown that the traffic rate ? is not expressed in terms of the first moments of the random variables defining the model for the preemptive repeat different service discipline (Gaver 1962). We also prove that Q(t) 8 as t 8 when ? = 1 and Q(t) is a stochastically bounded process when ? < 1.

We should consider that models with service interruptions occur in numerous applications including manufacturing processes, multiprocessor computer networks, telecommunicating networks and various types of service counters.

White and Christie (1958) were the first to study queueing systems with interruptions. Those authors investigated the M|M|1 model with preemptive resume priority discipline. Their results were later extended by (Avi-Itzhak and Naor 1963) and (Thiruvengadam 1963) who study queues with general service times. Gaver (1962) studied single-server queues with batch Poisson arrivals and generally distributed service times. So far there is extensive literature concerning queueing systems with interruptions. There are some review papers that cover most of the literature in this sphere. Some of the important papers on the single-server case are presented in Fiems and Bruneel (2013).

The most extensive literature survey on systems with interruptions both for single-server and multiserver cases is given by (Krishnamoorthy et al. 2012). This paper also covers some non-Markovian multichannel systems with homogeneous servers. There are some other articles with extensive literature survey as well (Pechinkin et al. 2009; Morozov et al. 2011). Nevertheless, to the best of our knowledge, there are no papers that study the stability problem for multichannel queueing systems with heterogeneous servers in non-Markovian case with general input flow and service times. Synchronization method combined with the regenerative theory is one of the powerful approaches to obtain stability conditions for such systems.

Let us also mention the fluid approximation approach as an alternative to the synchronization approach followed here. Such an approach has lent to significant progress in stability analysis of multiclass queueing networks (Dai 1995; Chen 1995; Chen and Yao 2001). See also Foss and Konstantopoulos (2004) for a survey of various approaches to stability of queueing systems with a focus on the fluid approach. Nevertheless, our analysis does not rely on a fluid approach because to the best of our knowledge, the synchronization method with regard to regenerative structure of the processes turns out to be suitable for obtaining complete and transparent proofs as well as natural stability conditions for the model at hand.

We also note that stability analysis is an essential and challenging stage of investigation of a stochastic model, however, stability conditions may be of independent interest. In particular, the stability criterion of the multiserver model can be used for the capacity planning of the model at the design stage to obtain the lower bound of the capacity that keeps system stable. As an example of applications of our results, we estimate the carrying capacity of the automobile road, intersected by a...