Keywords

1 Introduction and Preliminaries

As it is well known, queueing models, in particular with finite buffer capacities, can be successfully used in modelling different-type real issues typical for telecommunication and computer networks, manufacturing processes, transport organization and logistics. A special role in modelling play systems with less or more complex mechanisms limiting access to the service station. It is associated with the dynamically developing market of different-type solutions for energy consumption reducing and minimizing the costs of system operation. One of such mechanisms are setup and closedown times, occurring at the start and completion epoch of each busy period of the system, respectively. Due to frequent energy saving requirements, the service station is being switched off when there are no jobs waiting for processing, and is being switched on when a job arrives at the empty system. Safe deactivation of the server requires a random time, called a closedown time. Similarly, a randomly distributed setup time is needed for the server to initialize its work and achieve full readiness for processing. In the paper we consider a a single-channel queueing model with finite buffer capacity and the processing organized according to the FIFO service discipline, in which each busy period starts with a setup time and completes with a closedown time. One of the most important stochastic characteristics of each finite-capacity queueing model is the CDF (=cumulative distribution function) of the time to buffer overflow, i.e. the random time from the start epoch of the system to the first moment at which the buffer becomes saturated (the system contains maximal number of jobs). The knowledge of that time is of key importance, e.g. in QoS (=Quality of Service) in telecommunications, since during the buffer overflow period all incoming jobs or packets are lost. In the article, using the approach based on the conception of embedded Markov chain, the continuous version of total probability law and linear algebra, we derive a closed-form representation for the LT (=Laplace transform) of the CDF of the time to buffer overflow, conditioned by the number of jobs accumulated in the buffer at the opening of the system.

As one can observe, in the literature most results for different-type stochastic characteristics of queueing models are found only for the stable systems (stationary state). However, as it seems, non-stationary (transient) analysis is often recommended or directly necessary, e.g. due to high changeability of the traffic (e.g., packet streams in nodes of TCP/IP-based networks), enormous traffic load or unreliable server being subject to breakdowns. In these situations the stationary state of the system is difficult to achieve.

In [1] the queueing model of the M/G/1-type with server breakdowns, setup and closedown times, and with the controlled vacation periods is considered. The stationary results for the batch-arrival queue with multiple vacation policy and server setup and closedown times can be found in [2]. One can find some other results for models with group arrivals in [3, 4]. In [5] the case of discrete time is investigated: a combined control mechanism based on multiple vacation policy and server setup and closedown times is analyzed. The model of a multi-server queue is studied in [6]. Transient results for infinite-capacity systems with server setup times can be found in [7, 8]. In [9] analytical solution for non-stationary queue-size distribution in the queueing system with finite buffer and setup and closedown times is obtained (see also [10]). Similar technique is applied in [11] for the model with server breakdowns. Distributions of the time to buffer overflow in finite-capacity models are studied e.g. in [12, 13]. In [12] the case of MMPP-type (Markov-Modulated Poisson Process) arrival stream is investigated, while in [13] the general independent arrival process is assumed.

The remaining part of the paper is organized as follows. In the next Sect. 2 we give a detailed mathematical description of the studied queueing model. In Sect. 3 we find a system of integral equations for conditional CDF of the time to buffer overflow. In Sect. 4 we obtain the corresponding system for LTs and write it in a specific form. Section 5 contains main result: the compact-form representation for the LT of conditional distribution of the time to buffer overflow. In the last Sect. 6 a short conclusion can be found.

2 Description of Queueing Model

