Queueing Theory (M/M/1 with priorities)

[TaPaKaH]

Homework Statement

Suppose we have two types of customers, whose interarrival times are exponentially distributed with parameters $\lambda_1$ and $\lambda_2$.
These customers have to share one server that gives preemptive priority to customers of type 1.
The service times are exponentially distributed with parameters $\mu_1$ and $\mu_2$.

How can one compute the fraction of time, during which there are no type 1 customers in server+queue given that there is exactly one type 2 customer in server+queue?

The Attempt at a Solution

I tried to approach the problem via balance equations for the number of type 1 customers, but couldn't figure out a way to implement "having exactly one type 2 customer" into the transition rates.

 

[Ray Vickson]

Homework Statement

Suppose we have two types of customers, whose interarrival times are exponentially distributed with parameters $\lambda_1$ and $\lambda_2$.
These customers have to share one server that gives preemptive priority to customers of type 1.
The service times are exponentially distributed with parameters $\mu_1$ and $\mu_2$.

How can one compute the fraction of time, during which there are no type 1 customers in server+queue given that there is exactly one type 2 customer in server+queue?

The Attempt at a Solution

I tried to approach the problem via balance equations for the number of type 1 customers, but couldn't figure out a way to implement "having exactly one type 2 customer" into the transition rates.

You need to show your work: what are the balance equations you tried to use?

 

[TaPaKaH]

The unconditioned number of type 1 customers in the system is a Markov chain with the following transition rates:

This yields balance equations $p_n=\left(\frac{\lambda_1}{\mu_1}\right)p_{n-1}$ that are easy to solve.

But, when we condition on there being exactly one type 2 customer, the "observation periods" have different lengths (which is ~$exp(\lambda_2)$ for $p_n,n\in\mathbb{N}$ until another customer of type 2 arrives and ~$exp(\lambda_2+\mu_2)$ for $p_0$ until either another type 2 customer arrives or current type 2 customer goes through their service) and might not start at "random times", which is causing me problems.

 

[Ray Vickson]

The unconditioned number of type 1 customers in the system is a Markov chain with the following transition rates:

This yields balance equations $p_n=\left(\frac{\lambda_1}{\mu_1}\right)p_{n-1}$ that are easy to solve.

But, when we condition on there being exactly one type 2 customer, the "observation periods" have different lengths (which is ~$exp(\lambda_2)$ for $p_n,n\in\mathbb{N}$ until another customer of type 2 arrives and ~$exp(\lambda_2+\mu_2)$ for $p_0$ until either another type 2 customer arrives or current type 2 customer goes through their service) and might not start at "random times", which is causing me problems.

This transition diagram does not include any type-2 customers. I think you need a 2-dimensional diagram with nodes of the form (i,j), i = number of type 2 present and j = number of type 1. You have drawn the diagram for the first "row" (0,j), j = 0,1,2, ... .

 

[TaPaKaH]

Two-dimensional diagram is what I initially started with but it eventually reduced to this, which I thought might be "easier" to solve.

 

[Ray Vickson]

/

Two-dimensional diagram is what I initially started with but it eventually reduced to this, which I thought might be "easier" to solve.

"Easier" ≠ "correct". The type-2 customers make an important contribution to the system: for example, if $\lambda_2 / \mu_2 > 1$ the system will be unstable (having no finite steady-state distribution) even though the type-1 queue might be stable, with $\lambda_1 / \mu_2 < 1$.

 

[Ray Vickson]

/

"Easier" ≠ "correct". The type-2 customers make an important contribution to the system: for example, if $\lambda_2 / \mu_2 > 1$ the system will be unstable (having no finite steady-state distribution) even though the type-1 queue might be stable, with $\lambda_1 / \mu_2 < 1$.

Just to clarify: assuming a stable system and states of the form (i,j), where i = number of type-2 customers present in the system, and j = number of type-1, the two-dimensional transitition diagram can be analyzed using principles of balance, to conclude that the quantities
p_j = \sum_{i=0}^{\infty} \pi_{i,j}
do, indeed satisfy $\lambda_1 p_j = \mu_1 p_{j+1}$, giving $p_0 = 1/(1-\rho_1)$ and $p_j = {\rho_1}^j\, p_0, \; j = 1, 2, \ldots .$ Here, $p_j$ is the equilibrium probability that there are $j$ type-1 customers present in the system (in queue + in service). However, in terms of the 2-dimensional state space (i,j), you are asked to compute $P(j=0|i=1)$.

 

[TaPaKaH]

Well, the global balance equations system is as follows$$\begin{cases}\begin{array}{rl}(\lambda_1+\lambda_2)p_{0,0}=\mu_2p_{0,1}+\mu_1p_{1,0}\\(\lambda_1+\lambda_2+\mu_1)p_{i,0}=\lambda_1p_{i-1,0}+\mu_1p_{i+1,0}&i\in\mathbb{N}\\(\lambda_1+\lambda_2+\mu_2)p_{0,j}=\lambda_2p_{0,j-1}+\mu_2p_{0,j+1}+\mu_1p_{1,j}&j\in\mathbb{N}\\(\lambda_1+\lambda_2+\mu_1)p_{i,j}=\lambda_1p_{i-1,j}+\lambda_2p_{i,j-1}+\mu_1p_{i+1,j}&(i,j)\in\mathbb{N}^2\end{array}\end{cases}$$In addition, we have the normalisation $\sum_{i,j=0}^\infty p_{i,j}=1$ and from analysis of queue 1 that doesn't "see" queue 2 we have $\sum_{j=0}^\infty p_{i,j}=\left(1-\frac{\lambda_1}{\mu_1}\right)\left(\frac{\lambda_1}{\mu_1}\right)^i$ for $i\in\mathbb{N}_0$.
But I still can't see how this whole system could be explicitly solved to obtain $p_{i,j}$ and $p_{0,1}$ in particular.

 

