Stability

In this section we derive stability conditions for cycle stealing with switching times and thresholds. We find for example that the stability condition for the donor jobs remains $\rho_D < 1$, regardless of whether the donor jobs experience switching times. By contrast, the stability region for the beneficiary jobs can be significantly below $2 - \rho_D$, specifically because the switching time erodes the beneficiary stability region. Also, interestingly, the value of $N_B^{th}$ does not affect the stability region of either the donor or beneficiary jobs. By contrast, increasing $N_D^{th}$ increases the stability region of the beneficiary jobs; however it has no effect of the stability region of the donor jobs.

Theorem 12   The donor queue is stable iff $\rho_D < 1$.

Proof:It makes intuitive sense that the donor queue is stable iff $\rho_D < 1$ regardless of the switching times and threshold values, since the donor would never switch if the donor queue was persistently backlogged. Below, we prove sufficiency more formally. The necessity of $\rho_D < 1$ is trivial.

Assume $\rho_D < 1$. Let $B_D$ denote the length of a busy period at the donor queue. We first consider the case of $N_B^{th}=0$. A busy period at the donor queue is started by a switching time $K_{ba}$ and $N_D^{th}$ donor jobs. As $\rho_D < 1$, the mean length of a busy period is

$$\mbox{{\bf\sf E}}\left[ B_D \right] = \frac{N_D^{th}\mbox{{\... ...t]+\mbox{{\bf\sf E}}\left[ K_{ba} \right]}{1-\rho_D} < \infty.$$

In this case $B_D$ clearly has a proper limiting distribution, and hence the donor is stable. Next we consider the case of $N_B^{th}>0$. In this case $\mbox{{\bf\sf E}}\left[ B_D \right]$ is smaller than in the case of $N_B^{th}=0$ because there will be donor busy periods in which the donor server has not left the donor queue, implying (i) there is no switching back time, and (ii) the busy period is started by only one donor job.     width 1ex height 1ex depth 0pt

Before we derive the stability condition on $\rho _B$, we prove a lemma allowing us to assume $N_B^{th}=0$.

Lemma 8   If the beneficiary queue is stable at $N_B^{th}=0$, then it is stable at $N_B^{th} = n$, $\forall \ 0 \leq n < \infty$.

Proof:Intuitively, the stability of the beneficiary queue is independent of $N_B^{th}$, since $N_B^{th}$ would be irrelevant when the beneficiary queue was continuously backlogged.

More formally, let $L^{(n)}_B(t)$ denote the number of beneficiary jobs at time $t$ given $N_B^{th} = n \geq 1$. Consider a new process $\widehat{L}^{(n)}_B(t)$ in which the number of jobs at time $t=0$ is $n$, instead of $0$ as in the original process, and no service is given by either server to a beneficiary job if there are $\leq n$ jobs present at the beneficiary queue. Note that $\widehat{L}^{(n)}_B(t)$ stochastically dominates ${L}^{(n)}_B(t)$. Also, along any sample path, $\widehat{L}^{(n)}_B(t)$ will be equal to $n$ + $L^{(0)}_B(t)$. Therefore, if $L^{(0)}_B(t)$ is proper, so too is $\widehat{L}^{(n)}_B(t)$ and hence $L^{(n)}_B(t)$.     width 1ex height 1ex depth 0pt

We now prove the stability condition on $\rho _B$.

Theorem 13   The beneficiary queue is stable iff

$$\rho_B < 1 + \frac{\max(1-\rho_D,0)\sum_{i=0}^{N_D^{th}}(N_D... ...D)}{N_D^{th}+\lambda_D\mbox{{\bf\sf E}}\left[ K_{ba} \right]},$$ (6.2)

where $\widetilde K_{sw}(s)$ is the Laplace transform of $K_{sw}$ and $\widetilde K_{sw}^{(i)}(s)$ is its $i$-th derivative. In particular, when $K_{sw}$ is exponentially distributed, the condition is expressed by the closed form:

$$\rho_B < 1 + \frac{\max(1-\rho_D,0)\left\{N_D^{th}-\frac{q}{... ...\}}{N_D^{th}+\lambda_D\mbox{{\bf\sf E}}\left[ K_{ba} \right]},$$ (6.3)

where

$$q=\frac{\lambda_D\mbox{{\bf\sf E}}\left[ K_{sw} \right]}{1+\lambda_D\mbox{{\bf\sf E}}\left[ K_{sw} \right]}.$$

Proof:We first prove sufficiency. By Lemma 8, we can assume $N_B^{th}=0$. Let $F$ denote the fraction of time that the donor server helps the beneficiary. Then the strong law of large numbers can be used to show that the necessary and sufficient condition for stability of the beneficiary jobs is $\rho_B < 1 + F$. If $\rho_D \geq 1$, $F = 0$. Thus we assume $\rho_D < 1$ and derive $F$ using renewal reward theory.

Let a renewal occur every time the donor queue becomes empty (see Figure 6.2). Recall $N_B^{th}=0$. By renewal-reward theory, the fraction of time donor helps beneficiary is $F = \frac{\mbox{{\bf\sf E}}\left[ R \right]}{\mbox{{\bf\sf E}}\left[ Y \right]}$, where $R$ denotes the total time that donor helps beneficiary (reward) during the renewal cycle, and $Y$ denotes the length of the renewal cycle. Observe that there may be any number of donor arrivals ranging from $0$ to $N_D^{th}$ during $K_{sw}$ and we switch back only after the $N_D^{th}$ arrival.

Figure 6.2: A renewal cycle of the donor queue under the threshold-based policy for reducing switching costs in cycle stealing.]

Let $S$ denote the sum of the service times of $N_D^{th}$ donor jobs and $B_{S + ba}$ denote the length of the busy period started by these jobs of total size $S$ plus $K_{ba}$. Then, as $\rho_D < 1$,

$$\mbox{{\bf\sf E}}\left[ Y \right] = N_D^{th} \mbox{{\bf\sf E... ...\right] + \mbox{{\bf\sf E}}\left[ K_{ba} \right]}{1 - \rho_D},$$

where $I_D$ is the interarrival time for donor jobs.

To compute $\mbox{{\bf\sf E}}\left[ R \right]$, we condition on the number of donor jobs arriving during $K_{sw}$. If there are $i$ arrivals, then the mean time spent helping is the time until there are $(N_D^{th} - i)$ more donor arrivals, $(N_D^{th} - i)\mbox{{\bf\sf E}}\left[ I_D \right]$. Let $p_i$ denote the probability that there are $i$ donor jobs arriving during $K_{sw}$. Then,

$$p_i=\frac{(-\lambda_D)^i}{i!}\widetilde K_{sw}^{(i)}(\lambda_D).$$

Using $p_i$, $\mbox{{\bf\sf E}}\left[ R \right]$ is now derived as follows:

$$\begin{eqnarray*} \mbox{{\bf\sf E}}\left[ R \right] & = & \sum_{i=0}^{N_D^{th}-1} (N_D^{th}-i)\frac{1}{\lambda_D} p_i. \end{eqnarray*}$$

Thus, $\rho_B < 1 + F$ is equivalent to (6.2). When $K_{sw}$ is exponentially distributed, $p_i = q^i(1-q)$, where $q = \lambda_D / (\lambda_D+\mu_{sw})$. Therefore,

$$\begin{eqnarray*} \mbox{{\bf\sf E}}\left[ R \right] & = & \frac{1}{\lambda_D}\left\{N_D^{th}-\frac{q}{1-q}(1-q^{N_D^{th}})\right\}. \end{eqnarray*}$$

Thus, $\rho_B < 1 + F$ is equivalent to (6.3).

Above, we have proved the necessary and sufficient condition for $N_B^{th}=0$. By Lemma 8, this is also the sufficient condition for $N_B^{th}>0$. Now, we prove necessity for $N_B^{th}>0$. When $N_B^{th}>0$, the donor server does not necessarily help the beneficiary even when it is available for help. Therefore, there are two types of renewal periods. In the first type of renewal period, the donor server helps the beneficiary, i.e. $R>0$. In this case, $\mbox{{\bf\sf E}}\left[ Y \right]$ is the same as for $N_B^{th}=0$, and $\mbox{{\bf\sf E}}\left[ R \right]$ for $N_B^{th}>0$ is at most $\mbox{{\bf\sf E}}\left[ R \right]$ for $N_B^{th}=0$. In the second type of renewal period, the donor server does not help the beneficiary, i.e. $R=0$. (In this case $\mbox{{\bf\sf E}}\left[ Y \right]$ can be smaller than that for $N_B^{th}=0$.) The fraction of time, $F$, that the donor server helps the beneficiary can be expressed as $F=F_1+F_2$, where $F_1$ is the fraction of time that the donor server helps the beneficiary and the renewal period is type 1, and $F_2$ is the fraction of time that the donor server helps the beneficiary and the renewal period is type 2. In fact, $F_2=0$. Therefore, $F = F_1 \leq \mbox{{\bf\sf E}}\left[ R \right] / \mbox{{\bf\sf E}}\left[ Y \right]$. This proves the necessity for $N_B^{th}>0$.     width 1ex height 1ex depth 0pt

Note that the right hand side of (6.2) is an increasing function of $N_D^{th}$; in terms of stability, the larger $N_D^{th}$, the more stable the beneficiary queue. In particular, when $N_D^{th}=0$, (6.2) is $\rho_B < 1$; as $N_D^{th}\rightarrow\infty$, (6.2) becomes $\rho_B < 2-\rho_D$.

Figure 6.3: Stability region for the threshold-based policy for reducing switching costs in cycle stealing. Switching times are denoted by $K\equiv K_{sw}=K_{ba}$.

(i) $\mbox{{\bf\sf E}}\left[ X_D \right]=1, \mbox{{\bf\sf E}}\left[ K \right]=1$

(ii) $\mbox{{\bf\sf E}}\left[ X_D \right]=1, \mbox{{\bf\sf E}}\left[ K \right]=10$

(iii) $\mbox{{\bf\sf E}}\left[ X_D \right]=10, \mbox{{\bf\sf E}}\left[ K \right]=1$

Figure 6.3 shows the stability condition for beneficiary jobs as a function of $\rho_D$ when $K_{sw}$ is exponentially distributed. In case (i), we set $\mbox{{\bf\sf E}}\left[ X_D \right] = 1$ and $\mbox{{\bf\sf E}}\left[ K_{sw} \right]=\mbox{{\bf\sf E}}\left[ K_{ba} \right]=1$. The region below each line satisfies the stability condition. As $N_D^{th}$ increases as high as 100, the effect of switching overhead becomes negligible, and the stability condition approaches $\rho_B < 2-\rho_D$. In case (ii), we set $\mbox{{\bf\sf E}}\left[ X_D \right] = 1$ and $\mbox{{\bf\sf E}}\left[ K_{sw} \right]=\mbox{{\bf\sf E}}\left[ K_{ba} \right]=10$. The switching time is large, and there is little benefit at moderate or high $\rho_D$ in terms of stability, unless $N_D^{th}$ is large. However, there is still large benefit at low $\rho_D$. In case (iii), we set $\mbox{{\bf\sf E}}\left[ X_D \right] = 10$ and $\mbox{{\bf\sf E}}\left[ K_{sw} \right]=\mbox{{\bf\sf E}}\left[ K_{ba} \right]=1$. The stability region is larger; when $N_D^{th}=1$, the stability region is almost the same as that of $N_D^{th}=10$ in case (i). This is intuitive: when $\mbox{{\bf\sf E}}\left[ X_D \right] = 10$ and $N_D^{th}=1$, the expected amount of donor work when the donor switches back is the same as that when $\mbox{{\bf\sf E}}\left[ X_D \right] = 1$ and $N_D^{th}=10$.