In the article we deal with a single-channel queueing model with finite capacity of the buffer accumulating jobs (customers, packets, calls, etc.) waiting for processing. We assume that the arrival stream is governed by simple Poisson process with rate \( \lambda , \) while the service time of each job is generally distributed random variable with a CDF \( F\left( \cdot \right). \) A number of jobs simultaneously present in the system is bounded by a non-random value \( N, \) i.e. we have a buffer with \( N - 1 \) places and one place in service station. At the opening of the system, at time \( t = 0, \) a buffer may contain a number of jobs waiting for service in the buffer. Every time when the system empties, i.e. if at the completion epoch of the job service there is no job waiting in the buffer, the service station starts a randomly distributed closedown time with a CDF \( C\left( \cdot \right). \) If at the completion epoch of a closedown time a buffer contains at least one job waiting for service, the server is being switched on at this moment, otherwise the server waits in the standby mode for the first arrival. The first processing after the idle period is always preceded by a setup time, with random duration with a CDF \( S\left( \cdot \right) \) (the server begins the setup time simultaneously with the moment of its switching on). Besides, if a job arrives at the system during the closedown time, after its completion epoch the server immediately begins the setup time and next starts the service process. The service station needs the closedown time to be closed safely. Similarly, the setup time is needed for a server to achieve full readiness for processing after the idle period. We assume the well-known FIFO service discipline. Moreover, if the entering job finds the buffer already being overflowed, it is lost (it leaves the system without service).

3 Equations for Conditional CDF of Time to Buffer Overflow

Let \( \Delta _{n} \) be the time to the buffer overflow, conditioned by the number of jobs accumulated in the buffer before the opening of the system, i.e.

$$ \Delta _{n} \mathop = \limits^{\text{def}} { \inf }\,\{ t > 0:X\left( t \right) = N | X\left( 0 \right) = n\} ,\,\,\,\,0 \le n \le N - 1, $$
(1)

where \( X\left( t \right) \) denotes the number of jobs present in the system at time \( t, \) including the one being processed at this time (if any).

Assume, firstly, that the system is empty at the start moment \( t = 0 \). In this case we consider \( t = 0 \) as the moment at which the last service completes during a busy period. Thus, in consequence, a closedown time begins at this time. Let us note that we can distinguish six different mutually excluding random events:

  1. 1.

    the first job arrives during the closedown time, and both the closedown and setup times finishes before time \( t \) (let us denote this random event by \( E_{1} (t) \));

  2. 2.

    the first job arrives during the closedown time and before time \( t, \) but the following setup time finishes after \( t \) (\( E_{2} (t)); \)

  3. 3.

    the first job occurs before \( t \) and during the closedown time but that period completes after \( t \) (\( E_{3} (t)) \);

  4. 4.

    the first job enters after the closedown time but before \( t \), and the setup time finishes after \( t \) (\( E_{4} (t)); \)

  5. 5.

    the first job enters after the closedown time but before \( t \), and the setup time ends before \( t \) (\( E_{5} (t)); \)

  6. 6.

    the first job occurs after time \( t \) (\( E_{6} (t)) \).

Observe that the following representations hold true:

$$ \varvec{P}\left\{ {\left( {\Delta _{0} > t} \right)\mathop \cap \nolimits E_{1} (t)} \right\} = \mathop \smallint \limits_{u = 0}^{t} dC\left( u \right)\mathop \smallint \limits_{x = 0}^{u} \lambda e^{ - \lambda x} dx\mathop \smallint \limits_{v = 0}^{t - u} \mathop \sum \limits_{k = 0}^{N - 2} \frac{{\left[ {\lambda \left( {u + v - x} \right)} \right]^{k} }}{k!}e^{{ - \lambda \left( {u + v - x} \right)}} P\left\{ {\Delta _{k + 1} > t - u - v} \right\}dS\left( v \right), $$
(2)
$$ \varvec{P}\left\{ {\left( {\Delta _{0} > t} \right)\mathop \cap \nolimits E_{2} (t)} \right\} = \mathop \smallint \limits_{u = 0}^{t} \bar{S}(t - u)dC(u)\mathop \smallint \limits_{x = 0}^{u} \lambda e^{ - \lambda x} \mathop \sum \limits_{k = 0}^{N - 2} \frac{{\left[ {\lambda \left( {t - x} \right)} \right]^{k} }}{k!}e^{{ - \lambda \left( {t - x} \right)}} dx, $$
(3)
$$ \varvec{P}\left\{ {\left( {\Delta _{0} > t} \right)\mathop \cap \nolimits E_{3} (t)} \right\} = \bar{C}\left( t \right)\mathop \sum \limits_{k = 1}^{N - 1} \frac{{\left( {\lambda t} \right)^{k} }}{k!}e^{ - \lambda t} , $$
(4)
$$ \varvec{P}\left\{ {\left( {\Delta _{0} > t} \right)\mathop \cap \nolimits E_{4} (t)} \right\} = \mathop \smallint \limits_{u = 0}^{t} dC(u)\mathop \smallint \limits_{x = u}^{t} \lambda e^{ - \lambda x} \bar{S}(t - x)\mathop \sum \limits_{k = 0}^{N - 2} \frac{{\left[ {\lambda \left( {t - x} \right)} \right]^{k} }}{k!}e^{{ - \lambda \left( {t - x} \right)}} dx, $$
(5)
$$ \varvec{P}\left\{ {\left( {\Delta _{0} > t} \right)\mathop \cap \nolimits E_{5} (t)} \right\} = \mathop \smallint \limits_{u = 0}^{t} dC\left( u \right)\mathop \smallint \limits_{x = u}^{t} \lambda e^{ - \lambda x} dx\mathop \smallint \limits_{v = 0}^{t - x} \mathop \sum \limits_{k = 0}^{N - 2} \frac{{\left( {\lambda v} \right)^{k} }}{k!}e^{ - \lambda v} P\left\{ {\Delta _{k + 1} > t - {\text{x}} - v} \right\}dS(v) $$
(6)

