Keywords

1 Preliminaries

Queueing systems with finite buffer capacities are intensively studied nowadays due to their wide applications, in particular in modelling the operation of computer and telecommunication networks’ nodes. Models with different-types limitations in the access to the service station seem to be of particular importance, due to their potential using in energy saving modelling, being one of the most essential problems in wireless communication. In this case each busy period of the considered queueing system can be treated as an active period in the operation of the wireless network node (e.g. wireless sensor network) while, similarly, each idle time may be considered as a sleep (power saving) period.

In the literature different-type policies are proposed for supporting energy saving modelling. One of them is the so called multiple vacation policy (MVP in short). The sense of MVP is in that the service station (e.g. the radio transmitter/receiver of the wireless sensor network’s node) takes a number of repeated independent vacation periods, every time when the queue of buffered packets being directed to the node becomes empty. Successive vacation periods are being initialized until, at the end of one of them, at least one packet will be detected (so at least one packet will income into the accumulating buffer). For example, the mechanism of repeated vacations implemented into the M / G / 1-type system is proposed in [14] (see also [1, 18]) in modelling of type I energy-saving mode in IEEE 802.16e standard, and some performance measures are found there.

It is easy to note that theoretical results obtained for different-type queueing models with some service limitations are given in the stationary regime, i.e. they relate to the stochastic characteristics in the case of \(t\rightarrow \infty \). In practice, there are some situations in which transient analysis seems to be more recommended. For example, in the case of rather low intensity of input traffic (as it can be observed e.g. in some wireless sensor networks), in the case of performance evaluation of the system shortly after its starting (or after the application of a new control mechanism) or after the breakdown that destabilizes the system’s operation.

In the paper we study the transient queueing delay in the \(M^{X}/G/1/N\)-type finite-buffer queueing model with batch arrivals and the power saving mechanism based on a variant of MVP in that successive server vacations in a single MVP period have constant lengths. Queueing delay (called also virtual waiting time) at arbitrary fixed time epoch t takes a random value equal to the waiting time of the packet occurring in the system exactly at time t. Since this time need not be a “real” arrival moment, hence the term “virtual”. Applying the theoretical approach based on the idea of embedded Markov chain, the formula of total probability and linear algebra, the representation for the Laplace transform of the tail cumulative distribution function (CDF for short) of the queueing delay at given time t is found, conditioned by the initial level of buffer saturation.

The review of steady-state results for different vacation queueing models can be found in [4, 19]. An infinite-buffer queueing model with BMAP-type input stream and server vacations is investigated in [17]. Analytical results for finite-capacity systems with server vacations can be found e.g. in [5, 6, 15, 16, 20]. In particular, one can find the formulae for the stationary waiting-time distribution in the case of autocorrelated arrival stream in [15, 16]. The formula for the queueing delay distribution in the system with MVP and Poisson arrivals in equilibrium is derived in [20]. More complex vacation policies can be found in [2, 21]. In [2] M / G / 1-type system with server activity controlled by a timer is studied in the stationary case. The model reduces to the “usual” MVP queue with a zero-length timer duration. A queueing system with batch Poisson arrivals and server vacations controlled by the Randomly Timed Gated protocol is investigated in [21].

Time-dependent (transient) results on the queueing delay distribution in general-type models with batch arrivals and infinite buffers can be found e.g. in [7, 8]. The approach used there is based on integral equations and Wiener-Hopf factorization technique. Finite-capacity queue with MVP is studied in [9]. Analytical results on non-stationary queueing delay in systems with more complex control mechanisms can be found in [10,11,12].

The remaining part of the article is organized as follows. In the next section we give the detailed description of the considered queueing model. In Sect. 3 we obtain a system of integral equations for conditional queueing delay tail CDF. The corresponding system for Laplace transforms is found in Sect. 4. The solution of the system, written in a compact form (main result) is given in Sect. 5.

2 Model Description

