The Analytical Method of Transient Behavior of the M|M|1|n Queuing System for Piece-Wise Constant Information Flows

Abstract

The analytical method for studying the behavior of queuing system with abruptly changing information flows is presented in this paper for the first time. The proposed method is based on the conception of fundamental matrix of the Kolmogorov system and allows studying the transient and stationary modes of functioning different types of queuing system. The transient behavior of the M|M|1|n system with constant flows and piecewise constant arrival and service rates of flows are considered. It is obtained the analytical expressions for the state probabilities of the queuing system as in transient and in stationary mode. The conception of transient time for the queuing system has been introduced and the formulas for calculation of such transient performance metrics as throughput, a number of received and processed packets have been obtained for the first time.

The reported study was funded by RFBR, project number 19-29-06043.

1 Introduction

The queuing theory is widely-used for modeling of processes in telecommunication networks [1,2,3,4,5]. Now various classes of queuing systems including different types of single- and multi-channel systems as well as single- and multi-phase systems have been investigated in sufficient detail [1,2,3,4,5]. As a rule calculations of basic characteristics of queuing systems, such as blocking probability, the size of buffer and others are carried out in a steady-state mode, when $t \rightarrow \infty$. This mode occurs some time after the system starts functioning. And the mode from the beginning of system functioning before transition it in stationary mode when its behavior depends on time is called as the transient mode [6,7,8,9,10,11,12,13,14,15,16]. In addition, the system turns out to be in a transitional mode also when its normal functioning is disrupted. Note that, although the stationary mode is used to analyze most queuing systems, in some cases it is not describing behaviour of one’s adequately. Such situations often arise in the network when arrival rate of packets rises or the service rate decreases sharply. For example, “broadcast storm” when traffic intensity increases sharply is a fairly common situation in computer networks. Analogously subscriber load in telephone networks increases when emergence situation occurs. Also service rate decreases sharply in a moment when a system starts to reboot. For the above-described cases analyzing transient behavior of queuing network allows us not only to predict operation of telecommunication equipment but also to identify critical situations that can completely disable the network. Transient modes have been considered quite deeply in radio engineering, electrodynamics, optics, etc. The transient behavior of the queuing system M|M|1 has been considered by Prabhu [7] in 1965 and Cohen [6] in 1982 years for the first time. Harrison was the first who pays attention to the study of the transient behavior of a computer network [8]. The author has considered the non-steady-state mode of a closed homogeneous queuing network and he has developed a convergent iterative method for the solution of the Kolmogorov forward equations for Gordon-Newell type queuing networks. The transient mode of queuing networks has been considered in a number of other works [9,10,11,12,13,14,15,16]. For example in [10] the author investigated the transient behavior of M|M|n system that is used to describe the call centre. The author has proposed the approximate analytical method for solving the system of homogeneous Kolmogorov equations. In [11] the authors have presented the method for analyzing the transient state of the queuing system M|M|1 and the approximate calculation of the state probabilities. Their approach is based on the representation of the system in the form of an inhomogeneous Markov chain with continuous time and the number of the states much less than the ones of original system. In this paper the authors used approximate analytical method for solving Kolmogorov equation system describing the considered queuing system. The transient mode of a single-server queuing system with a finite buffer and correlated input flows has been considered in [12]. But the authors present only approximate numerical solution of corresponding different equations by the Runge-Kutta method. Despite the transient mode of queuing systems has been considered in a number of the scientific works [6,7,8,9,10,11,12,13,14,15,16,17], its analysis has been carried out by using numerical methods of solving Kolmogorov equations only. These are, for example, the Runge-Kutta method [12, 17], boundary value methods [17] and others. All of them have a number of disadvantages. First of all, they are approximate, the accuracy of calculations caring out by these methods is not always controlled, numerical methods are very problematic to use when solving so-called inverse problems also. Besides the dependence of the system states on time for real values of arrival and service rates and the special cases when the arrival rate exceeds the service rate practically have not been considered early. Moreover, the case of time-dependent incoming flows has hardly been studied. In particular, an abrupt change in arrival rate is analytically investigated in the presented work for the first time. In this paper, the accurate analytical method for the analysis of transient behavior of queuing systems is proposed for the first time. The method is based on concept of the fundamental matrix of the Kolmogorov equation system. The transient mode when the system is turned on is considered (Sect. 3). Here analytical expressions for the probabilities of system states as functions of time are presented and expressions that determine the time of the transient mode are received. Throughput of the system, the number of packets received and processed during the transient mode are calculated also. The mathematical model of queuing system for the case of a jump-like change in arrival and service rates at an arbitrary time instant by an arbitrary value is presented in Sect. 4. The fundamental matrix of Kolmogorov equations for this case is written in analytical form in elementary functions. A rigorous proof that this matrix correctly describes the behaviour of the system is given. Numerical calculations in accordance with the constructed models are presented in Sect. 5. The calculation results for the limiting cases fully correspond to the previously obtained analytical and numerical results.