and

$$ \varvec{P}\left\{ {\left( {\Delta _{0} > t} \right)\mathop \cap \nolimits E_{6} (t)} \right\} = e^{ - \lambda t} . $$
(7)

In the formulae above we use the nomenclature \( \bar{G}\left( t \right) = 1 - G\left( t \right), \) where \( G\left( \cdot \right) \) denotes arbitrary CDF. Comment shortly the formulae (2)–(7). In (2) and (6) the setup time completes before the moment \( t, \) hence the service station starts the processing with the number of jobs which have occurred during the service suspension period. In (3)–(5) and (7), if the condition determined in the definition of the appropriate \( E_{i} (t) \) is satisfied, the time to buffer overflow exceeds \( t \) with probability 1.

Now, let us investigate the situation in which at \( t = 0 \) the buffer contains at least one job, i.e. the level of buffer saturation equals n, where \( 1 \le n \le N - 1. \) Due to the fact that successive service completion moments are Markov epochs in the operation of the system, then, by virtue of the continuous version of the total probability law applied in relation to the first departure moment after the opening of the system at time \( t = 0 \), the following system of Volterra-type integral equations can be written:

$$ \varvec{P}\left\{ {\Delta _{n} > t} \right\} = \mathop \sum \limits_{k = 0}^{N - n - 1} \mathop \smallint \limits_{0}^{\varvec{t}} \varvec{P}\left\{ {\Delta _{n + k - 1} > t - x} \right\}\frac{{\left( {\lambda x} \right)^{k} }}{k!}e^{ - \lambda x} dF\left( x \right) + \bar{F}(t)\mathop \sum \limits_{k = 0}^{N - n - 1} \frac{{\left( {\lambda t} \right)^{k} }}{k!}e^{ - \lambda t} , $$
(8)

where \( 1 \le n \le N - 1. \) Indeed, the first summand on the right side of (8) refers to the case in which the first service finishes at time \( x < t. \) The second summand presents the situation where the first departure occurs after \( t, \) hence the time to buffer overflow exceeds \( t \) with probability 1 if and only if at most \( N - n - 1 \) jobs arrive up to \( t. \)

4 Corresponding System of Equations for LTs

In this section we obtain the corresponding system of equations for LTs of conditional CDFs of the time to buffer overflow (more precisely: for the tail of CDF) and write it in a specific form. Let us start with introducing the following notation:

$$ \delta_{n} \left( s \right)\mathop = \limits^{\text{def}} \mathop \smallint \limits_{0}^{\infty } e^{ - st} \varvec{P}\left\{ {\Delta _{n} > t} \right\}dt,\quad {\text{Re}}\left( s \right) > 0,\,0 \le n \le N - 1. $$
(9)

