2. PRELIMINARIES

Throughout this article, we assume that the generic service time B with distribution function F in the M/G/1 queue satisfies the following assumption.

Assumption 1: The generic service time B has an exponential moment (i.e., E exp(γB) < ∞ for some γ > 0).

In addition, let the stability condition ρ = λEB < 1 hold, where λ is the rate of the Poisson arrival process. The proofs in this article rely on some properties of the busy-period length L and related random variables, which we derive in this section.

Under Assumption 1, Cox and Smith [3] have shown that P(L > x) ∼ bx^−3/2e^−cx for certain constants b,c > 0. In particular, L has decay rate c. In fact, by expression (46) in Cox and Smith [3, p.154], c = λ − ζ − λg(ζ), where g is the Laplace transform of the service-time distribution and ζ < 0 is such that g′(ζ) = −λ⁻¹. Hence, ζ is the root of the derivative of the function m(x) = λ − x − λg(x). Since m(x) attains its maximum at the point ζ, we can write c in terms of the Legendre transform of B:

Remark: This expression shows up as well in the following context. Consider a Poisson stream, with intensity λ, of independent and identically distributed (i.i.d.) jobs, where every job is distributed according to the random variable B. Let A(x) denote the amount of work generated in an arbitrary time window of length x. It is an easy corollary of Cramér's theorem that

Noting that

we observe that P(L > x) and P(A(x) > x) have the same decay rate. This is somewhat surprising, as {A(x) > x} obviously depends just on A(x) (i.e., the amount of traffic in a window of length x), whereas {L > x} depends on A(y) for all y ∈ [0,x], due to

Here, B₁ is the first service time in the busy period L.

In renewal theory, the notion of residual life, also known as excess or forward-recurrence time, is standard. Let

be the residual life of a busy period. Then

; see, for instance, Cox [2]. Using standard calculus, we find

Hence,

has the same decay rate as L.

Another ingredient used in the proofs below is the M/G/1 queue with truncated generic service time B ∧ τ, τ > 0. Call this the τ-queue and let L(τ) denote the length of a busy period (a τ-busy period) in this queue. Let

be its residual life and define L*(τ) to be the length of a τ-busy period in which the first service time B₁ is at least τ; that is,

We now show that the random variables

have the same decay rate.

Lemma 2: Let τ > 0 be such that P(B ≥ τ) > 0. Then

Proof: We show that L and L* have the same decay rate. The proof is then completed by using (5). Assume that τ > 0 is such that P(B ≥ τ) > 0. If B₁ ≥ τ, then the first service time is maximal in the τ-queue, as all service times are bounded by τ. Hence,

Further,

From (6), it follows that P(L*(τ) > x) and P(L(τ) ≥ x) differ only by a factor independent of x. Hence,

. █

In this article, we need the following lemma about the decay rate of the sum of two independent random variables.

Lemma 3: Let X and Y be nonnegative, independent random variables such that dr(X) = α₁ and dr(Y) = α₂ for some α₁,α₂ > 0. Then dr(X + Y) = min{α₁,α₂}.

Proof: Since both X and Y are positive, −min{α₁,α₂} is clearly a lower bound for lim inf_x→∞ x⁻¹ log P(X + Y > x). For the upper bound, let

be fixed. Then,

For x sufficiently large, for all i ∈ {0,…,n − 1},

Hence,

Since (7) holds for every

, we can take the limits n → ∞ and ε ↓ 0, and the result follows. █

Let D be the time from the arrival of a customer until the first moment that the system is empty. The following proposition is valid even when Assumption 1 does not hold.

Proposition 4: Consider a stationary queue with an arbitrary service-time distribution, Poisson arrivals, and a work-conserving discipline. Then

, where P(A = 1) = ρ = 1 − P(A = 0) and

are independent.

Proof: The value of the random variable D does not depend on the service discipline. There are two possibilities. With probability 1 − ρ, the customer finds the system empty. In this case, D is just the length L of the busy period started by the customer. Second, if our customer enters a busy system, then the server can first finish all the work in the system apart from the work of our tagged customer. The moment the remainder of the original busy period, which has length

, is finished, our customer starts a subbusy period. This length of this subbusy period, which is independent of

, is distributed like L. █

For the stationary τ-queue with Poisson arrivals and a work-conserving discipline, we have the following corollary.

Corollary 5: In the stationary τ-queue, the random variable D satisfies

, where P(A(τ) = 1) = λE(B ∧ τ). If the customer has service time τ in the τ-queue, then

.

Since the system is work-conserving, the sojourn time of a customer is not longer than D. Hence, V ≤_st D for every service discipline. Since

satisfy the conditions of Lemma 3, the following corollary holds.

Corollary 6: For every work-conserving service discipline, the sojourn time V of a customer in the stationary queue satisfies

An immediate consequence of this corollary and Theorem 1, which will be proved in the next section, is the following.

Corollary 7: The FB discipline minimizes the decay rate of the sojourn time in the class of work-conserving disciplines.

