Open access peer-reviewed chapter

Performance Modeling of Finite Sources Retrial Queue Using Markov Regenerative Approach

Written By

Lyes Ikhlef

Submitted: 23 October 2022 Reviewed: 11 December 2022 Published: 13 February 2023

DOI: 10.5772/intechopen.1000858

From the Edited Volume

Markov Model - Theory and Applications

Hammad Khalil and Abuzar Ghaffari

Chapter metrics overview

37 Chapter Downloads

View Full Metrics

Abstract

We study a finite sources retrial queue with deterministic service times using an approach based on the theory of Markov regenerative process. A Deterministic Stochastic Petri Net DSPN model which copes with the complexity of this queue is given. For the steady state of this model, we construct the one-step transition probability matrix of Embedded Markov Chain (EMC) and the conversion matrix. We establish an algorithm based on the theoretic results obtained in order to compute efficiently various performance measures and to study the effect of system parameter’s on the characteristics of the M/D/1/N/N retrial queue.

Keywords

  • Markov regenerative process
  • stochastic Petri nets
  • embedded Markov chain
  • steady state
  • retrial queue

1. Introduction

The performance analysis of queueing systems has been studied over the past years. There are many models that have been developed in the queueing systems analysis using stochastic process, particularly Markov process, semi-Markov process, and Markov regenerative process. Different approaches have been explored in the literature dealing with non-Markovian models: method of supplementary variable [1], approximate analysis by phase type expansion [2], Markov renewal theory [3], etc.

The standard queueing systems with deterministic service times are widely found in the literature Bunday [4], Kashyap and Chaudhry [5], Bhat [6]. Brun and Garcia [7] give an analytical solution of the system M/D/1/K. Franx et al. [8] study the multi-server system M/D/c. Madan and Saleh [9] study the queue M/D/1 with general vacations. Choi et al. in [3, 10] investigate the transient and sensitivity analysis of DSPN. As an application, they detailed the analysis of the classical queue M/D/1/2/2 and M/D/1/2/2 with vacation. However, little attention has been paid to retrial queues with deterministic service times and finite sources [11]. Wu and Ke in [12], consider an infinite single server retrial queueing system in which each customer (primary or secondary customer) has discrete service times. For bibliographies on retrial queues, see [13, 14, 15, 16] and the references therein.

In this paper, we give a model and performance analysis of the finite sources retrial system with deterministic service times by using DSPN tool.

Advertisement

2. Analysis of DSPN class

The DSPN class was introduced by Ajmone and Chiola [17]. The DSPN class was proposed to study a qualitative and quantitative behavior of non-Markovian systems. This class allows transitions with zero firing times (immediate transitions), exponentially distributed or deterministic distributed firing times. A DSPN describes a stochastic process referred to as the marking process Mt,t0. This marking process can not mapped into a Continuous Time Markov Chain CTMC [18]. Choi et al. have shown that, under the restriction the deterministic transitions are mutually exclusive, the underlying stochastic process of the DSPN class is a Markov regenerative process [3]. This process has a sequence of embedded time points T0,T1, such that the states Y0,Y1, of the process at these time points satisfy the Markov property. These time points are indicated by the Markov regeneration instants (regenerative time points, RTP). Note that the stochastic proces Ynn0 is an EMC. The steady-state solution of the DSPN, based on the Markov renewal method, can be summarized in the following steps:

  • Constructing the two kernels: global kernel Kt=Kijt and local kernel Et=Eijt, where:

    1. Kijt=PY1=jT1tY0=i,i,jΩ is the probability that the system transits from state i to state j upon firing of a general transition, or upon the firing of an exponential transition which is computed with a general transition.

    2. Eijt=PMt=jT1>tY0=i,i,jΩ'Ω is the probability that the system transits from state i to state j while the general transition and the exponential that is competing with a general transition do not firing. The matrix Et describes the behavior of the marking process between two regeneration instants.

  • Obtaining the one step transition probability matrix P=Pij=K of the EMC defined at RTP, Tnn1, and the matrix α=αij. Here, the elements αij represent the mean time that the DSPN spends in state j between two successive regeneration instants, given that it started in state i after the last regeneration. They are given by:

    αij=0Eijtdt.E1

  • Computing υ the steady state probability vector of the EMC by solving the linear system:

υP=υ,υe=1.E2

Where e is a column vector of ones.

  • Computing the steady state probability distribution vector π of the DSPN, by the formula:

πj=kΩvkαkjvkuk=kΩβkαkjuk,E3

where,

μi=jΩαijandβk=vkukkΩvrur.E4

We define the conversion matrix C=Cij by,

Cij=αijui.E5

Let a vector β=βk, the Eq. (3) can be rewritten in the matrix form:

π=βC.E6
Advertisement

3. Model description

