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).