A Stochastic Fluid Model Approach to the Stationary Distribution of the Maximum Priority Process

Consider a single-server queue with Poisson arrivals such that customers of class $i=1,2$ arrive to the queue at rate $\lambda_{i}>0$. Service times of different customers are independent of each other and of the arrival process, and are distributed according to some generic random variable $X$;also, let $X_{n}$ be the service time of the $n^{th}$ arriving customer. We assume that the system is stable.

Upon arrival to the queue, a customer of class $i$ starts accumulating priority at rate $b_{i}>0$. We assume $b_{1}>b_{2}$, so that class $1$ customers accumulate priority at a higher rate than class $2$ customers. After completion of a service, the server starts serving the customer with the highest accumulated priority, regardless of their class.

Let $\gamma_{n}$ denote the time of the $n^{th}$ arrival, and let $\chi(n)$ be the customer class of the $n^{th}$ arrival. Then we define the accumulated priority function $V_{n}(t)$ by

$\displaystyle V_{n}(t)=b_{\chi(n)}[t-\gamma_{n}]^{+}.$

(1)

Thus, $V_{n}(t)$ denotes the priority accumulated by the $n^{th}$ customer up to time $t$. Note that $b_{\chi(n)}$ is the rate of the $n^{th}$ arriving customer. Also note that if the $n^{th}$ customer arrived after time $t$, that is when $\gamma_{n}>t$, then the accumulating priority at time $t$ is set to $0$.

Let $n(m)$ be the function recording the position in the arrival sequence of the $m^{th}$ customer to be served. For example, if the third customer to be served was the fourth arrival then $n(3)=4$.

Let $C_{n}$ be the time at which the $n^{th}$ arrival starts service and $D_{n}$ be the departure time of this customer, with clearly $D_{n}=C_{n}+X_{n}$. The time at which the $m^{th}$ customer commences service is therefore $C_{n(m)}$ and the departure time of this customer is $D_{n(m)}$. For an illustration, see Figure 1 where five arrivals are shown with their corresponding start-of-service times $C_{n(m)}$ and departure times $D_{n(m)}$ for $m=1,2,\ldots,5$, and their accumulated priority functions $V_{n(m)}(t)$ starting in 0 at $t=\gamma_{n(m)}$ and increasing at rate $b_{\chi(n(m))}$ (the meaning of $V(t)$ will be given shortly).

After departure of a customer there are two possibilities. Either the queue is empty, or the queue is non-empty and the customer with the highest priority commences service. Thus

$\displaystyle n(m+1)=\text{min}\{\text{arg max}_{n\notin\{n(k)\ :1\leq k\leq m\}}V_{n}(D_{n(m)})\},$

(2)

where we use the minimum function to account for the possibility that the set in (2) contains more than one element, though the probability of this occurring is $0$.

Finally we define the accumulating priority process $\{V(t):t\geq 0\}$ by

$$V(t)=V_{n(m^{*}(t))}(t),$$

where $m^{*}(t)=\max\{m:D_{n(m)}\leq t\}+1$ i.e., $V(t)$ is the priority of the customer being served at time $t$, or 0 if there are no customers present at time $t$.

In this section we describe the maximum priority process $\{(M_{1}(t),M_{2}(t)):t\geq 0\}$, as defined in [9], that corresponds to the accumulating priority queue of Section 2.1. This process records for each time $t$ the least upper bounds $M_{1}(t)$ and $M_{2}(t)$ on the accumulated priority of any customers of classes $1$ and $2$ that might be present in the system, given the history of the process up to the time at which the customer in service entered service (i.e., up to the last departure before time $t$). An example, corresponding to Figure 1, of a sample path of the maximum priority process $\{(M_{1}(t),M_{2}(t)):t\geq 0\}$ is shown in Figure 2, where we observe that $M_{1}(t)$ and $M_{2}(t)$ grow at class-dependent rates during service, with $M_{1}(t)$ always and $M_{2}(t)$ possibly observing a downward jump at a service completion. The figure may prove helpful when reading the following recursive definition, and the explanation that follows.

From this definition it is clear that between jumps $M_{1}(t)$ and $M_{2}(t)$ indeed increase at rates $b_{1}$ and $b_{2}$ respectively, unless the queue is empty. We will now consider the service completions in some more detail. It is clear that $M_{1}(t)$ always makes a downward jump, since the accumulated priority of the departing customer is always higher than that of the next customer to be served. On the other hand, for $M_{2}(t)$ there are two possibilities since this may experience a downward jump, or it may not, depending on whether the next customer to be taken into service is, in the terminology of [9], ‘accredited’ or not. In fact we will distinguish three different types of behaviour at departure times, as follows.

