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 retrials and finite source population introduce analytical diculties. 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.
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 dicult to obtain. Taking 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↵erent approximating algorithms and approaches were proposed [11,18,19]. 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. Recently, the performance analysis of queueing systems M/G/1//N with di↵erent 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 related 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
Di↵erent approaches and numerical techniques have been explored in the literature for dealing with non-Markovian GSP N , we quote: – The approach of approximating the general distribution by phase type expansion [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 stochastic 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 probability 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 (⇡ 1, ⇡ 2, ...) of the M RGP can be obtained by: ⇡ = R 01 Eij (t)dt .
P vk↵ kj Pk2 v⌦k P ↵ kl where ↵ ij = k2 ⌦ l2 ⌦ 3
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.
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). • 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 consists 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
In this section we consider the M/G/1//2 retrial queue. We obtain the reachability 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 successor 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: e t [1
F g(t)] 0 0
0 R t e x dF g(x) 0
Where the density function of the firing time of t.serv is given by hyperexponential distribution ”H2( 31 , µ2 , µ)”: f g(x) = 16 µe 21 µx + 23 µe µx. The one-step transition probability matrix P given by: 0
0
1 µ(5 +3µ)
3 (2 +µ)( +µ)
0
0
,
,
↵ 11 = 21 , ↵ 22 = 23 (2 +3µ+)(2µ+µ) , ↵ 24 = 23 µ(24 +2µ+)3(µ +µ) , ↵ 33 = ↵ +1 , ↵ 44 = 34µ
The steady state probabilities: ⇡ = (⇡ (
+ 9✓µ 3 + 48✓ 39✓µ 2
+ 9✓µ 3 + 48✓
39✓µ 2
+ 9✓µ 3 + 48✓
3✓µ 2(5
3 + 72✓
+ 3µ)
2µ + 68 3µ + 24 2µ2 + 48 4
12✓µ (3
3 + 72✓
+ 2µ)
2µ + 68 3µ + 24 2µ2 + 48 4
Having the steady state probabilities ⇡ = (⇡ (
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 customers 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. 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
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 eciently exact performance measures. We have illustrated the functionality of this approach with the example M/G/1//2 with retrial. Some performance 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 interesting to provide a more detailed study by including to the same model: vacation, breakdown, etc.