An \(M^{X}/G/1/N\)-type queueing model is considered in which packets arrive according to a compound Poisson process with rate \(\lambda \) and generally-distributed group sizes. Namely, exactly k packets arrive simultaneously with probability \(p_{k}\), where \(\sum _{k=1}^{\infty }p_{k}=1\). It is assumed that packets are being processed one by one, under the FIFO service discipline, with a general-type cumulative distribution function (CDF for short) \(F(\cdot )\) of processing time. The accumulating buffer has capacity of \(N-1\) packets, so the maximal system state is assumed to be N. Every time when the service station becomes idle, a variant of a multiple vacation policy is being initialized: successive constant vacations of length \(D>0\) are being started repeatedly until at least one waiting packet will be detected in the accumulating buffer at the end of one of them. In such a case, at the same moment the processing restarts and so on.

3 Transient Equations for Queueing Delay Conditional Distribution

Let us denote by v(t) queueing delay at time t, namely the waiting time of a packet entering (hypothetically) exactly at time t.

Introduce the queueing delay conditional tail CDF as follows:

$$\begin{aligned} {}&V_{n}(t,x){\mathop {=}\limits ^{def}}{\mathbf P}\{v(t)>x\,|\,X(0)=n\},\quad t>0,\,x>0, \end{aligned}$$
(1)

where X(0) stands for the system state at the starting epoch \(t=0\).

Consider, firstly, the case of the system being empty before its opening and fix a moment \(t>0\). Three possible and mutually excluding situation may then occur:

  • the first multiple vacation period ends before t (A);

  • the first multiple vacation period ends after t but the system is not empty at t (B);

  • the first packet enters after time t (C).

Let us note that the following equation is then satisfied:

$$\begin{aligned} {}&{\mathbf P}\{\bigl (v(t)>x\bigr )\,\cap \,A\,|\,X(0)=0\}=\sum _{k=0}^{\infty }\int _{0}^{t}\lambda e^{-\lambda y}I\{kD\le y<(k+1)D<t\}\nonumber \\ {}&\times \Biggl [\sum _{i=1}^{N-1}p_{i}\Biggl (\sum _{r=0}^{N-i-1}\sum _{j=0}^{r} \frac{\{\lambda [(k+1)D-y]\}^{j}}{j!}e^{-\lambda [(k+1)D-y]}p_{r}^{j*}V_{i+r}(t-(k+1)D,x)\nonumber \\ {}&+V_{N}(t-(k+1)D,x)\sum _{r=N-i}^{\infty }\sum _{j=0}^{r}\frac{\{\lambda [(k+1)D-y]\}^{j}}{j!}e^{-\lambda [(k+1)D-y]}p_{r}^{j*}\Biggr )\nonumber \\ {}&+V_{N}(t-(k+1)D,x)\sum _{i=N}^{\infty }p_{i}\Biggr ]dy, \end{aligned}$$
(2)

where \(p_{r}^{j*}\) denotes the rth term of the j-fold convolution of the sequence \((p_{k})\) with itself and \(I\{\varPi \}\) is the indicator of the random event \(\varPi \).

Similarly, we have

$$\begin{aligned} {}&{\mathbf P}\{\bigl (v(t)>x\bigr )\,\cap \,B\,|\,X(0)=0\}=\sum _{k=0}^{\infty }\int _{0}^{t}\lambda e^{-\lambda y}I\{kD\le y,\,(k+1)D>t\}\nonumber \\ {}&\times \sum _{i=1}^{N-1}p_{i}\sum _{r=0}^{N-i-1}\sum _{j=0}^{r} \frac{[\lambda (t-y)]^{j}}{j!}e^{-\lambda (t-y)}p_{r}^{j*}\overline{F}^{(i+r)*}(x-(k+1)D+t)dy, \end{aligned}$$
(3)

where \(\overline{F}^{j*}(u){\mathop {=}\limits ^{def}}1-F^{j*}(u)\) and \(F^{j*}(u)\) stands for the i-fold Stieltjes convolution of the CDF \(F(\cdot )\) with itself and is defined as

$$\begin{aligned} {}&F^{0*}(t)=1,F^{1*}(t)=F(t),F^{(n+1)*}(t)=\int _{0}^{t}F^{n*}(t-y)dF(y), \end{aligned}$$
(4)

