5.5.1 Correction Factor

In an M / M / N queueing system with infinite queueing capacity, suppose that we start randomly sampling servers in the system until we find the first server who is available or free (if there is one). Let

B_j event that jth selected server is busy (not available)
F_j B_j^C = event that jth server selected is free (or available)
P{B₁B₂. . . B_jF_j+1} probability that the first free server is the (j + 1)st server selected

The server selection process here is a strictly random sampling without replacement. In effect, we are selecting servers in a "blindfolded" manner.

Now the probability P{B₁B₂. . . B_jF_j+1} corresponds, in an urban services context, to a dispatch probability, that is, the probability of assigning the (j + 1)st preferred server to a service request. If the nth server selected, say server s_n, is busy a fraction of time _sn, then a naive approach would be to assume that servers operate independently. In that case, we would have

P{B1B2. . . BjFj+1} s1s2. . . sj(1 - sj+1

j < N

P {B₁B₂. . . B_N} _si

We can see by inspection that this is mathematically incorrect since {B₁B₂. . . B_N} corresponds to the probability of saturation of the M / M / N system (i.e., all servers are simultaneously busy) and, as shown by (4.44), this is not equal to the product of utilization factors.

We can still utilize the multiplicative concept if we incorporate a suitable "correction factor." To do this, we write

Multiplying both numerator and denominator of the right-hand side by ^j(1 - ), we have

P{B₁B₂. . . B_jF_j+1}
= ^j(1 - )

(5.46)

If we define Q(N, p, j) to be the term preceding pJ(1 - p), we have

The factor Q(N, , j) indicates the extent to which the result of the server-independence argument must be "corrected" to obtain the exact result. Each of the j + 1 terms in the product comprising Q(N, , j) can be considered to be a separate correction factor indicating the relative amount by which or 1 - overestimates (or underestimates) the respective conditional probabilities of being busy or free. As shown in Problem 5.9, the exact expression for Q(N, , j) can be derived by conditioning on each possible number of servers busy in an M / M / N system, and then combining results by laws of conditional probability. The result is

Q(N, , j) =

In checking the result for a limiting case, we find that Q(N, , 0) = 1, indicating that the probability that the first selected server is free is exactly 1 - (a result in agreement with intuition, since = /N is the average fraction of time a server is busy). Additional work shows that Q(N, , 1) < 1, which implies that (l - ) is an overestimate of P{B₁F₂}. This is true since, given that the first selected server is busy, the probability P{F₂ | B₁} that the second selected server is free is less than (1 - ), the value predicted by the independence argument. Here, discovering that the first selected server is busy shifts the system state probabilities in the direction of busier states. One can show that if

> 1 -

(N 2

(5.49)

then Q(N, , j) is a monotonically decreasing function of j; otherwise, it is a unimodal function of j, reaching a minimum for some value of j, say j^o, and then increasing for all j greater than j^o. For illustrative purposes, plots of Q(8, , j) are given in Figure 5.18.

Even though the correction factor Q(N, , j) was derived assuming homogeneity of servers, one could conjecture that the same factor could be used as an approximation in an M / M / N system with distinguishable servers. This would seem especially appropriate for systems in which the workloads of servers do not differ too greatly and in which many different dispatch preference vectors (motivated by different customer locations) effectively simulate in the aggregate "blindfolded" selection of servers. Implementing this conjecture has yielded numerical results that are typically within 1 or 2 percent of the exact "hypercube" results.