Type 1 jump: the next customer to be served is ‘accredited’, meaning its current priority lies in $[M_{2}(t^{-}),M_{1}(t^{-}))$. In this case $M_{2}(t)$ remains unchanged, while $M_{1}(t)$ jumps down to the current priority of the (accredited) customer who is currently taken into service, since other class 1 customers can at most have accumulated this amount of priority. Notice that in this case the (accredited) customer taken into service can only be of class 1 (since all class 2 customers have current priority $<M_{2}(t^{-})$). An example can be seen in Figure 2 at the second departure (at time $t=D_{n(2)}$).

Type 2 jump: the next customer to be served is ‘unaccredited’, which means its current priority lies in $[0,M_{2}(t^{-}))$. In this case some customers are still present in the queue, but all of them have a current priority lower than the priority of the next (unaccredited) customer who is currently taken into service, and therefore lower than the value of $M_{2}(t^{-})$. Thus, both $M_{1}(t)$ and $M_{2}(t)$ make a downward jump to the current priority of the customer taken into service. This customer can be either of class 1 or of class 2. Examples can be seen in Figure 2 at respectively the first departure (at time $t=D_{n(1)}$) and the third departure (at time $t=D_{n(3)}$).

Type 3 jump: the next customer to be served is not present yet. In this case the queue is empty after the departure, so an idle period starts and both $M_{1}(t)$ and $M_{2}(t)$ are set to the value 0 where they will stay until the next busy period starts. An example can be seen in Figure 2 at the fourth departure (at time $t=D_{n(4)}$).

We summarize the behaviour of the maximum priority process $\{(M_{1}(t),M_{2}(t)):t\geq 0\}$ by giving a graphic illustration of the state space and a sample path, see Figure 3. The grey area indicates the states that can possibly be visited by $\{(M_{1}(t),M_{2}(t)):t\geq 0\}$, when the process starts from the origin (i.e., when the queue starts empty). The depicted sample path is the same as (the first part of) that in Figure 2. The dashed parts correspond to downward jumps, which are instantaneous; here the first downward jump is of type 2 and the second one is of type 1. A jump of type 3 is not depicted, but would be similar to the jump of type 2, with the dashed line extending to the origin.

Our goal is to find the stationary distribution of the process $\{({M_{1}}(t),{M_{2}}(t)):t\geq 0\}$ embedded at times right after a jump. From Figure 3 we see that at such times the process can only be in the (shaded) set $\mathcal{F}=\{(m_{1},m_{2}):0<m_{2}<m_{1}<m_{2}b_{1}/b_{2}\}$, or on the semi-line $\mathcal{G}=\{(m_{1},m_{2}):m_{1}=m_{2}>0\}$, or at the origin. Therefore, this stationary distribution can be given in terms of a two-dimensional density function $f$ on $\mathcal{F}$, a one-dimensional density $g$ on $\mathcal{G}$ and a point mass $h$ in $(0,0)$. In order to find the densities $f$ and $g$ and the probability $h$ in the next section, we define

$$\widetilde{M}_{1}(t)=M_{1}(t)-M_{2}(t),$$

(3)

and work with the transformed process $\{(\widetilde{M}_{1}(t),M_{2}(t)):t\geq 0\}$, see Figure 4.

Let $\{\varphi(t):t\geq 0\}$ be the background continuous-time Markov chain with state space $\mathcal{S}=\{+,-\}$, where state $+$ is referred to as the up-phase, and state $-$ as the down-phase. In our mapping, these phases correspond to the service time and the jump down in the process $\{(M_{1}(t),M_{2}(t)):t\geq 0\}$ of Section 2, respectively. The generator of this chain is assumed to be

$${\bf T}=\left[\begin{array}[]{cc}-\mu&\mu\\ 1&-1\end{array}\right].$$

(6)

Note that the distribution of the time spent in phase $+$ is the same as the distribution of the service time in the process $\{(M_{1}(t),M_{2}(t)):t\geq 0\}$.

