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" t₁, t₂, t₃, . . . , that coincide with the completion of service to users) such that, given the number, n, of users  present at the queueing system at epoch t_k, one could immediately determine the probability that n' users will be  present at epoch t_k+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.