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 , regardless of whether the donor jobs experience switching times. By contrast, the stability region for the beneficiary jobs can be significantly below , specifically because the switching time erodes the beneficiary stability region. Also, interestingly, the value of does not affect the stability region of either the donor or beneficiary jobs. By contrast, increasing increases the stability region of the beneficiary jobs; however it has no effect of the stability region of the donor jobs.
Proof:It makes intuitive sense that the donor queue is stable iff 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 is trivial.
Assume . Let denote the length of a busy period
at the donor queue.
We first consider the case of . A busy period at the donor
queue is started by a switching time and donor
jobs. As , the mean length of a busy period is
Before we derive the stability condition on , we prove a lemma allowing us to assume .
Proof:Intuitively, the stability of the beneficiary queue is independent of , since would be irrelevant when the beneficiary queue was continuously backlogged.
More formally, let denote the number of beneficiary jobs at time
. Consider a new process
in which the number of jobs at time is
, instead of as in the original process, and no service is
given by either server to a beneficiary job if there are jobs
present at the beneficiary queue. Note that
. Also, along any sample path,
will be equal to + .
Therefore, if is proper, so too is
and hence . width 1ex height 1ex depth 0pt
We now prove the stability condition on .
Proof:We first prove sufficiency. By Lemma 8, we can assume . Let 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 . If , . Thus we assume and derive using renewal reward theory.
Let a renewal occur every time the donor queue becomes empty (see Figure 6.2). Recall . By renewal-reward theory, the fraction of time donor helps beneficiary is , where denotes the total time that donor helps beneficiary (reward) during the renewal cycle, and denotes the length of the renewal cycle. Observe that there may be any number of donor arrivals ranging from to during and we switch back only after the arrival.
Let denote the sum of the service times of donor jobs
and denote the length of the busy period started by these
jobs of total size plus .
Then, as ,
, we condition on
the number of donor jobs arriving during . If there are
arrivals, then the mean time spent helping is
the time until there are
more donor arrivals,
Let denote the probability that there are donor jobs arriving during .
Above, we have proved the necessary and sufficient condition for .
By Lemma 8, this is also the sufficient condition for .
Now, we prove necessity for .
When , 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. .
In this case,
is the same as for ,
for is at most
In the second type of renewal period, the donor server does not help the beneficiary, i.e. .
(In this case
can be smaller than that for .)
The fraction of time, , that the donor server helps the beneficiary can be expressed as
, where is the fraction of time that the donor server helps the beneficiary
and the renewal period is type 1, and is the fraction of time that the donor server helps
the beneficiary and the renewal period is type 2. In fact, .
This proves the necessity for . width 1ex height 1ex depth 0pt
Note that the right hand side of (6.2) is an increasing function of ; in terms of stability, the larger , the more stable the beneficiary queue. In particular, when , (6.2) is ; as , (6.2) becomes .
Figure 6.3 shows the stability condition for beneficiary jobs as a function of when is exponentially distributed. In case (i), we set and . The region below each line satisfies the stability condition. As increases as high as 100, the effect of switching overhead becomes negligible, and the stability condition approaches . In case (ii), we set and . The switching time is large, and there is little benefit at moderate or high in terms of stability, unless is large. However, there is still large benefit at low . In case (iii), we set and . The stability region is larger; when , the stability region is almost the same as that of in case (i). This is intuitive: when and , the expected amount of donor work when the donor switches back is the same as that when and .