where \(t>0\) and \(n\ge 1\).

Evidently, \({\mathbf P}\{\bigl (v(t)>x\bigr )\,\cap \,C\,|\,X(0)=0\}=0\), since then the packet entering at time t has no waiting time.

Due to the fact that

$$\begin{aligned} {}&V_{0}(t,x)={\mathbf P}\{\bigl (v(t)>x\bigr )\,\cap \,A\,|\,X(0)=0\}\nonumber \\ {}&+{\mathbf P}\{\bigl (v(t)>x\bigr )\,\cap \,B\,|\,X(0)=0\}+{\mathbf P}\{\bigl (v(t)>x\bigr )\,\cap \,C\,|\,X(0)=0\}, \end{aligned}$$
(5)

evaluating integrals in (2)–(3), we obtain

$$\begin{aligned} {}&V_{0}(t,x)=\sum _{k=0}^{\infty }e^{-\lambda (k+1)D}I\{(k+1)D<t\}\nonumber \\ {}&\times \Biggl [\sum _{i=1}^{N-1}p_{i}\Biggl (\sum _{r=0}^{N-i-1}\sum _{j=0}^{r} \frac{(\lambda D)^{j+1}}{(j+1)!}p_{r}^{j*}V_{i+r}(t-(k+1)D,x)\nonumber \\ {}&+V_{N}(t-(k+1)D,x)\sum _{r=N-i}^{\infty }\sum _{j=0}^{r}\frac{(\lambda D)^{j+1}}{(j+1)!}p_{r}^{j*}\Biggr )+V_{N}(t-(k+1)D,x)\sum _{i=N}^{\infty }p_{i}\Biggr ]\nonumber \\ {}&+e^{-\lambda t}\sum _{k=0}^{\infty }I\{(k+1)D>t\}\sum _{i=1}^{N-1}p_{i}\sum _{r=0}^{N-i-1}\overline{F}^{(i+r)*}(x-(k+1)D+t)\nonumber \\ {}&\times \sum _{j=0}^{r}\frac{[\lambda (t-kD)]^{j+1}}{(j+1)!}p^{j*}_{r}. \end{aligned}$$
(6)

Assume now that the buffer is not empty at the starting time. In such a case successive departure epochs are Markovian moments in the evolution of the system (see e.g. [3]). Applying the law of total probability with respect to the first departure epoch \(y>0\) after the opening of the system, we obtain

$$\begin{aligned} {}&V_{n}(t,x)=\int _{0}^{t}\Biggl [\sum _{i=0}^{N-n-1}\sum _{j=0}^{i}\frac{(\lambda y)^{j}}{j!}e^{-\lambda y}p^{j*}_{i}V_{n+i-1}(t-y,x)\nonumber \\ {}&+V_{N-1}(t-y,x)\sum _{i=N-n}^{\infty }\sum _{j=0}^{i}\frac{(\lambda y)^{j}}{j!}e^{-\lambda y}p^{j*}_{i}\Biggr ]dF(y)+\int _{t}^{\infty }\overline{F}^{(n-1)*}(x-y+t)dF(y), \end{aligned}$$
(7)

where \(1\le n\le N\).

4 Linear Equations for Transforms

In this section we transform the original system of Eqs. (6)–(7) to the corresponding linear one written for Laplace transforms.

Indeed, let us introduce the following nomenclature:

$$\begin{aligned} {}&v_{n}(s,x){\mathop {=}\limits ^{def}}\int _{0}^{\infty }e^{-st}V_{n}(t,x)dt;\end{aligned}$$
(8)
$$\begin{aligned} {}&a_{r}(s){\mathop {=}\limits ^{def}}\int _{0}^{\infty }e^{-(\lambda +s)t}\sum _{j=0}^{r}\frac{(\lambda t)^{j}}{j!}p^{j*}_{r}dF(t);\end{aligned}$$
(9)
$$\begin{aligned} {}&\alpha _{r}(s){\mathop {=}\limits ^{def}}\frac{e^{-(\lambda +s)D}}{1-e^{-(\lambda +s)D}}\sum _{j=0}^{r}\frac{(\lambda D)^{j+1}}{(j+1)!}p^{j*}_{r};\end{aligned}$$
(10)
$$\begin{aligned} {}&b_{n}(s,x){\mathop {=}\limits ^{def}}\int _{t=0}^{\infty }e^{-st}dt\int _{y=t}^{\infty }\overline{F}^{(n-1)*}(x-y+t)dF(y),\end{aligned}$$
(11)
$$\begin{aligned} {}&\beta (s){\mathop {=}\limits ^{def}}\frac{e^{-(\lambda +s)D}}{1-e^{-(\lambda +s)D}}\Biggl [\sum _{i=1}^{N-1}p_{i}\sum _{r=N-i}^{\infty }\sum _{j=0}^{r}p^{j*}_{r}\frac{(\lambda D)^{j+1}}{(j+1)!}+\sum _{i=N}^{\infty }p_{i}\Biggr ] \end{aligned}$$
(12)

and

$$\begin{aligned} {} \gamma (s,x){\mathop {=}\limits ^{def}}&\int _{0}^{\infty }e^{-(\lambda +s)t}\sum _{k=0}^{\infty }I\{(k+1)D>t\}\nonumber \\ {}&\sum _{i=1}^{N-1}p_{i}\sum _{r=0}^{N-i-1}\overline{F}^{(i+r)*}(x-(k+1)D+t)\sum _{j=0}^{r}\frac{[\lambda (t-kD)]^{j+1}}{(j+1)!}p^{j*}_{r}dt. \end{aligned}$$
(13)

Now, the Eqs. (6)–(7) can be rewritten as follows:

$$\begin{aligned} {}&v_{0}(s,x)=\sum _{i=1}^{N-1}p_{i}\sum _{r=0}^{N-i-1}\alpha _{r}(s)v_{i+r}(s,x)+v_{N}(s,x)\beta (s)+\gamma (s,x),\end{aligned}$$
(14)
$$\begin{aligned} {}&v_{n}(s,x)=\sum _{i=0}^{N-n-1}a_{i}(s)v_{n+i-1}(s,x)+v_{N-1}(s,x)\sum _{i=N-n}^{\infty }a_{i}(s)+b_{n}(s,x), \end{aligned}$$
(15)

where \(1\le n\le N\).

Let us introduce into Eqs. (14)–(15) the following substitution:

$$\begin{aligned} {}&w_{n}(s,x){\mathop {=}\limits ^{def}}v_{N-n}(s,x), \end{aligned}$$
(16)

where \(0\le n\le N\).

After this transformation the system (14)–(15) takes the following shape:

$$\begin{aligned} {}&\sum _{k=-1}^{n}a_{k+1}(s)w_{n-k}(s,x)-w_{n}(s,x)=\phi _{n}(s,x), \end{aligned}$$
(17)

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

$$\begin{aligned} {}&w_{N}(s,x)=\sum _{i=1}^{N-1}p_{i}\sum _{r=0}^{N-i-1}\alpha _{N-i-r}(s)w_{r}(s,x)+w_{0}(s,x)\beta (s)+\gamma (s,x), \end{aligned}$$
(18)

where the functional sequence \(\bigl (\phi _{n}(\cdot ,\cdot )\bigr )\) is defined in the following way:

$$\begin{aligned} {}&\phi _{n}(s,x){\mathop {=}\limits ^{def}}a_{n+1}(s)w_{0}(s,x)-w_{1}(s,x)\sum _{k=n+1}^{\infty }a_{k}(s)-b_{N-n}(s,x). \end{aligned}$$
(19)

5 Compact-Form Solution

The general solution of the algebraic system of the form (17) but with infinite number of equations (written for \(n\ge 0\)) can be written as follows (see [13]):

$$\begin{aligned} {}&w_{n}(s,x)=C(s,x)R_{n+1}(s)+\sum _{k=0}^{n}R_{n-k}(s)\phi _{k}(s,x), \end{aligned}$$
(20)

