Threshold-based policies in Beneficiary-Donor model

Figure 3.21: Threshold-based policies for the Beneficiary-Donor model. (a) The Beneficiary-Donor model. (b)-(c) show examples of threshold-based policies for the Beneficiary-Donor model: whether server 2 works on jobs from queue 1 or queue 2 is shown as a function of the length of queue 1, $N_1$, and the length of queue 2, $N_2$.

(a) Beneficiary-Donor model.

(b) type 1 threshold-based policy

(c) type 2 threshold-based policy

We consider a broad family of threshold-based (resource allocation) policies in the Beneficiary-Donor model, as shown in Figure 3.21(a). Here, jobs arrive at queue 1 and queue 2 according to Poisson processes with rate $\lambda_1$ and $\lambda_2$, respectively, and their service demands have exponential distributions. Server 1 processes only jobs in queue 1 with rate $\mu_1$. Server 2 can process either jobs in queue 1 with rate $\mu_{12}$ or jobs in queue 2 with rate $\mu_2$, and which jobs are processed by server 2 is determined by the queue lengths (the length of queue 1, $N_1$, and the length of queue 2, $N_2$) and threshold values. Figures 3.21(b)-(c) show examples of such threshold-based policies. We assume that there are a finite number of thresholds, and the rules are enforced preemptively. That is, there exists a threshold on queue 1, $\kappa\equiv T_1^{(i)}$, such that server 2 processes jobs in queue 1 whenever $N_1\geq \kappa$ (type 1 threshold-based policy, as shown in Figure 3.21(b)), or there exists a threshold on queue 2, $\kappa\equiv T_2^{(i)}$, such that server 2 processes jobs in queue 2 whenever $N_2\geq \kappa$ (type 2 threshold-based policy, as shown in Figure 3.21(c)). We will study the performance of these threshold-based policies in Chapter 7. Below, we model the Beneficiary-Donor model with the threshold-based policies as GFB processes.

The number of jobs in the system under the threshold-based policies (both type 1 and type 2) can be modeled as a GFB process. For the type 1 threshold-based policy, we define the background process so that it tracks the number of jobs in queue 1, including the jobs in service, $N_1$; we define the foreground process so that it tracks the number of jobs in queue 2, including the job in service, $N_2$. Specifically, level $\ell$ in the background process (respectively, foreground process) corresponds to the state with $N_1=\ell$ (respectively, $N_2=\ell$). Likewise, for the type 2 threshold-based policy, we define the background process as tracking $N_2$ and the foreground process as tracking $N_1$.

Now, it is easy to see that these foreground and background processes constitute a GFB process. For the type 1 threshold-based policy, as long as $N_1\geq \kappa$, the foreground and background processes can be modeled as birth-and-death processes, respectively. Figure 3.22(a) shows the background process when $N_1\geq \kappa$, and Figure 3.22(b) shows the foreground process given $N_1\geq \kappa$. Since $N_1\geq \kappa$, server 2 processes jobs in queue 1, and jobs are completed with rate $2\mu_1$ from queue 1 (background process), while there is no job completion from queue 2 (foreground process). Also, any transition from level $<\kappa$ to level $\geq\kappa$ is (from level $\kappa-1$) to level $\kappa$ in the background process, since $N_1$ is never incremented more than one at a time. Further, any transition changes the level of the foreground process by at most one, since any event (job arrival, or job completion) changes $N_2$ by at most one. Thus, these foreground and background processes constitute a GFB process. Likewise, for the type 2 threshold-based policy, as long as $N_2\geq \kappa$, the foreground and background processes can be modeled as birth-and-death processes, respectively, as shown in Figures 3.22(c)-(d). Again, since any event changes $N_1$ and $N_2$ by at most one, these foreground and background processes constitute a GFB process.

Figure 3.22: Examples of GFB processes: Threshold-based policies for the Beneficiary-Donor model. The top row illustrates the GFB process for the type 1 threshold-based policy. (a) Markov chain for the number of jobs in queue 1, $N_1$, (background process) when $N_1\geq \kappa$. (b) Markov chain for the number of jobs in queue 2, $N_2$ (foreground process) when $N_1\geq \kappa$. The bottom row illustrates the GFB process for the type 2 threshold-based policy. (c) Markov chain for $N_2$, (background process) when $N_2\geq \kappa$. (d) Markov chain for $N_1$ (foreground process) when $N_2\geq \kappa$.

Type 1 threshold-based policy

(a) number of jobs in queue 1, $N_1$, when $N_1\geq \kappa$

(b) number of jobs in queue 2 when $N_1\geq \kappa$

Type 2 threshold-based policy

(c) number of jobs in queue 2, $N_2$, when $N_2\geq \kappa$

(d) number of jobs in queue 1 when $N_2\geq \kappa$