We consider the retrial queue, M/D/1/N/N, in which primary customers arrive according to a Poisson process with rate λ. If an arriving customer finds the server idle, he obtains service immediately and joins the sources after service completion. Otherwise, if the server is occupied, the arriving primary customer enters into the orbit. The policy of access from the orbit to the server is governed by an exponential law with rate , where k is the number of customers in the orbit. Each customer has a deterministic (constant) service times of length τ>0. The Figure 1 shows the DSPN model describing the M/D/1/N/N retrial queue.

Figure 1.

DSPN models retrial queue M/D/1/N/N with classical retrial policy.

This DSPN has four places p.sour, p.chec, p.serv, p.orbi noted by circles, two immediate transitions t.acc1, t.acc2 noted by thin black bars, two exponential EXP transitions t.arri, t.retr indicated by white rectangular boxes, and one deterministic DET transition t.serv noted by thick black rectangular box.

The vectors Mp.sourMp.checMp.servMp.orbi, describe the possible markings of the given DSPN model (i.e., where Mp represents the number of tokens in the place p). The vector M0=N,0,0,0 is its initial marking. The transitions are interpreted as follows:

  • The EXP transition t.arri represents the arrival of the primary customers. The firing of this transition consists to remove a token in the place p.sour and to deposit a token in the place p.chec.

  • The immediate transition t.acc1 represents the access to the service. The instantly firing of this transition consists to remove a token in the place p.chec and to deposit a token in the place p.serv.

  • The DET transition t.serv represents the service of the customer. The firing of this transition consists to remove a token in the place p.serv and to construct a token in the place p.sour.

  • The transition t.acc2 represents the access to the orbit. The firing of this transition consists to destroy a token in the place p.chec and to deposit a token in the place p.orbi.

  • The EXP transition t.retr represents the retrial customers. The firing of this transition consists to destroy a token in the place p.orbi and to construct a token in the place p.chec. The firing rate of t.arri and t.retr are marking dependent and equals, respectively Mp.sourλ, Mp.orbiγ.

  • The immediate transition t.acc1 has higher priority than the immediate transition t.acc2.

The interpretation of the places are given in the following Table 1.

Place nameDescriptionInitial marking
p.sourSource of primary customersN
p.checContains primary customers or secondary customers0
p.servCustomers requiring a service0
p.orbiOrbit for the retrial customers0

Table 1.

Interpretation of the places in the DSPN Model given in Figure 1.

Advertisement

4. EMC and steady-state results

In this section, we details the steady-state analysis of the DSPN models the M/D/1/N/N retrial queue. The state transition diagram of the DSPN depicted in Figure 1 is given in Figure 2 with states space Ω such that:

Figure 2.

Subordinated CTMC for the DSPN associated to M/D/1/N/N with classical retrial policy.

Ω=M2k=k0M2k+1=k1,0kN1.E7

Let Mi,MjΩ, the infinitesimal generator matrix Q=qMiMj of the subordinated CTMC with respect to DET transition t.serv is given by:

qMiMj=Ni+12λ,if0kN2,i=2k+1andj=i;Ni+12λ,if0kN2,i=2k+1andj=i+2;0,otherwise.E8

The one step transition probability matrix P=PMiMj is given by:

PMiMj=1,ifi=0andj=1;CNi+12ji+121eλτji+12eλτNj+22,if0kN1,i=2k+1andi1j2N2,j=2k;i2γi2γ+Ni2λ,if1kN1,i=2k+1andj=i1;Ni2λi2γ+Ni2λ,if1kN1,i=2k+1andj=i+1;0,otherwise.E9

The conversion matrix C=cMiMj is given by:

cMiMj=1,ifi=j=0;1τ0τCNi+12ji21eλtji2eλtNj+12dt,if0k<N1,i=2k+1andij2N1,j=2k+1;1,if1kN1,i=2k,andj=i;0,otherwise.E10
Advertisement

5. Example

When N=2, we obtain the state transition diagram (Figure 3) of the DSPN model depicted in Figure 1, with state space:

Figure 3.

Subordinated CTMC for the DSPN models M/D/1/2/2.

Ω=M0=00M1=10M2=01M3=11.E11

The infinitesimal generator matrix Q=qMiMj of the subordinated CTMC with respect to DET transition, t.serv, is given by:

Q=00000λ0λ00000000.E12

The one step transition probability matrix, P=PMiMj, is given by:

P=0100eλτ01eλτ00γγ+λ0λγ+λ0010.E13

The steady state probabilities of the EMC are given by:

vM0=12γeλτγ+λλeλτ,vM1=12γγ+λλeλτ,vM2=121eλτγ+λγ+λλeλτ,vM3=12λ1eλτγ+λλeλτ.E14

The elements cMiMj are given by the conversion matrix C:

C=100001λτ1eλτ01+1λτeλτ100100001.E15

