Next: Mean response time of Up: Static robustness and mean Previous: Single-threshold allocation policies: T1   Contents

## Stability under single-threshold allocation policies

Figure 7.3: Stability conditions for the T1 policies, T1(1) and T1(5), and for the T2 policy. Upper bounds on are plotted as functions of .
 (a)
 (b)

We first consider the stability conditions for the T1 and T2 policies. In the T1 policy, higher values yield the larger stability regions, and in the limit as , the queues under the T1 policy are stable as long as and . In contrast, the T2 policy guarantees stability whenever and for any finite . The T2 policy clearly dominates the T1 policy in this respect. The stability conditions under the T1 and T2 policies are illustrated in Figure 7.3.

More formally, the necessary and sufficient conditions for the stability under the T1 and T2 policies are given by the following theorems.

Theorem 14   Under the T1 policy with parameter , queue 1 is stable if and only if . Stability of queue 2 is given by the following conditions:
• For , queue 2 is stable if and only if
 (7.1)

• For , if , queue 2 is stable if and only if equation (7.1) holds with .

• For , if , queue 2 is stable if and only if

Proof:We prove only the case when and . The case when or can be proved in a similar way. Let be the joint process of the number of jobs in queue 1 and queue 2, respectively. The expected length of a busy period,'' during which , is finite if and only if . This proves the stability condition for queue 1.

Based on the strong law of large numbers, the necessary and sufficient condition for stability of queue 2 is , where denotes the time average fraction of time that server 2 processes jobs from queue 2 given . Below, we derive . Let be a process in which behaves the same as except that it has no transition from to . Consider a semi-Markov process of , where the state space is (0,1,2,...,,). The state denotes there are jobs in queue 1 for , and the state denotes there are at least jobs in queue 1. The expected sojourn time is for state 0, for states , and for state , where is the mean duration of the busy period in an M/M/1 queue with arrival rate and service rate . The limiting probabilities for the corresponding embedded discrete time Markov chain are for and , where

As server 2 can work on queue 2 if and only if , the fraction of time that server 2 can work on queue 2 is

width 1ex height 1ex depth 0pt

The following corollary is an immediate consequence of Theorem 14.

Corollary 4   Under the T1 policy, the stability region increases with (i.e., the right hand side of equation (7.1) is an increasing function of ).

Theorem 15   Under the T2 policy with , queue 1 is stable if and only if , and queue 2 is stable if and only if .

Theorem 15 can be proved in a similar way as Theorem 14.

Next: Mean response time of Up: Static robustness and mean Previous: Single-threshold allocation policies: T1   Contents
Takayuki Osogami 2005-07-19