Advanced
TAIL ASYMPTOTICS FOR THE QUEUE SIZE DISTRIBUTION IN AN MX/G/1 RETRIAL QUEUE†
TAIL ASYMPTOTICS FOR THE QUEUE SIZE DISTRIBUTION IN AN MX/G/1 RETRIAL QUEUE†
Journal of Applied Mathematics & Informatics. 2015. May, 33(3_4): 343-350
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : November 26, 2014
  • Accepted : March 20, 2015
  • Published : May 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
JEONGSIM KIM

Abstract
We consider an MX / G /1 retrial queue, where the batch size and service time distributions have finite exponential moments. We show that the tail of the queue size distribution is asymptotically given by a geometric function multiplied by a power function. Our result generalizes the result of Kim et al. (2007) to the MX / G /1 retrial queue. AMS Mathematics Subject Classification : 60K25.
Keywords
1. Introduction
Retrial queues are queueing systems in which arriving customers who find all servers occupied may retry for service again after a random amount of time. Retrial queues have been widely used to model many problems/situations in telephone systems, call centers, telecommunication networks, computer networks and computer systems, and in daily life. For an overview regarding retrial queues, refer to the surveys [7 , 12 , 16] . For further details, refer to the books [4 , 8] and the bibliographies [1 , 2 , 3] .
The single server batch arrival retrial queues are characterized by the following features: If the server is idle when a batch of customers arrive from outside the system, then one customer of that batch begins to be served immediately while the other customers join a retrial group, called an orbit. If the server is busy when a batch of customers arrive from outside the system, then all the customers of that batch join the orbit. All the customers in the orbit behave independently of each other. If the server is idle when a customer from the orbit attempts service, this customer receives service immediately. Otherwise the customer comes back to the orbit immediately and repeats the retrial process. Thus only the external arrivals take place in batches and the retrials are conducted singly.
We consider the MX / G /1 retrial queue where customers arrive from outside the system in batches according to a Poisson process with rate λ . The batch sizes are independent and identically distributed (i.i.d.) random variables with a generic random variable B and common distribution ℙ( B = k ) = bk , k = 1, 2, . . .. Let
PPT Slide
Lager Image
be the probability generating function (pgf) of the batch size distribution. The service times are i.i.d. random variables with a generic random variable S . Let β ( s ) =
PPT Slide
Lager Image
[ e−sS ] be the Laplace-Stieltjes transform of the service time distribution. The inter-retrial time, i.e., the length of the time interval between two consecutive attempts made by a customer in the orbit, is exponentially distributed with mean ν −1 . The arrival process, the batch sizes, the service times, and the inter-retrial times are assumed to be mutually independent. The offered load ρ is defined as ρ = λ
PPT Slide
Lager Image
[ B ]
PPT Slide
Lager Image
[ S ]. It is assumed that ρ < 1 for stability of the system.
The MX / G /1 retrial queue has been studied by several authors. Falin [5] obtained the pgf of the joint distribution of the server state and the number of customers in the orbit (queue size). For a detailed analysis of the MX / G /1 retrial queue, we refer to the book of Falin and Templeton [8 , pp. 173-186]. The MX / G /1 retrial queue with multiclass of customers was studied by Kulkarni [11] , Falin [6] and Grishechkin [9] .
We are interested in the tail asymptotics of the queue size distribution. Shang et al. [13] studied the heavy-tailed asymptotics for the queue size distribution in the M / G /1 retrial queue. Specifically, Shang et al. [13] showed that the stationary distribution of the queue size in the M / G /1 retrial queue is subexponential if the stationary distribution of the queue size in the corresponding standard M / G /1 queue is subexponential. As a corollary of this property, they proved that the stationary distribution of the queue size has a regularly varying tail if the service time distribution has a regularly varying tail. Yamamuro [15] extended the result of Shang et al. [13] to the MX / G /1 retrial queue, when the batch size distribution has a finite exponential moment.
The main contribution of this paper is to find the light-tailed asymptotics for the queue size distribution in the MX / G /1 retrial queue, when the service time and batch size distributions have finite exponential moments, i.e.,
PPT Slide
Lager Image
PPT Slide
Lager Image
If (1) and (2) hold, then it can be shown that
PPT Slide
Lager Image
In order to obtain the light-tailed asymptotics, we assume that there is a real number σ satisfying
PPT Slide
Lager Image
We will show that if (3) holds, then
PPT Slide
Lager Image
PPT Slide
Lager Image
for positive constants a , c 0 and c 1 , where N is the number of customers in the orbit at steady state and C is 0 if the server is idle at steady state and 1 otherwise. The constants a , c 0 and c 1 are given explicitly. The results (4) and (5) are obtained by investigating the pgfs for C and N through decomposing a component of the pgfs as a sum of the principal part and the analytic part. Our result generalizes the result of Kim et al. [10] to the MX / G /1 retrial queue.
The paper is organized as follows. In Section 2, we study the pgfs for the server state and the number of customers in the orbit. In Section 3, we prove (4) and (5). In Section 4, numerical results are presented to illustrate our results.
2. Probability generating function of the queue size distribution
Consider the MX / G /1 retrial queue at steady state. Recall that N is the number of customers in the orbit and C is 0 if the server is idle and 0 otherwise. We suppose that (3) holds. We define the pgfs p 0 ( z ) and p 1 ( z ) as follows:
PPT Slide
Lager Image
It is well known (see Falin [5] , Theorem 3.1 in Falin and Templeton [8] ) that the pgfs p 0 ( z ) and p 1 ( z ) are given by
PPT Slide
Lager Image
PPT Slide
Lager Image
where
PPT Slide
Lager Image
at z = 1 is interpreted as
PPT Slide
Lager Image
To investigate the light-tailed behavior of the queue size distribution, we need to have a close look at singularities of
PPT Slide
Lager Image
on { z ∈ ℂ : | z | < γ }. Lemma 2.1, below, locates the zeros of β ( λ λ b ( z )) − z , | z | ≤ σ . The proof is very similar to Lemma 1 of Kim et al. [10] and so we will omit it.
Lemma 2.1. The analytic function β ( λ λ b ( z ))− z , | z | < γ , has simple zeros at 1 and σ. Furthermore, it has no other zeros on { z ∈ ℂ : | z | ≤ σ }.
The following lemma decomposes
PPT Slide
Lager Image
as sums of the principal parts at z = σ and the analytic parts.
Lemma 2.2. There are δ ∈ (0, γ σ ) and analytic functions Ξ 1 ( z ) and Ξ 2 ( z ) on { z ∈ ℂ : | z | < σ + δ } such that
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof . Since the proofs of (8) and (9) are very similar, we only prove (8). We note that
PPT Slide
Lager Image
has a removable singularity at z = 1 and is regarded as analytic at z = 1. By Lemma 1, there is δ > 0 such that
PPT Slide
Lager Image
is analytic on { z ∈ ℂ : | z | < σ + δ , z σ }. We observe that
PPT Slide
Lager Image
has a simple pole at z = σ and the residue of
PPT Slide
Lager Image
at z = σ is
PPT Slide
Lager Image
. Therefore,
PPT Slide
Lager Image
has a removable singularity at z = σ . Let
PPT Slide
Lager Image
Then Ξ 1 ( z ) is an analytic function on { z ∈ ℂ : | z | < σ + δ } and satisfies (8). ΢
3. Tail asymptotics for the queue size distribution
In this section we prove the main result of this paper which provides the tail asymptotics of the queue size distribution in the MX / G /1 retrial queue when condition (3) holds.
Theorem 3.1. If (3) holds, then
PPT Slide
Lager Image
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and Γ(·) denotes the gamma function .
Proof . First we prove (10). Substituting (8) into (6) yields
PPT Slide
Lager Image
Since Ξ 1 ( z ) is analytic on { z ∈ ℂ : | z | < σ + δ }, so is exp
PPT Slide
Lager Image
. Let
PPT Slide
Lager Image
be the power series expansion of exp
PPT Slide
Lager Image
at z = 0, i.e.,
PPT Slide
Lager Image
We note that
PPT Slide
Lager Image
has the power series expansion at z = 0:
PPT Slide
Lager Image
Substituting (13) and (14) into (12) yields
PPT Slide
Lager Image
Therefore,
PPT Slide
Lager Image
Following the same argument as in the proof of Theorem 1 in Kim et al. [10] , we get
PPT Slide
Lager Image
Since
PPT Slide
Lager Image
as n → ∞, (10) follows from (15).
Next we prove (11). Substituting (8) and (9) into (7) yields
PPT Slide
Lager Image
Now we consider the power series expansions of the two terms on the right-hand side of (16) separately as follows:
PPT Slide
Lager Image
By the same method which we used to derive (10), we obtain
PPT Slide
Lager Image
Therefore qn = o ( pn ) as n → ∞, and
PPT Slide
Lager Image
which completes the proof of (11). ΢
By Theorem 3.1, we have
PPT Slide
Lager Image
Therefore, the following corollary is immediate.
Corollary 3.2. If (3) holds, then the queue size N and the number of customers in the system, C + N, have distributions with the following tail asymptotics:
PPT Slide
Lager Image
Remark 3.1. If b ( z ) = z (i.e., single arrival M / G /1 retrial queue), then Theorem 3.1 reduces to Theorem 1 of Kim et al. [10] .
4. Numerical examples
In this section numerical examples are presented to illustrate our results. We consider the following batch arrival retrial queueing model.
Example 4.1. The batch arrival rate is λ and the batch size has a geometric distribution with probability mass function
PPT Slide
Lager Image
, k = 1,2,.... The service times of the customers have an exponential distribution with mean
PPT Slide
Lager Image
. The retrial rate is ν = 10.
In Figs. 1 and 2 , we plot the exact and asymptotic values of ℙ( C = i , N = n ), i = 0, 1, for Example 4.1 with λ = 0.6 and λ = 0.8, respectively. The asymptotic values of ℙ( C = 0, N = n ) and ℙ( C = 1, N = n ) are obtained by using formulas (10) and (11), respectively. The exact value is obtained as follows: It is known that
PPT Slide
Lager Image
, i = 0,1, where pin = ℙ( C = i , N = n ) and
PPT Slide
Lager Image
is the probability that the number of busy servers is i and there are n customers in the orbit at steady state in the corresponding queue with orbit of finite capacity K . The probability pin is obtained as
PPT Slide
Lager Image
in such that
PPT Slide
Lager Image
in does not vary numerically as K increases. Figs. 1 and 2 show that the asymptotic formulas (10) and (11) are very accurate.
PPT Slide
Lager Image
Exact and asymptotic values of ℙ(C = i,N = n), i = 0, 1 when λ = 0.6.
PPT Slide
Lager Image
Exact and asymptotic values of ℙ(C = i,N = n), i = 0, 1 when λ = 0.8.
BIO
Jeongsim Kim received B.S., M.S. and Ph. D. in Mathematics from Korea University. She is currently a professor at Chungbuk National University since 2004. Her research interests include probability theory, stochastic models and queueing theory.
Department of Mathematics Education, Chungbuk National University, 1 Chungdae-ro, Seowon-gu, Cheongju, Chungbuk, 362-763, Korea
e-mail: jeongsimkim@chungbuk.ac.kr
References
Artalejo J.R. (1999) A classified bibliography of research on retrial queues: Progress in 1990-1999 Top 7 187 - 211    DOI : 10.1007/BF02564721
Artalejo J.R. (1999) Accessible bibliography on retrial queues Math. Comput. Model. 30 1 - 6    DOI : 10.1016/S0895-7177(99)00128-4
Artalejo J.R. (2010) Accessible bibliography on retrial queues: Progress in 2000-2009 Math. Com-put. Model. 51 1071 - 1081    DOI : 10.1016/j.mcm.2009.12.011
Artalejo J.R. , Gómez-Corral A. Springer Retrial Queueing Systems 2008
Falin G.I. (1976) Aggregate arrival of customers in a one-line system with repeated calls Ukrainian Mathematical Journal 28 437 - 440    DOI : 10.1007/BF01101670
Falin G.I. (1988) On a multiclass batch arrival retrial queue Adv. Appl. Probab. 20 483 - 487    DOI : 10.2307/1427403
Falin G.I. (1990) A survey of retrial queues Queueing Systems 7 127 - 168    DOI : 10.1007/BF01158472
Falin G.I. , Templeton J.G.C. 1997 Retrial Queues Chapman & Hall London
Grishechkin S.A. (1992) Multiclass batch arrival retrial queues analyzed as branching process with immigration Queueing Systems 11 395 - 418    DOI : 10.1007/BF01163863
Kim J. , Kim B. , Ko S-S. (2007) Tail asymptotics for the queue size distribution in an M/G/1 retrial queue J. App. Probab. 44 1111 - 1118    DOI : 10.1239/jap/1197908829
Kulkarni V.G. (1986) Expected waiting times in a multiclass batch arrival retrial queue J. Appl. Probab. 23 144 - 154    DOI : 10.2307/3214123
Kulkarni V.G. , Liang L.H. 1997 Retrial queues revisited, In: Frontiers in Queueing: Models and Applications in Science and Engineering (J.H. Dshalalow, ed.) CRC Press Boca Raton 19 - 34
Shang W. , Liu L. , Li Q. (2006) Tail asymptotics for the queue length in an M/G/1 retrial queue Queueing Systems 52 193 - 198    DOI : 10.1007/s11134-006-5223-1
Shin Y.W. , Moon D.H. (2013) On approximations for GI/G/c retrial queues J. Appl. Math. & Informatics 31 311 - 325    DOI : 10.14317/jami.2013.311
Yamamuro K. (2012) The queue length in an M/G/1 batch arrival retrial queue Queueing Systems 70 187 - 205    DOI : 10.1007/s11134-011-9268-4
Yang T. , Templeton J.G.C. (1987) A survey on retrial queues Queueing Systems 2 201 - 233    DOI : 10.1007/BF01158899