Proof of Theorem 9

Let $W(t)$ be the virtual waiting time for the queue of long jobs at time $t$. That is, a long job arriving at time $t$ would wait $W(t)$ before it starts being processed. By the PASTA (Poisson arrival sees the time average) principle, the virtual waiting time $W$ is equal in distribution to the waiting time. Therefore, it suffices to analyze the virtual waiting time $W$ for the derivation of the response time of long jobs.

The following steps allow us to obtain the moments of $W=\lim_{t\rightarrow\infty}W(t)$:

(i)

Set up a differential equation for $\widetilde W(t,s)$, the Laplace transform of $W(t)$.

(ii)

Let $t\rightarrow\infty$; then, $\frac{d\widetilde W(t,s)}{dt}\rightarrow 0$, because the queue reaches the stationary state. Now, $\widetilde W(s)$ is obtained as a function of $\pi_0$.

(iii)

Evaluate $\widetilde W(s=0)$ to obtain $\pi_0$.

(iv)

Differentiate $\widetilde W(s)$ to obtain moments of $W$.

(i) We first set up a differential equation for $\widetilde W(t,s)$. For this purpose, we carefully examine the relationship between $W(t)$ and $W(t+\Delta t)$. First, suppose $W(t)\geq\Delta t$ (see Figure A.1(a)). Since the long server is always busy between $t$ and $t+\Delta t$, only long jobs could arrive at the queue. Since the arrival process is Poisson with rate $\lambda_L$, the probability of having a job arrival in time $\Delta t$ is $\lambda_L\Delta t+o(\Delta t)$. Any such arrival will have service time $X_L$. Therefore,

$$W(t+\Delta t) = \left\{ \begin{array}{ll} W(t)-\Delta t & \m... ...mething else} & \mbox{w/ prob. } o(\Delta). \end{array}\right.$$

Figure A.1: Virtual waiting time analysis: relationship between $W(t)$ and $W(t+\Delta t)$, when (a) $W(t)\geq\Delta t$ and (b) $0\leq W(t)<\Delta t$.

Next, suppose $0\leq W(t)<\Delta t$ (see Figure A.1). Let a random variable $\epsilon$ be the fraction of time that the long server was idle during $(t, t + \Delta t)$ given that there were no arrivals during this interval. Let a random variable $\epsilon_L$ be the fraction of time that the long server was busy during this interval given that there was a long job arrival. Let a random variable $\epsilon_S$ be the fraction of time that the long server was busy during the interval giving that there was a short job arrival. Then,

$$\begin{eqnarray*} W(t+\Delta t) & = & \left\{ \begin{array}{ll} 0 & \mbox{w/ pro... ...something else} & \mbox{w/ prob. } o(\Delta). \end{array}\right. \end{eqnarray*}$$

Note that $0\leq\epsilon, \epsilon_L, \epsilon_S\leq 1$.

Based on the above observation, the Laplace transform $\widetilde W(t+\Delta t, s)$ of $W(t+\Delta t)$ is obtained as follows:

$$\widetilde W(t+\Delta t, s) \equiv \mbox{{\bf\sf E}}\left[ e^{-sW(t+\Delta t)} \right]$$

$$= \int_{x=0}^\infty \mbox{{\bf\sf E}}\left[ e^{-sW(t+\Delta t)}\vert W(t)=x \right]d{\rm Pr}(W(t)\leq x)$$

$$= \left(1+(s-\lambda_L+\lambda_L\widetilde X_L(s))\Delta t\right)\widetilde W(t,s) + \int_{x=0^+}^{\Delta t} O(\Delta t) d{\rm Pr}(W(t)\leq x)$$

$$+ \left(-\lambda_S + \widetilde X_S(s)\lambda_S - s\right)\Delta t {\rm Pr}(W(t)=0) +o(\Delta t).$$

Thus, we obtain the next formula.

$$\frac{\widetilde W(t+\Delta t, s) - \widetilde W(t,s)}{\Delta t} = \left(s-\lambda_L+\lambda_L\widetilde X_L(s)\right)\widetilde W(t,s) + \int_{x=0^+}^{\Delta t} O(1) d{\rm Pr}(W(t)\leq x)$$

$$+ \left(-\lambda_S + \widetilde X_S(s)\lambda_S - s\right) {\rm Pr}(W(t)=0)+\frac{o(\Delta t)}{\Delta t}.$$

Letting $\Delta t \rightarrow 0$ in the above formula, we obtain a differential equation for $\widetilde W(t,s)$.

$$\begin{eqnarray*} \frac{d\widetilde W(t,s)}{dt} & = & \left(s-\lambda_L+\lambda_... ...mbda_S + \widetilde X_S(s)\lambda_S - s\right) {\rm Pr}(W(t)=0). \end{eqnarray*}$$

(ii) Let $t\rightarrow\infty$. Then, $\frac{d\widetilde W(t,s)}{dt}\rightarrow 0$ because the queue reaches the stationary state. Let $\widetilde W(s)\equiv\lim_{t\rightarrow\infty}\widetilde W(t,s)$. Then, $\widetilde W(s)$ is obtained as a function of $\pi_0={\rm Pr}(W(t)=0)$:

$$\widetilde W(s) = \frac{s+\lambda_S-\widetilde X_S(s)\lambda_S}{s-\lambda_L+\widetilde X_L(s)\lambda_L}\pi_0.$$

(iii) Next, we will obtain $\pi_0$ by evaluating $\widetilde W(s)$ at $s = 0$. Note that the Laplace transform $\widetilde Z(s)$ of a probability distribution $Z$ always has the property $\widetilde Z(0)=1$.

$$1 = \widetilde W(0) = \frac{1+\mbox{{\bf\sf E}}\left[ X_S \right]\lambda_S}{1-\mbox{{\bf\sf E}}\left[ X_L \right]\lambda_L}\pi_0.$$

The second equality follows from the L'Hopital's rule. Therefore,

$$\pi_0 = \frac{1-\lambda_L \mbox{{\bf\sf E}}\left[ X_L \right]}{1+\lambda_S \mbox{{\bf\sf E}}\left[ X_S \right]}.$$

(iv) The moments of waiting time, and subsequently response time, are easily obtained by differentiating $\widetilde W(s)$ and evaluating at $s = 0$. In particular, the $n$-th moment of $W$ is

$$\mbox{{\bf\sf E}}\left[ W^n \right] = \widetilde W^{(n)}(0).$$

    width 1ex height 1ex depth 0pt