Abstract
In this paper, we consider an MMPP/M/1/1 retrial queue where incoming fresh calls arrive at the server according to a Markov modulated Poisson process. Upon arrival, an incoming call either occupies the server if it is idle or joins an orbit if the server is busy. From the orbit, an incoming call retries to occupy the server and behaves the same as a fresh incoming call. The server makes an outgoing call in its idle time. Our contribution is to derive the asymptotics of the number of calls in retrial queue under the conditions of high rate of making outgoing calls and low rate of service time of outgoing calls.
A. Nazarov—The publication was financially supported by the Ministry of Education and Science of the Russian Federation (the Agreement number 02.a03.21.0008).
Access provided by CONRICYT-eBooks. Download conference paper PDF
Similar content being viewed by others
Keywords
- Retrial queueing system
- Incoming and outgoing calls
- Asymptotic analysis method
- Markov modulated Poisson process
- Gaussian approximation
- Gamma approximation
1 Introduction
In service systems idle time of an operator should be minimized to increase the productivity. An operator not only receives calls from outside but also makes outgoing calls in the idle time. The example of that could be the cellphone that is used for incoming and outgoing calls. In call centers operators could receive arriving calls but as soon as they have free time and are in standby mode they could make outgoing calls to sell packages and services of the center [1].
Retrial Queues with two-way communication have been extensively studied recently [2,3,4,5,6,7]. In these literatures the arrival process is Poisson process. However, it is well known that real traffic has a more complex structure. Markov modulated Poisson process (MMPP) can represent correlated traffic and thus it is more suitable for modelling real traffic.
In this paper, we consider asymptotic analysis for the distribution of the number of customers in the system under two conditions: (i) high outgoing call rate and (ii) low service rate for outgoing calls. In case (i), the server makes an outgoing call as soon as it becomes idle while in case (ii), the duration of an outgoing call is extremely long.
In both cases, the number of incoming calls in the system explodes. However, using suitable scalings, we prove that the scaled version of the number of incoming calls in the system follow some simple distributions, i.e. Gaussian distribution [8] and Gamma distribution, respectively [9].
The remainder of the paper is presented as follows. In Sect. 2, we describe the model in detail and preliminaries for later asymptotic analysis. In Sects. 3 and 4, we present our main contribution for the model with Markov modulated Poisson process. In Sect. 5 we show the ranges of parameters under which our approximations are usable. Section 6 is devoted to concluding remark.
2 Model Description and Problem Definition
We consider a single server queueing model with two types of calls: incoming calls and outgoing calls. Incoming calls arrive at the system according to a Markov modulated Poisson process. The incoming call that finds the server idle receives a service for an exponentially distributed time with rate \(\mu _{1}\). Upon entering the system the call that finds the server being busy immediately joins the orbit, where it stays during a random time exponentially distributed with rate \(\sigma \). If the server is idle (empty) it starts making outgoing calls to the outside with rate \(\alpha \). If the outgoing call finds the server free the call goes into service for an exponentially distributed time with rate \(\mu _{2}\). If upon entering the system the outgoing call finds the server being busy the call is lost and is not considered in the future. Let i(t) denote the number of calls in the system at the time t, k(t) denote the state of the server: 0 if the server is free, 1 if the server is busy serving an incoming call, 2 if the server is busy serving an outgoing call and n(t) denote the state of the background process of the MMPP at time t. The infinitesimal generator of n(t) is defined by matrix \(\mathbf Q \). When \(n(t) = n\), the arrival rate is given by \(\lambda _{n}\) \((n=1,2,...,N)\). To determine the condition for the existence of a stationary regime, we define the matrix \({\mathbf {\Lambda }}\) in the form \({\mathbf {\Lambda }}=\frac{\rho \mu _{1}{\mathbf {\Lambda }}_{1}}{\mathbf{r}{\mathbf {\Lambda }}_{1}{} \mathbf{e}},\) where \({\mathbf {\Lambda }}_{1}\) is a diagonal matrix with nonnegative elements, and the condition for the existence of a stationary regime is the fulfillment of the inequalities \(0<\rho <1\).
Under the current setting the three-dimensional process \(\{k(t), n(t), i(t)\}\) is a Markov chain. Under the stability condition, the stationary probability distribution \(P\{k(t) = k, n(t) = n, i(t) = i\}= P_k(n, i)\) is the unique solution of Kolmogorov system of equations:
We introduce partial characteristic functions [10], denoting \( j=\sqrt{-1} \):
For \(k = 1, 2\), there will be at least one call in the system. Rewriting system (1) in the following form:
We define \(\mathbf I \) - unit matrix, \({\mathbf {\Lambda }} =diag[\lambda _{n} ]\),
Let’s write system (2) in a matrix form (3):
Let’s sum the equations of the system (3)
Multiplying the last equation by a unit vector \(\mathbf {e}\) and using \(\mathbf {Qe} = 0\), we obtain
Multiplying the last equation by a \(e^{ju}\):
We will consider the system (3) and the Eq. (4), i.e. a system of three matrix equations and one scalar equation:
The characteristic function H(u) of the number of incoming calls in the retrial queue is expressed through partial characteristic functions \(\mathbf H _k(u)\) by the following equation
We will find the characteristics of our retrial queue with two-way communication with Markov modulated Poisson input. The main content of this paper is the solution of system (5) by using an asymptotic analysis method in two limit conditions: of the high rate of making outgoing calls and the low rate of service time of outgoing calls.
3 Asymptotic Analysis of MMPP/M/1/1 Retrial Queue with Two-Way Communication Under the High Rate of Making Outgoing Calls (\(\alpha \rightarrow \infty \))
We will investigate system (5) by asymptotic analysis method under the high rate of making outgoing calls.
3.1 First Order Asymptotic
Theorem 1
Suppose i(t) is the number of calls in the system of the stationary MMPP/M/1/1 retrial queue with outgoing calls, then the (6) holds
where \(\kappa _{1}\) is the positive root of the equation
The row vector \(\mathbf r \) is the stationary probability distribution of the underlying process n(t) which is given as the unique solution of the system \(\mathbf rQ = 0\), \(\mathbf re =1\).
Proof
We denote \(\alpha = 1/\varepsilon \) in the system (5), and introduce the following notations
in order to get the following system
Considering the limit as \(\varepsilon \rightarrow 0\) in the system (8), then we will get
Our idea is to find the solution of (9) in the form of
Here \(\mathbf r _k\), \(k = 1, 2\) are vectors with components \(r_{kn}\), where \(r_{kn}\) is the probability that the server is in state k, and the MMPP is in state n; \(\mathbf r _{0}\) is a vector with components \(\mathbf r _{0n}\), and has no sense of probability, since the probability that the server will be in the zero state (will be free) as \(\alpha \rightarrow \infty \) is zero.
As the relation \(j\frac{ \varPhi ' (w)}{\varPhi (w)}\) does not depend on w, the function is obtained in the following form
which coincides with (6). The value of the parameter \(\kappa _{1}\) will be defined below. We rewrite the system (11) in the form
Let’s review the normalization condition for stationary server state probability distribution
The row vector \(\mathbf r \) is the stationary probability distribution of the underlying process n(t). Vector \(\mathbf r \) is defined as the unique solution of the system \(\mathbf rQ = 0\), \(\mathbf re = 1\). We have
We substitute the values of the vectors \(\mathbf r _{k}\), \(k = 1, 2\) into the last equation of the system (13). We obtain an equation that determines the vector \(\mathbf r _{0}\):
Now we substitute the first two equalities of the system (13) into the scalar equation of system (12). We obtain the equation that determines the value of \(\mathbf r _{0}\):
Substituting this equality into Eq. (14), we obtain an equation for \(\kappa _{1}\), which coincides with (7):
The first order asymptotic i.e. Theorem 1, only defines the mean asymptotic value \(\kappa _{1}\alpha \) of a number of calls in an system in prelimit situation of \(\alpha \rightarrow 0\). For more detailed research of the number i(t) of calls in an system let’s consider the second order asymptotic.
3.2 Second Order Asymptotic
Theorem 2
In the context of Theorem 1 the following equation is true
where parameter \(\kappa _{2}\) is given by
Here the vector of \(\mathbf r _0\) and the vectors of probabilities \(\mathbf r _1\), \(\mathbf r _2\) are defined above. The vectors \(\mathbf g _0\), \(\mathbf g _1\), \(\mathbf g _2\), \(\mathbf y _0\), \(\mathbf y _1\), \(\mathbf y _2\) are defined by the two systems:
Proof
We introduce the following notations in the system (5)
and we get
Denoting \(\alpha = 1/ \varepsilon ^{2}\), and introducing the following notations
we obtain
Our idea is to seek a solution of the system (5) in the form
Substituting (24) to (23), we obtain
Previously, the system of equations (12) was obtained. Taking this into account, we have
Dividing these equations by \(\varepsilon \) and taking the limit as \(\varepsilon \rightarrow 0\) yields
These equations imply that \(\frac{\varPhi '_{2} (w)}{w\varPhi _{2} (w)} \) doesn’t depend on w and thus the scalar function \(\varPhi _{2}(w)\) is given in the following form
which coincides with (16). We have \(\frac{\varPhi '_{2} (w)}{w\varPhi _{2} (w)} =-\kappa _{2} \) and then we obtain the system
System (25) is an inhomogeneous system of linear equations, with respect to the vectors \(\mathbf f _0\), \(\mathbf f _1\), \(\mathbf f _2\). The determinant of the matrix of the system is zero (the sums of rows are all zero). The rank of the extended matrix and the rank of the matrix of coefficients coincide . Consider systems (12) and (25). System (12) is homogeneous, system (25) is inhomogeneous. Consequently, we can write the solution of the inhomogeneous system (25) in the form \(\mathbf f _{k}=C\mathbf r _{k} +\kappa _{2} \sigma \mathbf g _{k} +\mathbf y _{k} ,\) where C is a constant, vectors \(\mathbf r _n\) are defined above, vectors \(\mathbf g _k\) and \(\mathbf y _k\) are particular solutions of the system (25) and then
Previously, the system of Eq. (12) was obtained. Taking this into account, the coefficients of C are zeros and we can rewrite the last system in the form
We consider the first three equations of the system (26). We equate the corresponding coefficients for \(\kappa _{2}\) to obtain
and
From systems (27) and (28) we obtain systems:
The determinants of the coefficient matrices systems (29) and (30) are zero. Then we define an additional condition for this systems of equations
Thus, the solutions of inhomogeneous systems for \(\mathbf g _{0}\), \(\mathbf g _{1}\), \(\mathbf g _{2}\), \(\mathbf y _{0}\), \(\mathbf y _{1}\), \(\mathbf y _{2}\) are uniquely determined. We obtain systems that coincide with the systems (18) and (19). Substituting values \(\mathbf g _{0}\), \(\mathbf g _{1}\), \(\mathbf g _{2}\), \(\mathbf y _{0}\), \(\mathbf y _{1}\), \(\mathbf y _{2}\) into the scalar equation of the system (26), we obtain
This equality coincides with (17).
Second order asymptotic i.e. Theorem 2, shows that the asymptotic probability distribution of the number i(t) of calls in a system is Gaussian with mean asymptotic \(\kappa _{1}\alpha \) and dispersion \(\kappa _{2}\alpha \).
4 Asymptotic Analysis of MMPP/M/1/1 Retrial Queue with Two-Way Communication Under the Low Rate of Service Time of Outgoing Calls (\(\mu _{2} \rightarrow 0\))
We will research system (5) by asymptotic analysis method under the low rate of service time of outgoing calls.
Theorem 3
Suppose i(t) is a number of calls in an system of stationary \(MMPP{\slash }M{\slash }1{\slash }1\) retrial queue with two-way communication, then the following equation is true
where \(\rho \mu _{1}=\mathbf r {\mathbf {\Lambda }}{} \mathbf e \) and \(\rho \) is the trafic intensity.
Proof
We denote \(\mu _{2}=\varepsilon \), let’s substitute the following in the system (5)
We will get the system
Considering the limit as \(\varepsilon \rightarrow 0\) in the system (32) then we will get
From the first and second equations we obtain \( \mathbf F _{1} (w)\mathbf Q =0,\, \, \, \,\mathbf F _{2} (w)\mathbf Q =0.\) We seek the solution of the system (33) in the form \(\mathbf F _{k} (w)=\varPhi _{k} (w)\mathbf r ,\mathrm{\; \; \; \; }k=1,2.\) Then, given the fact that \(\mathbf r {\mathbf {\Lambda }} \mathbf e =\rho \mu _{1} \) and
we have
We denote \(\varPhi _{1} (w)+\varPhi _{2} (w)=\varPhi (w)\), then \(\varPhi _{1} (w)=\rho \varPhi (w), \, \, \, \, \varPhi _{2} (w)=\left( 1-\rho \right) \varPhi (w).\) Furthermore,
Multiplying the third equation of system (32) by the unit vector \(\mathbf e \), considering the limit as \(\varepsilon \rightarrow 0\), we have
We denote
Then
We consider the first equation of system (33), multiplying it by a unit vector \(\mathbf e \) and taking into account (34), (35) and (36), we obtain
The solution of the differential equation has the form
Then
Making reverse substitutions, we obtain the characteristic function (31).
Theorem 3 shows that the asymptotic probability distribution of i(t) of calls in the system under the low rate of service time of outgoing calls is Gamma.
5 Approximation Accuracy \( P^{(2)}(i)\)
The accuracy of the approximation \( P^{(2)}(i)\) is defined by using Kolmogorov range \(\varDelta _2 =\max \limits _{0\le i\le N} \left| {\sum \limits _{v=0}^i {\left( {P(v)-P^{(2)}(v)} \right) } } \right| ,\) which represents the difference between distributions P(i) and \( P^{(2)}(i)\), where P(i) is obtained by using numerical algorithm for the MMPP/M/1/1 retrial queue and the approximation \( P^{(2)}(i)\) is given by Gaussian and Gamma approximations.
Tables 1 contains the values of \(\varDelta _2\) for various values of rate \(\rho \) and \(\alpha \) for MMPP/M/1/1 retrial queue with two-way communication. We fix \(\mu _1 = 1\), \(\mu _2 = 2\) and \(\sigma = 1\) in Table 1. Table 2 contains the values of \(\varDelta _2\) for various values of rate \(\rho \) and \(\mu _2\) for MMPP/M/1/1 retrial queue with two-way communication. We fix \(\mu _1 = 1\), \(\alpha = 1\) and \(\sigma = 1\) in Table 2. We observe in Table 1 that the approximation accuracy increases with the increase in \(\alpha \) and in Table 2 that the approximation accuracy increases with the decrease in \(\mu _2\).
6 Conclusions
In this paper, we have considered retrial queue with two-way communication with MMPP input. 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 calls in the system. Our numerical results have revealed that the accuracy of Gaussian approximation increases while increasing \(\alpha \). We have found the Gamma approximation of the number of calls in the system under the condition of the low service rate of outgoing calls. Our numerical results have revealed that the accuracy of Gamma approximation increases while decreasing \(\mu _2\). In future we plan to consider this retrial queueing system in other asymptotic conditions.
References
Bhulai, S., Koole, G.: A queueing model for call blending in call centers. IEEE Trans. Autom. Control 48, 1434–1438 (2003)
Artalejo, J.R., Phung-Duc, T.: Markovian retrial queues with two way communication. J. Ind. Manag. Optim. 8(4), 781–806 (2012)
Artalejo, J.R., Phung-Duc, T.: Single server retrial queues with two way communication. Appl. Math. Model. 37(4), 1811–1822 (2013)
Phung-Duc, T., Kawanishi, K.: An efficient method for performance analysis of blended call centers with redial. Asia Pac. J. Oper. Res. 31, 1440008 (2014). https://doi.org/10.1142/S0217595914400089
Sakurai, H., Phung-Duc, T.: Two-way communication retrial queues with multiple types of outgoing calls. First Top 23, 466–492 (2014). doi:10.1007/s11750-014-0349-5
Sakurai, H., Phung-Duc, T.: Scaling limits for single server retrial queues with two-way communication. Ann. Oper. Res. 247(1), 229–256 (2016)
Nazarov, A., Paul, S., Gudkova, I.: Asymptotic analysis of Markovian retrial queue with two-way communication under low rate of retrials condition. In: Proceedings of the 31st European Conference on Modelling and Simulation, ECMS, Budapest, pp. 687–693 (2017)
Nazarov, A.A., Terpugov, A.F.: Queueing theory - Tutorial. NTL, Tomsk (2010). (in Russian)
Nazarov, A.A., Moiseeva, S.P.: Method of asymptotic analysis in queueing theory - Tutorial. NTL, Tomsk (2006). (in Russian)
Nazarov, A., Paul, S.: A cyclic queueing system with priority customers and t-strategy of service. In: Vishnevskiy, V.M., Samouylov, K.E., Kozyrev, D.V. (eds.) DCCN 2016. CCIS, vol. 678, pp. 182–193. Springer, Cham (2016). doi:10.1007/978-3-319-51917-3_17
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Nazarov, A., Phung-Duc, T., Paul, S. (2017). Heavy Outgoing Call Asymptotics for \({MMPP{\slash }}M{\slash }1{\slash }1\) Retrial Queue with Two-Way Communication. In: Dudin, A., Nazarov, A., Kirpichnikov, A. (eds) Information Technologies and Mathematical Modelling. Queueing Theory and Applications. ITMM 2017. Communications in Computer and Information Science, vol 800. Springer, Cham. https://doi.org/10.1007/978-3-319-68069-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-68069-9_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68068-2
Online ISBN: 978-3-319-68069-9
eBook Packages: Computer ScienceComputer Science (R0)