Benefit of cycle stealing: $.5 < \rho _B < 1.0$

For $.5 < \rho_B < 1$, cycle stealing has regions of high gain and low pain and also regions where the reverse is true. These regions depend on job sizes, switching times, and loads.

In Figure 6.5, we categorize performance into these gain/pain regions and also look at the overall mean response time (averaged over both beneficiary and donor jobs) to determine whether cycle stealing is ``good'' or ``bad'' overall. In general under higher $\rho _B$ and lower $\rho_D$, cycle stealing is ``good'' overall, because the gain of the beneficiary jobs is so high in this region. We will find that when the switching times are short, cycle stealing leads to high gain and low pain. However long switching times can reverse this effect. More important than the absolute switching times are the switching times relative to the mean donor job size. We will find that the mean response time of the donor jobs is sensitive to the switching times, while surprisingly the mean response time of the beneficiary jobs is far less sensitive.

Figure 6.5: The gain of beneficiary jobs and pain of donor jobs ((a) and (c)) and the effect of cycle stealing on the overall mean response time relative to dedicated servers ((b) and (d)). In (a) and (c), solid lines delineate high/mid/low gain regions, and dashed lines delineate high/mid/low pain regions. $X_B$ and $X_D$ have exponential distributions, and their means are as labeled. Switching times are exponential with mean 0 or 1 as labeled, where $K\equiv K_{sw}=K_{ba}$.

Gain of beneficiary jobs & pain of donor jobs ( $\mbox{{\bf\sf E}}\left[ X_B \right]=1,\mbox{{\bf\sf E}}\left[ X_D \right]=1$)

Gain of beneficiary jobs & pain of donor jobs ( $\mbox{{\bf\sf E}}\left[ X_B \right]=1,\mbox{{\bf\sf E}}\left[ X_D \right]=10$)

Gain of beneficiary jobs & pain of donor jobs ( $\mbox{{\bf\sf E}}\left[ X_B \right]=10,\mbox{{\bf\sf E}}\left[ X_D \right]=1$)

(a) $\mbox{{\bf\sf E}}\left[ K \right]=0$

(b) $\mbox{{\bf\sf E}}\left[ K \right]=0$

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

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

Figure 6.5 shows the gain of beneficiary jobs and the pain of donor jobs, where $.5 < \rho_B < 1$. The odd-numbered columns of Figure 6.5 divide the ($\rho _B$,$\rho_D$) space into regions of beneficiary gain and donor pain (low, mid, and high). We define low gain as a gain of $1.1$ or less; mid gain as a gain of between $1.1$ and $1.5$; and high gain as a gain of over $1.5$. Pain regions are defined similarly. While odd-numbered columns of Figure 6.5 consider the beneficiary and donor mean response time individually, the even-numbered columns of Figure 6.5 look at the overall mean response time and ask whether cycle stealing is ``good'' or ``bad'' with respect to the overall mean response time. The effect of mean job sizes is considered in Figure 6.5, where job sizes are exponential with mean 1 or 10.

Consider first row 1 in Figure 6.5. Under zero switching time (a)-(b), all regions are low pain regions (in fact zero pain), and higher $\rho _B$ yields higher gain for the beneficiary jobs. Non-zero switching times (c)-(d) create only slightly reduced gain for the beneficiary jobs, but they create pain for the donor jobs. When $\rho_D$ is very low, the pain appears high, but this is primarily due to the fact that ``pain'' is relative to the mean response time under dedicated servers, which is clearly low for small $\rho_D$. Although not shown, we have also investigated longer switching times, and these lead to the same trend of slightly less gain for beneficiary jobs and significantly more pain for donor jobs.

We now consider the effect of changes in job sizes. Row 2 of Figure 6.5 differs from row 1 only in $X_D$, which now has mean 10. The effect of this change is dramatic: now a switching time of 1 has almost no effect on either beneficiary jobs or donor jobs. This makes sense since the setup time experienced by donor jobs is now relatively small compared to their size. Row 3 in Figure 6.5 differs from row 1 only in $X_B$, which now has mean 10. Comparing these rows, we see the increase in $\mbox{{\bf\sf E}}\left[ X_B \right]$ has a surprisingly small effect on both beneficiary jobs and donor jobs, as compared with increasing $\mbox{{\bf\sf E}}\left[ X_D \right]$. This is because the donor still experiences the setup time, which has the same mean size as the donor job. We can conclude that cycle stealing is most effective when the switching time is small relative to the size of the donor jobs.

Focusing on columns 2 and 4 of Figure 6.5, which depict the effect on overall mean response time, we see that, for all rows, when the switching time is zero, cycle stealing always overwhelms the dedicated policy. When switching time is non-zero, cycle stealing is a good idea provided either $\rho _B$ is high, or the switching time is short compared to $X_D$. These trends continue for longer switching times.