Page 422 - A First Course In Stochastic Models

FINITE-CAPACITY QUEUES 417

X
is for instance the case in the M /G/c queue with general service times. In such
situations one might try to approximate the exact solution of the complex model
through the exact solutions of simpler related models. In this chapter we have
already seen several examples of such two-moment approximations. The rejection
probability itself is not directly amenable to a two-moment approximation, but
indirectly a two-moment approximation is possible through the ‘percentile’ N(α)
defined by

N(α) = the minimal buffer size for which the rejection probability P rej
does not exceed the value α.
2
X
This will be illustrated for the M /G/c/c +N queue. Denoting by c the squared
S
coefficient of the service time of a customer, the two-moment approximation to
N(α) is given by
2
2
N app (α) = (1 − c )N det (α) + c N exp (α), (9.8.14)
S S
where N det (α) and N exp (α) are the (approximate) values of the minimal buffer
X
X
size N(α) for the M /D/c/c + N queue and the M /M/c/c + N queue. The
buffer sizes N det (α) and N exp (α) are computed by using the (approximate) formula
for P rej in the particular cases of deterministic services and exponential services.
(∞)
Relatively simple algorithms are available to compute the state probabilities π in
j
X
X
the M /M/c queue and the M /D/c queue; see Section 9.6.3. The two-moment
2
approximation (9.8.14) is only recommended when c is not too large (say, 0 ≤
S
2
c ≤ 2).
S
Table 9.8.4 illustrates the performance of the two-moment approximation (9.8.14)
for the M/G/c/c+N queue, where the number of servers has the two values c = 1
2
and c = 10. For both Erlang-2 services (c = 0.5) and H 2 services with gamma
S
2
normalization (c = 2), the approximate and exact values of N(α) are given for
S
several values of α. Any fractional value resulting from the interpolation formula
(9.8.14) has been rounded up. The results in the table show an excellent perfor-
mance of the two-moment approximation and also nicely demonstrate that N(α)
increases logarithmically in α as α increases.
9.8.4 Discrete-Time Queueing Systems
Many practical queueing systems operate on a discrete-time basis. A discrete-time
queueing system is characterized by time-slotted service. A new service can only
start at the beginning of a time slot, and the service time is a multiple of time slots.
In applications the discrete-time queueing systems typically have finite buffers
to store incoming packets. Packets are the entities to be served. Let us assume
that there are c service channels and a buffer of capacity N to store incoming
packets. The buffer excludes any packet in service. Each service channel can handle
only one packet at a time. A new service can only start at the beginning of a
time slot. The service times of the packets are independent of each other. It is