Keywords

1 Introduction

This paper complements the research presented in the work [16] and is devoted to analysis of the stationary remaining service time in the multiclass retrial queueing systems with constant class-dependent retrial rates and non-reliable servers. In the paper [16], we study this problem for the classical buffered system with reliable servers. A common idea connecting these two papers is to apply the regenerative approach to deduce the stationary distribution of the remaining service time using the renewal process generated by the sequence of the actual service times realized in the given server.

In this paper we consider this problem in continuous-time setting to find the limiting (stationary) distribution of the remaining service time of a customer being in the server at instant t, as \(t\rightarrow \infty \). Another approach suggests that the remaining service time is estimated at the arrival instants of the customers and it leads to the discrete-time setting of the problem. It is worth mentioning that, because the input flow is Poisson, then both approaches give the same stationary distribution of the remaining service time due to the property PASTA [1].

In general, the analysis of the remaining service time is a challenging problem. On the other hand, it is an important Quality of Service parameter, especially in the retrial systems. The main reason is that, unlike the classic systems, in the retrial system after each departure of a customer, the server remains unused for a time, until the next exogenous customer arrives or a customer from an orbit occupies the server. These idle periods of the server occur after each departure, and thus the estimated remaining service time can be used by the orbital customers, for instance, to speed-up the attempts, in the appropriate time interval, to increase the chance to enter server. In this regard, the applications of this analysis in the framework of the game theory seem to be quite promising, see for instance, [7, 8]. It is well-known that the remaining service time is important in the regenerative stability analysis [10, 11]. However, in this case the tightness of the remaining service time plays a key role. To the best of our knowledge, a few papers only study the remaining service time as the main object of the research, see [4, 10, 18].

Now we describe the main underlying idea of the approach used in this paper to analyze the remaining service time. This approach is also developed in the paper [14] for the classic buffered queueing systems with reliable servers. However, as we show in this research, the method is extended to a wide class of the multiclass queueing systems in which the service times of a given class are independent identically distributed (iid) random variables; and we call them class-dependent service times. As we mention above, the systems we study possess regeneration property, and this is a critical requirement. We first assume that the basic regenerative queueing processes are positive recurrent, that is the mean regeneration period length is finite. In fact it implies stability of the system meaning that the stationary distribution of the basic process exists [1]. As to the stability conditions of the retrial systems, we refer to the papers [3, 17] in which such conditions, for a wide class of the systems with the constant retrial rate policy, are established. The servers are assumed to be unreliable, and the interruptions imply a service delay. In this work, we consider the following two service disciplines caused by the service interruptions: preemptive repeat different, and preemptive resume. To reflect the delay caused by the interruptions, we consider the so-called generalized service time of a customer which equals the full time that customer spends in the server, see [5]. This time includes in particular, all setup times following interruptions which occurring during service of this customer. These generalized service times, for each class i, are iid and thus the method we develop in this research is applicable to study the remaining generalized service time by the analogy with the system with reliable servers [14]. Using the same approach as in [14], we construct a simpler system in which the stationary distribution of the remaining generalized service time remains unchanged. Then, using the iid generalized service times of class-i customers, we construct a class-i renewal process and show that the target distribution coincides with the distribution of the stationary overshoot in this process, multiplied by the stationary probability that the server is busy by a class-i customer. The type of service interruptions caused by the failure of the server plays a key role in our analysis, while the retrial policy is important for the motivation of the research. The interrupted customer blocks the server for other customers until he finishes service.

This model is a generalization of the model considered in previous works [12, 15, 16], where reliable servers are only considered. We stress that it is not the purpose of this work to discuss the systems with service interruptions in details, instead we refer to the following survey papers on this topic [6, 9].

The main contribution of this paper is intuitive and states that the stationary distribution of the remaining generalized service time of a class-i customer coincides with the stationary overshoot in the renewal process generated by the class-i service times, multiplied by the stationary busy probability of the server by class-i customer. Because the distribution of the generalized service time is a convolution of the original service times and setup times, we apply the Laplace-Stieltjes transform (LST) representation of this distribution obtained earlier in the paper [5]. In particular this approach allows to calculate the moments of the target variable, and we give an example of this calculation in the last Sect. 5. Note that, in general, it is a challenging problem to obtain the entire distribution function by means of the inverting of the corresponding LST.

