Waiting time and queue length analysis of Markov-modulated fluid priority queues

In the system considered in the paper, K different (fluid) job types are distinguished, where class 1 has the lowest, and class K the highest priority. The priority of the fluid can be interpreted as “weight,” and can correspond to the importance or the urgency of the jobs.

The rates at which the fluid belonging to various job types enters the system are modulated by a continuous-time Markov chain (CTMC, also referred to as the background process) with generator denoted by \(\mathbf {Q}\). (The irreducibility of the background process is assumed throughout the paper.) The stationary probability vector of the CTMC is \(\pi \); hence, \(\pi \mathbf {Q}=0,\pi \mathbb {1}=1\) hold. (\(\mathbb {1}\) denotes the column vector of ones of appropriate size.) The rate at which class k fluid flows into the queue in state i is \(r_i^{(k)}\ge 0\). The matrix \(\mathbf {R}^{(k)}\) is a diagonal matrix composed of the class k incoming fluid rates; \(\mathbf {R}^{(k)}=\text {diag}\langle r_i^{(k)} \rangle \). For simplicity, we denote the input rates of classes having priority equal to or higher than k by \(r_i^{(k+)}=\sum _{\ell =k}^K r_i^{(k)}\), and the corresponding matrix by \(\mathbf {R}^{(k+)}=\text {diag}\langle r_i^{(k+)} \rangle \). The rate at which fluid can leave the queue is denoted by d.

Using the notation introduced above, the mean arrival rate of class k fluid can be obtained by \(\lambda ^{(k)}=\pi \mathbf {R}^{(k)}\mathbb {1}\), and the total input rate is \(\lambda =\sum _{k=1}^K \lambda ^{(k)}\). The system is assumed to be stable; hence, \(\lambda < d\).

In this paper, all performance measures will be derived from the analysis of the workload process. The workload, also called the unfinished work, or the virtual waiting time, is the amount of work present in the system, not in fluid level, but in time [11]. The fluid levels of different priorities are correlated; their joint analysis is rather complex. The workload process, however, makes it possible to obtain several performance measures from a Markov chain having only a single continuous variable, which is much more tractable numerically.

The solution is based on the “tagged customer” approach. When a class k fluid drop arrives into the queue, it finds a certain amount of class \(k+\) workload in the system. This amount of workload has to be served before the tagged fluid drop can leave the system. The workload of lower priority classes can be neglected. While the tagged fluid drop waits for its service in the queue, further class \((k+1)+\) fluid can arrive, which has to be served before the tagged one. After a certain amount of time, the tagged fluid drop reaches the head of the queue and can leave the system.It is shown in Sect. 4.1 that the workload process of a fluid priority queue can be characterized by a Markovian fluid flow model. In Sect. 4.2, we are going to show that the time until the workload ahead of the tagged fluid drop is processed by the system is equal to the busy period duration of a special Markovian fluid flow model defined appropriately. Finally, the queue length analysis problem is translated to the analysis of the amount of reward accumulated over the busy period of this special Markovian fluid flow model.

Since each step of the solution relies on Markovian fluid flow models, the following section gives an overview of their stationary distribution and the behavior of the busy period.

Several numerical methods are available to solve (2) and (3), including the eigenvalue decomposition-based method [12], the Schur decomposition-based method [13] and the matrix-analytic method [4]. The subsequent sections of this paper rely heavily on the matrix-analytic solution of fluid models; thus, the rest of the section provides a short summary of this approach.

