The MK-N and DR-A approximations

There are two sources of errors in MK-N and DR-A. The first source of error, which we call priority error, results from ignoring the priorities among the higher priority classes. The second source, which we call distribution error, results from the fact that the aggregated job size distribution matches only one moment in MK-N and three moments in DR-A.

Consider first the priority error. In the case of a single server, there is no priority error. This is because low priority jobs are excluded from service during busy periods of high priority classes, and its duration is the same regardless of whether or not the higher priority classes are prioritized. In the case of multiple servers, however, priority error exists, since low priority jobs are more likely to be present at the end of a busy period.

Next consider the distribution error. The distribution error exists even in the case of a single server unless the first two moments of the aggregated job size distribution are matched, as the mean delay of the lowest priority jobs, $\mbox{{\bf\sf E}}\left[ D_L \right]$, depends on the first two moments of the job size distributions:

$$\mbox{{\bf\sf E}}\left[ D_L \right] = \frac{\rho_H}{1-\rho_H... ...da \mbox{{\bf\sf E}}\left[ X^2 \right]}{2(1-\rho_H)(1-\rho)},$$ (4.3)

where $\rho_H$ is the load of high priority jobs, $\rho$ is the overall load, $\mbox{{\bf\sf E}}\left[ X_L \right]$ is the mean size of the lowest priority jobs, and $\mbox{{\bf\sf E}}\left[ X^2 \right]$ is the second moment of the overall job size distribution. Thus, MK-N has the distribution error even in the case of a single server, but DR-A does not in this case. In the case of multiple servers, matching even the first two or three moments is not sufficient in general. This can be gleaned from recent results illustrating the sensitivity of the stability conditions for the M/GI/$k$ systems to the exact tail behavior of the service distribution [172,203].

Figure 4.7 illustrates the quantitative difference in the priority and distribution errors in MK-N and DR-A. Overall, the error in MK-N can sometimes exceed 50%, while the error in DR-A never exceeds 5% for exponential job size distributions and never exceeds 10% for PH job size distributions. Note that MK-N does not show up in the bottom half of Figure 4.7 (PH job sizes) because the error is too great (usually $>50\%$) -- approximating a mixture of PH distributions with $C^2=8$ by an exponential distribution clearly does not work. Below, we discuss the error per class in MK-N and DR-A. (Class 1 is not discussed, since its analysis is exact via matrix analytic methods.)

For class 2 jobs (Figure 4.7, column 1), MK-N and DR-A are identical to DR and have little error when $C^2=1$. This is because we use DR in evaluating MK-N with two priority classes. When $C^2=8$, DR-A is still equivalent to DR for an M/PH/$k$ with two priority classes, and the error for DR is always within 5% for this case.

For class 3 (column 2), error in both MK-N and DR-A becomes apparent. Both approximations aggregate the two higher priority classes, and when $C^2=1$, the aggregated job size distribution is a two-phase hyperexponential distribution. The hyperexponential distribution is approximated by an exponential distribution in the MK-N approximation, while the exact two-phase hyperexponential distribution is used in DR-A. Therefore, the MK-N approximation has both priority error and distribution error, while DR-A has only priority error when $C^2=1$. We observe that the error in DR-A (priority error only) is orders of magnitude smaller than the error in MK-N (both priority and distribution error).

The effect of $\alpha$ on the error of MK-N in class 3 is significant. When $\alpha=1$ and $C^2=1$, MK-N (and DR-A) is exact, since the aggregated distribution is exponential. As $\alpha$ gets smaller or larger than 1, MK-N underestimates the mean delay. This makes intuitive sense because MK-N ignores the variability among the high priority classes, which leads to a lower mean delay estimate for the lower priority jobs. We can also observe that the error in MK-N is smaller when the high priority classes are small ($\alpha < 1$) as compared to the case when $\alpha > 1$. This is because when $\alpha$ is large, approximating the aggregated higher priority classes by an exponential distribution results in ignoring huge jobs in class 1, and ignoring huge jobs leads to a great underestimation in the mean delay of the low priority class.

The effect of $\alpha$ on the error of DR-A in class 3 is much smaller than the effect on MK-N. When $\alpha=1$ and $C^2=1$, DR-A is exact as is MK-N. When $\alpha=1$ and $C^2=8$, DR-A does not have distribution error but does have priority error. However, as for class 2, priority error is very small in this case as well. For all $\rho$'s and $C^2$'s, DR-A tends to slightly overestimates the mean delay for $\alpha < 1$, and it tends to slightly underestimates for $\alpha > 1$. This is explained by reasoning about the busy periods made up of the high priority classes, during which both servers are serving jobs of class 1 or 2. When smaller jobs have priority, more larger jobs are left at the end of a busy period. Since larger jobs are less likely to be balanced between two servers, one of the servers will likely become free sooner, which allows the lower priority class to get service sooner. When larger jobs have priority, both servers are likely to become free at a similar time as low priority (smaller) jobs can fill in the gaps. This causes the lower priority jobs to wait longer before they get service at either server. When $\alpha < 1$, smaller jobs have priority, but DR-A ignores the priority and the busy period estimated by DR-A is longer, which in turn yields overestimation of the mean delay. The underestimation for $\alpha > 1$ can be explained analogously.

Continuing with class 3, we see that the load does not significantly affect the class 3 error, but at higher load the error in MK-N is slightly larger and the error in DR-A is slightly smaller. This implies that the priority error is smaller and the distribution error is larger at higher load. The priority error is due to the error in estimating the busy period of the higher priority jobs, and at high load the busy period is long and the relative difference between priority scheduling and FCFS with respect to the length of the busy period is smaller. Larger distribution error at higher loads can be explained through an analogy to the case of a single server. Recall equation (4.3), the mean delay of the lower priority class in an M/PH/1 queue with two priority classes. The distribution error in this case corresponds to the error in the second moment of the job size, $\mbox{{\bf\sf E}}\left[ X^2 \right]$, and the term with the error, $\frac{\lambda \mbox{{\bf\sf E}}\left[ X^2 \right]}{2(1-\rho_H)(1-\rho)}$, increases as the load, $\rho$, approaches 1.

For class 4 (column 3), we observe that the error has a similar trend as in class 3. The only difference is that the aggregation in DR-A is no longer exact for class 4, even when $C^2=1$; however, we still see that DR-A always has a small error. We conclude that the priority error is small regardless of the load and the relative sizes among the classes, but ignoring the variability among the job sizes of higher priority classes (aggregated) can lead to significant error.