To this end we choose the fluid rates of the tandem fluid queue as follows (note that defining $\check{c}_{+}$ is not needed),

	$\displaystyle r_{+}$	$\displaystyle=b_{1}-b_{2},$	$\displaystyle\hat{c}_{+}$	$\displaystyle=b_{2},$				(7)
	$\displaystyle r_{-}$	$\displaystyle=-\left(\frac{\lambda_{1}}{b_{1}}\right)^{-1},$	$\displaystyle\hat{c}_{-}$	$\displaystyle=0,$	$\displaystyle\check{c}_{-}$	$\displaystyle=-\left(\frac{\lambda_{1}}{b_{1}}+\frac{\lambda_{2}}{b_{2}}\right)^{-1}.$		(8)

As a result we have the following.

Let the service times now have a phase type distribution $\sim PH(\mathcal{S}_{+},{\bf\mbox{\boldmath$\alpha$}},{\bf T}_{++}),$ where $\mathcal{S}_{+}$ is the phase space of the phase type distribution for the service times, and $\alpha$ and ${\bf T}_{++}$ are the corresponding intitial distribution and generator, respectively. To specify the fluid tandem model we first let $\mathcal{S}=\mathcal{S}_{+}\cup\mathcal{S}_{-}$ where $\mathcal{S}_{-}=\{-\}$. Thus, as before we have a single ‘down phase’, but we now have multiple up-phases.

The generator matrix T of the process $\{\varphi(t):t\geq 0\}$ on $\mathcal{S}$ is given in block matrix form as

$${\bf T}=\left[\begin{array}[]{cc}{\bf T}_{++}&{\bf T_{+-}}\\ {\bf T}_{-+}&{\bf T_{--}}\end{array}\right]$$

(9)

where ${\bf T}_{++}$ is as just introduced, ${\bf T}_{+-}=-{\bf T_{++}1}$, ${\bf T}_{-+}={\bf\mbox{\boldmath$\alpha$}}$, and and ${\bf T_{--}}=-1$. For the fluid rates we have the same values as before but now in matrix form. Writing $I$ for the $|\mathcal{S}_{+}|\times|\mathcal{S}_{+}|$ identity matrix we have

	$\displaystyle{\bf R}_{+}$	$\displaystyle=r_{+}I=(b_{1}-b_{2})I,$	$\displaystyle\widehat{\bf C}_{+}$	$\displaystyle=\hat{c}_{+}I=b_{2}I,$		(10)
	$\displaystyle{\bf R}_{-}$	$\displaystyle=\ r_{-}\ =-\left(\frac{\lambda_{1}}{b_{1}}\right)^{-1},\ \quad$	$\displaystyle\widehat{\bf C}_{-}$	$\displaystyle=\ \hat{c}_{-}\ =0,\qquad$		(11)
	$\displaystyle{\mathchoice{{\ooalign{\hbox{\raise 7.09259pt\hbox{\scalebox{1.0}[-1.0]{\lower 7.09259pt\hbox{$\displaystyle\widehat{\vrule width=0.0pt,height=6.83331pt\vrule height=0.0pt,width=7.22223pt}$}}}}\cr\hbox{$\displaystyle\bf C$}}}}{{\ooalign{\hbox{\raise 7.09259pt\hbox{\scalebox{1.0}[-1.0]{\lower 7.09259pt\hbox{$\textstyle\widehat{\vrule width=0.0pt,height=6.83331pt\vrule height=0.0pt,width=7.22223pt}$}}}}\cr\hbox{$\textstyle\bf C$}}}}{{\ooalign{\hbox{\raise 6.40926pt\hbox{\scalebox{1.0}[-1.0]{\lower 6.40926pt\hbox{$\scriptstyle\widehat{\vrule width=0.0pt,height=4.78333pt\vrule height=0.0pt,width=5.05556pt}$}}}}\cr\hbox{$\scriptstyle\bf C$}}}}{{\ooalign{\hbox{\raise 5.9537pt\hbox{\scalebox{1.0}[-1.0]{\lower 5.9537pt\hbox{$\scriptscriptstyle\widehat{\vrule width=0.0pt,height=3.41666pt\vrule height=0.0pt,width=3.61111pt}$}}}}\cr\hbox{$\scriptscriptstyle\bf C$}}}}}_{-}$	$\displaystyle=\check{c}_{-}=-\left(\frac{\lambda_{1}}{b_{1}}+\frac{\lambda_{2}}{b_{2}}\right)^{-1}.$				(20)

One can now easily verify that the following holds.

This enables us to find the stationary distribution i.e. the densities $f$ on $\mathcal{F}$, $g$ on $\mathcal{G}$, and the point mass $h$ in $(0,0)$.