Keywords

1 Introduction

Nowadays queuing systems are used in various spheres. They are used in service sector, everyday life, economics, commerce, different organizations and enterprises. This mathematical approach is widely used in telecommunication systems and networks also [1, 2]. Today there are a lot of various types of queuing systems. One of the important class of queuing systems is multi-channel queuing system with a finite buffer which is known as M/M/n/m systems. The systems with several servicing devices are used for describing distributed computer networks with several servers or multi-channel switching systems [1, 2]. Various types of multi-channel queuing systems have been considered in many domestic and foreign scientific works [1,2,3,4,5,6]. And in the most of them M/M/n/m systems are investigated in stationary mode. In paper [3] multi-server Feedback Markovian queuing model with encouraged arrivals, customer impatience, and retention of impatient customers have been performed. The authors presented expressions for steady-state probabilities and performance metrics calculating which had been derived using classical queuing theory approach. The M/M/N/N queue where two types of users compete for the N resources has been considered in paper [4]. The authors have presented the two-dimensional queue model for this case and calculated steady-state probabilities of the system. In paper [5] the authors have analyzed a multi-server queue with customers’ impatience and Bernoulli feedback under a variant of multiple vacations. They have investigated the mathematical model of the system and have developed the differential equations for the probability generating functions of the steady-state probabilities. A multi-server queuing system with reverse balking and impatient customers has been considered in [6]. The steady-state probabilities of system size are obtained using iterative method.

The most accurate analysis of multi-channel queuing system functioning can be obtained if the system is to be examined not only in stationary mode but in transient one too. The stationary mode occurs some time later after beginning system functioning and continue for \(t \rightarrow \infty \). In contrast to the stationary mode the transient mode occurs right after beginning of the system functioning before the system will be in the steady state [7, 8]. The system goes in the transient mode in result of rebooting or jumps of arrival and service rates caused by change in the information routes. There are only several works where two-channel queuing systems transient behavior has been described. In [9] authors have studied M/M/2/N queuing system with two-heterogeneous servers and retention of reneging customers and obtained its transient solution by employing matrix method. Transient analysis of two-heterogeneous servers queue with impatient behavior has been carried out in [10]. Additionally the steady-state probabilities of the system size are studied. The paper [11] presents an expression for finding the transient probabilities of system states with an infinite number of servers.

In all listed above works the transient behaviour of queuing systems is considered for the case of constant arrival and serviced rates. Nevertheless, the problem of studying the behavior of a queuing system in the case of arrival or service rates are piecewise-constant functions is very important in a number of telecommunication applications. For example, arrival rate is changed abruptly when control signals with a payload are transmitted to the tethered UAV through determinate time intervals [12]. In [13] time-varying rate multi-channel queueing systems \(M_t/G/L/L\) and \(M_t/M/L/L\) describing telecommunication system intended for transmission of realtime communication services like voice calls and video on demand are investigating. The dependencies of loss probability for the case of change in the arrival rate according to a sinusoidal law are obtained. The other performance metrics are not studied.

The authors of this paper proposed the analytical approach of M/M/1/n and MAP/M/1/n queuing systems transient behavior investigation for cases of constant and piecewise-constant arrival and service rates on based of method of translation matrix [7, 8, 13]. In this paper we continue to developed our approach considering multi-channel queuing system M|M|n|m with jumps in the arrival and service rates and investigating dependencies of system states transient probabilities in different initial conditions.

The paper is organized as follows. In Sect. 2 the statement of the problem is given. Section 3 presents the analytical approach of multi-channel queuing system investigation for cases of constant and piecewise-constant arrival or service rates in transient mode. Numerical simulation results are presented in Sect. 4. The paper is concluded in Sect. 5.

2 Statement of the Problem

Let us consider the system for transmitting information from a ground control station to a tethered UAV. The payload and control signals are transmitted over n wireless Wi-Fi channels with the same bandwidth. If all channels are busy, the information is stored in a buffer of the size m. So the considered telecommunication system can be described by a M/M/n/m queuing system.