For the matrix-analytic method, the state space of the Markov chain has to be partitioned into three sets, \({\mathcal {S}}={\mathcal {S}}_+\cup {\mathcal {S}}_-\cup {\mathcal {S}}_0\), according to the sign of the fluid rates, i.e., \(\mathcal {S_+}=\{i\in {\mathcal {S}},c_i>0\}\), \(\mathcal {S_-}=\{i\in {\mathcal {S}},c_i<0\}\) and \({\mathcal {S}}_0=\{i\in {\mathcal {S}},c_i=0\}\). From now on, it is assumed that the matrices \(\mathbf {F}\) and \(\mathbf {C}\) are partitioned, and thus,where all diagonal entries of \(\mathbf {C}_+ = \text {diag}\langle c_i \rangle _{i\in {\mathcal {S}}_+}\) are positive and all diagonal entries of \(\mathbf {C}_- = \text {diag}\langle c_i \rangle _{i\in {\mathcal {S}}_-}\) are negative. Furthermore, let us introduce the matrix \(\mathbf {F}^\bullet \) as the generator of \({\mathcal {J}}(t)\) restricted to nonzero states, and hence,The stationary solution of the differential equation (2) and (3) has a matrix-exponential form, as proven in [4]. If the drift of the queue is negative, \(\vartheta \mathbf {C}\mathbb {1}<0\), the density function of the stationary fluid level can be expressed as:where the matrix \(\varvec{\Psi }\) is the minimal nonnegative solution of the non-symmetric algebraic Riccati equation (NARE)and the matrix \(\mathbf {K}\) is obtained byThe probability mass at level zero is \(p=\begin{bmatrix}0&p_-&p_0\end{bmatrix}\). The vectors \(\kappa \), \(p_-\) and \(p_0\) are the solutions of the linear equationswith the normalization condition

The duration of the busy period of fluid flow models, \(\tau =\inf (t>0: {\mathcal {A}}(t)=0)\), has been studied extensively in the literature: in [14] the Laplace–Stieltjes transform (LST) of its distribution is provided, and in [15] an Erlangization-based algorithm is described to approximate its distribution in the time domain. Both of these papers are based on matrix-analytic methods. (We note that the busy period of Markovian fluid flows can be analyzed with other methodologies as well, like with the spectral decomposition method, as in [16].)

In this section, we consider a more general problem. We assign a reward rate to each state of the background process and characterize the accumulated reward over the busy period of the fluid model. It turns out that the main performance measures of the fluid priority queue can be related to the accumulated reward over the busy period.

The introduction of reward accumulation makes the system three-dimensional, \(\{{\mathcal {A}}(t),{\mathcal {B}}(t),{\mathcal {J}}(t),t\ge 0\}\), where \({\mathcal {B}}(t)\) represents the reward accumulated up to time t. The reward accumulation is linear; thus, \({\mathcal {B}}(t) = \int _{0}^{t}d_{{\mathcal {J}}(u)}du\), where \(d_i\) denotes the reward rate associated with state i. Let us also introduce the diagonal matrix of reward rates \(\mathbf {D}=\text {diag}\langle d_i \rangle \). The joint distribution of the accumulated reward and the state transitions over the busy period is given by the matrix \(\varvec{\Phi }(y)\), defined asfor \(i\in {\mathcal {S}}_+, j\in {\mathcal {S}}_-\). Observe that in the special case of \(\mathbf {D}=\mathbf {I}\), the matrix \(\varvec{\Phi }(y)\) equals the distribution of the busy period duration starting with zero initial fluid level.

The following theorem, from [17], provides the LST of \(\varvec{\Phi }(y)\), defined by \(\varvec{\Phi }^*(v)=\int _{0}^\infty e^{-vy}\,d\varvec{\Phi }(y)\).

To obtain the moments of the performance measures of the fluid priority queue, the derivatives of the matrix \(\varvec{\Phi }^*(v)\) will be required at \(v\rightarrow 0\). Let us introduce the matrices \(\mathbf {F}_{ij}^{(m)}\) defined by \(\mathbf {F}_{ij}^{(m)}=\frac{\hbox {d}^m}{\hbox {d}v^m}\mathbf {F}^*_{ij}(v)|_{v\rightarrow 0}\) for \(i,j\in \{+,-\}\). The next theorem provides the derivatives of \(\varvec{\Phi }^*(v)\).

Appendix A describes how to obtain the matrix derivatives \(\mathbf {F}_{ij}^{(m)},~i,j\in \{+,-\}\) in detail.

