Validation

In this section, we numerically evaluate the accuracy and running time of DR as well as its approximations, DR-PI and DR-CI, through the analysis of the preemptive priority queue (introduced in Section 3.4) and the size-based task assignment with cycle stealing under immediate dispatching, SBCS-ID, (introduced in Section 3.4). Note that the number of classes corresponds to the number of processes constituting an RFB process in the analysis of both the preemptive priority queue and SBCS-ID. Throughout we assume that the arrival process is Poisson. We will see that

• DR has a very small error in predicting the first order metric such as mean delay and mean queue length. Specifically, the error in DR is within 3% for a range of parameters (loads, service demand distributions, and the number of classes, $m$) in the analysis of both the preemptive priority queue and SBCS-ID.
• The error in DR is slightly larger but is still small in predicting the second order metric such as the second moment of the queue length. Specifically, the error is within 7% for a range of parameters in the analysis of SBCS-ID.
• The error in DR-PI and DP-CI is slightly larger than DR but is still small for both the first and second order metrics. Specifically, the error is within 6% (respectively, 10%) in predicting the first (respectively, second) order metric for a range of parameters in the analysis of SBCS-ID.
• DR is computationally quite efficient when it is applied to 2D Markov chains, i.e. RFB processes with $m=2$ (FB processes) and GFB processes. Specifically, in the analysis of the preemptive priority queue, the running time of DR is $\leq 0.1$ seconds for up to $k=10$ servers.
• The running time of DR can grow quickly as the number of processes, $m$, in an RFB process increases. Specifically, in the analysis of the preemptive priority queue with $k=2$ servers, the running time of DR is within 30 seconds for up to $m=11$ classes (processes); however, in the analysis of SBCS-ID, DR becomes computationally prohibitive with $m\geq 5$ classes (processes).
• DR-PI and DR-CI can reduce the running time of DR significantly. Specifically, in the analysis of SBCS-ID, the running time of DR-CI is within 30 seconds for up to $m=20$ classes (processes).

In all our experiments below, we use the algorithm in Figure 3.12 to compute R and G matrices, which we need in the analysis via DR, DR-PI, and DR-CI, and we set the error bound at $\epsilon = 10^{-6}$. All the experiments are run on a 1 GHz Pentium III with 512 MB RAM, using Matlab 6 running on Linux.