Stability Analysis of a Model with General Retrials and Constant Retrial Rate?

Abstract

The paper deals with a single-server model with constant retrial rate. If an arrival meets the server busy, it joins the in nite-capacity orbit and then tries to occupy the server again after generally distributed time interval. Unlike the classical retrial policy, the intensity of orbit customers does not depend on its number. To derive the stability condition for such a model, we construct less complicated for analysis dominating system and illustrate its stability condition, basing on Markov chain approach. Then, relying on heuristic method and using some results from renewal theory, we make a basic assumption about stability condition of the model under consideration. Simulation results for Pareto and Weibull distribution of retrial time con rm, that assumed stability condition gives a good approximation of theoretical stability region.

Keywords

• Retrial System
• Constant Retrial Rate
• Stability Analysis
• General Retrials
• Heuristic Approach
• Renewal Theory

-

We study a single-server retrial system with Poisson input. If an arrival nds the server busy, he joins a virtual orbit and after a retrial time attempts to enter server again. We consider a constant retrial rate policy, in which the total rate of secondary (retrial) attempts does not depend on the orbit size. Unlike the most of existing works in which exponential retrials are studied, we consider a general distribution of the retrial times. The main purpose of the research is to nd the stability conditions of the system under consideration.

For the retrial systems with classic retrial discipline (when the retrial rate increases with the orbit size) the tight su cient stability condition has been established for the New-Better-Than-Used (NBU) retrials in [ 1 ], and this condition indeed coincides with the stability criterion of the corresponding bu ered classic system.

The known su cient stability conditions for the constant rate retrial systems are de nitely super cial, and there is a gap between them and necessary stability conditions even for the exponential retrials (in this regard see stability analysis of a multiclass retrial system in [ 2 ]). To nd more tight stability condition in the system with non-exponential retrials, we construct a dominating retrial system which is more easy to be analyzed. This domination property is intuitive and we do not provide the proof in this work. Thus our analysis in this point is heuristic. Our main idea is to approach the remaining retrial times by the stationary overshoot in the renewal process generated by the sequence of the independent identically distributed (iid) retrial times. This assumption seems plausible since an arrival instant of a Poisson customer can considered as a random instant in a retrial interval. Indeed, as our simulation shows, this assumption is con rmed for a few speci c non-exponential distributions of the retrial times. This analysis allows to suggest more tight stability condition of the retrial systems and by this to extend the stability region of these systems.

To motivate our research, we outline the applicability of the retrial systems. A constant retrial rate system has been introduced in [ 3 ] to describe the behavior of telephone exchange centers. Later, the multi-server extension of such a model was analysed in [ 4 ]. Constant retrial rate systems are successfully used in simulation of multi-access protocols, in particular, see applications to TCP in [ 5 ], to CSMA/CD (Carrier Sense Multiple Access with Collision Detection) protocol in [ 6 ] and to ALOHA-type multiple access systems in [ 7 ], etc.

The most of stability results are obtained for the system with exponential retrial times. For instance, a multiserver bu erless system M=M=c=0 was analyzed by matrix analytic method in [ 8, 9 ]. Stability of a retrial system GI=M=1 with a renewal input has been investigated in [ 10 ], where the generating function method s applied. Stability conditions for a general GI=G=c=K system with exponential retrials have been obtained by the regeneration method in [ 11 ]. Just a few papers consider retrial systems with non-exponential retrials. In particular, the papers [ 12, 13 ] deal with PH- retrial times and provide some approximations and simulation results. Finally, the detailed overviews of the retrial systems can be found in the well-known monographs [ 14 ], [ 15 ] and in the paper [16].

The paper is organized as follows. Section 2 contains the description of the system. In Section 3, an auxiliary dominating system with the known stability condition is constructed. In Section 4, based on ideas from renewal theory, we make and advocate an assumption which allows to formulate a tighter stability condition of the system under consideration. Section 5 contains simulation results for the systems with Pareto and Weibull retrial times. 2

Description of the Model

We consider a single-server bu erless retrial system with constant retrial rate denoted by , which is fed by Poisson input of (primary) customers with arrival instants ftn; n 1g and rate . Thus exponential interarrival times n = tn+1 tn are iid. (Here and in what follows we omit serial index to denote generic element of an iid sequence.) The service times fSn; n 1g are assumed to be iid as well with a general distribution FS . Denote the tra c intensity = ES: If a primary customer meets the server busy, he joins the in nite-capacity virtual orbit and then attempts to occupy the server after a random time with a general dsitribution F . Denote by N (t) the number of customers in orbit (secondary customers) at instant t. (All continuous-time processes are assumed to be de ned at instant t .) By de nition, the retrial rate does not depend on the orbit size N (t).

