T1T2 policy

One might argue that the stability or static robustness issue of the T1 policy with small optimal $T_1$ is resolved simply by placing an additional threshold, $T_2$, on queue 2, so that whenever the length of queue 2, $N_2$, exceeds $T_2$, server 2 works on type 2 jobs regardless of the length of queue 1, thus preventing queue 2 from becoming unstable. We refer to this policy as the T1T2 policy. Surprisingly, we will see that the T1T2 policy improves upon static robustness of the T1 policy only slightly. Since the T1T2 policy generalizes the T1 policy (by setting $T_2=\infty$, the T1T2 policy is reduced to the T1 policy), one might also expect that the mean response time of the optimized T1T2 policy could be strictly better than that of the optimized T1 policy as long as $T_2<\infty$. This surprisingly turns out to be largely false; the mean response time of the optimized T1T2 policy does not appreciably improve upon that of the optimized T1 policy.

Figure 7.7: Figure shows whether server 2 works on jobs from queue 1 or queue 2 as a function of $N_1$ and $N_2$ under the T1T2 policy with parameters ($T_1,T_2$).

The T1T2 policy is formally defined as follows:

Definition 18   The T1T2 policy with parameters ($T_1,T_2$) operates as the T1 policy with parameter $T_1$ if $N_2 < T_2$; otherwise, it operates as the T2 policy with parameter $T_2$.

Figure 7.7 shows the jobs processed by server 2 a function of $N_1$ and $N_2$ under the T1T2 policy. Below, the T1T2 policy with parameters ($t_1,t_2$) is also denoted by the T1T2($t_1,t_2$) policy.

The stability region of the T1T2 policy is the same as that of the T2 policy; i.e. the T1T2 policy has the widest possible stability region regardless of its parameters ($T_1,T_2$). This makes intuitive sense, since a T1T2 policy behaves like a T2 policy at high load. The following theorem can be proved in a similar way as Theorem 14.

Theorem 18   Under the T1T2 policy with parameters ($T_1,T_2$) where $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$.

Figure 7.8: Static robustness of the T1T2 policy is illustrated by plotting their mean response time as functions of (a) $\rho_1$ ($\rho_2=0.6$ is fixed) and (b) $\rho_2$ ($\rho_1=1.15$ is fixed). Here, $c_1=c_2=1$, $c_1\mu_1=c_1\mu_{12}=1$, and $c_2\mu_2=\frac{1}{16}$ are fixed. The top row shows the mean response time under the T1T2 policy with various $(T_1,T_2)$ threshold values, and the bottom row compares the mean response time under the ``optimized'' T1T2 policy and two T1 policies.

Static robustness: T1T2 vs. T1

(a)

(b)

Figure 7.8 (top row) shows the mean response time under the T1T2 policy with various $T_2$ values (a) as a function of $\rho_1$ (b) as a function of $\rho_2$. In column (a), $T_1=3$ and $T_2$ ranges over 1, 40, and 100. In column (b), $T_1=5$ and $T_2$ ranges over 1, 10, and 100. Figure 7.8 (bottom row) compares the mean response time under the T1T2 policy with a ``good'' $T_2$ value ($T_2=40$ in column (a), and $T_2=10$ in column (b)) with that under two T1 policies studied in Figure 7.6. Note that the parameter settings are exactly the same as in Figure 7.6. The T1T2 policy with parameters (3,$T_2$) studied in column (b) is designed to provide a wider stability region with similar mean response time to the optimized T1 policy at $\rho_2=0.4$. Recall that the T1 policy achieves its lowest mean response time, given $\rho_2=0.4$, when $T_1=3$ (Figure 7.6). Likewise, the T1T2 policy with parameters (5,$T_2$) studied in column (a) is designed to provide a wider stability region with similar mean response time to the T1(5) policy.

Figure 7.8 shows that when $T_2$ is too large (respectively, too small), the T1T2 policy with parameters ($T_1,T_2$) behaves like the T1 policy with parameter $T_1$ (respectively, the T2 policy with parameter $T_2$). Specifically, by comparing the T1T2(3,100) policy and the T1(3) policy in column (b), we observe that the T1T2 policy with parameters (3,100) behaves like the T1(3) policy. Further, by comparing the T1T2(3,1) policy in column (b) and the T2(1) policy shown in the middle row of Figure 7.6(b), we observe that the T1T2 policy (3,1) behaves like the T2(1) policy. Similar observation holds for column (a) as well.

When $T_2$ is chosen appropriately, the T1T2 policy has a slight advantage over the T1 policy. The bottom row of Figure 7.8(b) shows that when $\rho_2=0.4$, the mean response time under the T1T2(3,10) policy is comparable to that under the T1(3) policy. For higher $\rho_2$ (specifically, $\rho_2>0.6$), the T1T2(3,10) policy provides lower mean response time than the T1(3) policy, hence being more robust. However, the range of load for which the T1T2(3,10) policy provides low response time is limited. For example, when $\rho_2=0.8$, the mean response time under the T1T2 policy with parameters (3,$T_2$) with any value of $T_2$ (the top row of Figure 7.8(b)) is significantly higher than the T1(19) policy. Again, similar observation holds for column (a) as well.

The inadequacy of the T1T2 policy is primarily due to the fact that the T1T2 policy operates like the T2 policy at higher load, but the mean response time of the T2 policy is typically poor at any load as compared to the optimized T1 policy. This motivates us to introduce a new policy, the ADT policy.