[Ray Vickson]

Well, the global balance equations system is as follows$$\begin{cases}\begin{array}{rl}(\lambda_1+\lambda_2)p_{0,0}=\mu_2p_{0,1}+\mu_1p_{1,0}\\(\lambda_1+\lambda_2+\mu_1)p_{i,0}=\lambda_1p_{i-1,0}+\mu_1p_{i+1,0}&i\in\mathbb{N}\\(\lambda_1+\lambda_2+\mu_2)p_{0,j}=\lambda_2p_{0,j-1}+\mu_2p_{0,j+1}+\mu_1p_{1,j}&j\in\mathbb{N}\\(\lambda_1+\lambda_2+\mu_1)p_{i,j}=\lambda_1p_{i-1,j}+\lambda_2p_{i,j-1}+\mu_1p_{i+1,j}&(i,j)\in\mathbb{N}^2\end{array}\end{cases}$$In addition, we have the normalisation $\sum_{i,j=0}^\infty p_{i,j}=1$ and from analysis of queue 1 that doesn't "see" queue 2 we have $\sum_{j=0}^\infty p_{i,j}=\left(1-\frac{\lambda_1}{\mu_1}\right)\left(\frac{\lambda_1}{\mu_1}\right)^i$ for $i\in\mathbb{N}_0$.
But I still can't see how this whole system could be explicitly solved to obtain $p_{i,j}$ and $p_{0,1}$ in particular.

This is not an easy problem. Perhaps you can try to use multi-dimensional generating function methods, in which you use the balance equations to obtain the mgf
M(u,v) = \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} p_{i,j} u^i v^j
You can look at this as either
M(u,v) = \sum_{i=0}^{\infty} B_i(v) u^i, \text{ where } <br /> B_i(v) = \sum_{j=0}^{\infty} p_{i,j} v^j
or as
M(u,v) = \sum_{j=0}^{\infty} A_j(u) v^j, \text{ where }<br /> A_j(u) = \sum_{i=0}^{\infty} p_{i,j} u^i
The balance equations might yield a solution for M(u,v) in terms of some undetermined constants, which could then be determined by using auxiliary information about system stability, etc. It might work; try it and see.

Another approach you might try is to look at the system from the point of view of type-2 customers. They see an M/M/1 queue with server 'vacations'. Vacations are periods during which the server is unavailable = times when it is serving customers of type-1. However, unlike many vacational queueing models, this one let's the server abandon service (to start a vacation) during the service of a customer (if a type-1 arrival kicks out the type-2 customer); most vacational queueing models allow the current service to be completed before the server goes on vacation. Anyway, the length of a server vacation is equal to the busy period of the M/M/1 queue for type-1 customers; this random variable (busy period length) has a complicated, non-exponential distribution involving Bessel functions, although its Laplace transform is not too bad.

Another, related approach is to note that the service time of a type-2 customer will be some very complicated thing consisting of a sum of iid exponentials and a random number of iid type-1 busy periods. (This corresponds to a number if iid exponential attempts, plus a number of type-1 busy periods during our poor type-2 customer is told to go and wait.) I think it might be possible to get the Laplace transform of the type-2 customer service time, and if so, the problem for type-2 customers becomes a simple M/G/1 queue with a horribly complicated service time distribution. However, getting from there to anything like a distribution of the number of type-2 customers present still seems difficult.

 

[TaPaKaH]

I tried the second approach: the busy period $BP$ for type-1 customers has the following Laplace-Stieltjes transform: $\tilde{BP}(s)=\frac{\lambda_1+\mu_1+s-\sqrt{(\lambda_1+\mu_1+s)^2-4\lambda_1\mu_1}}{2\lambda}$ so we can indeed model the type-2 queue as a queue, in which server uptimes are i.i.d. ~$\exp(\lambda_1)$ and downtimes have LST above. However, this didn't yield any progress as computing type-2 distribution was too technically difficult.

I will try the first approach you suggested and see what comes out of it.

 

[Ray Vickson]

I tried the second approach: the busy period $BP$ for type-1 customers has the following Laplace-Stieltjes transform: $\tilde{BP}(s)=\frac{\lambda_1+\mu_1+s-\sqrt{(\lambda_1+\mu_1+s)^2-4\lambda_1\mu_1}}{2\lambda}$ so we can indeed model the type-2 queue as a queue, in which server uptimes are i.i.d. ~$\exp(\lambda_1)$ and downtimes have LST above. However, this didn't yield any progress as computing type-2 distribution was too technically difficult.

I will try the first approach you suggested and see what comes out of it.

I found the following (free) paper that does all this:
http://arxiv.org/ftp/arxiv/papers/0902/0902.2086.pdf

It uses the 2-dimensional state space and finds the bivariate mgf. I have not checked it for correctness.

Note added in edit: I checked more carefully, and see that the above paper assumes $\mu_1 = \mu_2$, although $\lambda_1, \lambda_2$ may differ. Also: the priority is non-preemptive. So, the your case has still not been done, but the paper perhaps points out a way of getting started, and the types of arguments that may be involved.