Now, since \( \delta_{0} \left( s \right) = \mathop \sum \limits_{i = 1}^{6} \mathop \smallint \limits_{0}^{\infty } e^{ - st} \varvec{P}\left\{ {\left( {\Delta _{0} > t} \right)\mathop \cap \nolimits E_{i} (t)} \right\}dt \), then just from the representations (2)–(7) we get

$$ \delta_{0} \left( s \right) = \mathop \sum \limits_{k = 0}^{N - 2} \gamma_{k} \left( {\text{s}} \right)\delta_{{{\text{k}} + 1}} \left( s \right) + \eta \left( s \right), $$
(10)

where

$$ \gamma_{k} \left( s \right)\mathop = \limits^{\text{def}} \frac{{\lambda^{k + 1} }}{{\left( {k + 1} \right)!}}\mathop \smallint \limits_{u = 0}^{\infty } e^{{ - \left( {\lambda + s} \right)u}} dC(u)\mathop \smallint \limits_{v = 0}^{\infty } e^{{ - \left( {\lambda + s} \right)v}} \left[ {(u + v)^{k + 1} - v^{k + 1} } \right]dS\left( v \right) + \frac{\lambda }{\lambda + s}\tilde{c}(\lambda + s)\mathop \smallint \limits_{0}^{\infty } e^{{ - \left( {\lambda + s} \right)v}} \frac{{(\lambda v)^{k} }}{k!}dS\left( v \right), $$
(11)
$$ \eta \left( s \right)\mathop = \limits^{\text{def}} \mathop \smallint \limits_{u = 0}^{\infty } dC\left( u \right)\mathop \smallint \limits_{t = u}^{\infty } e^{{ - \left( {\lambda + s} \right)t}} \bar{S}\left( {t - u} \right)\mathop \sum \limits_{k = 0}^{N - 2} \frac{{\lambda^{k + 1} }}{{\left( {k + 1} \right)!}}\left[ {t^{k + 1} - \left( {t - u} \right)^{k + 1} } \right]dt + \mathop \sum \limits_{k = 1}^{N - 1} \mathop \smallint \limits_{0}^{\infty } e^{{ - \left( {\lambda + s} \right)t}} \frac{{\left( {\lambda t} \right)^{k} }}{k!}\bar{C}\left( t \right)dt + \mathop \smallint \limits_{t = 0}^{\infty } e^{{ - \left( {\lambda + s} \right)t}} dt\mathop \smallint \limits_{u = 0}^{t} dC\left( u \right)\mathop \smallint \limits_{x = u}^{t} \mathop \sum \limits_{k = 0}^{N - 2} \frac{{\lambda^{k + 1} }}{{{\text{k}}!}}\left( {t - x} \right)^{k} \bar{S}\left( {t - x} \right)dx + \frac{1}{\lambda + s} $$
(12)

and

$$ \tilde{c}\left( s \right)\mathop = \limits^{\text{def}} \mathop \smallint \limits_{0}^{\infty } e^{ - st} dC\left( t \right). $$
(13)

Similarly, the system of Eq. (8) will be transformed in the following way:

$$ \delta_{n} \left( s \right) = \mathop \sum \limits_{k = 0}^{N - n - 1} a_{k} (s)\delta_{n + k - 1} \left( s \right) + \theta_{N - n - 1} \left( s \right), $$
(14)

where \( 1 \le n \le N - \) 1 and

$$ a_{k} \left( s \right)\mathop = \limits^{\text{def}} \mathop \smallint \limits_{0}^{\infty } e^{{ - \left( {\lambda + s} \right)t}} \frac{{\left( {\lambda t} \right)^{k} }}{k!}dF\left( t \right), $$
(15)
$$ \theta_{k} (s)\mathop = \limits^{\text{def}} \mathop \smallint \limits_{0}^{\infty } e^{{ - \left( {\lambda + s} \right)t}} \bar{F}(t)\mathop \sum \limits_{i = 0}^{k} \frac{{\left( {\lambda t} \right)^{i} }}{i!}dt. $$
(16)

