=Paper=
{{Paper
|id=None
|storemode=property
|title=Performance Analysis of M/G/1 Retrial Queue with Finite Source Population Using Markov Regenerative Stochastic Petri Nets
|pdfUrl=https://ceur-ws.org/Vol-1160/paper13.pdf
|volume=Vol-1160
|dblpUrl=https://dblp.org/rec/conf/apn/LyesLA14
}}
==Performance Analysis of M/G/1 Retrial Queue with Finite Source Population Using Markov Regenerative Stochastic Petri Nets==
https://ceur-ws.org/Vol-1160/paper13.pdf
Performance Analysis of M/G/1 Retrial Queue
with Finite Source Population Using Markov
Regenerative Stochastic Petri Nets
Lyes Ikhlef1 , Ouiza Lekadir2 and Djamil Aı̈ssani3
Research Unit LaMOS (Laboratories of Modelization and Optimization of Systems)
Bejaia University.
1
ikhlefilyes@gmail.com
2
ouizalekadir@gmail.com
3
lamos bejaia@hotmail.com
Abstract. This paper aims to present an approach for modeling and
analyzing an M/G/1//2 retrial queue, using the M RSP N ( Markov
Regenerative Stochastic Petri Nets ) tool. The consideration of the re-
trials and finite source population introduce analytical difficulties. The
expressive power of the M RSP N formalism provides us with a detailed
modeling of retrial systems. In addition to this modeling, this formalism
gives us a qualitative and a quantitative analysis which allow us to obtain
the steady state performance indices. Indeed, some illustrative numerical
results will be given by using the software package Time Net.
Keywords: Markov Regenerative Process, Markov Regenerative Stochas-
tic Petri Nets, Retrial Systems, Steady State, Modeling, Performance
Evaluation.
1 Introduction
Retrial queueing systems have been extensively studied by several authors
including Kosten 1947, Wilkinson 1956, Cohen 1957. A survey work on the topic
has been written by Falin and Templeton [9]. An exhaustive bibliography is given
in Artalejo [5]. Recently, several papers were published for retrial systems [16,4].
These queueing models arise in many practical applications such as: computer
systems, communication systems, telephone systems, etc.
The main characteristic of retrial systems is that, an incoming customer having
found the server busy does not exit the system but it joins the orbit to repeat
its demand after a random period ( see FIG. 1 ).
Generally, the analytical treatment of retrial systems is difficult to obtain. Tak-
ing into account the flow of the repeated calls complicate the structure of the
stochastic process corresponds to the retrial systems.
In order to evaluate the performances of these systems, a large number of di↵er-
ent approximating algorithms and approaches were proposed [11,18,19].
222 PNSE’14 – Petri Nets and Software Engineering
Fig. 1. Schematic diagram of retrial queue
Stochastic Petri Nets (SP N ) are Petri nets in which each transition is associated
with an exponentially distributed random variable that expresses the delay from
the enabling condition to the firing of the transition. They are defined by Molloy
[12] then extended by A. Marson et al [8] to a class of generalized stochastic
Petri nets (GSP N ) by allowing immediate transition. The underlying stochastic
process of SP N or GSP N is a continuous time Markov chain (CT M C). H.
Choi [6] introduced a new class called Markov regenerative stochastic Petri nets
(M RSP N ), where a timed transition can fire according to an exponential or
any other general distribution function. The underlying stochastic process of
M RSP N is the Markov regenerative process (M RGP ). With the restriction
at most one generally distributed timed transition is enabled in each marking.
The process subordinated in two regeneration time points is a continuous time
Markov chain.
The main advantages of an M RSP N are:
– Modeling and evaluating the performance of complex systems comprising
concurrency, synchronization, etc
– Providing automated generation and solution to discrete time Markov chains.
– O↵ering a qualitative and a quantitative analysis of systems.
– Existence of software tools developed within the M RSP N (Time Net, SHARP,
WebSPN, . . .)
Most studies in the literature deal with infinite customers source retrials queues.
However, in many practical situations, it is important to consider that the rate
of generation of new primary calls decreases as the number of customers in the
system increases. This can be done with the finite-source or quasi-random input
models. The Markovian GSP N is used by N. Gharbi [14,4] for analyzing an
retrial queue and Oliver [17] for studying an M/M/1//N queue with vacation.
In 1993 H. Choi [6,7] carries out the transient and steady state analysis of
M RSP N (non-Markovian GSP N ), as example M/G/1/2/2 is analyzed. Re-
cently, the performance analysis of queueing systems M/G/1//N with di↵erent
I. Lyes et al.: Performance Analysis of M/G/1 Retrial Queue 223
vacation schemes is given by K.Ramanath and P.Lakshmi[10]. The structure of
the transition probability matrix P of the embedded Markov chain EM C re-
lated to M/G/1//N with retrial is not an M/G/1-type [13]. Unfortunately, for
such an EM C there is not a general solution and the matrix analytic method
(M AM ) can not be applied for analyzing these processes. Our goal in this work,
is to exploit the features of M RSP N for modeling and performance analysis of
retrial queue M/G/1 with finite source population.
The remainder of this paper is organized as follows. In section 2, we introduce
the analysis technique proposed for M RSP N . In section 3, we describe the
M RSP N associated to the system M/G/1//N with retrial. In section 4 and 5
some performance measures are provided. Finally, the section 6 concludes the
paper.
2 Steady State Analysis of MRSPN
Di↵erent approaches and numerical techniques have been explored in the liter-
ature for dealing with non-Markovian GSP N , we quote:
– The approach of approximating the general distribution by phase type ex-
pansion [1]
– The approach based on Markov regenerative theory [6]
– The approach based on supplementary variable [3]
The analysis of MRSPN is based on the observation that the underlying stochas-
tic process {M (t), t 0} enjoys the absence of memory at certain instants of
time (t0 , t1 , t2 , ...). This instants referred as regeneration points. An embedded
Markov chain (EM C) {Yn , n 0} can be defined at the regeneration points. An
analytical procedure for the derivation of expression for the steady state proba-
bility is proved in [6]. The conditionals probability necessary for the analysis of
a M RSP N are:
– The matrix K(t) is called global kernel given by Kij (t) = P {Y1 = j, t1
t/Y0 = i, i, j 2 ⌦}. It describes the process behavior immediately after the
next Markov regenerative point. (⌦ is the set of state of tangible markings).
– The matrix E(t) is called the local kernel given by Eij (t) = P {Mt = j, t1 >
t/Y0 = i}. It is for the behavior between two Markov regeneration points.
When the EM C is finite and irreducible its steady state probability vector v
is obtained by the solution of the linear system equation: vP = v and v1 = 1.
Where the one-step transition probability matrix P of the EM C is derived
from the global kernel ( P = lim K(t)). The steady state distribution ⇡ =
t!+1 P
vk ↵kj
(⇡1 , ⇡2 , ...) of the M RGP can be obtained by: ⇡ = Pk2⌦
v
P
↵
where ↵ij =
k kl
R1 k2⌦ l2⌦
0
Eij (t)dt .
224 PNSE’14 – Petri Nets and Software Engineering
3 M/G/1//N with Retrials
We consider a single server retrial queue with finite population of size N . A
customer arrives from the source according to a poisson process with parameter
” ”. When the server is idle the customer immediately occupies the service.
The service time distribution follows a general law with probability distribution
function F g (x). If the server is busy, the customer joins the orbit to repeat its
demand for service after an exponential time with parameter ✓ until it finds a free
server. FIG. 2 shows the M RSP N model describing the M/G/1//N queueing
system with retrial. In FIG. 2 thick black bar represents GEN transition, thick
white bars represent EXP transitions, thin bars represent immediate transitions.
Fig. 2. MRSPN for the M/G/1//N retrial queueing system.
The initial marking of the M RSP N is :
M1 (M (p.sour), M (p.sys), M (p.serv), M (p.orb)) = M1 (N, 0, 0, 0)
• The firing of timed transition t.arriv indicates the arrival of a customer in
source thus the place p.sys receives a token. The firing of t.arriv is marking
dependent, its firing rate is #(p.sour) .
• The immediate transition t.acc1 is enabled when the place p.sys contains at
least one token and p.serv contains no token ( the server is free). The firing
of t.acc1 consists to destroy a token in place p.sys and builds a token in place
p.serv (this represents the fact that the customer has started its service and
the server is moved from the free state to the busy state).
I. Lyes et al.: Performance Analysis of M/G/1 Retrial Queue 225
• The firing of the timed transition t.serv consists to destroy a token in the
place p.serv and constructs a token in the place p.sour (the costumer has
completed its service). The server is moved from the busy state to the free
state. The firing policies of t.serv is the race with enabling memory.
• The immediate transition t.acc2 is enabled when the place p.sys and p.serv
contain a token (the server is busy). The firing of the transition t.acc2 con-
sists to destroy a token in p.sys and constructs a token in place p.orb (the
customer joins the orbit). The immediate transition t.acc1 has higher priority
than the immediate transition t.acc2.
• The firing of the timed transition t.ret consists to remove a token from place
p.orb and constructs a token in place p.sys. The firing of t.ret is marking
dependent, thus its firing rate is #(p.orb) .
4 Case of the M/G/1//2 retrial queueing system
In this section we consider the M/G/1//2 retrial queue. We obtain the reacha-
bility tree which describes all possible states of our M RSP N starting from the
initial marking M1 (see FIG. 3).
From this reachability tree, by marging the vanishing markings into their suc-
cessor tangible markings, we have obtained the state transition diagram of the
M RSP N depicted in FIG.2
In FIG.4 solid arcs indicate state transition by EXP transitions, dotted arcs
indicate state transitions by GEN transitions.
The infinitesimal generator matrix of the subordinated CT M C with respect to
transition t.serv is given by:
0 1
2 2 0 0
B 0 0 C
Q=@
0 ✓ (✓ + ) A
0 0 0 0
Local kernel E(t) :
0 1
e 2 t 0 0 0
t g t g
B 0 e [1 F (t)] 0 (1 e )[1 F (t)] C
E(t) = @ A
0 0 e (✓+ )t 0
0 0 1 F g (t) 0
Global kernel K(t) :
0 1
0 1 e 2 t 0 0
Rt Rt
B e dF (x)
x g
0 [1 e]dF (x)x g
0 C
B
K(t) = @ 0 0 C
0 ✓
[1 e (✓+ )t
] 0 [1 e (✓+ )t ] A
✓+ Rt g ✓+
0 0 0
dF (x) 0
226 PNSE’14 – Petri Nets and Software Engineering
Fig. 3. Reachability tree for the M RSP N of FIG. 2 (N = 2).
Fig. 4. Subordinated CTMC for the M RSP N of FIG.2 (N = 2).
Where the density function of the firing time of t.serv is given by hyperexpo-
1
nential distribution ”H2 ( 13 , µ2 , µ)”: f g (x) = 16 µe 2 µx + 23 µe µx . The one-step
I. Lyes et al.: Performance Analysis of M/G/1 Retrial Queue 227
transition probability matrix P given by:
0 1
0 1 0 0
B1 µ(5 +3µ)
0 2 (3 +2µ)
0 C
P =B
@
3 (2 +µ)( +µ)
✓
3 (2 +µ)( +µ) C
A
0 ✓+
0 ✓+
0 0 1 0
The M RSP N depicted in FIG. 2 (N = 2), is bounded and admits M1 like home
state so it is ergodic.
We calculate the steady state probabilities by solving: vP = v and v1 = 1:
1 ✓µ(5 + 3µ)
v1 = ,
2 6✓ 2 + 9✓ µ + 3✓µ2 + 6 3 + 4 2 µ
3 ✓(2 + µ)( + µ)
v2 =
2 6✓ 2 + 9✓ µ + 3✓µ2 + 6 3 + 4 2 µ
(✓ + )(3 + 2µ)
v3 = ,
6✓ 2 + 9✓ µ + 3✓µ2 + 6 3 + 4 2 µ
2
(3 + 2µ)
v4 = 2 + 9✓
6✓ µ + 3✓µ2 + 6 3 + 4 2 µ
2
3 +2µ 4 +3 µ
↵11 = 21 , ↵22 = 23 (2 +µ)( 2 1
+µ) , ↵24 = 3 µ(2 +µ)( +µ) , ↵33 = ↵+ , ↵44 = 3µ
4
The steady state probabilities: ⇡ = (⇡(2,0,0,0) , ⇡(1,0,1,0) , ⇡(1,0,0,1) , ⇡(0,0,1,1) ) are
given by:
3✓µ2 (5 + 3µ)
⇡(2,0,0,0) =
39✓µ2 + 9✓µ3 + 48✓ 3 + 72✓ 2 µ + 68 3 µ + 24 2 µ2 + 48 4
12✓ µ(3 + 2µ)
⇡(1,0,1,0) =
39✓µ2 + 9✓µ3 + 48✓ 3 + 72✓ 2 µ + 68 3 µ + 24 2 µ2 + 48 4
12 2 µ(3 + 2µ)
⇡(1,0,0,1) =
39✓µ2 + 9✓µ3 + 48✓ 3 + 72✓ 2 µ + 68 3 µ + 24 2 µ2 + 48 4
4 2 (12 2 + 8 µ + 12✓ + 9✓µ)
⇡(0,0,1,1) =
39✓µ2 + 9✓µ3 + 48✓ 3 + 72✓ 2 µ + 68 3 µ + 24 2 µ2 + 48 4
Having the steady state probabilities ⇡ = (⇡(2,0,0,0) , ⇡(1,0,1,0) , ⇡(1,0,0,1) , ⇡(0,0,1,1) )
several performance characteristics of M/G/1//N with retrial can be derived:
– The e↵ective arrival rate e : e = [1 + ⇡(2,0,0,0) ⇡(0,0,1,1) ]
– The mean number of customers in the orbit norb : norb = ⇡(1,0,0,1) + ⇡(0,0,1,1)
– The mean number of customers in the system ns : ns = 1 ⇡(2,0,0,0) +⇡(0,0,1,1)
1 ⇡(2,0,0,0) +⇡(0,0,1,1)
– The mean response time ⌧ , from Little’s law: ⌧ = nes = [1+⇡(2,0,0,0) ⇡(0,0,1,1) ]
228 PNSE’14 – Petri Nets and Software Engineering
Table 1. Performance measures for the M RSP N of FIG.2 (N = 2, = 0, 8, ✓ =
0, 2, µ = 1, 0).
Steady state probabilities Performance indices
⇡(2,0,0,0) 0, 0456482045 e 0, 4403095383
⇡(1,0,1,0) 0, 0918181028 norb 0, 8625336928
⇡(1,0,0,1) 0, 3672724111 ns 1, 449613077
⇡(0,0,1,1) 0, 4952612817 ⌧ 3, 292259083
5 Numerical Results
In this section we present some numerical results using the Time Net [10] (Timed
Net Evaluation Tool) software package which supports a class of non-markovian
GSP N . We illustrate the e↵ect of the parameters on the main performance
characteristics. The model proposed was validated by the exact analytical results
of M/G/1//N without retrial, see Table 2.
Table 2. Validation of results.
Performance M/G/1//2 without retrial M RSP N associated to M/G/1//2
indices ( = 0, 5 , Service U[0,5;1,0] ) with retrial
( = 0, 5 , Service U[0,5;1,0] , ✓ ' 1)
e 0, 69488 0, 69390
ns 0, 61022 0, 61218
⌧ 0, 87816 0, 88223
From the Table 2, when the retrial rate is very large, the performance indices
corresponding the M RSP N associated to M/G/1//2 queue with retrial are very
close to those obtained by M/G/1//2 queue without retrial.
For N = 25, = 0.1, ✓ = 0.25, we obtain the performance indices of our
M RSP N . Where e , ✓e : respectively represents the e↵ective customers arrival
rate and retrial rate. norb , ns : respectively represents the average number of cus-
tomers in orbit and in system. W , T : respectively represents the mean response
time in system and mean waiting time in the orbit, which are summarized in the
Table 3.
In Figure 5, 6 and 7 we give some graphical results in order to illustrate the way
in which the model is a↵ected from the variation in the retrial rate and the size
of the source.
In FIG.5, we observe that the mean number of customers in the orbit decreases
as the retrial rate increases.
I. Lyes et al.: Performance Analysis of M/G/1 Retrial Queue 229
Table 3. Some performance measures for the M RSP N of FIG.2 (N = 25, = 0.1, ✓ =
0.25).
Performance indices Service Det(0, 8) Service U[0,5;1,0]
e 0,9865245 1,0340604
✓e 3,5863839 3,4709629
norb 14,3455359 13,8838515
ns 15,1347555 14,6593961
W 15,3414897 14,1765376
T 14,5414897 13,4265382
Fig. 5. E↵ect of retrial rate on mean number of customers in the orbit.
In FIG.6, we observe that mean response time of the system decreases as the
retrial rate increases.
In FIG.7, we observe that mean response time of the system increases as the size
of the source increases.
6 Conclusion
In this work a single server retrial queue M/G/1 with finite source population is
considered. We focused on how to exploit the features of M RSP N to cope with
the complexity of such system. The M RSP N approach allowed us to compute
efficiently exact performance measures. We have illustrated the functionality
of this approach with the example M/G/1//2 with retrial. Some performance
230 PNSE’14 – Petri Nets and Software Engineering
Fig. 6. E↵ect of retrial rate on mean response time in the system
Fig. 7. E↵ect of size of source on mean response time in the system
measures are carried out by the help of the software package Time Net. Our
future work aims at make generalization for any N (size of population) in order
to propose an algorithm for computing the transition matrix and performance
measures without generating the reachability graph. Also it may be interest-
ing to provide a more detailed study by including to the same model: vacation,
breakdown, etc.
I. Lyes et al.: Performance Analysis of M/G/1 Retrial Queue 231
References
1. A. Cumani. Esp: A package for the evaluation of stochastic Petri nets with
phase-type distributed transition times. In proceedings International Workshop
Timed Petri nets, pages 144-151, Torino (Italy), (1985). IEEE Computer Society
Press no. 674.
2. C.Ciardo, R.German, and C.Lindeman: A characterization of the stochastic process
underlying a stochastic petri nets. IEEE, Trans, 20,506-515(1994).
3. D.R. Cox: The analysis of non-markovian stochastic processes by the inclusion of
supplementary variables. Proceedings of the Cambridge Philosophical Society, 51:
433-440, (1955).
4. F. Zhang and Jinting Wang: Performance analysis of the retrial queues with finite
number of sources and service interruptions. Journal of the Korean Statistical Society
42 (2013) 117-131.
5. J. R. Artalejo: Accessible bibliography on retrial queues. Mathematical and com-
puter Modelling, 30: 1-6,(1999).
6. H. Choi, V.G.Kulkarni and K. Trivedi: Markov regenerative stochastic Petri nets.
Performance Evaluation, 20: 337-357, (1994).
7. H.Choi, V.G.Kulkarni and K.S.Trivedi: Markov Regenerative Stochastic Petri Nets.
IEEE trans. comput., 31(9): 913-917,(1982).
8. G. Chiola, M.A. Marsan, G.Balbo, and G.Conte: Generalized stochastic Petri nets,
a definition at the net level and its implications. IEEE trans. on software Eng.,19(2):
89-107,(1993).
9. G. I.Falin and J.G.C. Templeton: Retrial queues. Chapman and Hall, London, 1997.
10. K. Ramanath and P. Lakshmi: Modelling M/G/1 queueing systems with server
vacations using stochastic Petri nets, 22(2), pp.131-154(2006).
11. L. Berjdoudj and D. Aissani: Strong stability in retrial queues. Theor. Probability
and Math. Statis.,68,11-17,(2003)
12. M.K.Molloy: Performance analysis using stochastic Petri nets. IEEE trans. com-
put., 31(9):913-917,(1982)
13. M. Neuts: Structured Stochastic Matrices of M/G/1 Type and Their Applications,
Marcel Dekker, Inc., New York and Basel, 1989.
14. N.Gharbi and M.Ioualalen: Performance analysis of retrial queueing systems using
generalized stochastic petri nets. USTHB-Alger, Algérie.
15. N. Gharbi and C. Dutheillet: An algorithmic approach for analysis of finite-source
retrial systems with unreliable servers. Computers and Mathematics with Applica-
tions 62 (2011) 2535-2546.
16. O.Dudina , C. Kim and S.Dudin: Retrial queuing system with Markovian arrival
flow and phase-type service time distribution, Computers Industrial Engineering 66
(2013) 360-373.
17. Oliver C. and Kishor S: Stochastic Petri net analysis of finite population. J.C.
Baltzer A.G. Scientific Publishing Company, USA (1990).
18. S.N. Stepanov: Numerical methods of calculation for systems with repeated calls,
Nauka Moscow(1983).
19. T.Yang, M.J.M.Poser, J.G.C.Templeton and H.Li: An approximation for the
M/G/1 retrial queue with general retrials times, European Journal of Operational
Research, 76, 552-562,(1994).
20. TimeNET 4.0: A Software Tool for the Performability Evaluation with Stochas-
tic and Colored Petri Nets. User Manual. Armin Zimmermann and Michael Knoke
Technische Universität Berlin Real Time Systems and Robotics Group Faculty of EE
and CS Technical Report 2007/13 ISSN: 1436/9915, August (2007).