2 The Statement of the problem

In this work, the transient behavior of a single-channel queuing system with finite buffers M|M|1|n is considered. Identical requests arrive according to a time-homogeneous Poisson process at rate $\lambda$, and the service time of a request is exponentially distributed at rate $\mu$. A request from the incoming stream waits for the start of service in a buffer if the channel is busy and the buffer is free. If all n waiting places are occupied, then the next request lost. The state transition diagram of such a process is shown in Fig. 1. Here $S_0$ is the state when the service channel and the buffer are empty, $S_1$ is the state when the service channel is busy and the buffer is empty, $S_2$ is the service channel is busy and there is one request (one packet) in the buffer, $S_{n+1}$ is the service channel is busy and there are n requests in the buffer (n packages). As you can see, the process is the birth-and-death process, where $\lambda _i=\lambda$, $0\le i \le n$, $\mu _i=\mu$, $1\le i \le n+1$. The number of requests in the system and the number of states of the process describing its operation can take values on the set $\{\ 0,1,...,n+1\}\$, $n\in Z$.

Fig. 1.

The state transition diagram.

The main aim of this work is studying both the transient and steady-state modes of the system. First of all, the transient time, throughput and the probability of packet loss in the transient mode are investigated. In addition, the influence of jumps of arrival and service rates on the characteristics of the system is investigated in the paper also. In this case, the jumps of $\lambda (t)$ and $\mu (t)$ can occur at some fixed times, and the arrival and service rates are unchanged between the jumps. Thus in the case under consideration, $\lambda (t)$ and $\mu (t)$ are described by the expressions