where \(n\ge 0\) and the sequence \(\bigl (R_{n}(s)\bigr )\) is defined by coefficients \(a_{k}(s)\) as follows. Introduce the following generating functions:

$$\begin{aligned} {}&R(s,z){\mathop {=}\limits ^{def}}\sum _{k=0}^{\infty }z^{k}R_{k}(s),A(s,z){\mathop {=}\limits ^{def}}\sum _{k=0}^{\infty }z^{k}a_{k}(s),\quad |z|<1. \end{aligned}$$
(21)

Now the following relationship is true:

$$\begin{aligned} {}&R(s,z)=\frac{z}{A(s,z)-z}. \end{aligned}$$
(22)

To find successive terms of the sequence \(\bigl (R_{k}(s)\bigr )\) we can use the Maclaurin expansion. Indeed, if we denote \(Q(s,z){\mathop {=}\limits ^{def}}\frac{z}{A(s,z)-z}\), then we obtain

$$\begin{aligned} {}&\sum _{k=0}^{\infty }z^{k}R_{k}(s)=\sum _{k=0}^{\infty }z^{k}\frac{\partial ^{k}Q}{\partial z^{k}}\Bigr |_{(s,0)}\frac{1}{k!} \end{aligned}$$
(23)

and hence

$$\begin{aligned} {}&R_{k}(s)=\frac{\partial ^{k}Q}{\partial z^{k}}\Bigr |_{(s,0)}\frac{1}{k!}. \end{aligned}$$
(24)

In particular, we have \(R_{1}(s)=\frac{1}{a_{0}(s)}\).

Since the number of equations in (17) is finite, we can use the Eq. (18) as a specific-type boundary condition to find C(s, x) explicitly. In fact, instead of C(s, x), we will find the formula for \(w_{0}(s,x)\). Indeed, the relationship between C(s, x) and \(w_{0}(s,x)\) can be easily obtained from (20). Substituting \(n=0\), we get

$$\begin{aligned} {}&C(s,x)=w_{0}(s,x)[R_{1}(s)]^{-1}=w_{0}(s,x)a_{0}(s). \end{aligned}$$
(25)

Similarly, since \(\sum _{k=0}^{\infty }a_{k}(s)=f(s)\), where \(f(\cdot )\) is the Laplace transform of CDF \(F(\cdot )\), we obtain from (19), written at \(n=0\),

$$\begin{aligned} {}&\phi _{0}(s,x)=a_{1}(s)w_{0}(s,x)-w_{1}(s,x)[f(s)-a_{0}(s)]-b_{N}(s,x). \end{aligned}$$
(26)

From (17), taking \(n=0\), we obtain

$$\begin{aligned} {}&\phi _{0}(s,x)=a_{0}(s)w_{1}(s,x)+a_{1}(s)w_{0}(s,x)-w_{0}(s,x). \end{aligned}$$
(27)

Comparing the right sides of (26) and (27), we get \(w_{1}(s,x)\) in a function of \(w_{0}(s,x)\), namely

$$\begin{aligned} {}&w_{1}(s,x)=[f(s)]^{-1}[w_{0}(s,x)-b_{N}(s,x)]. \end{aligned}$$
(28)

The remaining task is to find \(w_{0}(s,x)\) explicitly. In order to do it, we write the representation for \(w_{N}(s,x)\) in two different forms: in the first one we use the general form of solution (20) and in the second one we use the Eq. (18). From (20) written at \(n=N\) (having in mind (25) and (28)) we get

$$\begin{aligned} {}&w_{N}(s,x)=w_{0}(s,x)a_{0}(s)R_{N+1}(s)+\sum _{k=0}^{N}R_{N-k}(s)\nonumber \\ {}&\times \Bigl \{a_{k+1}(s)w_{0}(s,x)- [f(s)]^{-1}[w_{0}(s,x)-b_{N}(s,x)]\sum _{i=k+1}^{\infty }a_{i}(s)-b_{N-k}(s,x)\Bigr \}. \end{aligned}$$
(29)

Similarly, applying (25) in (18), we get

