Reducing switching costs in cycle stealing (Chapter 6)

In Chapter 6, we consider the benefit and penalty of cycle stealing in the context of a network of workstations, where the donor (Dan) allows the beneficiary (Betty) to steal his idle cycles (recall Figure 1.4). Although cycle stealing provides obvious benefits to the beneficiary, these benefits come at some cost to the donor. Typically, there is a switching time, $K_{sw}$, required for the donor server to start working on the beneficiary's jobs, as well as a switching back time, $K_{ba}$. For example, the beneficiary's job may have to be checkpointed and the donor's working set memory reloaded before the donor server can resume, delaying the resumption of processing of donor jobs. In our model, we refer to these additional costs associated with cycle stealing as switching costs (or switching times).

Figure 1.10: A threshold-based policy for reducing switching costs in cycle stealing. If $N_B \geq N_B^{th}$ and $N_D = 0$, the donor server starts switching to the beneficiary's queue. After $K_{sw}$ time, the donor server is available to work on the beneficiary's jobs. When $N_D$ reaches $N_D^{th}$, the donor server starts switching back to its own queue. After $K_{ba}$ time, the donor server resumes working on its own jobs.

Due to non-zero switching costs, the donor server's switching may pay only when the beneficiary's queue length, $N_B$, is sufficiently long, and the donor server's switching back may pay only when the donor's queue length, $N_D$, is sufficiently long. This motivates us to introduce a threshold-based policy, whereby whether the donor server should switch (and switch back) is decided based on a queue length, i.e. whether the queue length exceeds a threshold (see Figure 1.10).

Our primary goal is to understand the benefit of cycle stealing for the beneficiary and the penalty to the donor, as a function of switching times. A secondary goal is to derive parameter settings for cycle stealing. We seek to understand the optimal threshold values, $N_B^{th}$ and $N_D^{th}$. More broadly, we seek general insights into which system parameters have the most significant impact on the effectiveness of cycle stealing.

To quantitatively understand the benefit and penalty of cycle stealing as a function of switching times, we need to be able to analyze the mean response time under cycle stealing with switching times. However, an exact analysis for this system is not known in the literature (even without switching times), since it would involve multidimensional Markov chains. We will analyze the mean response time under the threshold-based policy for reducing switching costs in cycle stealing via DR. Our analysis yields many interesting results concerning cycle stealing.