The rest of this section focuses on the distribution of the reward accumulated over the busy period. Unfortunately, there are no exact solutions available to obtain \(\varvec{\Phi }(t)\). One can either rely on a generic numerical inverse Laplace transform (ILT) method to calculate it from \(\varvec{\Phi }^*(v)\), or, one can apply the Erlangization method to approximate it. Most numerical ILT algorithms have several well-known drawbacks: they require complex and high precision arithmetic, have convergence problems and are prone to over- and undershooting, meaning that they can result in negative or higher than 1 values instead of valid probabilities. The Erlangization method can be viewed as a special kind of ILT method as well. Compared to generic ILT methods, Erlangization is slower, in the sense that it needs more evaluations of \(\varvec{\Phi }^*(v)\) to achieve reasonable accuracy. On the other hand, it can be implemented using real, machine precision arithmetic and has no over- and undershooting problems; the result is always a valid probability. Additionally, Erlangization has an elegant stochastic interpretation, which can be exploited when tailored to specific problems. Below we present an Erlangization-based numerical method to approximate \(\varvec{\Phi }(t)\), following the approach of [15]. The basic algorithm in [15] is extended in two aspects: first, that paper studies the duration of the busy period, while we need the accumulated reward in this paper; second, zero rates are excluded in [15], while we need them here.

According to the Erlangization algorithm, the order-n approximation of the matrix \(\varvec{\Phi }(t)\) iswhere \(f_{{\mathcal {E}}(n,n/t)}(u)\) is an order-n Erlang density with rate parameter \(\nu =n/t\). As n tends to infinity, \(f_{{\mathcal {E}}(n,n/t)}(u)\) tends to a Dirac delta function \(\delta (u-t)\); hence, \(\varvec{\Phi }_{n}(t)\) tends to \(\varvec{\Phi }(t)\). The key idea behind Erlangization is that, by probabilistic interpretation, the integral in (15) is often easier to compute than \(\varvec{\Phi }(t)\) itself. In our case, the integral can be interpreted as the probability that the reward accumulated during the busy period is less than an Erlang\((n,\nu )\) variable.

As the first step of the analysis, the distribution of the total workload (also called backlog, unfinished work, or virtual waiting time in the literature) of classes \(\ge k\) is determined at class k fluid drop arrival instants. This is the amount of workload (and possibly more, due to further higher priority arrivals) that has to be accomplished before the tagged fluid drop can leave the system.

In non-fluid queues, where the jobs are discrete, the difference between the discrete-state queue length process and the continuous-state workload process is more obvious, but in the case of fluid queues both processes have continuous state space, and we will show that their dynamics are rather similar, too. Still, for the analysis of fluid priority queues, using the workload process is essential: it allows us to derive the performance measures from a process having only one continuous variable. Basing the analysis on the queue length process, we would need to solve a system with two continuous variables (the lengths of priority k and the priority \((k+1)+\) queues—since they are correlated), which is much more involved.

Let us denote the workload of classes \(\ge k\) at time t by \({\mathcal {V}}^{(k+)}(t)\). It is important to note that the workload is measured in time, and not in fluid level. \({\mathcal {V}}^{(k+)}(t)\) is the time needed by the system to accomplish all the work and become idle, given that no class \(\ge k\) fluid enters the queue after time t. \({\mathcal {V}}^{(k+)}(t)=0\) holds if and only if the class \(\ge k\) fluid level is zero, but in general the evolution of the workload process differs from the evolution of the fluid level process.

The joint density function of the workload and the state of the background process at time t is denoted by the row vector \(v^{(k+)}(t,x)\), whose elements are \(v^{(k+)}_i(t,x)=\frac{\hbox {d}}{\hbox {d}x}P({\mathcal {V}}^{(k+)}(t)\le x,{\mathcal {J}}(t)=i)\). The joint probability that the workload of the system is 0 and the state of the background process is i is stored by the row vector \(\alpha ^{(k+)}(t)=[\alpha ^{(k+)}_i(t)]\), where \(\alpha ^{(k+)}_i(t)=P({\mathcal {V}}^{(k+)}(t)=0,{\mathcal {J}}(t)=i)\).