$$\begin{aligned} {}&w_{N}(s,x)=\sum _{i=1}^{N-1}p_{i}\sum _{r=0}^{N-i-1}\alpha _{N-i-r}\Bigl \{w_{0}(s,x)a_{0}(s)R_{r+1}(s)\nonumber \\ {}&+\sum _{k=0}^{r}R_{r-k}(s)\Bigl [a_{k+1}(s)w_{0}(s,x)-[f(s)]^{-1}[w_{0}(s,x)-b_{N}(s,x)]\sum _{i=k+1}^{\infty }a_{i}(s)\nonumber \\ {}&-b_{N-k}(s,x)\Bigr ]\Bigr \}+w_{0}(s,x)\beta (s)+\gamma (s,x). \end{aligned}$$
(30)

Comparing the right sides of (29) and (30), we eliminate \(w_{0}(s,x)\) as follows:

$$\begin{aligned} {}&w_{0}(s,x)=T_{1}(s,x)T_{2}(s,x), \end{aligned}$$
(31)

where

$$\begin{aligned} {} T_{1}(s,x){\mathop {=}\limits ^{def}}&\Biggl \{a_{0}(s)R_{N+1}(s)+\sum _{k=0}^{N}R_{N-k}(s)\Bigl [a_{k+1}(s)-\bigl (f(s)\bigr )^{-1}\sum _{i=k+1}^{\infty }a_{i}(s)\Bigr ]\nonumber \\ {}&-\sum _{i=1}^{N-1}p_{i}\sum _{r=0}^{N-i-1}\alpha _{N-i-r}(s)\Biggl [a_{0}(s)R_{r+1}(s) +\sum _{k=0}^{r}R_{r-k}(s)\Bigl [a_{k+1}(s)\nonumber \\ {}&-\bigl (f(s)\bigr )^{-1}\sum _{i=k+1}^{\infty }a_{i}(s)\Bigr ]\Biggr ]-\beta (s)\Biggr \}^{-1} \end{aligned}$$
(32)

and

$$\begin{aligned} {} T_{2}(s,x){\mathop {=}\limits ^{def}}&\sum _{i=1}^{N-1}p_{i}\sum _{r=0}^{N-i-1}\alpha _{N-i-r}(s) \sum _{k=0}^{r}R_{r-k}(s)\nonumber \\ {}&\times \Bigl \{\bigl [f(s)\bigr ]^{-1}b_{N}(s,x)\sum _{i=k+1}^{\infty }a_{i}(s)-b_{N-k}(s,x)\Bigr \}+\gamma (s,x)\nonumber \\ {}&-\sum _{k=0}^{N}R_{N-k}(s)\Bigl \{\bigl [f(s)\bigr ]^{-1}b_{N}(s,x)\sum _{i=k+1}^{\infty }a_{i}(s)-b_{N-k}(s,x)\Bigr \}. \end{aligned}$$
(33)

Now, collecting the formulae (16), (20), (25) and (31), we obtain the following main result:

Theorem 1

The Laplace transform of the queueing delay conditional tail CDF in the considered queueing system with constant repeated vacations can be written in the following way:

$$\begin{aligned} {}&v_{n}(s,x)=\Bigl \{a_{0}(s)R_{N-n+1}(s)+\sum _{k=0}^{N-n}R_{N-n-k}(s)\Bigl [a_{k+1}(s)\nonumber \\ {}&-\bigl [f(s)\bigr ]^{-1}\sum _{i=k+1}^{\infty }a_{i}(s)\Bigr ]\Bigr \}T_{1}(s,x)T_{2}(s,x)\nonumber \\ {}&+\sum _{k=0}^{N-n}R_{N-n-k}(s)\Bigl \{\bigl [f(s)\bigr ]^{-1}b_{N}(s,x)\sum _{i=k+1}^{\infty }a_{i}(s)-b_{N-k}(s,x)\Bigr \}, \end{aligned}$$
(34)

where \(0\le n\le N\) and the formulae for \(a_{k}(s)\), \(b_{k}(s,x)\), \(R_{k}(s)\), \(T_{1}(s,x)\) and \(T_{2}(s,x)\) are given in (9), (11), (24), (32) and (33), respectively.