1. INTRODUCTION
The M/D/1 queue with deterministic services is a simple and generally useful model. It is an appropriate model for telecommunication applications among others (for instance, to describe the cell scale queuing problem in ATM multiplexes). In view of the wide scope of applicability of the M/D/1 model in modern performance evaluation, it is important to have quick and accurate approximations for the state probabilities and the waiting-time probabilities. In this article such approximation will be provided in the form of explicit expressions that are in terms of geometric distributions and exponential densities.
The derivation of the approximation is based on a largely unknown but extremely useful approximation idea of Nojo and Watanabe [4]. It is well known that the probability distribution of a nonnegative random variable with a squared coefficient of variation of at least ½ can be approximated by a Coxian-2 distribution by matching the first two moments (see, e.g., Tijms [5]). The squared coefficient of variation is the ratio of the variance and the squared mean. In their article, Nojo and Watanabe [4] presented a method to approximate the probability distribution of a nonnegative random variable with a squared coefficient of variation less than ½ by a two-phase distribution with branching probabilities that are negative or larger than one. Using this magical idea, continuous-time Markov chain analysis can be used by doing calculations with negative numbers as if they were legitimate probabilities (see also Van Hoorn and Seelen [6]). The approximation of a random lifetime X through a two-phase process is as follows. The process starts in phase 1. It stays in phase 1 for an exponentially distributed time with mean 1/γ. Upon completion of the sojourn time in phase 1, the process expires with probability r1 and moves to phase 2 with probability 1 − r1. The sojourn time in phase 2 is also exponentially distributed with mean 1/γ. Upon completion of the sojourn time in phase 2, the process expires with probability r2 and returns to phase 1 with probability 1 − r2. In phase 1, the process starts anew. The idea is to approximate the original lifetime X by the time it takes until the two-phase process expires. For a random variable X with squared coefficient of variation cX2 < ½, it is, under certain side conditions, possible to fit a two-phase process matching the first three moments of X when a negative value or a value larger than one are allowed for the branching probabilities r1 and r2. These side conditions are satisfied when X has a deterministic distribution. Using the Laplace transform
of the density of the expiration time in the two-phase process, it is matter of algebra to derive that
when X is deterministic and equals the constant D.
The remainder of the article is organized as follows. In Section 2 we present the explicit expression for the approximations to the state probabilities and the waiting-time probabilities in the M/D/1 queue with infinite waiting room. Approximations for the finite-capacity M/D/1/N + 1 queue are discussed in Section 3. We also give numerical results showing how amazingly accurate the approximations are.
2. THE M/D/1 QUEUE
In the single-server M/D/1 queue, the arrival process of customers is a Poisson process with rate λ and the service time of any customer is a constant D. There is an infinite waiting room. Customers are served in order of arrival. It is assumed that the offered load,
is smaller than one. Denoting by pj(t) the probability of having j customers in the system at time t, the state probability pj is defined by
Also, letting Dn denote the delay in queue of the nth arrival, the waiting-distribution function Wq(x) is defined by
Numerical methods for the exact computation of the pj and Wq(x) are available (see, e.g., Tijms [5]). However, for modern performance analysis in telecommunication applications, it is useful to have quick and accurate approximations.
Approximation Result 1: For any x ≥ 0, the complementary waiting-time distribution function 1 − Wq(x) can be approximated by
where c(D,ρ) is the real number
for
and c(D,ρ) is the complex number
otherwise.
The derivation of this result proceeds as follows. In the general M/G/1 queue, the Laplace transform of the complementary waiting-time distribution 1 − Wq(x) is given by
where f*(s) is the Laplace transform of the service time density (see, e.g., Tijms [5]). Let us now substitute in the right-hand side of (3) the Laplace transform (1) with γ = 2/D, r1 = −1, and
. In other words, the deterministic service distribution is approximated by the two-phase distribution discussed in Section 1. The right-hand side of (3) then becomes, after some algebra,
Denote the numerator of this expression by N(s) and the denominator by Q(s). The Laplace transform N(s)/Q(s) can be analytically inverted, using partial fraction expansion. The (complex) roots of the denominator Q(s) = D2s2 + (4 − ρ)Ds + 6 − 6ρ are
Partial fraction expansion gives
Then inversion gives that N(s)/Q(s) is the Laplace transform of
It is then a matter of simple algebra to get Result 1.
For several values of ρ, we give in Table 1 the approximate and exact values of 1 − Wq(x) for a number of x values. In all of the examples, the normalization D = 1 is used. The results in Table 1 show that the approximation is remarkably accurate. The accuracy also applies for small tail probabilities. However, depending on ρ, for very small tail probabilities, the approximate value of 1 − Wq(x) might become negative. Fortunately, for very small tail probabilities, one has available the useful asymptotic expansion
where τ = 1/η with η the unique root of the equation ρ(1 − x) + x ln(x) = 0 on (0,1) (see, e.g., Tijms [5, p.383]). It is interesting to observe that the solution η = η(ρ) can be very well approximated by the polynomial
The absolute error of this polynomial approximation is less than 1.1 × 10−5 for all practically relevant values of ρ (i.e., for all ρ ≥ 0.2).
Waiting-Time Probabilities in M/D/1 Queue
Next, we turn to approximations for the state probabilities. For the general M/G/1 queue, the generating function
of the state probabilities pj is given by
where f*(s) is the Laplace transform of the service time density (see, e.g., Tijms [5]). Substituting (1) with γ = 2/D, r1 = −1, and
in (4), we get, after some algebra, that
where
Denoting the complex roots of W(z) = 0 by z1, z2, and z3, we then find by partial fraction expansion that
where
The right-hand side of (7) can be inverted as
Defining the constants p and q by
it is a matter of tedious algebra to verify that the roots z1, z2, and z3 of the equation W(z) = 0 are given by
where w1, w2, and w3 are the complex roots of
Here we used the trick of reducing the equation x3 + px + q = 0 to the equation w6 + qw3 − (p3/27) = 0 by the change of variable x = w − (p/3w). It is standard to solve (10). The complex roots of the equation u3 = 1 are calculated as
Summarizing, we have the following result.
Approximation Result 2: For any j = 0,1,…, the state probability pj in the M/D/1 queue can be approximated by
where z1, z2, and z3 are calculated from (9)–(11) and the constants a1, a2, and a3 are calculated from (8).
The calculations for the approximate pj are simple and offer no numerical difficulties, unlike the calculations with the algebraic expression for the exact pj in Brun and Garcia [1]. For several values of ρ, we give in Table 2 the approximate and exact values of the tail probabilities
The results in Table 2 show that the approximations are remarkably accurate. The accuracy also holds for small tail probabilities. However, for very small values of Qj, it is better to use the asymptotic expansion
where τ is the same as in the asymptotic expansion of 1 − Wq(x) (see Tijms [5, p.378]).
The State Probabilities Qj in the M/D/1 Queue
3. THE M/D/1/N + 1 QUEUE
The M/D/1/N + 1 queue differs only from the M/D/1 queue by having a finite waiting room with capacity N rather than an infinite waiting room. An arriving customer who finds, upon arrival, the server busy and all of the N additional waiting places occupied is rejected and has no further influence on the system. In the discussion below, it is again assumed that ρ = λD is smaller than one. Under this assumption, the stationary state probabilities pj(N) in the M/D/1/N + 1 queue can be expressed in the corresponding state probabilities pj in the M/D/1 queue. The state probabilities pj(N) satisfy
where the proportionality constant γ is given by
(see, e.g., Tijms [5, p.410]). Thus, Approximation Result 2 leads directly to simple approximations for the state probabilities pj(N). In turn, the state probabilities pj(N) can be used to compute the stationary waiting-time distribution function Wq(x), using a beautiful result of Franx [2,3]. In Franx [2], a simple and numerically stable method was given to calculate the waiting-time probabilities in the multiserver M/D/c queue with infinite capacity. This exact method can be modified for the finite-capacity model when c = 1. For the M/D/1/N + 1 model, let us define Wq(x) = limn→∞ P(Dn ≤ x), with Dn denoting the delay in queue of the nth accepted customer. The following exact result holds for the M/D/1/N + 1 queue. For (k − 1)D ≤ x < kD and k = 1,…, N, the waiting-time probability Wq(x) is given by
where
for r = 0,1,…, N. This exact formula applies to the case of ρ ≥ 1 as well. For the case of ρ < 1, we can use the simple approximations for the pj(N) in order to get an easily calculated approximation for Wq(x).
In Table 3 we show that Approximation Result 2 leads to excellent approximations to the pj(N). For several values of ρ and N, we give the approximate and exact values of the rejection probability Prej = pN+1(N), the delay probability
, E(Lq), and σ(Lq), where E(Lq) and σ(Lq) denote the expected value and the standard deviation of the stationary queue size Lq.
Various Performance Measures for the M/D/1/N + 1 Queue
For several values of ρ and N, we give in Table 4 the approximate and exact values of 1 − Wq(x) for a number of x values. The results in Table 4 show an excellent performance of the approximation.
Results for 1 − Wq(x) in the M/D/1/N + 1 Queue
Summarizing, we can conclude for the M/D/1/N + 1 queue that approximating the deterministic service time distribution by a two-phase process with a negative branching probability leads to remarkably accurate approximations that are easy to use in practical applications. The approximation approach works only for the steady-state behavior of the system, not for the transient behavior. It is our conjecture that the approximation approach in conjunction with numerical Laplace inversion will lead to practically useful approximations for the stationary waiting-time probabilities in the notoriously difficult multiserver M/D/c/N + c queue. This will be the subject of further research.