The steady state probabilities of the DSPN are given by:

πM0=γeλτ2γτλ+2λ+2λ2τ+eλτγ2λ2λ2τ;πM1=2γ1eλτ2γτλ+2λ+2λ2τ+eλτγ2λ2λ2τ;πM2=2λ1eλτ2γτλ+2λ+2λ2τ+eλτγ2λ2λ2τ;πM3=2γ+γτλ+γeλτ+λ2τλ2τeλτ2γτλ+2λ+2λ2τ+eλτγ2λ2λ2τ.E16

The steady state probabilities v and π for λ = 0.5, γ = 0.2, τ = 1.5 are given in the following Table 2.

kvM2kvM2k+1πM2kπM2k+1
00.10184340.21560240.07168840.1601520
10.39815660.28439760.40037100.3677796

Table 2.

The steady state probabilities distributions of the DSPN models the M/D/1/2/2 retrial queue, “λ=0.5, γ=0.2, τ=1.5.”

Advertisement

6. Performance measures

By using the steady-state probabilities distributions

π=πM0πM1πM2kπM2k+1πM2N2πM2N1E17

the main system performance measures can be derived by the following formulas:

  • The mean number of customers in the orbit no:

    no=k=1N1kπM2k+πM2k+1.E18

  • The mean generation rate of primary calls λ¯:

    λ¯=λk=0N1NkπM2k+k=0N2Nk1πM2k+1.E19

  • The mean generation rate of repeated calls γ¯:

    γ¯=γk=1N1kπM2k+πM2k+1.E20

  • The mean generation rate of server τ¯:

    τ¯=τk=0N1πM2k+1.E21

  • The server utilization Us:

    Us=k=0N1πM2k+1.E22

  • The mean waiting time w¯ (Little’s law):

    w¯=noλ¯.E23

  • The mean response time ϖ (Little’s law):

ϖ=nsλ¯.E24
Advertisement

7. Numerical results

In this section, we give some numerical results, concerning the DSPN associated to M/D/1/N/N retrial queue. The results obtained based on the following algorithm.

Algorithm
Begin
Step 0: Give N the number of sources, λ customer arrival rate,
τ deterministic service times, γ the retrial rate.
Step 1: Compute the one step transition probability matrix P and the conversion matrix C using
the Eqs. (9) and (10).
Step 2: Compute the stationary distribution v of the EMC by solving the linear system (2).
Step 3: Compute the stationary distribution π of the DSPN using the formula (6).
Step 4: Compute the performance measures using the formulas (18)(24).
End

First, the DSPN model proposed for the queue M/D/1/N/N with classical retrial policy, is validated by the exact numerical results given in (Table 3) [11]. We see that the performance measures corresponding the DSPN associated to M/D/1/N/N queue are close to those obtained in [11]. Next, in Table 4, we present some performance measures. Finally, from Figures 410, we illustrate the effect of the arrival rate λ, deterministic service time τ and the retrial rate γ on the mean response time, the mean number of customers in the orbit and the server utilization.

  • In Figure 4, we see that the mean response time of the M/D/1/N/N retrial queue is maximum. The amplitude and the location of this maximum depend on the retrial rate γ. We observe that, the arrival rate λ has a significant influence on the mean response time when the retrial rate γ is weak.

  • In Figure 5, we see that the increase in the arrival rate λ induces an increase on the mean number of customers in the orbit. We observe that, the retrial rate γ has a significant influence on the mean number of customers in the orbit. This influence is more significant for smaller value of γ.

  • In Figure 6, we see that the increase in the arrival rate λ induces an increase on the server utilization.

  • From Figure 7, we see that the mean response time decreases with the increase of the retrial rate γ. This decrease becomes slow with the intensifying of the secondary calls.

  • In Figure 8, we see that the increase in the retrial rate γ induces a decrease on the mean number of customers in the orbit.

  • From Figure 9, we observe that, the deterministic service time τ has notable influence on mean response time, specifically for smaller values of τ.

  • From Figure 10, we see that the mean number of customers in the orbit increase with the increases of the deterministic service time τ.

  • From the graphs, we see that when the retrial rate tends to all the characteristics (the mean response times, the mean number of customer in the orbit, and the server utilization) approach those of the classical M/D/1/N/N queue which has the lower performance bound.

ip0ip1iπ0iπ1i
00.010100.038690.01010410.0386973
10.000740.091120.00074420.0911271
20.000780.158380.00078860.1583811
30.000810.210480.00081220.2104897
40.000700.211470.000708390.2114737
50.000480.156630.000488020.1566328
60.000250.082510.000251010.0825136
70.000090.029350.000090670.0293532
80,000020.006500.000021170.0065053
90.27×1050.000770.27×1050.0007788
100.14×1060.000030,14×1060.0000362

Table 3.

