In this paper we study the remaining service time in a wide class of queueing systems. The remaining service time in uences the behaviour of the customers and by this reason is often an important Quality of Service (QoS) indicator of the system. Our main result is intuitive and as follows: the stationary distribution of the remaining service time of a customer coincides with the stationary overshoot in the renewal process generated by service times multiplied by the stationary busy probability of the server. This distribution is also obtained for the non-stable system.
In this paper, we analyze the stationary remaining service time in a wide class of
queueing systems. The remaining service time can be considered as an important
QoS indicator of the system and may considerably in uence the behaviour of
the customers. It is worth mentioning that the remaining service time plays also
an important role in the stability analysis based on the regenerative approach,
see for instance [6]. However, in the stability analysis, rather the tightness of
the remaining service time turns out to be essential [5] while a more detailed
description, for instance, the explicit expression of the limiting distribution, plays
a secondary role. At the rst sight, the nding of the stationary distribution
of the remaining service time seems to be a challenging problem. However, as
this contribution shows, indeed this problem can be resolved, at least for a wide
class of multiclass queueing systems described by a regenerative process, in which
service times of a given class customers are independent identically distributed
(iid) but class-dependent random variables. The regeneration property of the
basic queueing process is critical for our analysis. By this reason, we focus on
the systems with Poisson inputs of customers. An alternative setting allows a
single renewal input where a class-i customer appears with a probability pi
regardless of the state of the system [6]. It follows from our analysis that the
service discipline and the reliability of the server is important for the analysis
of the remaining service time while the property of input ow is less important,
provided the regeneration property of the system takes place. To the best of our
knowledge, there are a few papers only in which the remaining service time is the
main object of research, see for instance [
Now we describe in brief the systems studying in this paper. We consider an
m-server system M=G=m with N independent Poisson inputs of customers
belonging to di erent classes. The service times are assumed to be class-dependent,
however iid for a given class. Such a system possesses a regeneration property
at the arrival instants when a new customer meets fully empty system. More
exactly, in this system the basic processes, the workload and queue-size, are
classically regenerative, in which the regeneration cycles are iid [
To analyze this system we rst assume that the system is stable (stationary).
More precisely, we assume that the basic regenerative processes are positive
recurrent that is the mean regeneration period of the system is nite [
The main result we obtain is intuitive and states that the stationary distribution of the remaining service time of a customer coincides with the stationary overshoot in the renewal process generated by the service times multiplied by the stationary busy probability of the server. This result holds even for non-identical servers, but the busy probability can be found explicitly for the identical servers only. We mention also that our results can be applied to the retrial systems with state-dependent retrial rates. Stability and performance analysis of such systems have been developed in the recent papers [8,7,9]. We note that the study of the remaining service time is especially motivated in the retrial systems in which, after each departure, there exists an idle time of the server. This idle time in general can be used by the orbital customers to control the rate of the retrial attempts. However a detailed analysis of the remaining service time in these system is assumed to be performed in a future research.
Thus the main contribution of this paper is as follows: the explicit expression for the stationary distribution of the remaining service time in the multiclass multiserver system both in stable and non-stable system.
The paper is organized as follows. In section 2, we describe the basic multiserver multiclass system. First, we de ne the regenerative structure of the system, and then construct a modi ed system which is easier to be investigated and in which the limit distributions related to the busy time process remain unchanged comparing with the original system. Then we obtain the stationary distribution of the remaining service time provided the system is positive recurrent (stationary). In Section 3, we nd the target distribution in the non-stationary system. 2
We consider the classic multi-server system M=G=m with m identical servers, N classes of customers which follow independent stationary Poisson inputs with rates i; i = 1; : : : ; N , and we denote = Pi i the rate of the superposed (Poisson) input. Also we denote by ftn; n 1g the instants of this aggregated input assuming t1 = 0. It is assumed that service times of class-i customers, denoted by fSn(i); n 1g, are iid with generic element S(i), service rate i = 1=ES(i) and distribution function Fi; i = 1; : : : ; N . Let Q(t) be the total number of customers in the system at instant t . First of all we describe the regenerative structure of the system. The regeneration instants fTng of the process fQ(t); t 0g (and other related processes describing the dynamics of the system) are de ned recursively as,
Tn+1 = inf(tk > Tn : Q(tk) = 0); n
k
0;
where T0 := 0 is the regeneration point provided zero initial condition holds:
Q(0) = 0; t1 = 0. In other words, zero initial condition means that the 1st
customer arrives at the empty system at instant t1 = 0. We denote by T the generic
regeneration period, which is distributed as any distance Tn+1 Tn between two
adjacent regeneration points, n 0. The regenerative process fQ(t)g (and the
underlying queueing system) is called positive recurrent if ET < 1. This
requirement in fact is equivalent to stability of the process meaning the existence of the
stationary distribution of Q(t) as t ! 1. (More on regenerative processes see in
[
Denote by S(t) the remaining service time at instant t , assuming S(t) = 0 if the server is empty. Because all servers are identical, then our limiting results will not be dependent on the server index, and as a rule we omit index of server in our notation. Also denote by Si(t) the remaining service time at instant t of class-i customer. By de nition Si(t) = 0 if, at instant t, the server is empty or serves class-k customer, k 6= i. Then the following relation between indicator functions 1( ) holds, for each x 0: 1(S(t) > x) =
N X 1(Si(t) > x); t i=1 0: (1) Thus, at each instant t, at most one indicator function in (1) equals one. Note that
P(Si(t) > x) = P(Si(t) > xjSi(t) > 0)P(Si(t) > 0); and thus (1) implies that
P(S(t) > x) =
N X P(Si(t) > xjSi(t) > 0)P(Si(t) > 0): i=1 Our purpose is to nd explicitly the limiting distribution of the remaining service time S(t) as t ! 1, when exists. By (1), it is enough to nd the weak limit (limit in distribution)
Si(t) ) Si; t ! 1; i = 1; : : : ; N; where Si denotes the stationary remaining service time of class-i customer. Denote i = iES(i) and = X i i; and let S(t) ) S be the stationary (unconditional) remaining service time (in an arbitrary server). Now we formulate and prove the following main result of this section.
Theorem 1. Assume the following negative drift condition holds: < m: Then the system is positive recurrent and the distribution of the stationary remaining service time S has the following form
P(S Proof. To prove the positive recurrence, we note that a new customer arriving in the system is a class-i one with the probability pi := i= . Then our system becomes a single-class one in which the mean service time of an arbitrary customer equals
ES =
N X piES(i):
and coincides with the well-known positive recurrence criterion of the M=G=m
system [
In what follows we consider an arbitrary but xed server and introduce the process
Z t
0 Bi(t) = 1(Si(u) > 0)du; t 0; i = 1; : : : ; N; (5) which, for each i, equals the total time that the server is occupied by class-i customer in the interval [0; t]. Let
Bn(i) = Bi(Tn)
Bi(Tn 1); i = 1; : : : ; N; n 1; be the increment of the process (5) in the n-th regeneration cycle of the system, that is in the interval [Tn 1; Tn); n 1. Evidently, the random variables fBn(i); n 1g are iid with B(i) representing a generic increment during a generic period T .
We now slightly modify the system in the following way. First, we couple together all busy periods of the server when it serves class-i customers within each regeneration cycle of the system and then shift the resulting busy period, distributed as B(i), to the beginning of the corresponding regeneration cycle. Denote by S~i(t) the remaining service time at instant t in this modi ed process, and put S~i(t) = 0 if no class-i customer in the server. We call the resulting process i-modi ed busy time process, and denote it by Also we construct a zero-delayed renewal process, denoted by
Z t
0 B~i(t) = 1(S~i(u) > 0)du; t
0: Zbi = fZb(ni) = S(i) + 1 + Sn(i); n 1g; (6) (7) which consists of the same service times fSn(i)g that are used in the original busy time process Bi(t) (and also in the process fB~i(t)g). Let
Sbi(t) = min(Zb(ni) n t : Zb(ni) t 0); be the remaining renewal time (at instant t) in the process Zbi. Note that the process Zbi has no gaps as opposed to the idle periods which occur after each busy period in the processes fB~i(t)g and fBi(t)g in each regeneration cycle. Recall that Fi represents the distribution function of service time S(i) of class-i customer. It follows from the above construction, that each service time Sn(i), as well as each (composed) busy period B~n(i), can be treated as a regeneration period of the remaining renewal time process fSbi(t)g. In particular, the renewal points Z^(ni); n 1, are the regeneration instants of the process fSbi(t)g. Since both types of regeneration periods have nite means,
ES(i) < 1; EB(i) < 1; i = 1; : : : ; N;
then we obtain from the standard regenerative argument [
1 1(Sbi(u) > x)du = EB(i) E 0
Z S(i) 1 1(Sbi(u) > x)du = ES(i) E 0
Z B(i) 1(Sbi(u) > x)du ; 1(Sbi(u) > x)du
Fi(u))du; (8) (9) where, in order to obtain the second equality in (9), we have relied on the equality Sbi(u) = S(i) u if u
S(i): Let us now again consider the original service process and make the following key observation: the stationary busy probability P(Bi) in the original system equals the corresponding quantity in the system with the modi ed busy time process (6) because the total busy time when the server is occupied by class-i customers, within each regeneration period of the system, remains unchanged. Thus, due to this construction, we obtain the following relations lim t!1 t 0
1 Z t = In order to obtain the last equality, we have taken into account that, in the modi ed system,
S~i(t) = 0; t 2 [B(i); T ) :
E
Z B(i) 0
Z B(i)
0
1(S~i(u) > x)du = E
1(Sbi(u) > x)du ;
(11)
because we apply the same service times both in the original service process and
in the renewal process fZbig. Since the input ow is Poisson then the regeneration
period length T is non-lattice, and it then follows from regenerative theory [
P(S x) = lim P(S(t) t!1 x (1 and thus the basic result (3) is proved.
Now we nd the probability P(Bi) in an explicit form. To this end, we denote by Aij (t) the number of class-i arrivals in server j in the interval [0; t); i = 1; : : : ; N; j = 1; : : : ; m. Because the servers are identical and the total number of class-i arrivals in the interval [0; t), satis es, w.p.1, then we obtain that
Ai(t) := Ai(t) t
N X Aij (t); j=1 ! i; t ! 1; Denote by Vij (t) the total work which is delivered to the server j by class-i arrivals in the interval [0; t). Let Sn(ij) be the service time of the n-th class-i customer being served in server j. Of course, for each server j, the service time Sn(ij) is distributed as S(i); i = 1; : : : ; N . Also denote by Bij (t) the busy time when server j is occupied by class-i customers in the interval [0; t]. Then we obtain the following balance equations
Vij (t) =
Aij(t) X Sn(ij) = Wij (t) + Bij (t); j = 1; : : : ; m; i = 1; : : : ; N; (15) where Wij (t) denotes the remaining class-i work at instant t assigned for server j. It is well known [6] that, in the positive recurrent system,
Wij (t) = o(t); t ! 1 w.p.1: Then it remains to take limit in both sides of the equation (15) as t ! 1 and use the Strong Law of Large Numbers to obtain the required equality (4): where, by the symmetry, the limit is independent of the server index j. This result allows to present the limit distribution (3) as follows x exists and is equal to the conditional tail distribution of the remaining service time provided the server is occupied by class-i customer, i = 1; : : : ; N . 3
The next problem we will address is the limiting distribution of the remaining service time provided the system is not positive recurrent (not stationary). In other words, we assume that ET = 1, in which case, as it follows for instance from [6], the queue size Q(t) ) 1, that is lim P(Q(t) > k) = 1 for each k t!1 0:
N = X i=1 i m; must be met. Because in this case all servers will be eventually full, then we expect that P(S(t) > 0) ! 1. Because the service discipline is assumed to be FIFO (earlier we did not specify the discipline), then a new customer assigning (16) (17) to a given server is class-i one with the probability pi = i= : Thus the limiting fraction of the class-i work Vij (t) (assigned for some server j) equals the limiting fraction of the total class-i work Vi(t) among all the work V (t) received in [0; t), that is (see (14)-(16)) lim t!1 Vi(t)
Vij (t) = lim t!1 V (t)
Vi(t) = lim t!1 PN i=1 PAi(t) Sn(i) n=1 PAi(t) Sn(i) = n=1 i =: P^(Bi); where the ratio P^(Bi) is the probability that, in the limit, an arbitrary server is occupied by a class-i customer. Note that if all customers have the same mean service time, that is i (13) the probability P(Bi) by the probability P^(Bi), implying
, then P^(Bi) = pi. Thus in this case we must replace in lim P(Si(t) > x) = t!1 (1
Fi(u))du; i = 1; : : : ; N; and thus nally we have, by analogy with (17), i Z 1
x N X i=1 i Z x
0 P(S Note that in this (non-stationary case) the normalizing constant m in (17) is replaced by the constant , that is the number of servers no more plays a role in this analysis. 4
In this work, we study the limiting distribution of the remaining service time in the bu ered queueing multiserver systems with Poisson inputs of multiple classes of customers. Using the coupling method and the regeneration property of the systems, we nd the target distribution in an explicit form. 5
This research is supported in part by Russian Foundation for Basic Research, projects No. 19-07-00303, 18-07-00156, 18-07-00147. 4. Kerner, Y.: Equilibrium joining probabilities for an m/g/1 queue. Games and Economic Behavior 71 (2), 521-526 (2011) 5. Morozov, E.: The tightness in the ergodic analysis of regenerative queueing processes. Queueing Syst. 27, 179{203 23 (1997) 6. Morozov, E., Delgado, R.: Stability analysis of regenerative queues. automation and remote control. 1977{1991 (2009) 7. Morozov, E., Dimitriou, I.: Stability analysis of a multiclass retrial system with coupled orbit queues. Proceedings of 14th European Workshop, 73-90, EPEW 2017, Berlin, Germany, September 7-8, 85{98 7 (2017). https://doi.org/10.1007/978-3319-66583-2-6 8. Morozov, E., Morozova, T.: Analysis of a generalized system with coupled orbits.
proceedings of FRUCT23 (2018) 9. Morozov, E., Morozova, T., Dimitriou, I.: Simulation of multiclass retrial system with coupled orbits. Proceedings of SMARTY18: First International Conference Stochastic Modeling and Applied Research of Technology Petrozavodsk, Russia 10 (2018) 10. Ross, S.M., Seshadri, S.: Hitting time in an m/g/1 queue. J. Appl. Prob, 36, 934940 6 (1999)