Lemma 1 has an important corollary: the workload process behaves like an ordinary Markovian fluid flow model with parametersthus, its stationary density, \(v^{(k+)}(x)=\lim _{t\rightarrow \infty }v^{(k+)}(t,x)\), and probability mass at zero, \(\alpha ^{(k+)}=\lim _{t\rightarrow \infty }\alpha ^{(k+)}(t)\), are given by the matrix-exponential formwhere the vectors \(\kappa ^{(k+)}, p^{(k+)}\) and the matrices \(\mathbf {K}^{(k+)},\mathbf {A}^{(k+)}\) are given by (6)–(10) with parameters (21). Hence, the density of the workload and the probability mass at zero embedded at class k fluid drop arrival instants are

As described in Sect. 2, the waiting time of a fluid drop is equal to the workload found in the system at its arrival, increased by the higher priority workload brought to the system while waiting.

Figure 1 shows an example for the evolution of the remaining waiting time process of a class k fluid drop, \({\mathcal {W}}^{(k)}(t,x)\), where the arriving fluid drop found x amount of class \(k+\) workload in the system. In the time periods where the curve is drawn with a solid line, the background process is in a state where \(r_{{\mathcal {J}}(t)}^{((k+1)+)}=0\) and there is no class \((k+1)+\) workload in the system either; hence, all the server capacity is spent on class k, and the remaining waiting time decreases with slope \(-1\). In the intervals where the curve is dashed, class \((k+1)+\) fluid is also present, and the service capacity is either fully taken by the higher priority classes, or, if their incoming rate is less than d and there is no high priority fluid accumulated in the buffer, it is shared between class k and the higher priority classes. While Fig. 1 depicts the remaining waiting time of a class k fluid drop, we can observe that it follows the same trajectory as the class \((k+1)+\) workload process, \({\mathcal {V}}^{((k+1)+)}(t)\), given that \({\mathcal {V}}^{((k+1)+)}(0)=x\).

Let \({\mathcal {T}}\) denote the random variable representing the waiting time of class k fluid drops. (For the sake of simplicity, we neglect the superscript (k) for \({\mathcal {T}}\) in this section.) By conditioning on the amount of class \(k+\) workload at a class k fluid drop arrival, we have thatwith \(\mathbf {G}^{((k+1)+)}(y,x)\) being the distribution of the busy period of the class \((k+1)+\) workload starting at level x, defined bywhere \(\tau ^{((k+1)+)} =\inf (t>0: {\mathcal {V}}^{((k+1)+)}(t)=0)\) is the first time point when the workload process reaches level 0.

To get rid of the integral, we apply a transformation that transforms the analysis problem of the class k waiting time to the analysis problem of the accumulated reward of an appropriately constructed fluid flow model over a busy period. The main idea (introduced in [18]) is to start this fluid model at level 0 and add a phase whose role is to set the fluid level according to the initial workload at class k fluid arrival, having density \({\hat{v}}^{(k)}(x)\) (Fig. 2). The main benefit of this transformation is that it makes it possible to use the results of Sect. 3.2, where the busy period with 0 initial level is characterized.

The generator of the background process, the fluid rates and the reward rates of this special fluid flow model areThe first state group of the background process is responsible for the accumulation of the workload a class k fluid drop finds in the system upon its arrival. Observe that the probability density of the time spent here equals \(e^{\mathbf {K}^{(k+)}t}\mathbf {A}^{(k+)}\mathbf {R}^{(k)}/\lambda ^{(k)}\), which, when started from the vector \(\kappa ^{(k+)}\), equals \({\hat{v}}^{(k)}(t)\), according to (23). (Remember that \(\kappa ^{(k+)}\) is the initial vector of the stationary solution of the workload process; see (23).) While staying in this state group the workload increases with rate 1 (hence the \(\mathbf {I}\) matrix in the first block of \(\mathbf {C}\)), and during this period no reward is accumulated, since the time spent here is not part of the waiting time. (There is a \(\mathbf {0}\) in the corresponding block in the matrix \(\mathbf {D}\).)

