Stability

Under the Dedicated policy, the queues are stable iff $\rho_L<1$ and $\rho_S<1$. The stability region becomes wider under SBCS-ID and SBCS-CQ, as is characterized in the next theorem.

Theorem 10   Under SBCS-ID, the queues are stable iff

$$\rho_L<1 \quad\mbox{and}\quad \rho_S < \frac{1-\rho_L+\sqrt{(1-\rho_L)^2+4}}{2}.$$

Under SBCS-CQ, the (central) queue is stable iff $\rho_L<1$ and $\rho_S<2-\rho_L$.

Proof:We first consider the stability conditions for SBCS-ID. Let $\widehat\rho_L$ (respectively, $\widehat\rho_S$) denote the load at the long server (respectively, short server). The queues are stable iff $\widehat\rho_L<1$ and $\widehat\rho_S<1$.

We first deduce $\widehat\rho_L$. The PASTA (Poisson arrivals see time averages) principle implies that the fraction of the short jobs that are dispatched to the long server is $1 - \widehat\rho_L$, assuming $\widehat\rho_L<1$. Thus,

$$\begin{eqnarray*} \widehat\rho_L = \rho_S ( 1 - \widehat\rho_L) + \rho_L \iff \widehat\rho_L = \frac{\rho_S + \rho_L}{1 + \rho_S}. \end{eqnarray*}$$

We therefore have the constraint that

$$\widehat\rho_L = \frac{\rho_S + \rho_L}{1 + \rho_S} < 1 \iff \rho_L < 1.$$

Next we deduce $\widehat\rho_S$. The PASTA principle implies that the fraction of the short jobs that are dispatched to the short server is $\widehat\rho_L$, assuming $\widehat\rho_L<1$. Thus,

$$\begin{eqnarray*} \widehat\rho_S & = & \rho_S \cdot \widehat\rho_L. \end{eqnarray*}$$

We therefore have the constraint that

$$\rho_S \cdot \frac{\rho_S + \rho_L}{1 + \rho_S} < 1 \quad \iff \quad \rho_S < \frac{1-\rho_L+\sqrt{(1-\rho_L)^2+4}}{2}.$$

The stability conditions for SBCS-CQ follow immediately via the law of large numbers. The long jobs (the number of the long jobs in the central queue) are stable iff $\rho_L<1$, and the short jobs are stable iff $\rho_S<2-\rho_L$.     width 1ex height 1ex depth 0pt

The restriction on $\rho_S$ for stability under each of the three task assignment policies is shown in Figure 5.2 as a function of $\rho_L$ ($\rho_L<1$ is necessary for all the three policies). Observe the advantage of cycle stealing in extending the stability region. When $\rho_L$ is near zero, $\rho_S$ can be as high as about $1.61$ (golden ratio) under SBCS-ID and close to $2$ under SBCS-CQ.

Figure 5.2: Stability region for Dedicated, SBCS-ID, and SBCS-CQ.