Next: Mean response time Up: Results Previous: Summary of results   Contents

## 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 , 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.

Theorem 12   The donor queue is stable iff .

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

In this case clearly has a proper limiting distribution, and hence the donor is stable. Next we consider the case of . In this case is smaller than in the case of 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 , we prove a lemma allowing us to assume .

Lemma 8   If the beneficiary queue is stable at , then it is stable at , .

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 given . 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 stochastically dominates . 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 .

Theorem 13   The beneficiary queue is stable iff
 (6.2)

where is the Laplace transform of and is its -th derivative. In particular, when is exponentially distributed, the condition is expressed by the closed form:
 (6.3)

where

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 ,

where is the interarrival time for donor jobs.

To compute , 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 . Then,

Using , is now derived as follows:

Thus, is equivalent to (6.2). When is exponentially distributed, , where . Therefore,

Thus, is equivalent to (6.3).

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 , and for is at most for . 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, . Therefore, . 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: Stability region for the threshold-based policy for reducing switching costs in cycle stealing. Switching times are denoted by .
 (i)
 (ii)
 (iii)

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 .

Next: Mean response time Up: Results Previous: Summary of results   Contents
Takayuki Osogami 2005-07-19