دانلود رایگان ترجمه مقاله سیستم های صف بندی زمان گسسته با تعطیلی های انحصاری مارکوفی (نشریه الزویر 2013)

سیستم های صف بندی زمان گسسته با تعطیلی های انحصاری مارکوفی

Discrete-time queueing systems with Markovian preemptive vacations

Abstract

In this contribution we investigate discrete-time queueing systems with vacations. A framework is constructed that allows for studying numerous different vacation systems, including a.o. classical vacation systems like the exhaustive and limited vacation systems as well as queueing systems with service interruptions. Using a probability generating functions approach, we obtain steady-state performance measures such as moments of queue content at different epochs and of customer delay. The usefulness of vacation models in teletraffic is then illustrated by means of some more practical applications (priority queueing, CSMA/CD).

1 Introduction

Queueing systems with vacations [1–3] have proven to be a useful abstraction in modelling unreliability of servers and in modelling systems where service resources are shared between classes of customers. Typical examples of the former class of applications include repair/maintenance models [4] and ARQ systems [5]. Priority queueing models [1,6] and polling models [7,8] are examples of the latter class.

In this contribution we consider the discrete-time GeoX /G/1 queue subjected to vacations. The vacation process is Markovian and may also depend on the system state: the probability to leave for a vacation at the end of a slot and the duration of this vacation depends on whether or not a customer receives service during the slot, and if so, whether or not this customer remains in service, ends service leaving behind an empty system, or ends service but leaves behind a non-empty system. As such, vacations can interrupt a customer’s service; such vacations are sometimes referred to as preemptive, in accordance with the terminology of priority queueing systems. We therefore consider three different operation modes to cope with these interruptions: the customer resumes its service after the interruption, the customer repeats its service or the customer repeats its service with a possibly different (resampled) service time.

The model under consideration can capture behaviour of a number of ‘‘classical’’ vacation models – including the exhaustive vacation system with single and multiple vacations and number- and time-limited vacation systems – as well as of systems with a preemptive independent vacation process. Classical vacation models are extensively treated in Takagi’s excellent monographs on continuous-time [1] and discrete-time [9] queueing theory. More recent results are also summarised by Tian and Zhang [10]. Systems with a preemptive independent vacation process are surveyed here. Such vacation models are often referred to as systems with server interruptions or server breakdowns. The availability of the server can then be modelled as an on–off process as server availability alternates between being on and being off.

We first focus on continuous-time models. According to Ibe and Trivedi [11], White and Christie [12] were the first to study queues with interruptions. They consider a continuous-time M/M/1 queueing system where the vacation process is modelled as an on–off process with exponentially distributed on- and off-periods. Generally distributed service times and off-periods are considered by Avi-Itzhak and Naor [13] and also by Thiruvengadam [14]. These authors consider exponentially distributed on-periods as opposed to Federgruen and Green [15], who consider phase-type on-periods. Van Dijk [16] provides an approximate analysis of a system with exponentially distributed service times but with generally distributed on- and off-periods whereas Takine and Sengupta [17] study a vacation queueing system in a Markov-modulated environment. The latter authors also allow correlation in the arrival process. Queues with interruptions are also studied outside the framework of single-server first-come-first-served queues. Ke et al. [18] consider a Markovian multi-server queueing system with server interruptions, show that the queueing process can be described by a quasi-birth–death (QBD) process and numerically solve the QBD process. Choudhury and Ke [19] assess performance of a retrial queue with server interruptions by means of a pgf approach. Further, a processor sharing queueing system with exponentially distributed on-periods and generally distributed vacation periods is studied by Núñez Queija [20]. All these contributions assume that customers resume service after the interruption. Gaver Jr. [21] also considers the case where service is either repeated or repeated and resampled after the interruption. The latter operation mode is also studied by Ibe and Trivedi [11] for a two station polling system and by Krishnamoorthy et al. [22] for a queue with a Markov arrival process and phase-type service times.

Research on discrete-time queueing systems with service interruptions started later. Early contributions include those by Hsu [23] and Heines [24]. Both authors treat the single server system with Bernoulli server vacations and a Poisson arrival process. The former considers queue content at random slot boundaries whereas the latter considers queue content at service completion times. A single server system with an independent arrival process and a correlated on/off server vacation process is treated by Bruneel [25], by Yang and Mark [26] and by Woodside and Ho [27]. Yang and Mark [26] and Woodside and Ho [27] model the on- and off-periods as two series of independent shifted geometric random variables, whereas Bruneel [25] assumes that the series of consecutive on-periods as well as the series of consecutive off-periods share a common general distribution. The only restriction in the latter contribution is that the common probability generating function of the on-periods must be rational. Alternatively, correlation in the vacation process is captured by means of a Markovian process by Lee [28].

Georganas [29] and Bruneel [30] treat multi-server systems with independent customer arrival and server vacation processes. The latter extends the former in the sense that it does not assume that all servers are either available or on vacation simultaneously. The delay analysis of the latter system is presented by Laevens and Bruneel [31]. Bruneel [32] also considers a multi-server system with a correlated vacation process. Here, the vacation process is modelled as an on/off process (geometrical on-periods). The numbers of available servers during the consecutive on-slots constitute a series of independent and identically distributed non-negative random variables whereas no servers are available during off-periods.

Some contributions also allow a certain degree of correlation in the arrival process. Bruneel [33] assumes that both arrival and vacation processes are on/off processes with geometric on- and off-periods. A stochastic number of customers enters the system during arrival-on periods, whereas no customers arrive in the system during arrival-off periods. The vacation process is similar to the one analysed by Yang and Mark [26] in the case of uncorrelated arrivals. This vacation process is also considered by Ali et al. [34] and by Kamoun [35]. These authors however assume that customer arrivals come from a superposition of two-state Markovian on–off sources [34] or from a train-arrival process [35]. All the former discrete-time queueing models have fixed customer service times of a single slot in common. Queueing systems where customers have fixed multiple-slot and generally distributed service times are considered by Inghelbrecht et al. [36] and Fiems et al. [6,37,38] respectively. The vacation process is either a Bernoulli [38], a two-state Markovian [36,37] or a renewal process [6]. The combination of multiple-slot service times and vacations implies that service of a customer can be interrupted. The service may then continue [6,36–38] or repeat the service with the same [6,36–38] or a different [38] service time after the interruption. Service may also be repeated partially [6,38] or ‘‘delayed’’ after the interruption [6]. In the latter case, service continues during the vacations but is repeated until the customer receives service without vacations. Finally, as interruptions and service repetitions do render the queueing systems non-work conserving, Morozov and Fiems [39] consider stability of a discrete-time queueing system with server interruptions and resampling after the interruption under the more general setting of generally distributed on-, off- and interarrival times.

The outline of the remainder of this contribution is as follows. In the next section, the model under consideration is described in detail. The analysis is then presented in Sections 3–5. In Section 3, we derive expressions for the probability generating functions of the ‘‘effective service times’’ of customers. The effective service time approach allows us to present a unified queueing analysis for all modes under consideration. The probability generating function of the queue content and customer delay are derived in Sections 4 and 5 respectively. In Section 6, we relate our model to some existing vacation models, whereas some teletraffic applications are presented in Section 7. Finally, conclusions are drawn in Section 8.