The paper is organized as follows. In Sect. 2 we describe the basic retrial system and its regenerative structure. Then, in Sect. 3, we introduce the generalized service time and give the representation of its the density for both preemptive repeat and for preemptive resume policies. Then the corresponding LST representations, adapted from the paper [5], are given. In Sect. 4 we outline the regenerative proof of the explicit form of stationary distribution of the generalized service time. In particular, we consider a simpler system, which is easier to be investigated, in which the limiting distribution of the remaining generalized service time is the same as in the original system. Then we deduce an explicit expression for the target distribution and the explicit expression for the stationary busy probability. To use the limiting distribution of the remaining generalized service time in practice, we need to be able to invert the corresponding LSTs. On the other hand, this expression allows in general to calculate numerically the moments of the target distribution, and in the last Sect. 5 we give some numerical examples which illustrate this point.

2 Description of the Model

In general, our analysis is applied to a wider class of the queueing systems with unreliable servers. Nevertheless, we describe in brief the following basic retrial system which, as we mentioned in the Introduction, motivates the present analysis of the remaining service time. It is assumed that the system has m indentical servers and is fed by N classes of customers following Poisson independent inputs. We denote by \(\lambda _i\) the input rate of class-i customers, and by \( \lambda =\sum _{i=1}^N\lambda _i\), the total input rate. It is clear that \( p_i:=\lambda _i/\lambda , \) is the probability that an arbitrary arrival belongs to class i; \(i=1,\ldots ,N\). We assume that the service times of class-i customers, \(\{S_n^{(i)},\,n\ge 1\}\), are iid with rate (where \(S^{(i)}\) denotes the generic service time). We further denote by \(F_i(x)\) the distribution function of \(S^{(i)}\), by \(f_{i}(x)\) its density and by \(\mathcal{F}_i(z)\) the corresponding LST, that is

(1)

Each server becomes unavailable time to time, interrupting current service if any. It is assumed that the interruptions of each server occur according to a Poisson process with rate \(\nu _i\) if a class-i customer is being served, \(i=1,\ldots , N\). After any interruption the server remains unavailable for a random setup time \(R_i\), assuming that a class-i customer is interrupted. It is important to note that the interrupted customer continues to occupy the service area to return for service after the setup period. Thus this server is blocked for other customers until current customer finishes service and leaves the system. We consider preemptive repeat different, and preemptive resume service rules. In the former case, the interrupted service starts again as a new independently sampled service time, while in the latter case, the service continues after each interruption, when the server becomes available again after setup time, until it is exhausted. We denote by \(r_i(x)\) the density of the setup time \(R_i\), and by \(\mathcal{R}_i(z)\) its LST,

$$\begin{aligned} \mathcal{R}_i(z)=\int _0^\infty e^{-zx} r_i(x)dx,\,\,z\ge 0; \,\,i=1,\ldots ,N. \end{aligned}$$
(2)

An arriving class-i customer meeting all servers occupied, joins a class-i (virtual) orbit and then attempts to occupy servers again following a Poisson process with i-dependent rate. (The exact values of the retrial rates are not used in the subsequent analysis.)

Now we define the regenerations of the system as the arrival instants when the new customer meets fully idle system. Denote by T the generic regeneration period length. Then stability means that the mean length is finite, , in which case the basic regenerative processes describing the dynamics of the system are called positive recurrent [1]. More detailed description of the regenerative structure of the retrial systems can be found in [5, 12], while the stability analysis of the constant retrial rate systems has been developed in particular in the papers [2, 3, 17].

3 Generalized Service Time

In the systems with server interruptions, the total time a class-i customer spends in the server becomes bigger than the “pure” service time \(S^{(i)}\) because it includes setup periods which occur during his service. By this reason, the distribution of this total time includes a convolution of the setup time distributions and in general is not easy to be calculated. We will call generalized service time the total time that a customer spends in the server which is precisely the time from the start of the service until the customer leaves the system. Denote by \(C_{n}^{(i)}\) the generalized service time of the nth arriving class-i customer. For each i, the sequence \(\{C_{n}^{(i)},\,n\ge 1\}\) is iid with generic element \(C^{(i)},\,i=1,\ldots , N.\)

3.1 Preemptive Repeat Service Discipline

We first consider the preemptive repeat interruption rule, which works as follows. If an interruption occurs while a class-i customer is being served then the attained service time is lost and a new independent service time, sampled from the common distribution \(F_i\), starts anew when server becomes available after the setup time. For a distribution F, denote by \(\bar{F}=1-F\) its tail distribution. Denote by \(G_i\) the distribution function of the generalized service time of class-i customer, and let \(g_i\) be its density. It is shown in [5] that the density \(g_i\) satisfies the following functional equation:

$$\begin{aligned} g_i(x)=e^{-\nu _ix}f_{i}(x) +\nu _{i}e^{-\nu _{i}x}\bar{F}_i(x) *r_{i}(x)* g_i(x),\,\,x\ge 0, \end{aligned}$$
(3)

where \(*\) means convolution. (A detailed discussion of this formula can be found in [5].) To solve this equation, we apply the LST. Define the LST of the generalized service time

$$ \mathcal{G}_i(z)=\int _{0}^{\infty }e^{-zx}g_i(x)dx,\,\,z>0. $$

Then, using (1)–(3) and the property of the LST of the convolution, we obtain, after a simple algebra (also see [5]), the following expression:

$$\begin{aligned} \mathcal{G}_i(z)= \frac{(\nu _i+z)\,\mathcal{F}_i(\nu _i+z)}{\nu _i+z-\nu _i\big (1-\mathcal{F}_i(\nu _i+z)\big )\,\mathcal{R}_i(z)},\,\,i=1,\ldots , N. \end{aligned}$$
(4)

In particular, using (4) and the property of the LST, we derive the mean generalized service time of the class-i customer,

(5)

This in turn allows to calculate the traffic intensity of class-i customers,

(6)

which is used in the subsequent analysis.

Remark 1. Traffic intensity is also used in the stability analysis of the retrial systems. For instance, as it is expected, condition \(\sum _i\rho _i<m\) is necessary for the positive recurrence of this retrial system. However the sufficient stability (positive recurrence) conditions are more complicated, see for instance the recent papers [12, 17].

3.2 Preemptive-Resume Service Discipline

In this case, each customer spends in the server his initial service time and all setup periods caused by the interruptions which occur during his service. As it is shown in [5], in this case the density of the generalized service time satisfies

$$\begin{aligned} g_i(x)=e^{-\nu _{i}x}f_{i}(x)+f_{i}(x)\sum _{n=1}^{\infty }e^{-\nu _{i}x} \frac{(\nu _{i}x)^{n}}{n!}*r_{i}^{(n)}(x),\,\,x\ge 0, \end{aligned}$$
(7)

where \(r^{(n)}_{i}(x)\) denotes the nth convolution of the density \(r_{i}(x)\) with itself. Then, as above, it follows that,

$$\begin{aligned} \mathcal{G}_i(z)=\mathcal{F}_i(\nu _i(1-\mathcal{R}_i(z))+z), \end{aligned}$$
(8)

(also see [5]) implying in particular that

(9)

4 Performance Analysis

Now we fix an arbitrary server and suppress server index in the following analysis. Denote by \(C_i(t)\) the remaining generalized service time at instant \(t^-\), and let \(C_i(t)=0\) if server is idle or serves a class-k customer with \(k\not =i\). Then the process

(10)

where denotes indicator function, describes the aggregated time, in the interval \([0,\,t]\), when the server is busy by class-i customers. Denote the weak limit, if exists,

$$ C_i(t)\Rightarrow \mathbb {C}_i,\,\,\, \;t\rightarrow \infty , $$

which is the stationary remaining generalized service time. When the system is positive recurrent, then it follows from the regenerative theory (and because the aggregated input process is Poisson) that the latter limit exists, and moreover,

(11)

where is the stationary probability that the server is occupied by class-i customer. Our main result is as follows.

Theorem 1

The stationary distribution of the remaining generalized service time of class-i customer has the following form:

(12)

Proof

The proof of this statement is similar to that is given in the paper [14] for the multiclass system with reliable servers. For the completeness we outline below the main steps of the proof. Denote by \(T_n,\,n\ge 1,\) the regeneration instants of the system, define the iid increments

of the process (10) over regeneration cycles, and let \(B^{(i)}\) represent a generic increment of this busy time process over a generic regeneration period T. Now we consider a modified system, denoted by \(\tilde{\Sigma }\), in which we couple together all class-i service times within a regeneration cycle, and then shift the obtained busy period, distributed as \(B^{(i)}\), to the beginning of the cycle. We then denote by \(\tilde{C}_i(t)\) the remaining (generalized) service time of a class-i customer in the given server in system \(\tilde{\Sigma }\) at the instant t. By definition, \(\tilde{C}_i(t)=0\) if the server is free or serves a class-k customer, \(k\not = i\). Using regenerative arguments, it is easy to show that the limiting distributions of \(C_i(t)\) and \(\tilde{C}_i(t)\) coincide, and in particular,