$$\begin{aligned} \begin{array}{ll} \lambda (t)= \left\{ \begin{array}{lcl} \lambda _1,t_0 \le t \le t_1\\ \lambda _2,t_1 \le t \le t_2\\ ...............\\ \lambda _K,t_{K-1} \le t \le t_K\\ \end{array} \right. ; &{} \mu (t)= \left\{ \begin{array}{lcl} \mu _1,t_0 \le t \le t_1\\ \mu _2,t_1 \le t \le t_2\\ ...............\\ \mu _K,t_{K-1} \le t \le t_K\\ \end{array} \right. \end{array} \end{aligned}$$

(1)

where on intervals with constant $\lambda _i$ and $\mu _i$, incoming Poisson flows and an exponential distribution of service time are assumed. Here to study such systems, the method of the fundamental matrix of Kolmogorov equations is proposed for both the case of constant and jump-like rates of arrival and service of claims.

The system of differential equations for a single-channel queuing system with finite buffers obtained by using $\varDelta t -$method can be written in the form

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

(2)

Here $P_i (t)$ is the probability of the i-th state at time t (the probability of i packets are in the buffer). The analytical solution [16] of the system (1) is following

$$\begin{aligned} P_i(t)=\sum _{j=1}^{n+1}P_{ij}(t)=\sum _{j=1}^{n+1}\xi _{ij}A_i\exp ({\gamma _j t)} \end{aligned}$$

(3)

for an arbitrary finite number n of the equations in (1). Here $\gamma _j$ are the roots of the characteristic equation of system (1), $A_i$ are the integration constants determined by the initial conditions, $\xi _{ij}$ are the coefficients expressing the probabilities $P_i(i\ne 0)$ in terms of $P_0$. The probabilities $P_{ij}$ in (3) can be expressed in terms of the probability $P_{0j}$ by using the relations

$$\begin{aligned} P_{ij}(t)=-\frac{1}{b_{i-1,i}^{(j)}} \left( b_{i-1,i-2}^{(j)}P_{i-2,j}(t)+b_{i-1,i-1}^{(j)}P_{i-1,j}(t)\right) =\xi _{ij}P_{oj}(t) \end{aligned}$$

(4)

where $b_{kl}^{(j)}$ are elements of the matrix

$$\begin{aligned} \mathbf{B} ^{(j)}=\mathbf{A} -\mathbf{I} \gamma _{j} \end{aligned}$$

(5)

where $\mathbf{A}$ is the coefficient matrix of system (1), $\mathbf{I}$ is the unit matrix. The index j in (2) and (3) corresponds to the index j of the eigenvalue of (4).

3 Transient Behavior of the System M|M|1|n with Constant Flows

A fundamental matrix $\mathbf{M}$ of a linear differential equation system of the order $n+1$ (1) is a matrix of the $n+1$-th rank and it relates the probabilities of the system states at an arbitrary time t to these probabilities at the initial time moment $t_0$:

$$\begin{aligned} \mathbf{U} (t)=\mathbf{M} _{n+2\times n+2}(t)\mathbf{U} (t_0) \end{aligned}$$

(6)

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

In accordance to the definition of a fundamental matrix [18,19,20], the elements of the $\mathbf{M} _{n+2\times n+2}(t)$ for a queuing system M|M|1|n are

$$\begin{aligned} m_{kl}=\sum _{q=0}^{n+1} (-1)^{k+q} \xi _{lq}\frac{\varDelta _{kq}}{\varDelta }\exp (\gamma _q t) \end{aligned}$$

(7)

where

$$\begin{aligned} \varDelta =\left( \begin{array}{cccccc} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1\\ \xi _{21}&{} \xi _{22}&{} \xi _{23} &{}\xi _{24} &{} ... &{}\xi _{2,n+2}\\ \xi _{31}&{} \xi _{32}&{} \xi _{33} &{}\xi _{34} &{} ... &{}\xi _{3,n+2}\\ \xi _{41}&{} \xi _{42}&{} \xi _{43}&{}\xi _{44}&{} ... &{}\xi _{4,n+2}\\ ...&{} ...&{}...&{}...&{} ...&{}...\\ \xi _{n+2,1}&{} \xi _{n+2,2} &{} \xi _{n+2,3}&{}\xi _{n+2,4}&{}... &{}\xi _{n+2,n+2}\\ \end{array} \right) \end{aligned}$$

(8)

$\varDelta _{kq}$ is the minor element of matrix $\varDelta$ with indices kq.

Thus, here, for the first time, an exact analytical expression for the fundamental matrix of system (1) with constant flux intensities was found, which makes it possible to fully describe the behavior of the system, both in transient and stationary modes.

In the limiting case, as $t \rightarrow \infty$, the obtained expressions (5)–(7) are reduced to the well-known formulas [1,2,3,4,5]. Indeed, one of the roots $\gamma _0$ of the characteristic equation of system (1) is always zero, and the rest $\gamma _i$, $i=\overline{1,n+1}$, are negative. Then, for all roots except $\gamma _0$, as $t \rightarrow \infty$, we have $exp(\gamma _q t)\rightarrow 0$.

$$\begin{aligned} P_i(t)=\sum _{j=0}^{n+1}m_{ij}P_i(t_0)=\sum _{j=0}^{n+1}(-1)^i\xi _{j0}\frac{\varDelta _{io}}{\varDelta }P_i(t_0) \end{aligned}$$

(9)

Obviously, at the moment of turning on the system the buffer is free. Therefore, the initial conditions are $P_0(t_0)=1,P_i(t_0)=0$, $i=\overline{1,n+1}$. Then, after algebraic transformations (8) it is reduced to the form

$$\begin{aligned} P_i(t\rightarrow \infty )=\frac{\lambda ^i}{(n+1)\mu ^i} \end{aligned}$$

(10)

Another important problem of transient mode investigation is determination of transient time. The proposed method allows to calculate the throughput of the system and the probability of packet loss in this mode also. It follows from (2) and (6) that the state probability is described by the sum of n decreasing exponential functions $(\exp (\gamma _qt),\gamma _q<0,i=\overline{1,n+1})$ and a constant term, since one of the roots of the characteristic equation $\gamma _0$ is equal to zero. As a result, over time, the probabilities of the states tend to the values determined by (9). To describe the rate of this process, we introduce the concept of the time constant of the system’s transient mode as the maximum time for which the probability of a state changes by e times. So the probability changes from $\exp (\gamma _it_0)=1$ if $t_0=0$ to $\exp [\gamma _i (t_0+\tau _i )]=e^{-1}$ if $\tau _i=1/\mid \gamma _i\mid ,i=\overline{1,n+1}$.

$$\begin{aligned} \tau =max\lbrace \tau _i,i=\overline{1,n+1}\rbrace =\max \lbrace \frac{1}{\mid \gamma _i\mid },i=\overline{1,n+1}\rbrace \end{aligned}$$

(11)

In next numerical calculations, it will be shown that the transient mode is almost completely ends and the system goes over to the steady-state mode if

$$\begin{aligned} \tau _{tr}=(3\div 5)\tau =(3\div 5)\max (\tau _i,i=\overline{1,n+1}) \end{aligned}$$

(12)

The transient instantaneous throughput is calculated as

$$\begin{aligned} A(t)=\left( 1-P_{n+1}\left( t\right) \right) \lambda \end{aligned}$$

(13)

where $P_{n+1}(t)$ is the instantaneous probability of loss which is calculated using (6) and (7). The number of arrive $N_a$ and served $N_s$ packets during the transient mode are

$$\begin{aligned} N_a=\lambda \tau _{tr} \end{aligned}$$

(14)

$$\begin{aligned} N_s=\mu \tau _{tr} \end{aligned}$$

(15)

Thus, in this section, a mathematical model of the M|M|1|n system with constant arrival and service rates is proposed. This model describes the behaviour of the system in both transient and steady-state modes.

4 Transient Behavior of the M|M|1|n Queue with Piecewise Constant Arrival and Service Rates of the Flows

First of all, let us show that the resulting matrix of a system with piecewise constant parameters is equal to the multiplication of the matrices of intervals with constant parameters. Indeed, let the process be described by a fundamental matrix on the first interval with constant transition probabilities. Then, on this interval, the states of the system at an arbitrary moment of time are found as

$$\begin{aligned} \mathbf{U} (t)=\mathbf{M} _{1}(t-t_0)\mathbf{U} (t_0) \end{aligned}$$

(16)

And for $t=t_1$ we have

$$\begin{aligned} \mathbf{U} (t_1)=\mathbf{M} _{1}(\varDelta t_1)\mathbf{U} (t_0) \end{aligned}$$

(17)

Analogously, for the second interval, we can write

$$\begin{aligned} \mathbf{U} (t)=\mathbf{M} _{2}(t-t_1)\mathbf{U} (t_1) \end{aligned}$$

(18)

where $\mathbf{M} _2= (t-t_1)$ is the fundamental matrix of the system on the second interval with constant rates of flows. Then, substituting (15) into (16), we obtain

$$\begin{aligned} \mathbf{U} (t)=\mathbf{M} _{2}(t-t_1)\mathbf{M} _1(\varDelta t_1)\mathbf{U} (t_0) \end{aligned}$$

(19)

And for $t=t_2$ we have

$$\begin{aligned} \mathbf{U} (t_2)=\mathbf{M} _{2}(\varDelta t_2)\mathbf{M} _1(\varDelta t_1)\mathbf{U} (t_0) \end{aligned}$$

(20)

Continuing this procedure for the third interval, we write

$$\begin{aligned} \mathbf{U} (t)=\mathbf{M} _3 (t-t_2)\mathbf{U} (t_2) \mathbf{U} (t)=\mathbf{M} _3 (t-t_2)\mathbf{M} _{2}(\varDelta t_2)\mathbf{M} _1(\varDelta t_1)\mathbf{U} (t_0) \end{aligned}$$

(21)

In the general case, for K intervals, we obtain

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

(22)

Then the fundamental matrix describing the behavior of the system on the K-th interval has the form

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

(23)

Thus, in this section, we have found the fundamental matrix of the system (1) with arbitrary piecewise constant flow rates in an analytical form. Note that the method also allows us to describe the dependence of the state probabilities on time for arbitrary laws of change $\lambda (t)$ and $\mu (t)$.

5 Numerical Calculations

5.1 Transient Analysis for a Time-Independent Queuing System

First of all, let us show that the presented method allows to carry out calculations for a large number of system state probabilities in the transient mode. For example, Fig. 2 shows the dependence of the probabilities of two hundred states on time for $\lambda =8.3\times 10^3$ packet/s, $\mu =5\times 10^3$ packet/s.

Fig. 2.

Time dependence of the probability of two hundred states of the M|M|1|n queue.

Further, this section presents the results of numerical calculations and their analysis for the M|M|1|n queue, where $n=\overline{1,3}$ for i = 5 states, where $i=\overline{0,4}$.

Transient modes are considered for the cases of constant $\rho$ and abruptly varying $\rho$. In addition, the analysis of dependence of the state probabilities including the probability of failures on time for the cases $\rho >1$, $\rho = 1$, $\rho < 1$ is carried out. Also the throughput of the system and the time of the transient mode are calculated.

Figure 3 shows the calculation results of the state probabilities dependences on time at $\lambda =8.3\times 10^5$ packet/s, $\mu =5\times 10^5$ packet/s [5] and initial conditions $(P_0 (0),P_1 (0),P_2 (0),P_3 (0),P_4 (0))^T\,=\,(1,0,0,0,0)^T$, meaning that the system buffer is completely free at the moment of time $t=0$. The indicated $\lambda$ corresponds to the maximum arrival rate of packets in the 10 Gbit/s communication channel when the size of packet is 1500 bytes [5]. The service rate of a particular switch $\mu$ depends on its performance and in this case corresponds to the average performance of a local area network switch. Thus, in this case $\rho = 1.66> 1$, which is typical for example, for a “broadcast storm”. Note that such a mode of operation for real systems is critical and can lead to fatal errors in information processing and require a complete reboot of the system [21]. In Fig. 3 $P_0 (t)$ is the probability that the service channel is idle and the buffer is empty, $P_1 (t)$ is the probability that the service channel is busy but the buffer is empty $P_1 (t)$, $P_2(t)$, $P_3 (t)$ are the probabilities that there are one and two packets in the buffer correspondingly and $P_4 (t)$ is the probability that there are three packets in the buffer and the next arrived packet will be lost.

In the transient mode, first of all, the bursts of state probabilities and the time of the transient mode are of interest. Studying these probability bursts in the transient mode, we can say that (Fig. 3) the maximum probability that the one packet is processing by the switch and the buffer is empty in this moment of time $P_{1max}(t=0.125\times 10^{-5})=0.33$. And it is three times higher the steady-state probability $P_1 (t\rightarrow \infty )=0.1$. Similarly, the maximum probability that one packet is in the buffer in the transient mode $P_{2max}(t=0.25\times 10^{-5})=0.22$. And it is almost one and a half times higher the steady-state probability $P_2 (t\rightarrow \infty )=0.16$. An increase in the arrival rate $\lambda$ leads to an increase in the amplitude of probability bursts: $P_{1max}=0.35$ and $P_{2max}=0.24$ if $\lambda =15\times 10^5$ packet/s. This situation can lead to buffer overflow and packet loss if taking into account the values of state probabilities in stationary mode only.

The second most important problem of transient analysis analogously as in radio electronics is to find the transient time of the system. In this case, in accordance with the theory described above, $\tau _{tr} = 1.74s$. Note that at the selected arrival rate $\lambda$ and service rate $\mu$ during the transient time $N_a=\lambda \tau _{tr}\approx 15$ packets are arrived in the switch and $N_s=\mu \tau _{tr}\approx 9$ packets are serviced by the switch. However, the probability of packet loss under the considered conditions is not large in comparison with the steady-state mode and increases according to the hyperexponential law (see Fig. 3 $p_4 (t)$).

Fig. 3.

Dependences of the states probabilities of the switch buffer

In the stationary mode probabilities of states are $P_0 (t=1,74\cdot 10^{-5})=0.07$, $P_1(t=1,74\cdot 10^{-5})=0.1$, $P_2(t=1,74\cdot 10^{-5})=0.16$, $P_3(t=1,74\cdot 10^{-5})=0.25$, $P_4(t=1,74\cdot 10^{-5})=0.4$. The throughput of the network in stationary state is $A(t=1,74\cdot 10^{-5})=(1-0.4)\cdot 8.3\cdot 10^5$ = 486 Kb/s. These results correspond to the ones obtained in previous works by well-known methods [1].

Figure 4 shows the dependence of states for the case $\rho = 1$. Here $\lambda = \mu = 5\,\cdot \,10^5$ packet/s. During this time, $N_a = N_s = \lambda \tau _{tr} = \mu \tau \approx 13$ packets are arrived and serviced. In this case, at the beginning of the transient mode, there is also a probability burst up to $P_{1max} (t=0.25\cdot 10^{-5})=0.31$ which 1.55 times more steady-state probability $P_1 (t\rightarrow \infty )=0.2$. The transient time in comparison with the previous case increased and amounted to $t_{tr}=2,6\cdot 10^{-5}$ s, which also corresponds to the results obtained known methods [1].

In addition, the steady-state probabilities take the same values $p_1 (2,6\cdot 10^{-5})= p_2 (2,6\cdot 10^{-5}) = p_3 (2,6\cdot 10^{-5})= p_4 (2,6\cdot 10^{-5})=0.2,\ the\ throughput\ is\ A(t=2,6\cdot 10^{-5})=(1-0.2)\cdot 5\cdot 10^5=391$ Kb/s, which also corresponds to the results obtained by well-known methods. Indeed, in [1] the formula is presented

$$\begin{aligned} P_i=\rho ^i\frac{1-\rho }{1-\rho ^{n+1}}, 0\le i\le n \end{aligned}$$

(24)

where n is the number of states. For $\rho = 1$, it gives the uncertainty 0/0 and the authors propose to use the L’Hospital’s rule to find the probabilities of states. Here we use the binomial decomposition $a^m-b^m=(a-b)(a^{m-1}+a^{m-2} b+...+ab^{m-2}+b^{m-1})$ and we obtain a simple expression for the case under consideration in a stationary mode.

$$\begin{aligned} P_i=\frac{1}{n}, 0\le i\le n \end{aligned}$$

(25)

For five states, we have $p_i = 0.2$, which corresponds to Fig. 4.

Fig. 4.

Dependences of the state probabilities of the switch buffer.

Figure 5 shows the third case, when $\rho <1$, where $\lambda =2\cdot 10^5$ packet/s and $\mu = 5\cdot 10^5$ packet/s, for $\rho = 0.4$. For this, small transition probability bursts are also observed, however, over time they disappear. The transition time in comparison with the previous cases increased slightly and amounted to $2,7\cdot 10^{-5}$ s. During this time, $N_a = \lambda \tau _{tr}\approx 6$ packets are arrived to the switch and $N_s = \mu \tau _{tr}\approx 14$ packets can be served.

The steady-state probabilities are $\pi _0=P_0 (t\rightarrow \infty )=0.6$, $\pi _1=P_1 (t\rightarrow \infty )=0.24$, $\pi _2=P_2 (t \rightarrow \infty )=0.1$, $\pi _3=P_3 (t\rightarrow \infty )=0.04$, $\pi _4=P_4 (t\rightarrow \infty )=0.02$, the throughput is $A (t= 2,7 \cdot 10^{-5}) = (1-0.02) \cdot 2 \cdot 10^5=191$ Kb/s. These values correspond to calculation results carried out by well-known formulas [1,2,3,4,5].

The analysis of transient behavior of the queuing system shows that when $\lambda$ decreases, the transient time increases, and, accordingly, the number of packets processed during this time increases too. In addition, with decreasing $\lambda$, the probability bursts decrease in the transient mode. It should be noted that the obtained numerical results of the steady-state probabilities of the system completely coincide with the numerical solutions obtained earlier [1,2,3,4,5].

Fig. 5.

Dependences of the states probabilities of the switch buffer.

5.2 Transient Analysis for a Time-Dependent Queuing System

In this section, we analyze the distribution of packets in the system when arrival rate of packets changes abruptly at some moments of time. So it will be consider how jumps of $\lambda$ affect the transient mode for three cases $\rho > 1$, $\rho = 1$, $\rho <1$ and initial conditions $((P_0 (0),P_1 (0),P_2 (0),P_3 (0),P_4 (0))^T=(1,0,0,0,0)^T$ as in case with time-independent flows.

Let us consider the first case when $\rho > 1$, $\lambda _0=8.3\cdot 10^5$ packet/s and $\mu _0=5\cdot 10^5$ packet/s. This is the case when a network has been overloaded before the arrival rate jump can degrade network performance even more (Fig. 4). For example, this situation occurs in the network as a result of a “broadcast storm”. Let at time $t_1=1\cdot 10^{-5}$ s there is a jump from $\lambda _0$ to $\lambda _1=2.5\cdot 10^6$ packet/s, $\mu _0=\mu _1=5\cdot 10^5$ packet/s.

From the distribution of state probabilities dependencies in the transient mode (Fig. 6) it is seen that the jump at $t=t_1$ affected the resulting transient time, which decreased to $1.5\cdot 10^{-5}$ s. Indeed, the resulting transient mode includes two modes. The first one is determined by the process of system starting at the moment of time $t=t_0$, and the second one depends on the jump of $\lambda$ at the moment of time $t=t_1$, when the previous transient mode has not ended yet. In this case, the time of the second transient mode is less than the time of the first one, since $\lambda _1 \gg \lambda _0$ (see the previous subsection).

Further, the steady-state probabilities take the following values: $\pi _0=P_0 (t\rightarrow \infty )=0$, $\pi _1 = P_1 (t \rightarrow \infty ) = 0.01$, $\pi _2 = P_2 (t \rightarrow \infty ) = 0.03$, $\pi _3 = P_3 (t \rightarrow \infty ) = 0.16$, $\pi _4 = P_4 (t \rightarrow \infty ) = 0.8$, the throughput is $A(t=1.5\cdot 10^{-5}) = (1-0.8)\cdot 2.5\cdot 10^6 = 488$ Kb/s. In this case, jump of arrival packet rate in the mode when the switch has been overload leads to sharp packet losses in the network (up to 80%). Note that the steady-state probabilities depend on $\lambda$ and $\mu$ after the jump and do not depend on the state of the system before the jump.

Fig. 6.

Dependencies of the states probabilities of the buffer for $\rho >1$ and jump of $\lambda$.

Fig. 7.

Dependencies of the states probabilities of the buffer for $\rho =1$ and jump of $\lambda$.

Figure 7 shows the calculation results of states probabilities for the case $\rho = 1$ before the jump. As in the previous case the jump from $\lambda _0=5\cdot 10^5$ to $\lambda _1=2.5\cdot 10^6$ packets/s occurs in the moment of time $t_1=1\cdot 10^{-5}$ s, when the previous transient mode has not been over yet. In this case, the jump of arrival rate $\lambda$ also leads to a decrease of transient period to $\tau _{tr}=2\cdot 10^{-5}$ s due to an increase of the $\lambda$. At the same time, it is obvious that the jump also influenced the redistribution of the probabilities of the system states in the stationary mode: $\pi _0=P_0 (t \rightarrow \infty ) = 0$, $\pi _1 = P_1 (t \rightarrow \infty ) = 0.01$, $\pi _2 = P_2 (t \rightarrow \infty ) = 0.03$, $\pi _3=P_3 (t \rightarrow \infty ) = 0.16$, $\pi _4 = P_4 (t \rightarrow \infty ) = 0.8$, the throughput is $A(t=2\cdot 10^{-5} )=(1-0.8)\cdot 2.5 \cdot 10^6 = 488$ Kb/s. These steady-state probabilities are equal to the probabilities of states in the previous case for $\rho > 1$. A similar picture is observed for $\rho <1$. Figure 8 shows the calculation results for the case $\rho > 1$ before the jump and $\rho < 1$ after the jump. In contrast to the previous cases, consider the decrease in intensity from $\lambda _0 = 8.3\cdot 10^5$ packet/s to $\lambda _1=2.5\cdot 10^5$ packet/s in the moment of time $t_1 = 1 \cdot 10^{-5}$ s. Obviously, the character of the probability of packet loss is changed at the moment of the jump, since the arrival rate of packets decreases sharply. It can be seen from the calculation results that in this case, the stationary mode is determined only by the characteristics of the system after the jump, and the arrival and service rates before the jump do not affect the stationary behavior of the system. For example for this case the probabilities of the system states in the stationary mode are $\pi _0 = P_0 (t \rightarrow \infty ) = 0.51$, $\pi _1 = P_1 (t \rightarrow \infty ) = 0.25$, $\pi _2 = P_2 (t \rightarrow \infty ) = 0.14$, $\pi _3 = P_3 (t \rightarrow \infty ) = 0.06$, $\pi _4 = P_4 (t \rightarrow \infty ) = 0.04$, the throughput is $A(t = 5.5\cdot 10^{-5} ) = (1-0.04)\cdot 2.5\cdot 10^5 = 234$ Kb/s. These results practically coincide the results obtained in the Sect. 7.1 for the case $\rho < 1$. Moreover, if the jump occurs before the end of the transient mode, then the resulting transient time $\tau _{tr}$ is equal to the sum of the transient time of the system before the jump and the transient time after the jump ($\tau _{tr} \approx 5.5\cdot 10^{-5}$ s). Thus, we have shown that the appearance of jumps in the intensity of the input flow during the transient mode leads to a decrease in the transient time, to a much faster process of buffer loading, and also to a significantly higher probability of packet loss regardless of the ratios of $\lambda$ and $\mu$ before the jump. Therefore, the traffic jumps must be taken into account when performance metrics of telecommunication network are calculated.

Fig. 8.

Dependences of the states probabilities of the buffer for $\rho >1$ and jump of $\lambda$.

6 Conclusion

In this paper, the transient behavior of the one of widely used queuing system such as the single-line system with a finite buffer M|M|1|n is considered. For this, the accurate analytical method of the fundamental matrix of Kolmogorov equations was proposed. The method allows calculating the characteristics of queuing systems, both in transient and stationary modes. The proposed mathematical model allows analyzing the dependences of the system state probabilities on time. Also using this method it can be calculated the throughput of the system, the number of arrived and served packets for the time of transient mode and the transient time and other performance metrics. In addition, the presented approach makes it possible to solve the problems of the synthesis of such systems, since all parameters in the final expressions are presented in an explicit form. Also, the mathematical model of the queuing system in the presence of the arrival and service rate jumps on arbitrary value at an arbitrary moment of time has been proposed. The performance metrics of the telecommunication network model are calculated according to the proposed method. The numerical calculation results of the steady-state characteristics of the considered system coincide with obtained by the well-known methods.