A simulation study of a discrete-time multiserver retrial queue with finite population
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 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 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 can be described by the process , where represents the number of busy servers and denotes the number of customers in orbit. We note that the process ; is a Markov chain with state space . Since S is finite, the Markov chain is always positive recurrent. Our main objective is to compute the steady-state probabilities , for .
The key point for computing ; 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 on the main system descriptors. To this end, we consider . Each cell in the table contains, from top to bottom, three values: , and . Numerical results show that and B are increasing functions of p and . In contrast, also increases with p but it decreases with .
Table 2 shows the incidence of c and N on the
Acknowledgment
This research was supported by the project MTM2005-01248.
References (16)
Accessible bibliography on retrial queues
Math. Comput. Modelling
(1999)- et al.
Performance analysis and optimal control of the Geo/Geo/c queue
Performance Evaluation
(2003) - et al.
A discrete-time /G/1 retrial queue with control of admission
Appl. Math. Modelling
(2005) - et al.
Discrete-time //1 retrial queue with Bernoulli feedback
Comput. Math. Appl.
(2004) - et al.
Discrete-time /G/1 retrial queueing system with two types of calls
Comput. Math. Appl.
(1997) - et al.
A finite source retrial queue
European J. Oper. Res.
(1998) - et al.
Discrete-time multiserver queues with geometric services times
Comput. Oper. Res.
(2004) - et al.
Geo/G/1 discrete time retrial queue with Bernoulli schedule
European J. Oper. Res.
(1998)