When the appropriate workload level is reached, a transition occurs to the second group of states. In this part, the fluid level in this special model represents the workload of the system ahead of the tagged class k fluid drop. If class k has the highest priority in the system, then the workload ahead of the tagged fluid drop decreases linearly by rate 1. If there is higher priority work, class \((k+1)+\) fluid flows in the system, then the workload brought by them increases the workload ahead of the tagged class k fluid drop. The rate at which the workload changes during this period is given by the diagonal elements of \(\frac{1}{d}\mathbf {R}^{((k+1)+)}-\mathbf {I}\). The reward rate is 1 in each state of the modulating CTMC; thus, the reward measures the time spent in this part of the state space. The time spent until the workload ahead of the tagged fluid drop reaches level 0 is identical to the waiting time.

Consequently, the waiting time is equal to the amount of reward accumulated during the busy period, starting from the first state group; thus, the initial phase distribution vector isBased on the above reasoning, we can state the following corollary.

In (29), the first term \({\hat{\alpha }}^{(k)}\mathbb {1}\) reflects that the waiting time is zero if the workload is zero when the fluid drop arrives.

The approach for characterizing the amount of class k fluid in the system at class k fluid drop departures is similar to the one presented in Sect. 4.2. A special Markov-modulated fluid model is constructed such that the reward accumulated during its busy period is equal to the queue length at departures. The matrices defining this special fluid model areObserve that these matrices are similar to (25), and the interpretation is similar as well. The first state group sets the initial workload seen by a class k fluid drop arrival. The second state group follows the workload ahead of the fluid drop until it leaves the system. With the given reward rate matrix \(\mathbf {D}\), however, the reward accumulated over the busy period measures the amount of class k fluid that arrives until the tagged fluid drop leaves; hence, it provides the class k queue length at the departure of the tagged class k fluid drop.

The first term in (33), \({\hat{\alpha }}^{(k)}\), is the probability that the class \(k+\) workload is zero at a class k fluid drop arrival, implying that the queue length is zero, too.

In the case of non-fluid queues with discrete customers, the relation between the queue length distribution at departures and at random point in time is known [19]. For fluid queues, however, such a result is not available in the literature.

Let \({\mathcal {Y}}\) denote the class k queue length at random point in time. The density function, the distribution function and the probability mass at level 0 are denoted by \(f_{\mathcal {Y}}(x), F_{\mathcal {Y}}(x)\) and \(p_{\mathcal {Y}}\), respectively. The following theorem establishes a relationship between the density and distribution functions of \({\mathcal {X}}\) and \({\mathcal {Y}}\). Before stating the theorem, we introduce the vector forms of these quantities that include the state of the background process as well, characterizing \(\lim _{t\rightarrow \infty }\{{\mathcal {Y}}(t),{\mathcal {J}}(t)\}\). These row vector quantities are defined by \([\underline{F_{\mathcal {Y}}}(x)]_i=\lim _{t\rightarrow \infty } P({\mathcal {Y}}(t)<x,{\mathcal {J}}(t)=i), \underline{f_{\mathcal {Y}}}(x)=\frac{\hbox {d}}{\hbox {d}x}\underline{F_{\mathcal {Y}}}(x)\), and \([\underline{p_{\mathcal {Y}}}]_i=\lim _{t\rightarrow \infty } P({\mathcal {Y}}(t)=0,{\mathcal {J}}(t)=i)\).

It is worth noting that (35) is the continuous counterpart of [21, Theorem 5], while the derivative of (34) is the one of [21, Theorem 6]. The relation between \({\mathcal {X}}\) and \({\mathcal {Y}}\) in the Laplace transform domain, given by the following corollary, is similar to the result obtained for discrete-state (non-fluid) queues in [21, Equation (30)].

Next, the class k queue length moments are derived based on the ones embedded at departure epochs. The moments are obtained by taking the derivatives of the LST, i.e.,The following theorem (which is the continuous counterpart of [21, Section 4.1]) provides a recursive algorithm to compute the vectors \(y^{(m)}\).

With the theorems and corollaries presented above, it is possible to compute the LST and the moments of the queue length distribution. Finally, it remains to obtain the order-n approximation of the class k queue length distribution in the time domain, \(F^{(n)}_{\mathcal {Y}}(x)\), based on Erlangization.

