1. INTRODUCTION
In this article we consider an M/G/1 retrial queue. Primary customers arrive according to a Poisson process with arrival rate λ and have a general service requirement with common probability distribution function B(x) (B(0) = 0), kth moment βk, and Laplace transform β(s). Any customer who, upon arrival, finds the server busy immediately leaves the service area and joins a retrial group called orbit. Each customer in orbit can retry for service after an exponential time of rate μ. The flow of primary arrivals, the intervals between successive repeated attempts, and the service times are assumed to be mutually independent.
The system state at time t can be described by means of the process X = {(C(t),N(t),ξ(t)); t ≥ 0}, where C(t) represents the server state at time t, 0, or 1 according to whether the server is free or busy, N(t) denotes the number of customers in orbit, and if C(t) = 1, then ξ(t) is defined as the elapsed service time of the customer being served. We assume that ρ = λβ1 < 1, so the queuing model is stable and the limiting probabilities Pij = limt→∞ P{C(t) = i,N(t) = j}, for
, exist and are positive.
The model described above is presented in the work of Falin and Templeton [4] as “the main single-server model.” Generalizations of the M/G/1 retrial queue can be used to model stochastically many telephone networks where new developments such as autorepeat facilities lead to an increase of the repeated attempts. The existing literature includes a large number of applications to computer and telecommunication systems: cellular mobile networks, call centers, collision-avoidance protocols for local area networks, and so forth.
The analysis of the limiting probabilities of the M/G/1 retrial queue is numerically tractable. In fact, the partial generating functions
, for i ∈ {0,1}, have explicit solutions [4, Sect.1.2]. Alternatively, the recursive computation of the limiting probabilities can be based on different approaches (embedded Markov chain at departure epochs, regenerative approach, limit results from Markov renewal theory, etc.). In contrast, it is still necessary to carry out a qualitative investigation of other classical descriptors of the queueing performance whose exact solution is very cumbersome. This is the case of the distributions of the busy period (i.e., the subject matter of this article) and the waiting time.
The busy period of the M/G/1 retrial queue, L, starts with the arrival of a primary customer who finds the system empty and ends at the first service completion epoch at which the system becomes empty again. The Laplace transform of L is given by (see [4, Sect.1.6])
where L∞*(s) denotes the Laplace transform for the busy period in the standard M/G/1 queue satisfying L∞*(s) = β(s + λ − λL∞*(s)) and e(s,u) is
Formulas (1.1) and (1.2) provide a theoretical solution, but they have serious limitations in practice. In particular, the moments of L cannot be obtained by direct differentiation. From the theory of regenerative processes, it is easy to express the expectation E [L] as follows:
In [3], direct method of calculation is developed to obtain explicit expressions for the second order moments of L.
Unfortunately, it does not seem possible to numerically invert the density function of L because solution (1.1) is derived when s is a real number and algorithmic methods of numerical inversion typically require to one evaluate the Laplace transform at any desired complex s. Our main objective in this article is to overcome the difficulties inherent to the busy period in the M/G/1 retrial queue. To this end, we approximate the original M/G/1 model by putting a fictitious limit, K, on the orbit capacity. The resulting M/G/1/K retrial queue can be algorithmically investigated by using simple tools.
For an approximate analysis of L in the M/M/c retrial queue, see the recent treatment given in [1]. As related work, we also mention the article by Artalejo and Falin [2] who studied in more detail the structure of L, in the single-server case by introducing two new characteristics of the orbit.
In the next section we use the catastrophe method to derive the system of equations governing the dynamic of L in the M/G/1/K retrial queue. As a result, we obtain a highly tractable route of approximate evaluation for the characteristics of L in the original intractable M/G/1 retrial queue. A numerical example illustrates the implementation of our approach.
2. THE BUSY PERIOD
In this section we investigate the busy period of the M/G/1/K retrial queue. We employ the method of catastrophes, which simplifies the probabilistic reasoning and readily leads to equations governing the dynamic of the busy period (see [5, Chap.7]). Let us assume that L starts at the instant t = 0. We consider a catastrophe process independent of the functioning of our queuing system, which generates catastrophes at a rate s according to a Poisson process. Suppose that at the epoch of the kth service completion, there are j customers in orbit, no catastrophe occurred prior to that moment, and the busy period is still in progress. Let Pj(k)(s) denote the probability of that event. We also define Πk(s) as the probability that during the busy period, no catastrophe occurs and k customers are served.
The probabilities Pj(k)(s) satisfy the following formulas:
where
To prove (2.1) we note that the event under consideration takes place if no catastrophe occurs and j primary customers arrive during the service time. Equation (2.3) describes the motion between two successive service completion epochs. The term λ/(s + λ + nμ) (respectively nμ/(s + λ + nμ)) indicates that the kth service time corresponds to a primary arrival (respectively retrial customer). In the case j = K, we accumulate the probability of the blocked customers and use the same argument to get (2.2) and (2.4).
It is clear that
Thus, the Laplace transform L*(s) can be obtained as
We now extend the notation and define
, for 0 ≤ j ≤ K, so L*(s) = φ0(s). Then, from (2.1)–(2.4), we have
After solving the linear system (2.9)–(2.10), we can compute L*(s) for any given s. This is the key to using Laplace inversion algorithms (see [7, Appendix F]) for the numerical inversion of the density fL(x).
After appropriate differentiation, we get equations for the computation of the moments of L. The derivations are standard and thus omitted. In particular, the expectation E [L] is helpful to determine the truncation level K as the first positive integer such that the first four decimal digits of E [L] are fitted. According to this criterion, we need to increase successively the value of K and compare the expected value of L in the M/G/1/K and the M/G/1 retrial queues. The latter can be calculated from (1.3).
In Figure 1, we compare the shape of fL(x) for different choices of the service time distribution. To this end, we consider exponential, Erlang-4 (E4), and hyperexponential (H2) service times with ρ = 0.4 and β1 = 1. We take the coefficient of variation of the H2 law as 1.25. Exponential and H2 densities exhibit a decreasing shape, whereas we observe a bell shape associated with E4 case. We note that the numerical inversion is consistent with the Tauberian expression fL(0) = lims→∞ sL*(s). As lims→∞ skj(s) = δj0 fB(0) (here fB(x) denotes the service time density and δj0 is Kronecker's function), (2.9) yields fL(0) = fB(0).
The effect of the service time distribution on L.
A question worthy of being investigated is the convergence of the truncated retrial queue to the original M/G/1 retrial queue as K → ∞. Since the distribution function of L in the M/G/1 retrial queue is unknown, in our numerical experiments we compare the value of the Laplace transform L*(s) of the infinite model versus their counterparts obtained in truncated models with increasing values of K. According to our experience, the convergence is fast and the proposed method for choosing K suffices for practical purposes. Indeed, our work yields more accurate estimations than those based on the use of the principle of maximum entropy [6].
Acknowledgment
This work was supported by MEC grant no. MTM2005-01248.
