In this paper, a large deviation probability in a single-server retrial system is considered. In this model, if server is busy, an arriving customer joins the so-called virtual orbit and then attempts to enter server again. We consider constant retrial rate discipline, in which case only the top (oldest) orbital customer makes the attempts. The input is assumed to be a general renewal process, service times are iid with a general distribution and the retrial attempts follow an exponential distribution. Such models are motivated by numerous applications in modelling modern communication systems. We focus on the decay rate of the probability that the orbit size reaches a high level N within busy period. We compare retrial system to equivalent classic system with service times of a special type. Simulation results show that original retrial system can be approximated with the classic bu ered model.
In this paper, we discuss a large deviation analysis of the stationary retrial system with constant retrial rate. In constant retrial rate system, retrial rate remains constant and does not depend on the orbit size. Retrial models are studied over a few decades and very well motivated by practical applications in the modern telecommunications systems, see for instance [10], [1], [8], [7], [9]. We focus on the asymptotic behaviour of the stationary probability that the orbit size of the system reaches a level N within busy period, as N ! 1. Under mild assumptions we show that this over ow probability has an exponential decay rate. The study of decay rate is closely connected with various aspects of the Quality of Service problem and in particular, plays a critical role in the analysis of the e ective bandwidths in communication networks [4]. Large deviation analysis of the over ow probabilities are discussed in [11] (in classic systems) and [3] (in tandem networks). The problem of calculating and estimating over ow probability in retrial systems was considered previously in [5], [6] for queue size process in MAP/G/1 systems.
We show, that under appropriate moment assumptions the decay of the probability is exponential with the known exponent. More exactly, we obtain the lower and upper exponential bounds for this decay rate. We discuss an interpretation of the original retrial model as a classic bu ered system with a slightly modi ed mechanism of service.
The paper is organized as follows. In section 1 we give a short introduction. In section 2.1, a detailed description of the single-server retrial systems with constant retrial rate and the over ow probability asymptotic are given. In section 2.2, the equivalent classic bu ered system is discussed. In section 3, simulation results are presented. 2 2.1
Description of the model and main result We consider a single-server retrial system with a renewal input of customers arriving at instants tn; n > 1, with independent identically distributed (iid) interarrival times n := tn+1 tn; n > 1; t1 = 0; and with the iid service times Sn; n > 1. We denote a renewal input with rate := 1=E 2 (0; 1), and the service rate of the system is := 1=ES 2 (0; 1).
In a retrial system, if a new customer nds the server busy he joins an in nite-capacity virtual orbit and attempts to occupy server after an exponentially distributed time with rate . We consider a constant retrial rate system. It means that retrial intensity of attempts equals and stays constant regardless of the orbit size. In this case, for convenience, we treat the orbit as a FIFO queue in which only the top (oldest) orbital customer makes attempts to enter server [2].
Denote K0 the index of the rst costumer which meets an empty system upon arrival, and KN { the index of the rst costumer which reaches the level N within busy cycle. We consider an over ow probability P(KN < K0) that the number of customers in the system reaches a (high) level N > 1 during busy cycle.
There are two basic assumptions required for the large deviation analysis: the system is in stationary regime and the possibility of an arbitrary (large) value of the queue. The su cient stability condition for retrial system is [2] := =
< 1;
P( < S) > 0; and coincides with the stability criterion of classic bu ered system GI=G=1. Also we assume that so the arbitrary large value of the queue is possible.
For a random variable X, we introduce the log moment generating function,
(
S ( ) exists for some > 0. Denote De ne and
^ = max( > 0 : Ee S < 1): = sup( 2 (0; ^) : ( ) +
S ( ) 6 0) = sup( 2 (0; min(^; )) : ( ) +
S ( ) + log
6 0):
Theorem 1. Assume that conditions
<
+
and (
N!1
1
N
ln P(KN < K0) 6
(
);
where and are de ned in (
To prove the statement presented in Theorem 1 we transform original retrial system to a classic bu ered system with special type of dependence between service times
S = S + I exp( ); where exp( ) is a random variable (r.v.) exponentially distributed with parameter , and I is an indicator function
Service time S (9) the retrial time. Such classic system is equivalent to original
retiral system from the point of view stability. To obtain a lower asymptotic
bound, we construct a minorant classic bu ered system GI=G=1 with the
minimal service times S~ = S and use a monotonicity of the queue-size process. To
obtain an upper bound, we also construct a dominating classic bu ered system
with the service time S^ = S +exp( ). This approach allows to obtain exponential
decay rate of the over ow probability as N ! 1, with di erent exponents in
the asymptotic lower and upper bounds (
Statement (8) in Theorem 1 can be rewritten as follows: eN ( ) 6 P(KN < K0) 6 eN ( ) + o(N ) as N ! 1: (10) Di erent exponents in the asymptotic lower and upper bounds (10) occur because we compare original retrial system with minorant and dominating classic models with service times
S~ 6 S 6 S^: As retrial rate grows ( ! 1) minorant, dominating and original systems coincide, parameters ! , upper bound approaches lower bound and we get accurate exponential asymptotic for the over ow probability. If retrial rate is not very large, we have to deal with lower and upper bounds with di erent exponents.
In the retrial system customer goes to orbit if server is busy upon the arrival of this customer. Occupation of server can be expressed by means of load coe cient = = . Hence, retrial system can be approximated by classic bu ered system with service times
Sc = S + I exp( ); (11) where In this section, we apply simulation to verify the accuracy of the obtained bounds for the over ow probability.
Experiment 1. First we simulate M=M=1 retrial system with input rate = 2, service rate = 3 and retrial rate = 30 and estimate the asymptotic probability that orbit reaches level N during a busy cycle, as N increases. Using Theorem 1, we calculate the lower and upper bounds, respectively, and compare them with the estimated probability. Then we simulate M=G=1 classic system with in nite bu er with input rate = 2 and service time Sc (see (11)) with I = (1; with probability 2=3;
0; with probability 1=3: We estimate the over ow probability that number of customers in this system reaches level N during a busy cycle, and compare the results with theoretical bounds and the original retrial system.
It is easy to see that parameters , and satisfy stability condition (
The results are presented in Figure 1. It is seen that the estimated probabilities both in the retrial and classic systems are indeed located between the bounds. Moreover they are quite close to each other. It means that more simple classic bu ered system can be analysed instead of the origin retrial system. Experiment 2. Now we consider M=W eibull=1 retrial system with exponential input rate = 0:9 and Weibull service time S with the density f (x) = x a 1 e (x=b)a ; x 0:
a b b = where is the gamma-function. In our experiment we take the following parameters of the Weibull distribution: a = 2 and b = 1. In this case function S can be explicitly calculated It allows us to calculate values and and, as a results, the upper and lower bounds, in an explicit form. Then we simulate M=G=1 classic system with in nite bu er with input rate = 0:9 and service times Sc (11) with We estimate the over ow probability that number of customers in this system reaches level N during a busy cycle, and compare the results with theoretical bounds and the original retrial system. Results presented on Figure 2. Again, the estimated probabilities both in the retrial and classic systems are located between the bounds and they are quite close to each other, as in experiment 1. 4
We consider retrial systems with constant retrial rate policy. The probability that the orbit size of the system reaches a high level N , within busy period, is studied. It is shown that the over ow probability has an exponential decay rate as N ! 1. To establish the asymptotic rate, we compare the original retrial system with the minorant and majorant classical bu ered systems. The opportunities to approximate retrial system with classic bu ered system are discussed. We present simulation results to demonstrate the accuracy of the obtained bounds.
This research is in part supported by Russian Foundation for Basic Research, projects 18-07-00146, 18-07-00156, President Grant MK-1641.2017.1 and Institute of Applied Mathematical Research, Karelian Research Centre Russian Academy of Sciences. 8. Morozov, E.: A multiserver retrial queue: regenerative stability analysis. Queueing
Systems 56(