Assume that the order-n approximation of the queue length distribution at fluid drop departures is available in the form of (33), \(F^{(n)}_{\mathcal {X}}(x) = {\hat{\alpha }}^{(k)}\mathbb {1} + {\hat{\kappa }}^{(k)}\varvec{\Phi }_{n}(x)\mathbb {1}\), where \(\varvec{\Phi }_{n}(x) = \sum _{\ell =0}^{n-1}{\hat{\varvec{\Psi }}}_\ell (n/x)\) (as given in (16)). The following theorem demonstrates how to obtain the approximation of \(F^{(n)}_{\mathcal {Y}}(x)\) from the same \({\hat{\varvec{\Psi }}}_\ell (n/x)\) matrices.

In the first example, there are three fluid types and the background process has four states. The generator of the CTMC and the fluid input rates in various states are given by the matricesand the service rate is \(d=4\). With these parameters, the utilization of the system is \(\lambda /d = 0.875\).

The algorithms returned the waiting time and queue length moments without a measurable delay. For the numeric results, see Table 1.

Obtaining the distributions is, however, more demanding computationally. The accuracy and the execution speed depend on how many terms are taken into account during the Erlangization. Our experience is in line with the earlier reports (see [15]), namely that Erlangization is able to provide relatively accurate results with a small number of terms (the parameter n). Figure 3 depicts the distribution functions of class 1 waiting times for different values of n. For \(n=10\), the approximation has some visible error, but the approximate distribution functions for \(n\ge 25\) are almost indistinguishable from each other.

Profiling this example revealed that the bottleneck of the Erlangization algorithm is the computation of the twofold summation at line 5 in (17). This term, however, is zero when the workload process of class 2 and 3 jobs does not have zero rates. The workload process does have a zero rate in this example, since in state 3 we have \(r_3^{(2)} + r_3^{(3)} = d\). Changing \(r_3^{(2)}\) to a value different from 4 eliminated the zero state, leading to an order of magnitude faster execution times² (Table 2).

The aim of the second example is to demonstrate how the speed of the algorithms scales with the size of the input. Let us define the model as the superposition of N identical on–off sources with exponentially distributed on and off periods, with transition rates denoted by \(\nu \) and \(\gamma \), respectively. Each source generates fluid with rate \(\rho /N\) while being in the on state. The matrix parameters of the superposed fluid model are given bywhere N determines the size of the model. The matrix \(\mathbf {Q}_N\) is the generator of the background process, and the matrix \(\mathbf {R}_N\) is the diagonal matrix of the overall fluid rates. If we assume that \(10\%\) of the fluid generated by the sources is class 1 fluid, \(30\%\) is class 2 fluid and \(60\%\) is class 3 fluid, the per class fluid input rates are \(\mathbf {R}_N^{(1)}=0.1\cdot \mathbf {R}_N, \mathbf {R}_N^{(2)}=0.3\cdot \mathbf {R}_N\) and \(\mathbf {R}_N^{(3)}=0.6\cdot \mathbf {R}_N\).

In this example, the parameters are \(\nu =1/N\) and \(\gamma =1/(3N)\) (the reason for making them dependent on N is to keep the values of the generator in the same range irrespective of the size), and the fluid rate parameter is \(\rho =50\). With these settings, the mean fluid arrival rate is \(\lambda =12.5\).

We have computed the first five moments of the queue length of all job classes with different model sizes (controlled by the parameter N) and with different utilizations u (controlled by the service rate \(d=\lambda /u\)). The execution times are depicted in Fig. 4, which reports the average of multiple repetitions for every point, together with the bootstrap-t confidence intervals (that are very tight).

As visible in the figure, the presented algorithms are able to solve huge models with 1000 states in reasonable time, without any numerical problems. The execution times depend on the utilization as well, since this affects the number of positive and negative states. At low utilization, obtaining five moments of the queue length for all job classes requires \(10\,s\) for \(N=1000\), while at high utilization about \(40\,s\) are required for the largest model.