4.8 Useful Results For Difficult-To-Analyze Queueing
Systems
4.8.1 Why Are M/G/m, G/G/1, and G/G/m
Difficult?
The
natural extension of
the M/G/1 model of Section 4.7 is the M/Gm case, in which m
independent and identical
servers process users from a common queue with service times
described by some
"general" type of pdf. Unfortunately, unlike the
transition from the M/M/1 to
the M/M/m case, which was straightforward, the transition from the
M/G/1 to the M/G/m
model involves a "quantum jump" in the level of analytical
complexity.
To see why, it is worthwhile to return to the
M/G/1 model and
review for a moment how our analysis of that queueing system
proceeded. It will be
recalled that in that case we identified instants of time (the
"epochs" t1,
t2, t3, . . . , that coincide with the
completion of service to
users) such that, given the number, n, of users present at the
queueing system at
epoch tk, one could immediately determine the probability
that n' users will
be present at epoch
tk+1. We did determine
these state transition probabilities in (4.64) and (4.65) after
deriving the expression
for  r,
(4.63).
Let us now consider the M/G/m case and attempt to
write a relation such
as (4.63) with the eventual aim of determining all state-transition
probabilities for a
state-transition diagram. Some thought will now convince the reader
that the presence of m
rather than 1 server makes it impossible to identify special
instants of time (epochs)
between which the M/G/m system undergoes state transitions that can
be described by easily
obtainable state-transition probabilities. At the instants of the
completion of a service,
for instance, it does not suffice any more to know just the number
of users in the system,
as with the M/G/1 system. In order to specify the transition
probabilities for the number
of users at the next completion of a service, one also needs to know
how long each one
of the other servers who are occupied at the instant of the
completion of a service
has been busy with its occupant. This, of course, is not a concern
in the M/G/1 case,
where there are never any other servers which can be busy at the
instant of a service
completion.
A similar rationale applies to the case of the G/G/1
queuing system. Here
there is only a single server, so, at the instant of a service
completion, we do not have
to worry about how long the other servers have been busy with their
present occupants.
However, interarrival gaps are now described by a general pdf
with
"memory." Therefore, at the time of a service completion,
it is now necessary to
know how long it has been since the last user arrival. That
information is necessary
to determine the probability that, say, r new users will
arrive at the queueing
system between the present service completion and the next
one. Consequently, the
transition probabilities, r, are also difficult to
obtain for the G/G/1
system.
Finally, it follows a fortiori that G/G/m systems pose
an even worse problem
to the analyst.
Contents of this section. We have
indicated above that
queueing systems of M/G/m, G/G/1, and G/G/m types are difficult to
analyze mathematically.
As a consequence, the readily usable, general, and exact results
about such systems are
very few. On the other hand, several quite useful
approximate results are
available, and these will be the focus of our attention in the
remainder of this section.
It should be noted that most of these results have been developed in
recent years, when
much attention has been turned to the question of approximations in
queueing theory. In
the following discussion we shall not derive or prove the validity
of the expressions that
will be presented. Appropriate references are provided for the
interested reader.
|
