Previous | Table of Contents | Next |
One of the important decisions to be made when there is more than one identical server is whether to keep separate queues for each server or to keep just one queue for all servers. For Poisson arrivals and exponential service times, the first option of separate queues can be modeled using m M/M/1 queues, each with an arrival rate of λ/m. The second option of one queue can be modeled using an M/M/m queue with an arrival rate of λ. It is easy to show that the single-queue alternative is better. We illustrate this with an example.
In general, if all jobs are identical, it is better to have just one queue than to have multiple queues. Of course, if some students need very short terminal sessions and others need very long sessions, this recommendation would not apply.
A special case of an M/M/m queue is the M/M/∞ queue with infinite servers. In such a queue, the jobs never have to wait. The response time is equal to the service time. The mean response time is equal to the mean service time regardless of the arrival rate. Such service centers are therefore also called delay centers. A delay center is used to represent dedicated resources, such as terminals in timesharing systems. Properties of such queues can be easily derived from those for M/M/m queues, Also results presented for M/G/∞ queues in Box 31.8 apply to delay centers as well.
An M/M/m/B queue is similar to the M/M/m queue except that the number of buffers B is finite. After B buffers are full, all arrivals are lost. We assume that B is greater than or equal to m; otherwise, some servers will never be able to operate due to a lack of buffers and the system will effectively operate as an M/M/B/B queue.
FIGURE 31.5 State transition diagram for an M/M/m/B queue.
The state transition diagram for an M/M/m/B queue is shown in Figure 31.5. The system can be modeled as a birth-death process using the following arrival and service rates:
Theorem 31.1 gives us the following expression for the probability of n jobs in the system:
In terms of the traffic intensity ρ = λ/mµ, we have
The probability of zero jobs in the system is computed by the relationship
This gives
or
Using the expression for pn, the mean number of jobs in the system E[n] and the mean number of jobs in the queue E[nq] can be computed straightforwardly:
Variance and other statistics on n and nq can be similarly computed.
All arrivals occurring when the system is in the state n = B are lost. The rate of the jobs actually entering the system, called effective arrival rate, is
The difference λ λ = λpB represents the packet loss rate.
Since the jobs are not lost after entering the system, Littles law can be used to determine the mean response time:
Similarly, the mean waiting time is
If we observe the system for a long time, T seconds, for instance, the total number of jobs arriving and getting service will be λT. Tle total busy time of m servers to service these jobs will be λT/µ, and the utilization of each server will be
The probability of the full system is given by pB. For a M/M/m/m system, the number of buffers is exactly equal to the number of servers, and the loss probability is
This formula is called Erlangs loss formula. It was originally derived by Erlang to compute the probability of lost phone calls at a telephone exchange. It turns out that the formula is valid not only for an M/M/m/m queue but also for M/G/m/m queues.
The results for the M/M/m/B queues are summarized in Box 31.3. For the special case of a single server, many of the results can be expressed in closed forms. This special case is summarized in Box 31.4. The following example illustrates the application of these results.
p1 = ρp0 = 0.25p0
p2 = ρ2p0 = 0.252 p0 = 0.0625p0
p0 + p1 + p2 = 1 = ⇒ p0 + 0.25p0 + 0.0625p0 = 1 = ⇒ p0
Previous | Table of Contents | Next |