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 di cult 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]. -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 MRSP 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 MRSP 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 MRSP 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 MRSP N. In section 3, we describe the MRSP 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.
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 (t 0 , t 1 , t 2 , ...). This instants referred as regeneration points. An embedded Markov chain (EM C) {Y n , 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 MRSP N are:
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 E ij (t) = P {M t = j, t 1 > t/Y 0 = 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
..) of the MRGP can be obtained by:
where
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 MRSP N model describing the M/G/1//N queueing system with retrial. In FIG. 2 • 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 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 reachability tree which describes all possible states of our MRSP N starting from the initial marking M 1 (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 MRSP 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:
Local kernel E(t) : Where the density function of the firing time of t.serv is given by hyperexponential distribution "H 2 ( 1 3 , µ 2 , µ)": f g (x) = transition probability matrix P given by:
The MRSP N depicted in FIG. 2 (N = 2), is bounded and admits M 1 like home state so it is ergodic.
We calculate the steady state probabilities by solving: vP = v and v1 = 1:
The steady state probabilities:
) are given by:
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 n orb : n orb = ⇡
(1,0,0,1) + ⇡ (0,0,1,1)
-The mean number of customers in the system n s :
-The mean response time ⌧ , from Little's law:
[1+⇡ (2,0,0,0) ⇡ (0,0,1,1) ] Table 1. Performance measures for the MRSP N of FIG. 2 (N = 2, = 0, 8, ✓ = 0, 2, µ = 1, 0).
Performance indices ⇡ (2,0,0,0) 0, 0456482045 e 0, 4403095383 ⇡ (1,0,1,0) 0, 0918181028 n orb 0, 8625336928 ⇡ (1,0,0,1) 0, 3672724111 ns 1, 449613077 ⇡ (0,0,1,1) 0, 4952612817 ⌧ 3, 292259083
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. From the Table 2, when the retrial rate is very large, the performance indices corresponding the MRSP 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 MRSP N. Where e , ✓ e : respectively represents the e↵ective customers arrival rate and retrial rate. n orb , n s : 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.
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 MRSP N to cope with the complexity of such system. The MRSP N approach allowed us to compute e ciently exact performance measures. We have illustrated the functionality of this approach with the example M/G/1//2 with retrial. Some performance