Now, let us apply to (10) and (14) the following substitution:

$$ \delta_{n} \left( s \right)\mathop = \limits^{\text{def}} D_{N - n} \left( s \right), $$
(17)

where \( 0 \le n \le N - 1. \) After this transformation (10) and (14) can be reformulated as follows:

$$ D_{N} \left( s \right) = \mathop \sum \limits_{k = 0}^{N - 2} \gamma_{k} \left( {\text{s}} \right)D_{n - k - 1} \left( s \right) + \eta \left( s \right), $$
(18)

and

$$ \mathop \sum \limits_{k = - 1}^{n - 1} a_{k + 1} \left( s \right)D_{n - k} \left( s \right) - D_{n} (s) = \phi_{n} \left( s \right), 1 \le n \le N - 1, $$
(19)

where

$$ \phi_{n} \left( s \right)\mathop = \limits^{\text{def}} a_{n} \left( s \right)D_{1} \left( s \right) - \theta_{n - 1} \left( s \right). $$
(20)

5 Compact Solution for LT of CDF of Time to Buffer Overflow

In [14] the system of equations of type (19) was considered but with infinitely many equations (infinite-sized), namely for \( n \ge 1. \) Moreover, originally, the system had coefficients being defined by usual number sequences, not by functional sequences as in (19). As it was proved in [14], each solution of (19) can be represented in the following form (we adjust here the original representation from [14] to the case of functional sequences \( \left( {a_{k} (s)} \right) \) and \( \left( {\phi_{k} (s)} \right) \)):

$$ D_{n} (s) = A(s)R_{n} \left( s \right) + \mathop \sum \limits_{k = 1}^{n} \phi_{k} (s)R_{n - k} \left( s \right),\quad n \ge 1, $$
(21)

where \( A\left( s \right) \) is a function of variable \( s \) which is independent on \( n, \) and successive terms of the functional sequence \( R_{k} (s), k \ge 0 \), can be found from the following recursion, by using coefficients \( a_{k} \left( s \right), k \ge \) 0:

$$ R_{0} \left( s \right) = 0,\quad \,\,R_{1} \left( s \right) = a_{0}^{ - 1} \left( s \right),\;\,\,R_{k + 1} \left( s \right) = R_{1} \left( s \right)\left( {R_{k} \left( s \right) - \mathop \sum \limits_{i = 0}^{k} a_{i + 1} \left( s \right)R_{k - i} \left( s \right)} \right),\,\,\,\,k \ge 1. $$
(22)

Let us note that, due the fact that the number of equations in (19) is finite, we can use the Eq. (18) written for \( n = N \) as a boundary condition which allows for expressing the function \( A(s) \) explicitly. Hence we can find the representation for the unknown function \( D_{n} (s) \) from (21) in a compact form.

Starting with substituting \( n = 1 \) into (21), we obtain

$$ D_{1} \left( s \right) = A\left( s \right)R_{1} \left( s \right). $$
(23)

Next, taking in (21) \( n = N \) and referring to (23), we get

$$ D_{N} \left( s \right) = A(s)R_{N} \left( s \right) + \mathop \sum \limits_{k = 1}^{N} \phi_{k} \left( s \right)R_{N - k} \left( s \right) = A\left( s \right)R_{N} \left( s \right) + \mathop \sum \limits_{k = 1}^{N} \left[ {a_{k} \left( s \right)D_{1} \left( s \right) - \theta_{k - 1} \left( s \right)} \right]R_{N - k} \left( s \right) = A\left( s \right)\left( {R_{N} \left( s \right) + R_{1} \left( s \right)\mathop \sum \limits_{k = 1}^{N} a_{k} \left( s \right)R_{N - k} \left( s \right)} \right) - \mathop \sum \limits_{k = 1}^{N} \theta_{k - 1} \left( s \right)R_{N - k} \left( s \right). $$
(24)

Introducing (21) into (18), we can rewrite (18) as follows:

$$D_{N} \left( s \right) = \mathop \sum \limits_{k = 0}^{N - 2} \gamma_{k} \left( s \right)\left\{ {A\left( s \right)R_{N - k - 1} \left( s \right) + \mathop \sum \limits_{i = 1}^{N - k - 1} \left[ {A\left( s \right)a_{i} \left( s \right)R_{1} \left( s \right) - \theta_{i - 1} \left( s \right)} \right]R_{N - k - 1 - i} \left( s \right)} \right\} + \eta \left( s \right) = A(s)\mathop \sum \limits_{k = 0}^{N - 2} \gamma_{k} \left( s \right)\left[ {R_{N - k - 1} \left( s \right) + R_{1} (s)\mathop \sum \limits_{i = 1}^{N - k - 1} a_{i} \left( s \right)R_{N - k - 1 - i} \left( s \right)} \right] + \eta \left( s \right) - \mathop \sum \limits_{k = 0}^{N - 2} \gamma_{k} \left( s \right)\mathop \sum \limits_{i = 1}^{N - k - 1} \theta_{i - 1} \left( s \right)R_{N - k - 1 - i} \left( s \right). $$
(25)

Comparing the right sides of (24) and (25), we eliminate \( A(s) \) in the following way:

$$ A\left( s \right) =\Psi _{1} \left( s \right)\Psi _{2}^{ - 1} , $$
(26)

where

$$ \Psi _{1} \left( s \right)\mathop = \limits^{\text{def}} \eta \left( s \right) - \mathop \sum \limits_{k = 0}^{N - 2} \gamma_{k} \left( s \right)\mathop \sum \limits_{i = 1}^{N - k - 1} \theta_{i - 1} \left( s \right)R_{N - k - 1 - i} \left( s \right) + \mathop \sum \limits_{k = 1}^{N} \theta_{k - 1} \left( s \right)R_{N - k} \left( s \right) $$
(27)

and

$$ \Psi _{2} \left( s \right)\mathop = \limits^{\text{def}} R_{N} \left( s \right) + R_{1} \left( s \right)\mathop \sum \limits_{k = 1}^{N} a_{k} \left( s \right)R_{N - k} \left( s \right) - \mathop \sum \limits_{k = 0}^{N - 2} \gamma_{k} \left( s \right)\left[ {R_{N - k - 1} \left( s \right) + R_{1} \left( s \right)\mathop \sum \limits_{i = 1}^{N - k - 1} a_{i} \left( s \right)R_{N - k - 1 - i} \left( s \right)} \right]. $$
(28)

Collecting the formulae (17), (20), (21) and (26), we can state the following main theorem:

Theorem 1

The representation for the LT \( \delta_{n} \left( s \right) \) of the conditional tail CDF of the time to the buffer overflow in the M/G/1/N-type finite-capacity queueing system with generally distributed setup and closedown times is following:

$$ \delta_{n} \left( s \right) = \mathop \smallint \limits_{0}^{\infty } e^{ - st} \varvec{P}\left\{ {\Delta _{n} > t} \right\}dt =\Psi _{1} \left( s \right)\Psi _{2}^{ - 1} \left( {R_{N - n} \left( s \right) + R_{1} (s)\mathop \sum \limits_{k = 1}^{N - n} a_{k} (s)} \right) - \mathop \sum \limits_{k = 1}^{N - n} \theta_{k - 1} \left( s \right)R_{N - n - k} \left( s \right), $$
(29)

where the formulae for \( \Psi _{1} \left( s \right),\Psi _{2} \left( s \right) \), \( R_{k} \left( s \right), a_{k} (s) \) and \( \theta_{k} \left( s \right) \) are given in (27), (28), (22), (15) and (16), respectively.

6 Conclusion

In the article a single-channel queueing model with finite buffer capacity and a mechanism of setup-closedown times of the service station is investigated. The arrival stream is described by a single Poisson process while the processing, setup and closedown times are generally distributed random variables. By using the analytical approach based on the concept of embedded Markov chain, continuous version of the total probability law and linear algebra a compact-form representation for the LT of the conditional tail CDF of the time to the buffer overflow is obtained. The final formulae are written in terms of “input” system characteristics and a functional sequence, defined recursively, connected with them.