(13)

Because \( \tilde{C}_i(t)=0\) when \(t\in [B^{(i)},\,T) \), then we obtain, after some algebra, that

(14)

Then we construct a renewal process \(\hat{\mathbb {Z}}_i \) generated by the iid generalized service times \(\{C_n^{(i)}\}\) realized in the given server, and denote by \(\{\hat{C}_i(t)\}\) the remaining renewal time at instant t in this process. Denote the weak limit

$$\begin{aligned} \hat{C}_i(t)\Rightarrow \hat{\mathbb {C}}_i, \,\,\,t\rightarrow \infty , \end{aligned}$$
(15)

which is the stationary overshoot in the renewal process \(\hat{\mathbb {Z}}_i \). The following evident representation, which holds for each \(x\ge 0\), is important for the further analysis:

Our purpose is to show that the conditional probability satisfies

(16)

that is, coincides with the (tail) distribution of the overshoot (14) in the renewal process \(\hat{\mathbb {Z}}_i\). (Note that, unlike (13), this convergence is not evident.) A key observation for our analysis is that each renewal point can be considered as a regeneration point of the process \(\{\hat{C}_i(t)\}\). On the other hand, we can also split the renewal process \(\hat{\mathbb {Z}}_i\) onto iid blocks distributed as a generic busy period \(B^{(i)}\), and then treat these blocks as the regeneration periods “embedded” in the renewal process \(\hat{\mathbb {Z}}_i\). By assumption, both these “regeneration periods” have finite means, and we obtain, using the well-known regenerative arguments [1], the following twofold representation, which holds for each \(x\ge 0\):

(17)

Combining (13)–(17) and after some algebra, we arrive to (12). \(\Box \)

Denote by C(t) the unconditional generalized remaining service time at instant t, and then \(C(t)=0\) only if the server is free. Because, by construction, for \(i=1,\ldots ,N\), only one indicator maybe positive at each instant t, then we obtain the following representation

(18)

Denote the weak limit \(C(t)\Rightarrow \mathbb {C}\). Then relation (18) immediately implies the following generalization of the statement (12). (Some details of the proof can be found in [14].)

Theorem 2

The stationary distribution of the remaining generalized service time (in an arbitrary server) has the following form:

(19)

It remains to find the probability . It can be done exactly as in [14] using the following balance equation connecting the work \(V_{i}(t)\), generated by class-i arrivals in the interval [0, t], the busy time \(B_i(t)\) and the remaining work (workload) needed to serve class-i customers present at instant t,

$$\begin{aligned} V_i(t)=W_i(t)+B_i(t),\,\,i=1,\ldots ,N, \end{aligned}$$
(20)

where, by the positive recurrence, \(W_i(t)=o(t),\,t\rightarrow \infty \) with probability 1 [19]. Recall that the servers are assumed to be equivalent and then, in the classic buffered systems, the realised class-i work \(B_i(t)\) in the limit is equally divided among all m servers. This is because, by the FCFS discipline, each server accepts class-i customers with the same probability \(p_i=\lambda _i/\lambda \) as in the input flow. In the retrial systems however the FCFS rule no longer holds. Nevertheless, because of the equivalence of the servers and by the positive recurrence implying the equality of the arrived and departed customers at the regeneration instants, we accept a plausible assumption that the mentioned uniform division of the work \(B_i(t)\) holds true in the limit in this case as well. Then we easily find from (20) and (6) that

implying

Thus in particular the distribution function (19) can be rewritten as

(21)

Note that, unlike the buffered system [14], we can not extend this analysis to the non-stationary (non-positive recurrent) retrial system because in this case the distribution of class-i customers among servers becomes unknown.

We stress that the distribution \(G_i\) of the generalized service time which is contained in (21) is obtained in the terms of the LST only. Thus, the extracting of the distributions \(G_i\) and \(D_i\) in an explicit form requires inversion of the LST, and as a rule is hardly available. Nevertheless in some cases the corresponding moments can be found. Indeed, it follows from (12), that the density \(d_i(x)\) of the distribution \(D_i(x)\) equals

$$\begin{aligned} d_i(x)= \frac{d D_i(x)}{dx}=:D_i^{(1)}(x)=\frac{\lambda _i}{m}(1-G_i(x)),\,\,i=1,\ldots ,N;\,\,\,x\ge 0. \end{aligned}$$
(22)

