The Buzen-Bondi (BB) approximation

The BB approximation is based on an intuitive observation that the ``improvement'' of priority scheduling over FCFS scheduling under multiple servers is similar to that for the case of a single server:

$$\frac{\mbox{{\bf\sf E}}\left[ D^{\mbox{\scriptsize M/GI/}k\m... ...iptsize M/GI/1/FCFS}} \right]} \equiv \mbox{ scaling factor}.$$ (4.2)

Here $\mbox{{\bf\sf E}}\left[ D^{\mbox{\scriptsize M/GI/}k\mbox{\scriptsize /prio}} \right]$ is the overall mean delay under priority scheduling with $k$ servers of speed $1/k$, and $\mbox{{\bf\sf E}}\left[ D^{\mbox{\scriptsize M/GI/}k\mbox{\scriptsize /FCFS}} \right]$ is defined similarly for FCFS. This relation is exact when job sizes are exponential with the same mean for all classes.

Specifically, BB analyzes the mean delay of class $i$ jobs, $\mbox{{\bf\sf E}}\left[ D_i \right]$, by analyzing both the mean delay over classes 1 to $i$, $\mbox{{\bf\sf E}}\left[ D \right]$, and the mean delay of the higher priority classes (classes 1 to $i-1$), $\mbox{{\bf\sf E}}\left[ D_H \right]$, and then using the following relation:

$$\mbox{{\bf\sf E}}\left[ D \right] = \frac{\lambda_H}{\lambda... ...i}{\lambda_H + \lambda_i} \mbox{{\bf\sf E}}\left[ D_i \right],$$

where $\lambda_H$ and $\lambda_i$ are the arrival rates of the higher priority classes and class $i$ jobs, respectively. To compute $\mbox{{\bf\sf E}}\left[ D \right]$ (respectively, $\mbox{{\bf\sf E}}\left[ D_H \right]$), BB aggregates classes 1 to $i$ (respectively, classes 1 to $i-1$) into a single class and analyzes the corresponding M/GI/$k$/FCFS queue (e.g. via known approximations [27,141]), and then calibrates this result using the scaling factor in (4.2), as shown in (4.1).