The state graph of the M/M/n/m system is presented in the Fig. 1. The first state \(S_0\) corresponds to the state when the system is empty. The second state \(S_1\) corresponds to the state when the first channel is busy but the buffer is empty. The third state \(S_2\) corresponds to the state when two channels are busy but the buffer is empty. The n state \(S_n\) corresponds to the state when n channels are busy but the buffer is empty. The state \(B_1\) corresponds to the state when all n channels are busy and one packet is in the buffer. The m state \(B_m\) corresponds to the state when all n channels are busy, m packets are in the buffer and the next arriving packet is lost. Here we consider the case when \(\lambda (t)\) or \(\mu (t)\) (the arrival or service rates correspondingly) are the piecewise-constant functions (Fig. 2).

Fig. 1.
figure 1

The state graph of the M/M/n/m system.

Full size image
Fig. 2.
figure 2

The arrival and service rates time dependence graphs.

Full size image

The Kolmogorov differential equations system for the multi-channel queuing system within the interval with constant parameters \(\lambda \) and \(\mu \) has the form

$$\begin{aligned} \left\{ \begin{array}{lc} \displaystyle \frac{dP_0(t)}{dt}=-\lambda P_0(t) + \mu P_1(t)\\ \displaystyle \frac{dP_i(t)}{dt}=\lambda P_{i-1}(t)-(\lambda +i\mu )P_i(t)+(i+1)\mu P_{i+1}(t), &{} 1\le i \le n-1\\ \displaystyle \frac{dP_i(t)}{dt}=\lambda P_{i-1}(t)-(\lambda +n\mu )P_i(t)+n\mu P_{i+1}(t), &{} n\le i \le n+m-1\\ \displaystyle \frac{dP_{n+m}(t)}{dt}=\lambda P_{n+m-1}(t)-n\mu P_{n+m}(t)\\ \end{array} \right. \end{aligned}$$
(1)

Here \(P_i(t)\) is the probability that the system is in i state at the time t. \(P_0(t)\) is the probability that the system is empty, \(P_{n+m}\) is the probability of loss.

The main aim of this paper is investigation of the multi-channel queuing system transient behavior for cases of constant and piecewise-constant information flow parameters. It is the problem to obtain the analytic expressions for main transient performance metrics of this system such as transient time, throughput, an average number of packets in the system, an average queuing delay, and probability of packet loss. The novel aspects of queueing systems transient behavior study considered in this paper is investigation probabilities of states and main performance metrics for different initial conditions.

3 Transient Behavior of Multi-channel Queuing System with Constant and Piecewise-Constant Rates

To analyze of the multi-channel queuing system M/M/n/m functioning in transient mode, the new approach based on the translation matrix method analogous to [7, 8, 14] is applied. According to this method the solutions of the system (1) are found as

$$\begin{aligned} P_i(t)=\sum _{j=0}^{n+m}m_{ij}P_{j}(0), \end{aligned}$$
(2)

where \(m_{ij}\) are elements of the translation matrix [7], which can be found using following expression (\(i=0..n+m\)):

$$\begin{aligned} m_{ij}=\sum _{j=0}^{n+m}\xi _{ij}A_j\exp ^{\gamma _{j} t}, \end{aligned}$$
(3)

where \(A_j\) are the integration constants determined by initial conditions, \(\gamma _j\) are the roots of the characteristic equation of the system (1), and \(\xi _{ij}\) are coefficients expressing probabilities \(P_i(t)\) as functions of \(P_0(t)\) \((i=\overline{1,n+m} )\).

Thus the probabilities of the states and the performance metrics of the multi-channel queueing system for time-constant parameters \(\lambda \) and \(\mu \) can be calculated by the expression (2). To determine analogous parameters of the system in case of piecewise-constant rates it is proposed to use the method of translation matrix [7, 8].

Now, the translation matrix describing the behavior of the system with piecewise-constant parameters on the K-th interval (Fig. 2) can be write in the form [7, 8]

$$\begin{aligned} {\textbf {M}}_K (t) ={\textbf {M}}_{K}(t-t_{K-1})\prod _{i=K-1}^1{\textbf {M}}_i(\varDelta t_i) \end{aligned}$$
(4)

The matrix (4) relates the probabilities of states on the K-th interval to the probabilities of states in the initial time \(t_0\):

$$\begin{aligned} {\textbf {U}}(t)=\left( {\textbf {M}}_{K}(t-t_{K-1})\prod _{i=K-1}^1{\textbf {M}}_i(\varDelta t_i) \right) {\textbf {U}}(t_0). \end{aligned}$$
(5)

Here \({\textbf {U}}(t)=(P_i)^T\) (\(i=\overline{0,n+m}\)) is the \(1\times (n+m+1)\)-vector of the system states, T is the transpose operator.

The performance metrics of M/M/n/m system can be found by using (2) and (4). According to the [7] the so-called transient instantaneous throughput is calculated as

$$\begin{aligned} A(t) = [1-P_{n+m}(t)]\lambda (t), \end{aligned}$$
(6)

Here \(P_{n+m}(t)\) is the instantaneous probability of loss:

$$\begin{aligned} P_{loss}(t) = \sum _{j=0}^{n+m}P_j(0)\sum _{j=0}^{n+m}\xi _{n+m,j}A_jexp(\gamma _jt) \end{aligned}$$
(7)

An average number of packets in the system E(m(t)) and an average number of busy channels E(n(t)) can be determine using following formulae:

$$\begin{aligned} E(m(t)) = \sum _{i=1}^{n+m} i P_i(t) \end{aligned}$$
(8)
$$\begin{aligned} E(n(t)) = \sum _{i=1}^n i P_i(t) \end{aligned}$$
(9)

Therefore an average number of packets in the buffer can be calculated using expression:

$$\begin{aligned} E(N(t)) = \sum _{i=1}^{n+m} i P_i(t)-\sum _{i=1}^n i P_i(t) \end{aligned}$$
(10)

Given (2) and (3), the final expressions for an average number of packets in the system and an average number of busy channels can be written as follows

$$\begin{aligned} E(m(t)) = \sum _{i=1}^{n+m} i \sum _{j=0}^{n+m} P_j(0) \sum _{j=0}^{n+m} \xi _{ij}A_{j}exp^{\gamma _j t} \end{aligned}$$
(11)
$$\begin{aligned} E(n(t)) = \sum _{i=1}^n i \sum _{j=0}^{n+m} P_j(0) \sum _{j=0}^{n+m} \xi _{ij}A_{j}exp^{\gamma _j t} \end{aligned}$$
(12)

According to the [1] an average waiting time in a buffer (queuing delay) can be given as:

$$\begin{aligned} W(t) = E(N(t))/\lambda (t) \end{aligned}$$
(13)

The other important characteristic of transient mode is transient time \(\tau _{tr}\). The detail theory of the transient time determination is presented in [7, 8]. Here we use that method to the considered problem and obtain:

$$\begin{aligned} \tau _{tr}=(3\div 5)\tau \end{aligned}$$
(14)

where \(\tau \) is the time constant:

$$\begin{aligned} \tau =\max \lbrace \tau _i,i=\overline{0,n+m}\rbrace = \displaystyle \max \lbrace \frac{1}{\mid \gamma _i\mid },i=\overline{0,n+m}\rbrace \end{aligned}$$
(15)

4 Numerical Results

In this section, we consider the M/M/2/3 system describing a wireless access point functioning installed on a tethered UAV and connected with a ground control station through two Wi-Fi channels. The size of wireless access point buffer is three packets.

At first, let us consider the case when the parameters of the information flow are constant (\(\lambda =200\) pps, \(\mu =300\) pps) and investigate the transient behavior of the system under different initial conditions. In Fig. 3, Fig. 4 and Fig. 5 we presented the dependencies of transient states probabilities for following initial conditions:

  1. 1.

    \([P_0(0), P_1(0), P_2(0), P_3(0), P_4(0), P_5(0)]^T\) = \((1,0,0,0,0,0)^T\).

  2. 2.

    \([P_0(0), P_1(0), P_2(0), P_3(0), P_4(0), P_5(0)]^T = (0,1,0,0,0,0)^T\).

  3. 3.

    \([P_0(0), P_1(0), P_2(0), P_3(0), P_4(0), P_5(0)]^T = (0,0,0,0,1,0)^T\).

The first case corresponds to a free state of both channels (Fig. 3), the second case corresponds to a working state only of the first channel (Fig. 4) and the third case corresponds to the state when both channels suddenly became unavailable but two packets remained in the buffer (Fig. 5). Figure 3 – Fig. 5 show that transient probabilities are differ for three cases, and the steady-state probabilities of the system states do not depend on the initial conditions: \(\pi _0=0.501\), \(\pi _1=0.334\), \(\pi _2=0.112\), \(\pi _3=0.037\), \(\pi _4=0.012\), \(\pi _5=0.004\). These values coincide with the values calculated by the well-known formula for steady-state probabilities applied to the M/M/2/3 system [1]:

$$\begin{aligned} \pi _i= \left\{ \begin{array}{lc} \displaystyle \frac{\rho ^i}{i!}\pi _0, 0\le i\le n-1\\ \displaystyle \frac{\rho ^i}{n!n^{i-n}}\pi _0, n\le i\le n+m\\ \end{array} \right. \end{aligned}$$
(16)

Here \(\displaystyle \pi _0=\left[ \sum _{i=0}^{n-1}\frac{\rho ^i}{i!}+\frac{\rho ^n}{n!}\frac{(1-(\frac{\rho }{n})^{m+1})}{1-\frac{\rho }{n}}\right] ^{-1}\) is the empty state of the system and \(\rho =\lambda /\mu \) is the system load factor.

Fig. 3.
figure 3

Dependencies of the state probabilities on time for the first initial conditions.

Full size image
Fig. 4.
figure 4

Dependencies of the state probabilities on time for the second initial conditions.

Full size image
Fig. 5.
figure 5

Dependencies of the state probabilities on time for the third initial conditions.

Full size image

It can be conclusion from Fig. 3 – Fig. 5 that there are differences between the speeds of establishing the transient mode for different initial conditions, but the transient time is the same \(\tau _{tr}=0.02\)s. However, when calculating specific cases by using the classical theory, their own peculiarities may arise. Indeed, as it has been shown in [7] from a physical point of view the transient mode can be considered as finite if \(\mid P_j(t) - \pi _j\mid \le \varepsilon \), where \(\varepsilon \) is some infinitesimal value, \(P_j(t)\) is the transient probability of the j-th state at the time t, \(\pi _j\) is the stationary probability of the j- th state. Let determined the first state probability \(P_1(t)\) at the time \(t=0.01\) s supposed that \(\varepsilon \) is constant for all cases. For the first case (Fig. 3) \(P_{1}(0.01) = 0.335\) therefore \(\mid P_{1}(t) - \pi _1\mid = 0.001\); for the second case (Fig. 4) \(P_{1}(0.01)=0.34\) therefore \(\mid P_{1}(t) - \pi _1\mid = 0.006\); for the third case (Fig. 5) \(P_{1}(0.01)=0.325\) therefore \(\mid P_{1}(t) - \pi _1\mid = 0.009\). If suppose that \(\varepsilon =0.001\) we can prove that the transient mode is finished for the first initial conditions and has not been finished yet for the second and third initial conditions. In general case the choice of \(\varepsilon \) value is determined by the practical requirements.

As it can be seen from Fig. 6 the throughput of the system in transient mode depends on the initial conditions and in stationary mode \(A=199\) pps. Here \(A_1(t)\), \(A_2(t)\), \(A_3(t)\) are values of throughput corresponding to the first, the second and the third cases of the initial conditions considered above and for the parameters of an information flow: \(\lambda =200\) pps, \(\mu =300\) pps. The Fig. 6 shows that a sudden unavailability of both channels leads to the most significant decrease of the system throughput. In the point of time \(t= 0.0018\) s the system throughput has a minimum value \(A_3(0.018)=176.8\) pps. It corresponds throughput decreasing of \(11.6\%\) in comparison of initial moment of time and \(11.2\%\) in comparison of stationary mode.

The dependencies of an average number of packets in the system on time for different initial conditions described below are presented in Fig. 7. The value of steady-state probabilities is equal to 0.74 and coincides with the value obtained using existing approaches [1, 9]:

$$\begin{aligned} \displaystyle L = \sum _{i=1}^{n+m} i\pi _i . \end{aligned}$$
(17)
Fig. 6.
figure 6

Dependencies of throughput on time taking into account different initial conditions.

Full size image
Fig. 7.
figure 7

An number of packets in the system size in transient mode.

Full size image

Next, consider the case of piecewise-constant information flow for periodic jumps of arrival rate \(\lambda \) and find the transient probabilities of states (Fig. 8, Fig. 9). In practical point of view, it corresponds of periodic transmitting control signals parallel of payload transmitting. In the first case jumps of \(\lambda \) occur when the network is working normally (\(\lambda <\mu \)) (Fig. 8). The arrival rate is changed periodically from \(\lambda _0=200\) pps to \(\lambda _1=250\) pps, the service rate is constant \(\mu _0\) = \(\mu _1=300\) pps. In the second case jumps of \(\lambda \) occur when the network is overloaded (\(\lambda >\mu \)) (Fig. 9). Arrival rate is changed periodically from \(\lambda _0=400\) pps to \(\lambda _1=450\) pps, the service rate is constant \(\mu _0 = \mu _1=300\) pps. Comparing the probabilities of states in Fig. 8 and Fig. 9 it can be conclude that the changing of state probabilities in the second case (Fig. 9) has smoother character. The maximum value of loss probability is 0.001 (\(p_{loss1} = 0.001\)) in the first case and it is in 55 times more in the second case (\(p_{loss2} = 0.055\)).

Dependencies of the average waiting time for a packet in the buffer on time (queuing delay) for cases of periodic piecewise-constant arrival rate are presented in Fig. 10. Here \(W_1(t)\) is the average queuing delay for the case of \(\lambda <\mu \) (\(\lambda \) is changed periodically from \(\lambda _0=200\) pps to \(\lambda _1=250\) pps, \(\mu _0\) = \(\mu _1=300\) pps), and \(W_2(t)\) is the average queuing delay for the second case of \(\lambda >\mu \) (\(\lambda _0=400\) pps, \(\lambda _1=450\) pps, \(\mu _0\) = \(\mu _1=300\) pps). Analysing the obtained results it can be conclude that the difference between maximum and minimum values of the average queuing delay \(\mod W_{1max}(t)-W_{1min}(t)\) = \(800\,\upmu s\) in the first case, and \(\mod W_{2max}(t)-W_{2min}(t)\) = \(950\,\upmu s\) in the second case.

Fig. 8.
figure 8

Dependencies of the state probabilities on time \((\lambda <\mu )\).

Full size image
Fig. 9.
figure 9

Dependencies of the state probabilities on time \((\lambda >\mu )\).

Full size image
Fig. 10.
figure 10

An average waiting time for a packet in the buffer on time.

Full size image

5 Conclusion

The transient behavior of the multi-channel queuing system M/M/n/m for cases of constant and piecewise-constant rates has been studied for the first time. The analysis has been carried out by the accurate analytical method based on the so-called translation matrix. The method made it possible to study the change in the probabilities of the multi-channel queuing system states, throughput and an average number of packets in the system in transient mode depending on the initial conditions. The numerical simulation of M/M/2/3 system confirmed the analytical results. The correctness of the proposed approach also confirmed by the coincidence of the obtained steady-state probabilities and performance metrics with the results have been obtained by well-known methods [1, 9]. The case of periodic jumps of an arrival rate is investigated numerically for different ratios of arrival and service rates. The proposed approach can be used for performance metrics calculation of multi-channel wireless telecommunication system designed to transmit payload and control signals from a ground station to a tethered UAV.