2
$\begingroup$

I am studying queueing theory and in particular I am dealing with priority queues with preemption.

I found this very interesting paper that treats various topics of interest.

The system is composed of two queues and only one service. One of the two queues has higher priority and preempt the other. So the competition time of a job on the lower queue is:

$$C = S + \sum_{i=0}^{N}S'(i) + \sum_{i=0}^{N}D(i)$$ where $S$ is the service time without interruption from the higher priority jobs, $D$ is the duration of the interruption and $S'$ is the portion of a potential service time duration (since after the interruption, the job begins from the begin and a new independent service time is added).

The server has a service time $S$.

The jobs with higher priority appear with a Poisson process with rate $\upsilon$

In the paper the expected value of the competition time is: $$ E(C) = (E(e^{\upsilon S})-1 )(E(D) + \frac{1}{\upsilon})$$

where $E(D)$ is known.

My problem is with $E(e^{\upsilon S})-1$ . In my calculations, $S$, the service time, is a random variable like $\lambda e^{-\lambda x} \frac{1}{C}$, since the jobs length is exponential and where $C$ is the server speed.

To compute the expected value I used this formula (present in my notes): given X a RV and Y = g(X), then $E[Y] = E[g(X)] = \int_{-\infty}^{\infty}g(x)f(x) dx$, so $$ \int_{0}^{\infty}e^{\upsilon x}\lambda e^{-\lambda x}\frac{1}{C} dx = \frac{1}{C}\frac{\lambda}{\lambda -\upsilon}$$since $\upsilon - \lambda < 0$. But this quantity, given fixed values for $\upsilon, \lambda$ and $C$ is less than $1$ so the final result would be negative!

Where am I wrong?

$\endgroup$
  • $\begingroup$ It's not at all clear why the expectation should exist in the first place. You're implicitly assuming that $v-\lambda<0$ to make the calculation. Are you sure about the form of $S$'s distribution? $\endgroup$ – Alex R. Jul 15 at 23:23
  • $\begingroup$ @AlexR.yes, I added the assumption. I have some values of these variables so the assumption is correct. Since the result is negative, I think that the error is the form of S, but I cannot see where. The text says: "the length of the packet is exponential with mean $1\\lambda$ and the server speed is C. Also the arrival of the jobs is exponential [...]", so I assume that the service rate is the duration of the job\the speed of the server. $\endgroup$ – linofex Jul 15 at 23:34
5
$\begingroup$

I am not going to wade through the initial queueing model, so I'll just take your word for it that you want to find the expected value of $e^{vS}$ where $S$ is an exponential random variable. This being the case, what you are looking for here is the moment generating function of an exponential random variable. From what you say in your comments, it appears to me that you have a random variable $S \sim \text{Exp}(\lambda/C)$ with rate parameter $\lambda/C$. (You have stated the PDF for this random variable incorrectly.)

Using the correct density function for this random variable, and applying the law of the unconscious statistician gives:

$$\begin{equation} \begin{aligned} M_S(v) \equiv \mathbb{E}(\exp(vS)) &= \int \limits_0^\infty \exp(vs) \cdot \frac{\lambda}{C} \exp \Big( - \frac{\lambda}{C} \cdot s \Big) \ ds \\[6pt] &= \frac{\lambda}{C} \int \limits_0^\infty \exp \Big( - \frac{\lambda-vC}{C} \cdot s \Big) \ ds \\[6pt] &= \begin{cases} \frac{\lambda}{\lambda-vC} & & & \text{for } v < \lambda / C, \\ \infty & & & \text{otherwise}. \\ \end{cases} \\[6pt] \end{aligned} \end{equation}$$

In your working you have made a few errors. Firstly, you have written the density function incorrectly. More importantly, the integral you are calculating diverges when $v \geqslant \lambda /C$, so it is not correct to assert the same formula for the MGF in this case.

$\endgroup$
  • $\begingroup$ there is no term 1/C in the analysis. Which analysis? The paper just says that S is the service time and in my case, the service time is a random variable derived from the jobs length is an exponential, but the service time involves even the speed of the server, so I have to count it $\endgroup$ – linofex Jul 16 at 0:47
  • $\begingroup$ Do you intend to have $S \sim \text{Exp}(\lambda/C)$? Because at the moment it is unclear how you intend for $C$ to enter the analysis; you have just stuck it on to the end of the PDF for some reason. $\endgroup$ – Reinstate Monica Jul 16 at 0:49
  • $\begingroup$ I will try to explain better the situation. I have a server that has to compute some jobs. The speed of this server is C (operation\second). Some jobs arrived with length (number of operation) that is an exponential with parameter $\lambda$ (a random variable). So, the service time $S$ will be the length of the job divided by the speed of the server. So, in my opinion, will have a new random variable $S = exp(\lambda)/C$. Or should I still treat S as exp(\lambda)? $\endgroup$ – linofex Jul 16 at 1:06
  • $\begingroup$ @linofex: But, that's NOT a random variable, because it's not normalized. Did you mean $E[e^{vS/C}]$ perhaps? Or alternatively $\exp(\lambda C) \lambda C$ is a normalized distribution. $\endgroup$ – Alex R. Jul 16 at 1:58
  • $\begingroup$ @linofex: I have amended the answer to use $S \sim \text{Exp}(\lambda/C)$, which appears to be consonant with your intention. $\endgroup$ – Reinstate Monica Jul 16 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.