This system is regenerative and it is important to emphasize that the number of customers in the system and in particular, the orbit-size process fN (t)g are both regenerative processes, and regenerations occur when a new arrival sees an empty system. We call the process fN (t)g and the system positive recurrent if the mean regeneration period is nite. Positive recurrence means that the system possesses stationary regime [17]. 3

A Dominating System

First we present some known stability results for particular systems with constant retrial rate. In the paper [ 11 ] the following stability condition of a singleserver system with exponential retrials is obtained: < 0(1 ); (1) where 0 = 1=E is the retrial rate. Because is the stationary busy probability of the server (again see [ 11 ]), then condition (1) has an evident probabilistic interpretation: input rate to the orbit must be less that the successful rate from the orbit. We note that a similar interpretation can be applied to the stability condition of the retrial system with renewal input and exponential retrials considered in [ 10 ]. Assume rst that the retrial time is NBU, that is for arbitrary x; y 0 Note that in this case the tail of the retrial time is stochastically less or equal than . A su cient stability condition of a model with NBU retrials and classical retrials, has been obtained in the recent work [ 1 ]. Denote by fDk; k 1 departure instants of the customers from the system, and de ne Nk = N (gDtk+h)e, the orbit size just after the k-th departure, k 1. An important observation is that interval [Dk; Dk+1); k 1 contains two phases: an idle period Ik which appears after each departure, and the actual service time Sk+1. (By assumption, we assign service times in the order the customers enter server.) Now we construct a new single-server retrial system ^ with constant retrial rate and the same input and service times as in the system , in which the retrial times after departures are constructed as follows. If the orbit is not empty after a departure, then the residual retrial time is replaced by an independent variable distributed as generic retrial time in the original system . Note that if the orbit is idle after a departure, then the idle period distributed as interarrival time . Also we note that the retrial times in ^ between (unsuccessful) attempts which see server busy are distributed as generic variable . (Indeed we could ignore such attempts because they do not a ect the state of the system.) We denote the departure instants in the system ^ by fDkg. (In fact the system ^ is a partic^ ular case of a system considered in [18].) It follows from construction that the following recursions hold:

Dk+1 = stDk + min D^ k+1 = stD^ k + min (Dk); ;

+ Sk+1; + Sk+1; k 1; (2) where (Dk) denotes the remaining retrial time at instant Dk in the system . By the NBU property st (Dk), and then recursion (2) supports our Assumption 1: the system is less loaded than the system ^ . (The exact proof of this assumption could be based on the coupling arguments developed in the paper [ 2 ].) Thus the stability of ^ yields the stability of the original system .

Now we consider the stability condition of the system ^ . Denote by fN^k; k 1g the orbit size in the system ^ just after departure instant D^ k. It is easy to ^ see, that the sequence fNkg (unlike the sequence fNkg) de nes an irreducible, aperiodic, time-homogeneous Markov chain with the state space f0; 1; 2; : : : g. Now we nd the ergodicity condition of this Markov chain, which is equivalent to the positive recurrence (stability) of the system ^ .

First assume that, at some instant D^ k, the orbit is empty, that is N^k = 0. Then the server can be captured by a primary customer only, and the following idle period is distributed as exponential variable . When server becomes busy, arrival input (with rate ) joins the orbit. Thus, in the interval [D^ k; D^ k+1), the sequence fN^kg transits from state 0 to a state i with probability (w. p.) pi = dFS (t); i 0: If N^k > 0, then the the two following alternative events may happen: i) the primary customer occupies the server with w.p. P( < ), or ii) a retrial attempt is successful w. p. P( ). (In the original system this happens w. p. P( < (Dk)) and P( (Dk)), respectively, which are not analytically available unless is exponential.) It then follows that N^k+1 = N^k + i w.p.

P( < ; i arrivals during Sk+1) = pi (1 e x)dF (x) and N^k+1 = N^k + i

1 w.p.

P( ; i arrivals during Sk+1) = pi xdF (x): Now we apply the well-known su cient (negative drift) condition for the Markov chain to be ergodic [17,19] which in our case can be formulated as supk EjN^k+1 ^ Nkj < 1 and

E[N^k+1

NkjN^k = j] < 0; j > 0: ^ (3) A simple algebra gives, regardless of k, 1

E[N^k+1

N^k]

X ipi = i < 1; and to check (3), we have

