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 rule [45],
which biases in favor of jobs with
high (high importance) and high (small expected size).
Applying the c rule to our setting, server 2 serves type 1 jobs
(rather than type 2 jobs) if
, or queue 2 is
empty. The 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 rule may lead to
instability even if and [71,181]
More recently, Mandelbaum and Stolyar as well as van Mieghem
have introduced and analyzed the *generalized rule*.
However, in our model, the generalized rule reduces to
the 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 rule with respect to mean response time, guaranteeing stability whenever and [181,205]. We refer to this threshold-based policy as the T1 policy, since it places a threshold value, , on queue 1, so that server 2 processes type 1 jobs only when there are at least 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 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,
, where threshold is used when the length
of queue 2 is . 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].