In Section 4, we indicate that for service times with a finite exponential moment, there are disciplines with a strictly larger decay rate than FB (e.g., FIFO).

Interestingly, for service times with certain Gamma distributions, the FB discipline stochastically minimizes the queue length, as was mentioned in Section 1, but the sojourn time has the smallest decay rate. This shows that optimizing one characteristic in a queue could have an ill effect on other characteristics.

The existence of a finite exponential moment in the corollary is crucial: For heavy-tailed service times, the tail of V cannot be bounded by that of L. For example, in the M/G/1 FIFO queue with service times satisfying

, where

is a slowly varying function at ∞ and ν > 1, De Meyer and Teugels [4] showed that

It may be seen that in this case, the tail of

, the residual life of the generic service time B, is one degree heavier than that of B. Now, note that for the FIFO discipline, we have

. Hence, the tail of V is at least one degree heavier than that of L; see also Borst et al. [1] for further references. In the light-tailed case, this phenomenon is absent because the tails of

have the same decay rate.

3. PROOF OF THE THEOREM

In this section, Theorem 1 is proved. The results in this section rely on the following decomposition of V. Let V(τ) be the sojourn time in the stationary M/G/1 queue of a customer with service time τ. The sojourn time V of an arbitrary customer in the stationary queue satisfies

Here, F is the service-time distribution. Hence, we may write P(V > x) = E_B P(V(B) > x), where B is a generic service time independent of V(τ), and E_B denotes the expectation w.r.t. B. Theorem 1 is proved using this representation of V. In Proposition 8, we compute the decay rate of V(τ).

Proposition 8: Let τ > 0 be such that P(B ≥ τ) > 0. If the service-time distribution satisfies Assumption 1, then dr(V(τ)) = dr(L(τ)).

Proof: By the nature of the FB discipline, the sojourn time V(τ) of a customer with service time τ who enters a stationary queue is the time until the first epoch that no customers younger than τ are present. This is the time until the end of the τ-busy period that he either finds in the τ-queue, or starts. By Corollary 5, V(τ) then satisfies

where

is the residual life of a τ-busy period, L*(τ) is a τ-busy period that starts with a customer with service time τ,

and

are independent. By Lemma 2, the random variables

satisfy the condition of Lemma 3. From (9) and Lemma 2, it follows that

This completes the proof. █

Having found the lower bound for the decay rate in Corollary 6, the following lemma provides the basis for finding the upper bound. The endpoint x_F ∈ [0,∞] of the service-time distribution F is defined as x_F = inf{u ≥ 0 : F(u) = 1}.

Lemma 9: Let V be the sojourn time of a customer in the stationary M/G/1 FB queue. Suppose the service-time distribution satisfies Assumption 1. If τ₀ > 0 and P(B ≥ τ₀) > 0, then

Here, F is the distribution function of the generic service time B.

Proof: We have

Using the representation (8), we find

Since log x is a concave function, applying Jensen's inequality to the conditional expectation in (13) yields

From (12)–(14), it follows that Θ := lim inf_x→∞(1/x)log P(V > x) satisfies

Applying Fatou's lemma to (15) yields

The result now follows from Proposition 8. █

The following lemma is used to develop the upper bound for the decay rate of V from Lemma 9. We introduce the notation c(τ) = dr(L(τ)), so that c = dr(L) = c(x_F).

Lemma 10: The function c(τ) is decreasing in τ. Furthermore, c(τ) → c(x_F) as τ → x_F.

Proof: For all τ, the function h_τ(θ) = θ − λ(Ee^θ(B∧τ) − 1) is concave in θ, since any moment generating function is convex. Furthermore, lim_θ→−∞ h_τ(θ) = lim_θ→∞ h_τ(θ) = −∞. By definition of L(τ) and (3), we can write c(τ) = sup_θ{h_τ(θ)}. Then c(τ) is decreasing in τ, since h_τ(θ) is decreasing in τ. Since c(τ) ≥ h_τ(0) = 0 for all τ and c(τ) is decreasing, c(τ) converges for τ → x_F. Now, note that h_τ(θ) is continuous in τ for all θ ∈ [0,sup{η : Ee^ηB < ∞}), even if B has a discrete distribution. Since the supremum of θ − λ(Ee^θB − 1) is attained in this interval, we have lim_τ→xF c(τ) = c(x_F). █

Proposition 11: Let V be the sojourn time of a customer in the stationary M/G/1 FB queue. If the service-time distribution satisfies Assumption 1, then

Proof: If P(B = x_F) > 0, then choosing τ₀ = x_F in (11) yields

and (16) holds. Assume P(B = x_F) = 0 and let ε > 0. By Lemma 10, there exists an x_ε < x_F such that c(τ) ≤ c + ε for all τ ≥ x_ε. Choosing τ₀ = x_ε in (11) then yields

Since ε > 0 was arbitrary, the lower bound (16) follows. █

Proof of Theorem 1: The lower bound for dr(V) is established in Corollary 6, and the upper bound in Proposition 11. █