Page 403 - A First Course In Stochastic Models

398 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

approximation to the percentiles η(p) of the waiting-time distribution of the delayed
customers is provided by

2 2
η app (p) = (1 − c )η det (p) + c η exp (p), 0 < p < 1.
S S
However, it turns out that in the batch-arrival case the two-moment approximation
to η(p) works only for the higher percentiles. Fortunately, higher percentiles are
X
usually the percentiles of interest in practice. Table 9.6.3 gives for the M /E 2 /c
queue the exact and approximate values of the conditional waiting-time percentiles
η(p) both for the case of a constant batch size and the case of a geometrically
distributed batch size. In both cases the mean batch size E(X) = 3. The normal-
ization E(S) = 1 is used for the service time. The percentiles η exp (p) for exponen-
tial services and η det (p) for deterministic services have been computed from the
asymptotic expansions (9.6.39) and (9.6.47). These asymptotic expansions already
apply for moderate values of x provided the traffic load on the system is not very
small. An appropriate measure for the traffic load is the probability that all servers
c−1
are simultaneously busy. This probability is given by P B = 1 − p j . As a
j=0
rule of thumb, the asymptotic expansions can be used for practical purposes for
√
x ≥ E(X)E(S)/ c when P B ≥ 0.2.
9.7 THE GI/G/c QUEUE

It seems obvious that the general GI/G/c queue offers enormous difficulties in
getting practically useful results. Nevertheless, using specialized techniques for
solving large-scale systems of linear equations for structured Markov chains, the
continuous-time Markov chain approach has proved to be quite useful for an exact
analysis of the GI/G/c queue when the interarrival time and service time both have
phase-type distributions; see also Van Hoorn and Seelen (1986) for an approxima-
tive analysis. By a detailed state description involving sufficient information about
the number of customers present and the status of both the arrival in progress
and the services in progress, it is possible to set up the equilibrium equations for
the microstate probabilities. The resulting large-scale system of linear equations
possesses a structure enabling the application of specialized algorithms to solve
numerically the equations, provided the number of servers is not too large; see
Seelen et al. (1985) and Takahashi and Takami (1976). However, this numerical
approach is not suited to routine calculations. The specialized algorithms involve
a clever use of asymptotic expansions for the GI/G/c queue. It is assumed that
the server utilization ρ = λE(S)/c is smaller than 1, where λ denotes the average
arrival rate and E(S) is the mean service time.

Asymptotic expansions
Under Assumption 9.2.1 with B(t) replaced by B(ct), asymptotic expansions can
be given for the state probabilities p j and the waiting-time probabilities W q (x). It