Keywords

1 Introduction

Retrial queue [1–3] is a queuing system characterized by the following basic assumption: a customer who cannot get service goes to the orbit and, after some random period of time, returns to the system and tries to get service again. It is assumed that the orbit is infinitely large and every call repeats his attempts until he is satisfied. Retrial queueing systems are important to study computer and telephone systems, digital communication networks with random access protocols, engineering cellular mobile radio networks, computer networks and other technical systems. For a comprehensive review of retrial queues and a summary of many results and literature, the reader is directed to the works by Falin and Templeton [4], Artalejo and Gomez-Corral [5], and references therein.

In many practical situations, it is important to take into consideration the fact that the rate of generation of a primary calls degreases as the number of customers in the system increases. This can be done with the help of finite source models where each source generates its own flow of a primary customers.

Finite source retrial model can be applied for researching magnetic disk memory systems, local area networks with CSMA/CD protocols with star topology, ets. The seminal papers of this area are [6–9]. Dragieva V. in [10] considered a single server unreliable finite source retrial model in which breakdowns occur only when the server is busy and after breakdown the server is immediately sent for repair. A various types of unreliable system with finite numbers of sources are investigated by Almási B., Sztrick J., Roszik J., for example, in [11, 12]. In this works authors used the software tool MOSEL (Modeling, Specification, and Evaluation Language) to formulate the model and to calculate and display the main performance measures.

In present paper we consider the M/M/1//N retrial queue with collision. In the main model it is assumed that if an arriving customer finds the server busy, then the arriving customer collides with a customer in service and they both goes to the orbit and the server becomes idle immediately. Choi et al. [13] considered retrial queues with collision arising from the specific communication protocol CSMA/CD. In the papers Nazarov A., Lyubina T. are considered the various open retrial queuing systems with collision of customers [14, 15].

In our previous paper [16] we considered a closed retrial queueing system M/M/1//N with collision. Using method of asymptotic analysis under conditions of infinitely increasing number of sources, we obtained a distribution of the number of sources in “waiting” state.

In this paper we propose method of asymptotic analysis under conditions of infinitely increasing number of sources to research the sojourn time in finite source Markov retrial queueing system with collision.

2 Model Description

We consider a finite source retrial queuing system of type M/M/1//N in Kendals notation with collision of the customers. This mean that the system has one server and N sources. Each one of them generates a primary customers according to a Poisson flow with rate \(\lambda /N\). We assume that sources can be in two states: generating a primary customers and waiting for the end of successful service. Source which send the customer for service, moves into the “waiting” state and stays in this state till the end of the service of this customer. If a primary customer finds server idle, he enters into service immediately, during service time, which distributed exponentially with parameter \(\mu \). Otherwise, if server is busy, arriving customer involves into collision with servicing customer and they both moves into the orbit. Retrial customer repeat his demand for service with an exponential distribution with rate \(\sigma /N\). We assume that primary customers, retrial customers and service time are mutually independent.

Lets select a random customer from the system and shall call him the observed customer. Let us first consider the time between the moment, when a primary customer enters service for the first time and the time point on which this customer successfully ends his service. This time period is called the sojourn time. In the system occur of a situation of the conflict (collision of the customers) is possible, this feature is necessary to consider in the study of the sojourn time in the system. Therefore, the sojourn time consist of the total time, which customer spend on the orbit and the total time of the service. Total service time includes all period of time in which the observed customer tried to get service, but it was interrupted by arriving customer and the service time in which observed customer successfully finished his service.

At time t let i(t) be the number of sources locating in “waiting” state and k(t) determines the server state