This gives the following expression for the nth moment of the target variable \(\mathbb {C}_i\):

(23)

provided the moment exists. Thus if we can calculate using the LST representation (4) or (8) then we obtain the moment in an explicit form.

It is worth mentioning that, by the property PASTA, expression (23) gives also the moments of the stationary remaining generalized service time observed by an arrival customer.

5 Examples

In this section we calculate some moments of the generalized service time for the preemptive-resume service interruption policy and class-i customers, using representation (8):

$$\begin{aligned} \mathcal{G}_i(z) =\mathcal{F}_i(\nu _i-\nu _i\mathcal{R}_i(z)+z). \end{aligned}$$
(24)

The second derivation of \(\mathcal{G}_i(z)\), denoted \(\mathcal{G}_i^{(2)}(z)\), equals

$$\begin{aligned} \mathcal{G}_i^{(2)}(z)= & {} -\nu _i \mathcal{R}_i^{(2)}(z) \mathcal{F}_i^{(1)}(\nu _i-\nu _i\mathcal{R}_i(z)+z)\nonumber \\+ & {} (1-\nu _i \mathcal{R}_i^{(1)}(z))^2 \mathcal{F}_i^{(2)}(\nu _i-\nu _i\mathcal{R}_i(z)+z). \end{aligned}$$
(25)

Because

(26)

then, substituting \(z = 0\) in both sides of (25), we obtain

(27)

Now (23) gives the mean stationary generalized remaining service time of class-i customer:

(28)

To calculate the second moment , we find the third derivative of \(\mathcal{G}_i(z)\):

$$\begin{aligned} \mathcal{G}_i^{(3)}(z) =- & {} \nu _{i} \mathcal{R}_i^{(3)}(z) \mathcal{F}_i^{(1)}(\nu _{i} -\nu _{i} R(z) + z) (-\nu _{i} \mathcal{R}_i^{(1)}(z) + 1) \\- & {} \nu _{i} \mathcal{R}_i^{(2)}(z) \mathcal{F}_i^{(2)}(\nu _{i} -\nu _{i} R(z) + z) (-\nu _{i} \mathcal{R}_i^{(1)}(z) + 1) \\+ & {} 2 (1 - \nu _{i} \mathcal{R}_i^{(1)}(z))(-\nu _{i} \mathcal{R}_i^{(2)}(z)) \mathcal{F}_i^{(2)}(\nu _{i} -\nu _{i} R(z) + z) \\+ & {} (1 - \nu _{i} \mathcal{R}_i^{(1)}(z))^3 \mathcal{F}_i^{(3)}(\nu _{i} -\nu _{i} R(z) + z), \end{aligned}$$

which, after substituting \(z = 0\), gives

Now we present two numerical examples which illustrate formula (28) and show the impact of the preemptive-resume service interruptions on the mean generalized service time. In both examples we allow arbitrary number of servers m and arbitrary input rate \(\lambda _i\).

Pareto Service Time. First we consider Pareto service time distribution

(29)

and the exponential setup period \(R_i\) with rate 4. Moreover we take the interruption rate \(\nu _i=2\). As a result, we obtain the following values of the required moments:

(30)

Now, substituting these values in formula (28), we obtain the mean stationary remaining generalized service time:

(31)

Weibull Service Time. In this example we choose the Weibull service time distribution

$$\begin{aligned} F_i(x) = 1 - e^{-x^2}, \,\,\,x\ge 0, \end{aligned}$$
(32)

leaving all other parameters unchanged. This gives

where \(\varGamma \) denotes Gamma-function, and by (28), we obtain

It is seen that in both examples the influence of interruptions on the mean remaining generalized service time turns out to be not very significant. Also note that the Weibull service time with the shape parameter 2 as in (32) has the New-Better-Than-Used property [1], and it may cause a decreasing of the remaining generalized service time.

6 Conclusion

In this work we consider a multisever multiclass retrial system with unreliable servers. We investigate the remaining generalized service time of a customer observed at a random instant as time goes to infinity. The generalized service time includes possible unavailable periods (setup times) caused by the interruptions of the server occurring during service. We consider both preemptive repeat different service and preemptive resume service disciplines. Using the regenerative arguments, we obtain the stationary distribution of the remaining generalized service time, which is available in the terms of the LST. In general, this allows to calculate the moments of the remaining generalized service time when the moments of the generalized service time can be found. Some numerical examples are included as well.