E[N^k+1

NkjN^k = j] = P( < ) X(i + j)pi ^

i 1 + P( = X ipi Thus the system ^ is stable if the following condition holds: which has a clear probabilistic interpretation. Namely, the probability that an arriving customer joins the orbit must be less than the probability P( ) that an attempt happens earlier than the next primary customer arrives. Note that P( ) = is Laplace-Stieltjes transform of the retrial time . Remark that condition < L ( ) coincides with the stability condition, obtained in [18] for a general case of retrial system with balking and repairable server, where retrial time begins only when the server is idle. 4

Stability Analysis

In previous section we have found a su cient stability condition for a dominating system ^ . One may expect that this condition is not tight enough for the original system, and in this section we use an idea from renewal theory to formulate more tight stability condition for the system . First, we construct a renewal process generated by the iid copies f i; i 1g of the generic retrial time . Denote the renewal process

n Zn = X and de ne the residual renewal time at instant t as (t) = mninfZn t : Zn t 0g; t 0: (5) It is well-known that if E < 1 and is non-lattice (it is assumed in what follows) then the convergence in distribution holds [17]:

(t) ) s t ! 1; where s denotes the stationary excess of the renewal process fZng. Denoting the tail distributions

F s (x) = P( s > x);

F (x) = P( > x); we have (see, for instance, [17])

F s (x) = P( ) = e xP( x)dx e xP( s x)dx = P( s ); where, to obtain the independence between and s, we use the resampling of the interarrival time at the corresponding departure instant. Thus we have the inequality

