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 $\rho_2$ are plotted as functions of $\rho_1$.

(a) $\mu_{12}=\mu_1$

(b) $\mu_{12}=\frac{\mu_1}{2}$

We first consider the stability conditions for the T1 and T2 policies. In the T1 policy, higher $T_1$ values yield the larger stability regions, and in the limit as $T_1\rightarrow\infty$, the queues under the T1 policy are stable as long as $\hat\rho_1<1$ and $\rho_2<1$. In contrast, the T2 policy guarantees stability whenever $\hat\rho_1<1$ and $\rho_2<1$ for any finite $T_2$. 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 $T_1<\infty$, queue 1 is stable if and only if $\lambda_1 < \mu_1 + \mu_{12}$. Stability of queue 2 is given by the following conditions:

• For $1<T_1<\infty$, queue 2 is stable if and only if
  

  $$\rho_2 < \left\{\begin{array}{ll} \frac{1-\rho_1^{T_1}}{1-\rho_1^{T_1} + \... ...T_1}{T_1+\lambda_1/\mu_{12}} & \mbox{\rm if } \rho_1 = 1.\\ \end{array}\right.$$ (7.1)

  
  

• For $T_1=1$, if $\mu_1\geq\mu_{12}$, queue 2 is stable if and only if equation (7.1) holds with $T_1=2$.

• For $T_1=1$, if $\mu_1<\mu_{12}$, queue 2 is stable if and only if
  
  $$\rho_2 < \frac{1}{1+\frac{\rho_1+\lambda_1/\mu_{12}}{1-\rho_1+\mu_{12}/\mu_1}}.$$
  
  

Proof:We prove only the case when $T_1>1$ and $\rho_1\neq 1$. The case when $T_1=1$ or $\rho_1=1$ can be proved in a similar way. Let $N=(N_1,N_2)$ 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 $N_1 \geq T_1$, is finite if and only if $\lambda_1 < \mu_1 + \mu_{12}$. 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 $\rho_2 < F$, where $F$ denotes the time average fraction of time that server 2 processes jobs from queue 2 given $N_2>0$. Below, we derive $F$. Let $\widetilde N=(\widetilde N_1,\widetilde N_2)$ be a process in which $\widetilde N$ behaves the same as $N$ except that it has no transition from $\widetilde N_2=1$ to $\widetilde N_2=0$. Consider a semi-Markov process of $\widetilde N_1$, where the state space is (0,1,2,...,$T_1-1$,$T_1^+$). The state $n$ denotes there are $n$ jobs in queue 1 for $n=0,1,...,T_1-1$, and the state $T_1^+$ denotes there are at least $T_1$ jobs in queue 1. The expected sojourn time is $1/\lambda_1$ for state 0, $1/(\lambda_1+\mu_1)$ for states $n=1,...,T_1-1$, and $b=\frac{1/(\mu_1+\mu_{12})}{1-\lambda_1/(\mu_1+\mu_{12})}$ for state $T_1^+$, where $b$ is the mean duration of the busy period in an M/M/1 queue with arrival rate $\lambda_1$ and service rate $\mu_1+\mu_{12}$. The limiting probabilities for the corresponding embedded discrete time Markov chain are $\pi_n = (1+\rho_1)\rho_1^{n-1}\pi_0$ for $n=1,...,T_1-1$ and $\pi_{T_1^+}=\rho_1^{T_1}\pi_0$, where

$$\pi_0 = \frac{1-\rho_1}{(1+\rho_1^{T_1-1})(1-\rho_1)+(1+\rho_1)(1-\rho_1^{T_1-1})}.$$

As server 2 can work on queue 2 if and only if $\widetilde N_1< T_1$, the fraction of time that server 2 can work on queue 2 is

$$F = \frac{\pi_0/\lambda_1 + (1-\pi_0-\pi_{T_1^+})/(\lambda_1... ...{T_1}+\frac{(1-\rho_1)\rho_1^{T_1}}{1-\rho_1+\mu_{12}/\mu_1}}.$$

    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 $T_1$ (i.e., the right hand side of equation (7.1) is an increasing function of $T_1$).

Theorem 15   Under the T2 policy with $T_2<\infty$, queue 1 is stable if and only if $\hat\rho_1<1$, and queue 2 is stable if and only if $\rho_2<1$.

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