State of the art in resource allocation policies for the Beneficiary-Donor model

There has been a large amount of prior work on the Beneficiary-Donor model, the majority of which has focused on proving the optimality of allocation policies in limiting or special cases. With respect to calculating mean response times, only coarse approximations exist for most of the allocation policies in our model. By contrast, dimensionality reduction (DR) developed in Chapter 3 allows us to analyze these and other allocation policies with respect to mean response time, as well as static and dynamic robustness.

One common allocation policy is the $c\mu$ rule [45], which biases in favor of jobs with high $c$ (high importance) and high $\mu$ (small expected size). Applying the c$\mu$ rule to our setting, server 2 serves type 1 jobs (rather than type 2 jobs) if $c_1\mu _{12}> c_2\mu _2$, or queue 2 is empty. The $c\mu$ rule is provably optimal when server 1 does not exist [45] or in the fluid limit [125,182]. However, Harrison as well as Squillante et. al. have shown that $c\mu$ rule may lead to instability even if $\hat\rho_1<1$ and $\rho_2<1$ [71,181] More recently, Mandelbaum and Stolyar as well as van Mieghem have introduced and analyzed the generalized $c\mu$ rule. However, in our model, the generalized $c\mu$ rule reduces to the $c\mu$ rule and hence has the same stability issues [121,126].

In light of this instability, Squillante et. al. and Williams have independently proposed a threshold-based policy that, under the right choice of threshold value, improves upon the $c\mu$ rule with respect to mean response time, guaranteeing stability whenever $\hat\rho_1<1$ and $\rho_2<1$ [181,205]. We refer to this threshold-based policy as the T1 policy, since it places a threshold value, $T_1$, on queue 1, so that server 2 processes type 1 jobs only when there are at least $T_1$ jobs of type 1, or if queue 2 is empty. The rest of the time, server 2 works on type 2 jobs. This ``reserves'' a certain amount of work for server 1, preventing server 1 from being under-utilized and server 2 from becoming overloaded, as can happen under the $c\mu$ rule. Bell an Williams prove the optimality of the T1 policy for a model closely related to ours in the heavy traffic limit [17].

However, studies by Ahn et. al. and Meyn suggest that the T1 policy is not optimal in general [4,125]. Ahn et. al. characterize the optimal policy with respect to minimizing the total holding cost until all the jobs in the system at time zero leave the system, assuming that there are no arrivals after time zero. They find that the optimal policy is in general a ``flexible'' T1 policy that allows a continuum of T1 thresholds, $\{T_1^{(i)}\}$, where threshold $T_1^{(i)}$ is used when the length of queue 2 is $i$. Meyn obtains, via a numerical approach, the optimal allocation policy in the Beneficiary-Donor model when both queues have finite buffers. Although not proven, the optimal policy appears to be a ``flexible'' T1 policy in the Beneficiary-Donor model.

All of the work above investigates a class of allocation policies that are optimal in limiting or special cases. In contrast, there has been little work on the analysis and evaluation of the mean response time of general allocation policies in our model, and no work evaluating robustness. Complicating this problem is the fact that the analysis involves 2D Markov chains; i.e., the Markov chains need to track both the number of type 1 jobs and the number of type 2 jobs. Hence, only approximate analyses exist for most of allocation policies in our model. For example, Squillante et. al. derive a coarse approximation for the mean response time of the T1 policy under Poisson arrivals based on vacation models [181]. The mean response time of other simple allocation policies (in more general models) such as (idle) cycle stealing, where server 2 works on type 1 jobs when queue 2 is empty, have also been analyzed (with approximation) either by matrix analytic methods with state space truncation [61,185,186] or by approximate solutions of a 2D Markov chain via state space decomposition [176].