P( P( and

P( ) < P( s); s); which becomes equality for general being exponential. If is not exponential then in One can expect that the actual stationary remaining retrial time at the departure instants is close to the stationary residual renewal time (5) in the renewal process fZng, and it implies the following Assumption 2: for a generally distributed (non-exponential) condition < P( s) (6) allows to delimit more exact stability region of the original system than the (excessive) condition (4) obtained for the dominating system under NBU retrials. (For exponential , conditions (4) and (6) coincide with stability condition (1), obtained in [ 11 ].)

In the next Section we demonstrate, for Weibull and Pareto retrials times, that condition (6) indeed provides a good approximation of stability region for the corresponding system.

Simulation

To verify the tightness of the new (heuristic) stability condition (6) for a nonexponential retrial time , we study the dynamics of the orbit provided the tra c intensity is selected to satisfy the following inequalities:

P( ) that is, when su cient stability condition (4) is violated. De ne the unknown real stability region border S, that is condition

< S is the stability (positive recurrence) criterion of the system. (Conversely, condition S implies instability of the system.) In sections 5.1 { 5.2 we obtain an approximate value of S by analysing the orbit behavior in simulated system as follows. First, we vary the value of load coe cient and illustrate the dynamics of mean orbit size. When for some value we obtain stable orbit if < , while for the orbit goes to in nity, we de ne the approximate value of S by .

Below we show by simulation that the value S is indeed close to the probability P( s) for Weibull and Pareto retrial times.

with the scale parameter 1 and the shape where

P(

P( where is Gamma function. If w = 2, then

has NBU property and s) = xdF s (x) = 1 (1:5) 0 e xe x2 dx =

p 2 (1:5) e 2=4 erfc 2 ; erfc(x) = 1 2 Z x p 0 Figure 1 presents the orbit dynamics for a few values of ES = for exponential service time. As Figure 1 shows, when satis es inequalities (7) (solid lines) then orbit demonstrates stability behaviour, while when violates (7) (dash line) the orbit becomes unstable. Note that in these experiments

S and we conclude, at least for the studied NBU Weibull retrials, that the bound P( s) indeed slightly violates the border of stability region. However the proximity between P( s) and (in general unknown) actual border S can be used to approach S e ectively in simulation. where erf(x) = p 2 Z x is Gauss error function [20]. (Note, that in the NWU case, we can not claim that the corresponding system ^ dominates the system .) Selecting w = 1=2 and = 1, we have s) = = = 1 = 0:227: e (x+px)dx erf 1=2 1 + 1i The orbit dynamics for w = 1=2 is presented on Figure 2, where the solid grey 0 0 2 0 5 1 0 0 1 0 5 0

Load coefficient = 0.30 Load coefficient = 0.27

Load coefficient = 0.21 0 1000 2000 4000 5000

6000 3000

n

s) narrows the actual stability region.

Now we consider retrial time with Pareto distribution

In this case

For instance, for = 1 and = 2, Simulation shows that in this experiment,

e

1 Z 1 1 e e xx xx dx dx : P(

s) = (0:632 + 0:148)=2 = 0:390: 0 0 2 0 5 1 0 0 1 0 5 0

Load coefficient = 0.40 Load coefficient = 0.36

Load coefficient = 0.32 0 1000 2000 4000 5000

6000 3000

n and thus the border P( s) \extend" actual stability region a little. The results of simulation are illustrated by Figure 3.

Conclusion

In this paper we develop a heuristic approach, using an idea from renewal theory, to construct more tight stability condition for a single-server retrial system with Poisson input, general iid service times and general (iid) retrial times. It is assumed that the system follows a constant retrial rate policy. We construct a dominating retrial system and study an embedded Markov chain at the departure instants to nd su cient stability condition for the NBU retrials. Then we formulate a more tight stability condition and verify its accuracy by simulation in the systems with Weibull (both NBU and NWU retrials) and Pareto retrials. As experiments show, this new condition allows to approach the actual border of the stability region but it must be used carefully. 16. Phung-Duc, T.: Retrial Queueing Models: A Survey on Theory and Applications (2017) 17. Asmussen, S.: Applied probability and Queues. 2nd edn. Springer, Springer-Verlag

New York (2003) 18. Taleb, S., Saggou, H., Aissani, A.: Unreliable M/G/1 retrial queue with geometric loss and random reserved time. Int. J. Oper. Res. 7(2), 171{191 (2010) 19. Kulkarni, V. G.: Modeling and Analysis of Stochastic Systems. 2nd edn. Chapman and Hall/CRC (2009) 20. Andrews, L.: Special functions of mathematics for engineers. SPIE Press (1998).

References

1. Morozov E. , Nekrasova R. : Stability Conditions of a Multiclass System with NBU Retrials. Lecture Notes in Computer Science 11688 , 51 { 63 ( 2019 )

2. Morozov , E. , Rumyantsev , A. , Dey , S. , Deepak , T. G.: Performanace Analysis and Stability of Multiclass Orbit Queue with Constant Retrial Rates and Balking . Performance Evaluation 102005 , ( 2019 )

3. Fayolle , G.: A simple telephone exchange with delayed feedback . In Boxma, O.J. , Cohen J.W. , and Tijms , H.C. (eds.) In: Teletra c Analysis and Computer Performance Evaluation, 7 , pp. 245 { 253 . ( 1986 )

4. Artalejo , J.R. , G´omez - Corral , A. , Neuts , M.F. : Analysis of multiserver queues with constant retrial rate . In: European Journal of Operational Research , 135 , pp. 569 | 581 . ( 2001 )

5. Avrachenkov , K. , Yechiali , U. : On tandem blocking queues with a common retrial queue . In: Computers and Operations Research , 37 ( 7 ), pp. 1174 { 1180 . ( 2010 )

6. B. D. Choi , Y. W. Shin and W. C. Ahn . Retrial queues with collision arising from unslotted CSMA/CD protocol . Queueing Systems , 11 , pp. 335 { 356 , ( 1992 )

7. Choi , B.D. , Rhee , K.H. , Park , K.K. : The M/G/1 retrial queue with retrial rate control policy . Probability in the Engineering and Informational Sciences, 7 , pp. 29 | 46 . ( 1993 )

8. Neuts , M. F. : Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach . Johns Hopkins University Press ( 1981 )

9. Latouche , G. , Ramaswami , V. : Introduction to matrix analytic methods in stochastic modelling, Philadelphia PA ( 1999 )

10. Lillo , R.E. A G /M/1 -queue with exponential retrial . Top 4 , pp. 99 - { 120 ( 1996 ).

11. Avrachenkov , K. , Morozov , E.: Stability Analysis of GI/G/c/K Retrial Queue with Constant Retrial Rate . Mathematical Methods of Operations Research 79 ( 2010 )

12. Chakravarthy , S. R.: Analysis of MAP/PH/c retrial queue with phase type retrials - simulation approach . Modern Probabilistic Methods for Analysis of Telecommunication Networks 3 , 7 - 49 ( 2013 )

13. Shin , Y. W. , Moon D. H.: Approximation of PH/PH/c retrial queue with PHretrial time . Asia-Paci c Journal of Operational Research , 31 . ( 2014 )

14. Falin , G. I.: A survey of retrial queues . Queueing Systems , 7 , 127 - 168 . ( 1990 )

15. Artalejo , J. R. , Gomez-Corral , A. : Retrial queueing systems: a computational approach . Berlin Heidelberg: Springer-Verlag ( 2008 )