Heavy outgoing call asymptotics for retrial queue with two way communication and multiple types of outgoing calls

Full Text

Introduction Retrial queueing systems are characterized by the following distinctive fea- ture: a customer who cannot receive service remains in the system and tries to occupy the server after some random delay. The pool of unsatisfied customers is called the orbit. Retrial queues have applications in telecommunication, computer networks and in daily life [1, 2]. In retrial queues idle time of the server is the downtime and it should be reduced to increase the efficiency of the system. We consider systems where operator not only receives calls from outside but also makes outgoing calls in the idle time. In queueing theory a model with this feature have been considered previously [3]. However, the retrial behaviour of customers is not taken into account. In call centers operators could receive arriving calls but as soon as they have free time and are standby mode they could make outgoing calls [4-7]. Systems with this server behaviour are called retrial queues with two way communication. Retrial Queues with two way communication have been studied recently [8-11]. In these papers Markovian models with two way communication were considered. Model of retrial queue with two way communication and multiple types of outgoing calls was considered by Sakurai and Phung-Duc [12]. For this model numerical algorithm of calculating joint stationary distribution of system state was obtained. Multiserver retrial queue with two way communication was studied in [13]. Recently the two way communication retrial queues with finite source [14], with server-orbit interaction [15, 16], with finite orbit [17], with breakdowns [18] and with a constant retrial rate [19] were considered. Asymptotic analysis methods have applications in queueing theory. Nazarov, Paul and Gudkova propose an asymptotic analysis method to research M |M |1|1 retrial queue with two way communication under low rate of retri- als condition [20]. Nazarov, Paul and Phung-Duc extended this model to MMPP|M |1|1 retrial queues and derived asymptotics in heavy outgoing call conditions [21]. In this paper, we consider retrial queue with two way communication and multiple types of outgoing calls. We assume that each type of outgoing calls has different rate and service times follow distinct exponential distributions. The main aim of this paper is to derive asymptotics for the model in two limit conditions: i) high rate of outgoing calls and ii) low service rate of outgoing calls. In both cases, the number of incoming calls in the system increases. The rest of the current paper is organized as follows. In Section 2 and 3, we describe the model in detail and preliminaries for later asymptotic analysis. In Section 4 and 5, we present our main contribution to the model. In Section 6 we show the ranges of parameters under which our approximations are usable. Section 7 is devoted to concluding remarks. Model and preliminaries Model description Figure 1 shows the structure of the model. We consider a single server retrial queue with two way communication and multiple types of outgoing calls. Incoming calls arrive at the system according to a Poisson process with rate λ and try to occupy the server for an exponentially distributed time with rate µ1. Incoming calls that find the server busy join the orbit and repeat their request for service after an exponentially distributed time with rate σ. When the server is idle it makes an outgoing call of type n in an exponentially distributed time with rate αn. There are N types of outgoing calls whose durations follow N distinct exponential distributions. We assume that the durations of outgoing calls of type n follow the exponential distribution with rate µn. ♥ ♥ ❄σ . . . ❄σ ✚ ✚ ✚ λ ✲ µ1 ✚ ✚ ✚ ✚✚ µn ✏ ✑ ✒✻ αn Figure 1. Markovian retrial queue with two way communication and multiple types of outgoing calls Problem definition Let k(t) denote the state of the server at the time t � 0,  0, if the server is idle, k(t) = 1, if an incoming call is in service, n, if an outgoing call of type n is in service, n = 2, N + 1. Let i(t) denote the number of incoming calls in the system at the time t. It is easy to see that process {k(t), i(t)} forms a continuous time Markov chain. We assume that the Markov chain is ergodic and the stationary distribution of {k(t), i(t)} exists. Let P {k(t) = k, i(t) = i} = Pk (i) denote the stationary probability distri- bution of the system state which is the unique solution of Kolmogorov system of equations:    - г λ + iσ + N +1 l αn n=2 P0(i) + µ1P1(i + 1) + N +1 n=2 µnPn(i) = 0, (1)  - (λ + µ1)P1(i) + λP1(i - 1) + λP0(i - 1) + iσP0(i) = 0,  - (λ + µn)Pn(i) + λPn(i - 1) + αnP0(i) = 0, n = 2, N + 1. ∞ Let Hk (u) denote the partial characteristic functions Hk (u) = i=0 ejuiPk (i), k = 0, N + 1, where j = √-1. Multiplying equations of system (1) by ejui and taking the sum over i yields    - г N +1 l λ + αn n=2 t - H0(u) + jσH0(u) + µ1e ju H1(u) + N +1 n=2 µnHn(u) = 0, (2) ju  - (λ + µ1)H1(u) + λe  H1(u) + λeju 0 H0(u) - jσHt (u) = 0,  - (λ + µn)Hn(u) + λejuHn(u) + αnH0(u) = 0, n = 2, N + 1. The characteristic function H(u) of the number of incoming calls in the retrial queue is expressed through partial characteristic functions Hk (u) by N +1 H(u) = Hk (u). The main content of this paper is the solution of system k=0 (2) by using an asymptotic analysis methods in two limit conditions: of the high rate of making outgoing calls and the low rate of service time of outgoing calls. Prelimit analysis In this section, we obtain expressions for the stationary distribution using the characteristic functions. First, we derive explicit expression for the characteristic function H(u) of the number of incoming calls in the system. Theorem 1. Explicit expression for the characteristic function H(u) of the number of incoming calls in M |M |1|N retrial queue is given as follows: H(u) = 1 ( N +1 1 + αn \ × 1 + ν1 n=2 µn + λ(1 - eju) λ αn(θn-λ) Г 1 - ρ тт n l σ (1+ν2)+1 N +1 Г 1 - p l σθn , where × 1 - ρeju λ N +1 α n=2 N +1 α 1 - pneju k ρ = , ν1 = , ν2 µ1 µk k=2 λ = k , θk k=2 µ pn = n + λ , θn = λ + µn - µ1, n = 2, N + 1. Proof. From equations 2 and 3 of the system (2) we obtain expressions for partial characteristic functions: λeju jσ t (3) µ H1(u) = 1 0 - ju 0 H (u) + λ(1 - eju) µ1 αn H (u), + λ(1 - e ) (4) µ Hn(u) = n H0(u), n = 2, N + 1. + λ(1 - eju) Substituting this equations into the first equation of the system (2), we find that λ г λeju Ht N +1 µ1 + λ(1 - eju) αneju l H (u). (5) 0(u) = j σ + µ1 - λeju µ1 - λeju n=2 0 µn + λ(1 - eju) The solution of this differential equation is given by Г 1 - ρ l σ (1+ν ) N +1 Г 1 - p λ 2 тт n l αn(θn-λ) σ(θn) (6) H0(u) = r0 1 - ρeju n=2 1 - pn eju , 0 where ρ = λ , r = H0(0) = P {k(t) = 0}, ν2 N +1 = n αk , p = λ , µ1 θn = λ + µn - µ1, n = 2, N + 1. Substituting u = 0 into the system (2) yields: k=2 θk µn + λ    - ( N +1 \ λ + αn n=2 t r0 + jσ H0(u)|u=0 + N +1 k=1 µkrk = 0, (7) 0  - µ1r1 + λr0 - jσ Ht (u)| u= 0 = 0,  - µnrn + αnr0 = 0, n = 2, N + 1, 0 where expression for Ht (u)| u=0 can be obtained substituting u = 0 into (5). It follows from equations 2 and 3 of the system (7) that г λ λ ( λ N +1 α \l n r1 = + µ1 µ1 - λ + 1 n µ µ n=2 r0, µ n r = αn n r0, n = 2, N + 1. Furthermore, from the normalization condition: N +1 rk = 1, we obtain k=0 µ1 - λ λ αn(µ1 - λ) µ r0 = 1 , r1 = (1 + ν1) µ1 1 n , rn = µ µ , n = 2, N + 1, (1 + ν1) where ν1 = we obtain αk N +1 . Substituting (6) into (3) and (4) and summing up results, k=2 µk H(u) = 1 ( N +1 1 + αn \ × 1 + ν1 n=2 µn + λ(1 - eju) λ αn(θn-λ) Г 1 - ρ тт n l σ (1+ν2)+1 N +1 Г 1 - p l σθn . × 1 - ρeju n=2 1 - pneju Asymptotic analysis of the model under the high rate of making outgoing calls In this section, we will investigate system (2) by asymptotic analysis method under the high rate of making outgoing calls condition. In particular, we prove that asymptotic characteristic function of the number of incoming calls in the system corresponds to Gaussian distribution. Denoting αn = αγn, we obtain    - г λ + α N +1 l γn n=2 t - H0(u)+jσH0(u) + µ1e ju H1(u)+ N +1 n=2 µnHn(u) = 0, (8) ju  - (λ + µ1)H1(u) + λe  H1(u) + λeju 0 H0(u) - jσHt (u) = 0,  - (λ + µn)Hn(u) + λejuHn(u) + αγnHn(u) = 0, n = 2, N + 1. First order asymptotic Theorem 2. Suppose i(t) is the number of incoming calls in the system of the stationary M |M |1|N retrial queue with outgoing calls, then the (9) holds where i(t) lim Eejw α = ejwκ1 , (9) α→∞ λν1µ1 γ N +1 n (10) 1 κ1 = σ(µ , ν1 = - λ) . n µ n=2 Proof. We denote α = 1/ε in the system (8), and introduce the following notations u = εw, H0(u) = εF0(w, ε), Hk (u) = Fk (w, ε), k = 1, N + 1, in order to get the following system    - (λε +      N +1 n=2 γn)F0(w, ε) + jσ ∂F0(w, ε) + µ e- ∂w 1 N +1 jwε F1(w, ε)+ +  n=2 µnFn(w, ε) = 0,  - (λ + µ1)F1(w, ε) + λe jwε F1(w, ε) + λe jwε εF0(w, ε)- (11)      jwε - jσ ∂F0(w, ε) ∂w = 0,  - (λ + µn)Fn(w, ε) + λe  Fn(w, ε)+  + γnF0(w, ε) = 0, n = 2, N + 1. Summing up equations of system (11), we obtain N +1 λεF0(w, ε) + (λ - µ1e-jwε)F1(w, ε) + λ Fn(w, ε) = 0. (12) n=2 Considering the limit as ε → 0 in the system (11) and equation (12), then we will get  N +1   -  n=2   0 γnF0(w) + jσF t(w) + N +1 k=1 µk Fk (w) = 0, 0  - µ1F1(w) - jσF t(w) = 0,  - µnFn(w) + γnF0(w) = 0, n = 2, N + 1, (13)    1 1  - (µ - λ)F (w) + λ  N +1 n=2 Fn(w) = 0. We propose to get the solution of the system (13) in the form of Fk (w) = Φ(w)rk, k = 0, N + 1. (14) Here rk , k = 1, N + 1 is the probability of the server state k; r0 has no sense of probability, since the probability that the server will be in the zero state as α → ∞ is zero:  N +1   -  n=2   γnr0 + jσ Φt(w) Φ(w) r0 + N +1 k=1 µkrk = 0,  Φt(w)  - µ1r1 - jσ Φ(w) r0 = 0,  n n n 0  - µ r + γ r = 0, n = 2, N + 1, (15)     - (µ1 - λ)r1 + λ N +1 n=2 rn = 0. As the relation j Φt(w) Φ(w) does not depend on w, the function is obtained in the following form Φ(w) = exp{jwκ1}, which coincides with (9). The value of the parameter κ1 will be defined below. We rewrite the system (15) in the form  N +1  -   n=2  γnr0 - κ1r0σ + N +1 k=1 µkrk = 0,  - µ1r1 + κ1r0σ = 0,  - µnrn + γnr0 = 0, n = 2, N + 1, (16)    - (µ - λ)r + λ  1 1 N +1 n=2 rn = 0. The normalization condition for stationary server state probability distri- N +1 bution is rk = 1. We have k=1  - µnrn + γnr0 = 0, n = 2, N + 1,     - (µ1 - λ)r1 + λ  N +1   N +1 n=2 rn = 0, (17)   k=1 rk = 1. The solution of the system (17) is given by µ1 - λ λ γn(µ1 - λ) r0 = , r1 = µ1ν µ1 , rn = µnµ1ν1 , n = 2, N + 1, (18) where ν1 = γn N +1 . Substituting (18) into system (16), we obtain an equation n=2 µn for κ1, which coincides with (10). The first order asymptotic i.e. Theorem 2, only defines the mean asymptotic value κ1α of a number of incoming calls in the system in prelimit situation of α → ∞. For more detailed research of number i(t) of incoming calls in the system let’s consider the second order asymptotic. D Second order asymptotic Theorem 3. In the context of Theorem 2 the following equation is true ( lim E exp jw κ i(t) √ α - 1 (jw)2 = e , (19) α→∞ 2 κ2 α where λ µ1(µ1 - λ)(λν2 + ν1) + λ2ν1 γ N +1 n γ N +1 n (20) κ2 = σ · (µ1 , ν1 = - λ)2 n=2 µ , ν2 = n µ 2 . n=2 n Proof. We introduce the following notations in the system (8) and we get k Hk (u) = exp{juακ1}H(2)(u), k = 0, N + 1, (21)  (   - λ + α    N +1 n=2 \ γn + ασκ1 0 H(2)(u) + jσ N +1 dH(2)(u) 0 + du   + µ1e    -ju H (2) 1 (u) + n=2 n µnH(2)(u) = 0, (2) ju  - (λ + µ1)H1 (u) + λe   1 H(2)(u) + (λeju 0 + ασκ1)H(2)(u)- 0 dH(2)(u) (22)     - (λ + µn)H(2)(u) + λejuH(2)(u)+ - jσ du = 0, n n  0  + αγnH(2)(u) = 0, n = 2, N + 1. Denoting α = 1/ε2, and introducing the following notations u = wε, H(2)(u) = ε2F (2)(w, ε), H(2) 0 0 (2) (23) we obtain k (u) = Fk (w, ε), k = 1, N + 1,   jσε   0 ∂F (2)(w, ε) ∂w - ( σκ1 + λε2 N +1 \ + γn n=2 0 F (2)(w, ε)+    + µ1e    -jwε F (2) 1 (w, ε) + N +1 n=2 n µnF (2)(w, ε) = 0, (2)  - (λ + µ1)F1 (w, ε) + λe  jwε 1 F (2)(w, ε)+ ∂F (2)(w, ε) (24) 0   + (λejwεε2 + σκ1)F (2)(w, ε) - jσε 0  ∂w  = 0,  - (λ + µn)F (2)(w, ε) + λejwεF (2)(w, ε)+  n n   + γnF (2) 0 (w, ε) = 0, n = 2, N + 1. Summing up equations of the system (24), we obtain λε2F (2) (2) N +1 n 0 (w, ε) + (λ - µ1e-jwε)F1 (w, ε) + λ n=2 F (2)(w, ε) = 0. (25) Our idea is to seek for a solution of the system (24) and equation (25) in the form F (2) 2 k (w, ε) = Φ2(w){rk + jwεfk } + o(ε ), k = 0, N + 1. (26) Substituting (26) to (24) and (25), laying out the exhibitors in tailor series and taking (16) into account, dividing these equations by ε and taking the limit as ε → 0, we have ( N +1 \ - σκ1 + γn n=2 N +1 f0 + µkfk - µ1r1 + σ k=1 2 Φt (w) wΦ(w) r0 = 0, σκ1f0 - µ1f1 + λr1 - σ 2 Φt (w) wΦ(w) r0 = 0, -µnfn + λrn + γnf0 = 0, n = 2, N + 1, N +1 -(µ1 - λ)f1 + λ fn + µ1r1 = 0. n=2 2(w) This equations imply that Φt wΦ2(w) doesn’t depend on w and thus the function Φ2(w) is given in the following form (jw)2 Φ2(w) = exp which coincides with (19). We have t Φ2(w) wΦ2(w) and then we obtain the system κ2 , 2 = -κ2  ( -  σκ1 +    N +1 \ γn n=2 f0 + N +1 k=1 µkfk = µ1r1 + σκ2r0, σκ1f0 - µ1f1 = -λr1 - σκ2r0,  - µnfn + γnf0 = -λrn, n = 2, N + 1, (27)    1 1  - (µ - λ)f + λ N +1 n=2 fn = -µ1r1. Substituting values (18) into the system (27), we have f = γn n µ f0 + λ(µ1 - λ)γn µ µ2 , n = 2, N + 1, n 1 nν1 λν1 λ2ν2 λ where µ f1 = 1 f0 + - λ µ1ν1 + , µ1 - λ γ k N +1 ν1 = , ν2 µk γ N +1 = k . µ2 k=2 k=2 k Substituting this expressions into equation 2 of the system (27), we obtain an equation for κ1, which coincides with (20). Second order asymptotic i.e. Theorem 3, shows that the asymptotic prob- ability distribution of the number i(t) of incoming calls in the system is Gaussian with mean asymptotic κ1α and variance κ2α. D Asymptotic analysis of the model under the low rate of service time of outgoing calls In this section, we will investigate system (2) by asymptotic analysis method under the low rate of service time of outgoing calls condition. Denoting µn = µγn, we obtain    - г N +1 l λ+ αn n=2 t - H0(u)+jσH0(u)+µ1e ju H1(u)+µ N +1 n=2 γnHn(u) = 0, (28) ju  - (λ + µ1)H1(u) + λe  H1(u) + λeju 0 H0(u) - jσHt (u) = 0,  - (λ + µγn)Hn(u) + λejuHn(u) + αnHn(u) = 0, n = 2, N + 1. Theorem 4. Suppose i(t) is a number of incoming calls in a system of stationary M |M |1|N retrial queue with two way communication, then the following equation is true H(u) = lim Eejwµi(t) = 1 α N +1 n 1 N +1 тт 1 \ µ1αn λ - σ(µ1-λ) jw , (29) where ν1 = µ→0 αn N +1 . 1 ν n=2 γn - jwλ n=2 - γn n=2 γn Proof. We denote µ = ε, let’s substitute the following in the system (28) u = wε, H0(u) = εF0(w, ε), Hk (u) = Fk (w, ε), k = 1, N + 1. We will get the system  (   - λ +      N +1 n=2 \ αn εF0(w, ε) + jσ -jwε ∂F0(w, ε)+ ∂w N +1 + µ1e   F1(w, ε) + ε ∂F0(w, ε) n=2 γnFn(w, ε) = 0, jwε (30)  - (λ + µ1)F1(w, ε) - jσ     ∂w jwε + λe + λεejwε F1(w, ε)+ F0(w, ε) = 0,  - (λ + εγn)Fn(w, ε) + λe  Fn(w, ε)+  + αnεF0(w, ε) = 0, n = 2, N + 1. Considering the limit as ε → 0 in the system (30) then we will get -jσF t(w) - µ1F1(w) = 0, jσF t(w) + µ1F1(w) = 0. (31) 0 0 Summing up equations of the system (30) we have N +1 λεF0(w, ε) + (λ - µ1e-jwε)F1(w, ε) + λ γnFn(w, ε) = 0. (32) n=2 Laying out the exhibitors in tailor series, dividing equations by ε and taking the limit as ε → 0, taking (31) into account, we obtain ( N +1 \ - λ + αn n=2 N +1 F0(w) - jwµ1F1(w) + γnFn(w) = 0, n=2 0 -jσF t(w) - µ1F1(w) = 0, (λjw - γn)Fn(w) + αnF0(w) = 0, n = 2, N + 1 N +1 -(µ1 - λ)F1(w) + λ Fn(w) = 0. n=2 From the last system of equations we have αn (33) γ Fn(w) = n F0(w), - jwλ λ N +1 (34) µ F1(w) = 1 - λ n=2 Fn(w). Then λ α N +1 n (35) µ F1(w) = 1 F0(w) - λ n=2 . γn - jwλ Substituting (35) into (31), we obtain F t λµ1 α N +1 n 1 0(w) = j σ(µ F0(w) - λ) n=2 . γn - jwλ The solution of differential equation is given by N +1 1 F0(w) = C тт n=2 1 - jw \ µ1αn λ - σ(µ1-λ) γn , (36) where C is an integration constant and its value will be obtained later. We N +1 denote asymptotic characteristic function (36) into (33) and (34), we obtain Fk (w) = Φ(w). Substituting k=1 λ N +1 α N +1 1 λ \- µ1αk k тт σ(µ1-λ) µ F1(w) = 1 - λ k=2 C γk - jwλ k=2 γ 1 - jw , k γ Fn(w) = n αn C - jwλ 1 N +1 тт k=2 λ \- γ 1 - jw k µ1αk σ(µ1-λ) , n = 2, N + 1. Summing up equations, we have N +1 µ1αn - N +1 Φ(w) = µ1 C тт 1 λ \ 1 - jw . σ(µ1-λ) αn µ1 - λ n γ n=2 n - γ jwλ n=2 Using condition Φ(0) = 1, we obtain C = µ1 - λ µ1ν1 , where ν1 = α N +1 n n . γ n=2 We obtain the characteristic function (29). D Approximation accuracy The accuracy of the approximation P (2)(i) is defined by using Kolmogorov i range ∆2 = max (P (ν) - P (2)(ν)) , which represents the difference be- ν=0 0�i�N tween distributions P (i) and P (2)(i), where P (i) is obtained by using inverse Fourier transform for the characteristic function of the M |M |1|N retrial queue and the approximation P (2)(i) is given by obtained asymptotics. We consider N = 3, λ = 0.2, µ1 = 1 and σ = 1 for Tables 1 and 2. Kolmogorov range, µ2 = 2, µ3 = 3, µ4 = 4, γ2 = 1, γ3 = 2, γ4 = 3 Table 1 α = 3 α = 5 α = 10 α = 50 α = 100 ∆2 0.066 0.043 0.023 0.01 0.007 Kolmogorov range, γ2 = 2, γ3 = 3, γ4 = 4, α2 = 1, α3 = 2, α4 = 3 Table 2 µ = 0.05 µ = 0.035 µ = 0.02 µ = 0.01 ∆2 0.059 0.044 0.026 0.014 Conclusions In this paper, we have considered retrial queue with two way communication with multiple types of outgoing calls. We have found characteristic function of the number of incoming calls in the system. We have found the first and the second order asymptotics of the number of calls in the system under the condition of the high rate of making outgoing calls. Based on the obtained asymptotics we have built the Gaussian approximation of the probability distribution of the number of incoming calls in the system. We have found asymptotic characteristic function of the number of incoming calls in retrial queue under the condition of the low service rate of outgoing calls. In future we plan to consider this retrial queueing system under other asymptotic conditions.

About the authors

Anatoly A Nazarov

National Research Tomsk State University

Author for correspondence.
Email: nazarov.tsu@gmail.com

Professor, Doctor of Technical Sciences, Head of Department of Probability Theory and Mathematical Statistics, Institute of Applied Mathematics and Computer Science

36 Lenina ave., Tomsk, 634050, Russian Federation

Svetlana V Paul

National Research Tomsk State University

Email: paulsv82@mail.ru

Candidate of Physical and Mathematical Sciences, Assistant Professor of Department of Probability Theory and Mathematical Statistics, Institute of Applied Mathematics and Computer Science

36 Lenina ave., Tomsk, 634050, Russian Federation

Olga D Lizyura

National Research Tomsk State University

Email: oliztsu@mail.ru

Master’s Degree Student of Institute of Applied Mathematics and Computer Science

36 Lenina ave., Tomsk, 634050, Russian Federation

References