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

- Received : November 26, 2014
- Accepted : March 20, 2015
- Published : May 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

We consider an
M^{X}
/
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
M^{X}
/
G
/1 retrial queue.
AMS Mathematics Subject Classification : 60K25.
M^{X}
/
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
) =
b_{k}
,
k
= 1, 2, . . .. Let
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
) =
[
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
ρ
=
λ
[
B
]
[
S
]. It is assumed that
ρ
< 1 for stability of the system.
The
M^{X}
/
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
M^{X}
/
G
/1 retrial queue, we refer to the book of Falin and Templeton
[8
, pp. 173-186]. The
M^{X}
/
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
M^{X}
/
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
M^{X}
/
G
/1 retrial queue, when the service time and batch size distributions have finite exponential moments, i.e.,
If (1) and (2) hold, then it can be shown that
In order to obtain the light-tailed asymptotics, we assume that there is a real number
σ
satisfying
We will show that if (3) holds, then
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
M^{X}
/
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.
M^{X}
/
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:
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
where
at
z
= 1 is interpreted as
To investigate the light-tailed behavior of the queue size distribution, we need to have a close look at singularities of
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
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
Proof
. Since the proofs of (8) and (9) are very similar, we only prove (8). We note that
has a removable singularity at
z
= 1 and is regarded as analytic at
z
= 1. By Lemma 1, there is
δ
> 0 such that
is analytic on {
z
∈ ℂ : |
z
| <
σ
+
δ
,
z
≠
σ
}. We observe that
has a simple pole at
z
=
σ
and the residue of
at
z
=
σ
is
. Therefore,
has a removable singularity at
z
=
σ
. Let
Then Ξ
_{1}
(
z
) is an analytic function on {
z
∈ ℂ : |
z
| <
σ
+
δ
} and satisfies (8).
M^{X}
/
G
/1 retrial queue when condition (3) holds.
Theorem 3.1.
If (3) holds, then
where
and
Γ(·)
denotes the gamma function
.
Proof
. First we prove (10). Substituting (8) into (6) yields
Since Ξ
_{1}
(
z
) is analytic on {
z
∈ ℂ : |
z
| <
σ
+
δ
}, so is exp
. Let
be the power series expansion of exp
at
z
= 0, i.e.,
We note that
has the power series expansion at
z
= 0:
Substituting (13) and (14) into (12) yields
Therefore,
Following the same argument as in the proof of Theorem 1 in Kim et al.
[10]
, we get
Since
as
n
→ ∞, (10) follows from (15).
Next we prove (11). Substituting (8) and (9) into (7) yields
Now we consider the power series expansions of the two terms on the right-hand side of (16) separately as follows:
By the same method which we used to derive (10), we obtain
Therefore
q_{n}
=
o
(
p_{n}
) as
n
→ ∞, and
which completes the proof of (11).
By Theorem 3.1, we have
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:
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]
.
Example 4.1.
The batch arrival rate is
λ
and the batch size has a geometric distribution with probability mass function
,
k
= 1,2,.... The service times of the customers have an exponential distribution with mean
. 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
,
i
= 0,1, where
p_{in}
= ℙ(
C
=
i
,
N
=
n
) and
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
p_{in}
is obtained as
in such that
in does not vary numerically as
K
increases.
Figs. 1
and
2
show that the asymptotic formulas (10) and (11) are very accurate.
Exact and asymptotic values of ℙ(C = i ,N = n ), i = 0, 1 when λ = 0.6.
Exact and asymptotic values of ℙ(C = i ,N = n ), i = 0, 1 when λ = 0.8.
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

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
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

2. Probability generating function of the queue size distribution

Consider the
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

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
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

4. Numerical examples

In this section numerical examples are presented to illustrate our results. We consider the following batch arrival retrial queueing model.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

BIO

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**

Citing 'TAIL ASYMPTOTICS FOR THE QUEUE SIZE DISTRIBUTION IN AN MX/G/1 RETRIAL QUEUE†
'

@article{ E1MCA9_2015_v33n3_4_343}
,title={TAIL ASYMPTOTICS FOR THE QUEUE SIZE DISTRIBUTION IN AN MX/G/1 RETRIAL QUEUE†}
,volume={3_4}
, url={http://dx.doi.org/10.14317/jami.2015.343}, DOI={10.14317/jami.2015.343}
, number= {3_4}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={KIM, JEONGSIM}
, year={2015}
, month={May}