$$\begin{aligned} k(t)=\left\{ \begin{array}{cl} 0, &{} \text{ if } \text{ the } \text{ server } \text{ is } \text{ free, } \\ 1, &{} \text{ if } \text{ the } \text{ server } \text{ is } \text{ busy } \text{(not } \text{ by } \text{ observed } \text{ customer), } \\ 2, &{} \text{ if } \text{ the } \text{ server } \text{ is } \text{ busy } \text{ by } \text{ observed } \text{ customer. } \end{array} \right. \end{aligned}$$

Introduce T(t) - the residual sojourn time of the observed customer in the system at time t.

Assuming that the observed customer locates in the orbit, lets denote by \(G_k(u,i,t)=M\{e^{juT(t)}|k(t)=k,i(t)=i\}\) the joint conditional characteristic function.

For the functions \(G_k(u,i,t)\), we can write the system of the finite-difference equation:

$$\begin{aligned} \begin{array}{ll} \displaystyle G_0(u,i,t-\varDelta t)=&{}\displaystyle \left( 1-\lambda \frac{N-i}{N}\varDelta t\right) \left( 1-\sigma \frac{i}{N}\varDelta t\right) e^{ju\varDelta t} G_0(u,i,t) \\ &{}{}+\displaystyle \lambda \frac{N-i}{N}\varDelta t G_1(u,i+1,t)+\sigma \frac{i-1}{N}\varDelta t G_1(u,i,t) \\ &{}{}+ \displaystyle \frac{\sigma }{N}\varDelta t G_2(u,i,t)+o(\varDelta t),\\ \\ \displaystyle G_1(u,i,t-\varDelta t)=&{}\displaystyle \left( 1-\lambda \frac{N-i}{N}\varDelta t\right) \left( 1-\sigma \frac{i-1}{N}\varDelta t\right) \left( 1-\mu \varDelta t\right) e^{ju\varDelta t} G_1(u,i,t)\\ &{}{}+\displaystyle \lambda \frac{N-i}{N}\varDelta t G_0(u,i+1,t)+\sigma \frac{i-1}{N}\varDelta t G_0(u,i,t)\\ &{}{}+ \mu \varDelta t G_0(u,i-1,t)+o(\varDelta t),\\ \\ \displaystyle G_2(u,i,t-\varDelta t)=&{}\displaystyle \left( 1-\lambda \frac{N-i}{N}\varDelta t\right) \left( 1-\sigma \frac{i-1}{N}\varDelta t\right) \left( 1-\mu \varDelta t\right) e^{ju\varDelta t} G_2(u,i,t)\\ &{}+\displaystyle \lambda \frac{N-i}{N}\varDelta t G_0(u,i+1,t)+\sigma \frac{i-1}{N}\varDelta t G_0(u,i,t)+ \mu \varDelta t+o(\varDelta t).\\ \end{array} \end{aligned}$$

The Kolmogorov backward differential equations are

$$\begin{aligned} \begin{array}{ll} \displaystyle -\frac{\partial {G_0(u,i,t)}}{\partial {t}}=&{}\displaystyle \left[ ju-\lambda \frac{N-i}{N}-\sigma \frac{i}{N}\right] G_0(u,i,t)+\lambda \frac{N-i}{N} G_1(u,i+1,t)\\ &{}{}+\displaystyle \sigma \frac{i-1}{N}G_1(u,i,t)+ \frac{\sigma }{N} G_2(u,i,t),\\ \displaystyle -\frac{\partial {G_1(u,i,t)}}{\partial {t}}=&{}\displaystyle \left[ ju-\lambda \frac{N-i}{N}-\sigma \frac{i-1}{N}-\mu \right] G_1(u,i,t)+\lambda \frac{N-i}{N} G_0(u,i+1,t)\\ &{}{}+\displaystyle \sigma \frac{i-1}{N}G_0(u,i,t)+ \mu G_0(u,i-1,t),\\ \displaystyle -\frac{\partial {G_2(u,i,t)}}{\partial {t}}=&{}\displaystyle \left[ ju-\lambda \frac{N-i}{N}-\sigma \frac{i-1}{N}-\mu \right] G_2(u,i,t)+\lambda \frac{N-i}{N} G_0(u,i+1,t)\\ &{}{}+\displaystyle \sigma \frac{i-1}{N}G_0(u,i,t)+ \mu .\\ \end{array} \end{aligned}$$

Note this system in steady state

(1)

In order to solve this system, we use method of asymptotic analysis [17] under conditions of infinitely increasing number of sources \((N\rightarrow \infty )\).

3 Method of Asymptotic Analysis

Let us denote \(\displaystyle \frac{1}{N}=\varepsilon \;\).

Introducing following substitute

$$\begin{aligned} i\varepsilon = x, \qquad \, \, u=\varepsilon w,\qquad \, \, G_k(u,i)=F_k(w,x,\varepsilon ), \end{aligned}$$
(2)

we can transform system (1) to the form:

(3)

Theorem 1

The limiting value \(F_0(w,x),\) \(F_1(w,x),\) \(F_2(w,x)\) of function \(F_0(w,x,\varepsilon ),\) \(F_1(w,x,\varepsilon ),\) \( F_2(w,x,\varepsilon )\)(the solutions of the system (3)), can be represented in the following form

$$\begin{aligned} \begin{array}{c} F_0(w,x)=F_1(w,x)=F(w,x)=\displaystyle \frac{d}{d-jw},\\ \\ F_2(w,x)=\displaystyle \frac{\mu +a(\kappa _1) F(w,x)}{b(\kappa _1)}, \end{array} \end{aligned}$$

where

$$\begin{aligned} \begin{array}{c} d=\displaystyle \frac{\sigma \mu }{2a(\kappa _1)+\mu },\\ \\ a(\kappa _1)=\lambda (1-\kappa _1)+\sigma \kappa _1, \\ \\ b(\kappa _1)=\lambda (1-\kappa _1)+\sigma \kappa _1+\mu , \\ \\ \kappa _1=\displaystyle \frac{2\mu R_1^2}{\sigma (1-2R_1)}, \\ \\ R_1=\displaystyle \frac{\sigma (2\lambda +\mu )-\sqrt{\sigma ^2(2\lambda -\mu )^2+8\sigma \mu \lambda ^2}}{4\mu (\sigma -\lambda )}. \end{array} \end{aligned}$$

Proof

There are two stages of proving.

Stage 1. Using the following denotation \(\lim \limits _{\varepsilon \rightarrow 0}{F_k(w,x,\varepsilon )}=F_k(w,x)\) as \(\varepsilon \rightarrow 0\), the system (3) has the form

$$\begin{aligned} \begin{array}{l} \displaystyle -\left[ \lambda \left( 1-x\right) +\sigma x\right] F_0(w,x)+\left[ \lambda \left( 1-x\right) +\sigma x\right] F_1(w,x)=0 \ ,\\ \\ \displaystyle -\left[ \lambda \left( 1-x\right) +\sigma x+\mu \right] F_1(w,x)+\left[ \lambda \left( 1-x\right) +\sigma x+\mu \right] F_0(w,x)=0 \ ,\\ \\ \displaystyle -\left[ \lambda \left( 1-x\right) +\sigma x+\mu \right] F_2(w,x)+\left[ \lambda \left( 1-x\right) +\sigma x\right] F_0(w,x)+\mu =0 \ . \end{array} \end{aligned}$$
(4)

From system (4) we obtain that the functions \(F_0(w,x)\) and \(F_1(w,x)\) is equal and function \(F_2(w,x)\) can be represented as

$$\begin{aligned} \begin{array}{c} F_0(w,x)=F_1(w,x)\mathop {=}\limits ^{.}F(w,x), \\ \\ F_2(w,x)=\displaystyle \frac{\left[ \displaystyle \lambda (1-x)+\sigma x\right] F(w,x)+\mu }{\displaystyle \lambda (1-x)+\sigma x+\mu }. \end{array} \end{aligned}$$
(5)

Stage 2. Lets consider the system (3). Using the expansion into a Taylor series of the first order of smallness about a point x, we get

(6)

Denote the solution of the system (6) as follows

$$\begin{aligned} \begin{array}{l} F_k(w,x,\varepsilon )=\displaystyle F_k(w,x)+\varepsilon f_k(w,x)+o(\varepsilon ),\ \ \ k=0,1,2. \end{array} \end{aligned}$$
(7)

Substituting (7) to the system (6) we obtain

$$\begin{aligned} \begin{array}{l} \displaystyle \varepsilon \left\{ jw F_0(w,x)-\sigma F_1(w,x)+\sigma F_2(w,x)+\lambda \left( 1-x\right) \frac{\partial {F_1(w,x)}}{\partial {x}}\right. \\ \qquad \qquad {}+\displaystyle \Big [\lambda \left( 1-x\right) +\sigma x\Big ]\cdot \Big (f_1(w,x)-f_0(w,x)\Big )\bigg \}\\ \qquad \qquad {}+\displaystyle \Big [\lambda \left( 1-x\right) +\sigma x\Big ]\Big (F_1(w,x)-F_0(w,x)\Big )=O(\varepsilon ^2) ,\\ \\ \end{array} \end{aligned}$$
$$\begin{aligned} \begin{array}{l} \displaystyle \varepsilon \bigg \{\big (jw+\sigma \big ) F_1(w,x)-\sigma F_0(w,x)+\Big [\lambda \left( 1-x\right) -\mu \Big ]\frac{\partial {F_0(w,x)}}{\partial {x}}\\ \qquad \qquad {}+\displaystyle \Big [\lambda \left( 1-x\right) +\sigma x+\mu \Big ]\cdot \Big (f_0(w,x)-f_1(w,x)\Big )\bigg \} \\ \qquad \qquad {}+\displaystyle \Big [\lambda \left( 1-x\right) +\sigma x+\mu \Big ]\Big (F_0(w,x)-F_1(w,x)\Big )=O(\varepsilon ^2) ,\\ \\ \displaystyle \varepsilon \bigg \{\big (jw+\sigma \big ) F_2(w,x)-\sigma F_0(w,x)+\lambda \left( 1-x\right) \frac{\partial {F_0(w,x)}}{\partial {x}}\\ \qquad \qquad {}+\displaystyle \Big [\lambda \left( 1-x\right) +\sigma x\Big ]\cdot \Big (f_0(w,x)-f_2(w,x)\Big )-\mu f_2(w,x)\bigg \} \\ {}+\displaystyle \Big [\lambda \left( 1-x\right) +\sigma x\Big ]F_0(w,x)-\Big [\lambda \left( 1-x\right) +\sigma x+\mu \Big ]F_2(w,x)+\mu =O(\varepsilon ^2).\\ \\ \end{array} \end{aligned}$$

Considering expressions (5) for the functions \(F_0(w,x),\ F_1(w,x)\) and \(F_2(w,x)\) the system rewrite as

(8)

Dividing each part of the equation of the system (8) and executing an asymptotic transition as \(\varepsilon \rightarrow 0\), we obtain the following system

(9)

Using the following denotation

$$\begin{aligned} \begin{array}{c} a(x)=\displaystyle \lambda (1-x)+\sigma x,\\ b(x)=\displaystyle \lambda (1-x)+\sigma x+\mu ,\\ \\ \end{array} \end{aligned}$$
(10)

lets multiply the first equation of (9) by b(x), the second equation by a(x) and add the resulting equation together:

(11)

Taking into account the entered denotation (10), expression (5) can be rewritten as

$$\begin{aligned} b(x)F_2(w,x)=\displaystyle a(x)F(w,x)+\mu . \end{aligned}$$

Substituting this expression to the Eq. (11) we obtain

(12)

In our previous paper [16] we investigated the closed M/M/1//N retrial queueing system with collision. In this article it was shown that the number of sources in “waiting” state \(i(t)\varepsilon \) asymptoticaly converge to the deterministic quantity \(\kappa _1\). Therefore, taking into account the denotation (2) \(x=i\varepsilon \), we obtain that \(x=\kappa _1\).

Putting \(x=\kappa _1\) in the Eq. (12), the multiplier before partial derivative \(\displaystyle \frac{\partial {F(w,x)}}{\partial {x}}\) becomes equal to zero and Eq. (12) can be rewritten as

$$\begin{aligned} \displaystyle \Big [\big (jw-\sigma \big )b(\kappa _1)+\big (jw+\sigma \big )a(\kappa _1)\Big ]F(w,\kappa _1)+\sigma \mu =0. \end{aligned}$$

Performing this equation and entering denotation \(d=\displaystyle \frac{\sigma \mu }{2\cdot a(\kappa _1)+\mu }\), we obtain the following expression for the function \(F(w,\kappa _1)\)

$$\begin{aligned} F(w,\kappa _1)=\displaystyle \frac{d}{d-jw} \end{aligned}$$

Note, that function \(F(w,\kappa _1)\) does not depend on argument x. Taking into account this fact and (5), we can write

$$\begin{aligned} \begin{array}{c} F(w)=\displaystyle \frac{d}{d-jw},\\ \\ F_2(w)=\displaystyle \frac{\mu }{b(\kappa _1)}+ \frac{a(\kappa _1)}{b(\kappa _1)}F(w). \end{array} \end{aligned}$$

The theorem is proved. \(\quad \square \)

We obtain the characteristic functions of the distribution of the residual sojourn time. Using the formula of total probability, we can write the following expression for the characteristic functions of the distribution of the total sojourn time:

$$\begin{aligned} \begin{array}{c} H(w)=\displaystyle R_0 F_2(w)+(1-R_0)F(w)= \displaystyle \frac{\mu }{b(\kappa _1)}R_0 + \Big (1-\frac{\mu }{b(\kappa _1)}R_0\Big )\frac{d}{d-jw}, \end{array} \end{aligned}$$
(13)

where \(R_0\) was previously obtained in [16].

Lets perform the inverse substitutions (2) in the formula (13):

$$\begin{aligned} H(u)\approx \displaystyle \frac{\mu }{b(\kappa _1)}R_0 + \Big (1-\frac{\mu }{b(\kappa _1)}R_0\Big )\frac{d/N}{d/N-ju}. \end{aligned}$$

Using denotation \(q=\displaystyle \frac{\mu }{b(\kappa _1)}R_0\), we can write the following expression for the approximation h(u) of the characteristic function H(u):

$$\begin{aligned} h(u)=\displaystyle q + \Big (1-q\Big )\frac{d/N}{d/N-ju}. \end{aligned}$$

Knowing h(u), it is easy to show that the approximation of distribution of the total sojourn time can be written as

$$\begin{aligned} A(x)=\displaystyle 1-(1-q)\displaystyle e^{-\frac{d}{N}x}. \end{aligned}$$

4 Conclusion

In this paper, we have considered a finite source retrial queuing system M/M/1//N with collision of the customers. We obtain the equations for conditional characteristic function of the distribution of the residual sojourn time. This equation was solved under an asymptotic condition of infinitely increasing number of sources. As the result, we obtain the approximation of the distribution of the total sojourn time in the system.