A simulation study of a discrete-time multiserver retrial queue with finite population

https://doi.org/10.1016/j.jspi.2006.04.018Get rights and content

Abstract

In this paper, we deal with a discrete-time multiserver retrial queue with finite population. Firstly, we study the Markov chain at the epochs immediately after slot boundaries making emphasis on the computation of its steady-state distribution. Then, the main performance measures are investigated. Besides, we simulate the waiting time of a customer in the retrial group under three different queueing policies. Some numerical examples are given to illustrate the analysis.

Introduction

Many queueing situations have the feature that customers who find all the servers busy upon arrival are obliged to abandon the service area and repeat their request after some random time. The most obvious applications of retrial queues arise in telephony where customers receiving a busy signal are not allowed to queue and have to try again at some time later. Many other applications include communication protocols, local area networks and queues arising in daily life situations. For a comprehensive survey of the main results and literature, the reader is referred to Falin and Templeton (1997) and Artalejo (1999).

Retrial literature was initially focused on continuous-time systems. Yang and Li (1995) were the first to study a discrete-time model of Geo/G/1 type with geometric retrial times. Since the publication of this pioneering paper, several authors have investigated a variety of single-server discrete-time retrial queues (see e.g. Artalejo et al., 2005; Atencia and Moreno, 2004a, Atencia and Moreno, 2004b; Choi and Kim, 1997; Li and Yang, 1998, Li and Yang, 1999; Takahashi et al., 1999). A fundamental motivation for the study of discrete-time queues is that these models are appropriate for modelling computer and telecommunications systems since the basic units are digital. In this sense, we refer to the books by Bruneel and Kim (1993) and Woodward (1994).

As far as we know, the existing literature on discrete-time retrial queues covers only the single-server case. In this paper, we try to fill this gap. Investigation of multiserver continuous-time retrial queues is a complicate problem due to the space-heterogeneity caused by the repeated attempts. In fact, explicit solutions have been achieved only in a few special cases, so the implementation of numerically tractable approximations is a must (see Falin and Templeton, 1997; and Artalejo and Pozo, 2002). The analytical difficulties typically increase when we deal with discrete-time models. It should be noticed that many different events may occur within a determined slot. The nature and combination of the occurring events lead to a diversity of transition possibilities. Therefore, the underlying matrix structure becomes sparse.

We will focus on the case in which the population under study is finite so each individual customer generates his own flow of primary arrivals. As a result, the system state is finite but the dynamic of the queue depends on non-homogeneous rates. For the analysis of finite source retrial queues in continuous-time, the interested reader is referred to Falin and Templeton (1997) and Falin and Artalejo (1998).

As related work, we mention the existence of an abundant related literature in the context of multiserver discrete-time queues without retrials (see Artalejo and Hernandez-Lerma, 2003; Gao et al., 2004).

The rest of the paper is organized as follows. In Section 2, we describe the mathematical model and the order in which the queueing activities occur within each slot. In Section 3, we present the steady-state analysis of the system state and describe three different queueing policies: random order (RO), first-come-first-served (FCFS) and last-come-first-served (LCFS). The exact meaning of the three policies in the context of a discrete-time retrial queue is discussed. The incidence of the queueing discipline on the waiting time is studied through simulation because there are no analytical results available. This is done in Section 4. Furthermore, some other performance measures are numerically investigated.

Section snippets

The mathematical model

We consider a multiserver discrete-time retrial queue where the time axis is divided into equal intervals, of width one, called slots. The number of servers is denoted by c. We deal with a finite population of size N(N>c) where each individual customer generates requests independently of the rest of the population. It is assumed that all queueing activities (i.e., arrivals, departures and retrials) occur around the slot boundaries. For mathematical convenience, we suppose that departures occur

Steady-state analysis

The system state at time h+ can be described by the process Xh=(Ch,Oh), where Ch represents the number of busy servers and Oh denotes the number of customers in orbit. We note that the process {Xh; h0} is a Markov chain with state space S={0,,c}×{0,,N-c}. Since S is finite, the Markov chain is always positive recurrent. Our main objective is to compute the steady-state probabilities πij=limhP{(Ch,Oh)=(i,j)}, for (i,j)S.

The key point for computing {πij; (i,j)S} is to obtain the one step

Performance analysis and simulation

In order to evaluate the system quality some computational experiments are performed.

First, in Table 1 we illustrate the influence of the pair (p,s) on the main system descriptors. To this end, we consider (q,c,N)=(0.5,5,20). Each cell in the table contains, from top to bottom, three values: E[O], E[C] and B. Numerical results show that E[C] and B are increasing functions of p and s. In contrast, E[O] also increases with p but it decreases with s.

Table 2 shows the incidence of c and N on the

Acknowledgment

This research was supported by the project MTM2005-01248.

References (16)

There are more references available in the full text version of this article.

Cited by (0)

View full text