Comparison of stationary distributions of the model M/D/1/N/N retrial queue given in [11], with the DSPN model, “N=11, λ=0.01, γ=5.2, and τ=15.

MeasuresDSPN Model
no8.0342602
Us0.6552466
λ¯1.3104932
γ¯2.0085650
τ¯0.3276233
w¯6.1307148
ϖ6.6307148

Table 4.

Some performance measures, “N=10, λ=1, γ=0.25, τ=0.5.

Figure 4.

Effect of arrival rate λ on mean response time ϖ, “N=3, λ=103,,6, τ=1.5.

Figure 5.

Effect of arrival rate λ on mean number of customers in the orbit no, “N=3, λ=103,,6, τ=1.5.”.

Figure 6.

Effect of arrival rate λ on the server utilization Us, “N=3, λ=0.15,,6, γ=0.1, τ=1.”

Figure 7.

Effect of retrial rate γ on mean response time ϖ, “N=3, λ=0.5, γ=101,,10, τ=2.”

Figure 8.

Effect of retrial rate γ on mean number of customers in the orbit no, “N=3, λ=0.5, γ=101,,10, τ=2.”

Figure 9.

Effect of service rate τ on mean response time ϖ, “N=3, λ=0.2, τ=101,,10.”

Figure 10.

Effect of deterministic service time τ on mean number of customers in the orbit no, “N=3, λ=0.2, τ=101,,10.”

Advertisement

8. Conclusion

We have studied a single server queue with finite sources, deterministic service, and classical retrial policy. A detailed model DSPN is given and validated by numerical results existing in the literature. Some performance measures of our model were given. It is very inserting to study the transient behavior and sensitivity of this system.

References

  1. 1. Cox DR. The analysis of non-markovian stochastic processes by the inclusion of supplementary variables. Mathematical Proceedings of the Cambridge Philosophical Society. 1955;51(9):433-441. DOI: 10.1017/S0305004100030437
  2. 2. Cumani A. ESP-A package for the evaluation of stochastic Petri nets with phase-type distributed transition times. In International Workshop on Timed Petri Nets. IEEE Computer Society, Washington, DC, USA. 1985. pp. 144–151
  3. 3. Choi H, Kulkarni VG, Trivedi KS. Transient analysis of deterministic and stochastic Petri nets. The 14th International Conference on Application and Theory of Petri Nets, Chicago, U.S.A. 1993. pp. 21-25
  4. 4. Bunday BD. Basic Queueing Theory. Australia: Edward Arnold; 1986
  5. 5. Kashyap BRK, Chaudhry ML. An Introduction to Queueing Theory, A & A Publications. Ontario, Canada: Kingston; 1988
  6. 6. Bhat UN. Elements of Applied Stochastic Processes. New York: John Wiley and Sons. Inc.; 1972
  7. 7. Brun O, Garcia J. Analytical solutions of finite capacity M/D/1 queues. Journal of Applied Probability. 2000;37:1092-1098
  8. 8. Franx GJ. A simple solution for the M/D/c waiting time distribution. Operations Research Letters. 2001;29:221-229
  9. 9. Madan CK, Saleh MF. On M/D/1 Queue with General Server Vacations. Information and Management Sciences. 2001;12(2):25-37
  10. 10. Choi H, Mainkar V, Trivedi KS. Sensitivity analysis of deterministic and stochastic Petri nets, Inetrnational Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, San Diego, USA. 1993. pp. 17-20
  11. 11. Artalejo JR, Gomez-Corral A. Information theoretic analysis for queueing systems with quasi-random input. Mathematical and Computer Modelling. 1995;22:65-76
  12. 12. Wu X, Ke X. Analysis of an M/Dn/1 retrial queue. Journal of Computational and Applied Mathematics. 2007;200:528-536
  13. 13. Artalejo JR. Accessible bibliography on retrial queues: Progress in 2000-2009. Mathematical and Computer Modelling. 2010;51(9–10):1071-1081
  14. 14. Falin GI. A survey of retrial queues. Queueing Systems. 1990;7:127-168
  15. 15. Falin GI, Templeton JGC. Retrial Queues. London: Chapman and Hall; 1997
  16. 16. Yang T, Templeton JGC. A survey on retrial queue. Queueing Systems. 1987;2:201-233
  17. 17. Marsan MA, Chiola G. On Petri nets with deterministic and exponentially distributed firing times. In: Rozenberg G, editor. Advances in Petri Nets 1986, Lecture Notes in Computer Science. Vol. 266. Springer-Verlag; 1987. pp. 132-145
  18. 18. Ciardo G, German R, Lindemann C. A characterization of the stochastic process underlying a stochastic Petri net. IEEE Transactions on Software Engeneering. 1994;20:506-515

Written By

Lyes Ikhlef

Submitted: 23 October 2022 Reviewed: 11 December 2022 Published: 13 February 2023