2. THE GI/G/1 QUEUE

In this section, we consider the GI/G/1 queue with partial rejection, which is also known as the finite GI/G/1 dam. Before we present our main result, we first introduce some notation and give a detailed model description.

Let T₁,T₂,… be the interarrival times of customers and denote the nth arrival epoch after time 0 by

. We assume that the interarrival times form an independent and identically distributed (i.i.d.) sequence and that

. The service requirement of the nth customer is denoted by S_n, n = 1,2,…, whereas S₁,S₂,… are also assumed to be i.i.d. Define

as the load of the system. We like to emphasize that ρ may take any (positive) value. To obtain a nontrivial model though, we additionally assume that

(otherwise P_K ≡ 1).

The workload process

is now defined recursively by (cf. [11])

Since the workload in the system is uniformly bounded, the process

is regenerative with customer arrivals into an empty system being regeneration points, independent of the load of the system. Let a regeneration cycle start at time 0 and define the first return time to state 0 by

Furthermore, let C_max be the cycle maximum of a busy cycle or, more formally,

Observe that, for

is the same for the finite dam and its infinite-buffer counterpart. So, without affecting the results, we will henceforth adopt the above definition of C_max when we consider the cycle maximum in the GI/G/1 queue with infinite-buffer capacity. Note that

if K = ∞ and ρ > 1.

From the workload process in the finite GI/G/1 dam we construct a process

, as in [19], by defining

Away from the boundaries, this process increases linearly at rate 1 and negative jumps occur at times T_n of size S_n, n = 1,2,…. By definition, jumps below zero are truncated and if the process hits state K, it remains in K until the next (downward) jump (see Fig. 1 for an illustration). In fact, we are only interested in the behavior of R(t) until it hits one of the boundaries, and in this region, the process

shows a strong resemblance to a risk process (where 0 is supposed to be an absorbing state).

Two sample paths of D(t) until it hits one of the boundaries, with corresponding R(t).

Due to the finite capacity, the process

is also regenerative, and regeneration points in the process correspond to downward jump epochs from level K. Hence, τ₀ can be alternatively defined by τ₀ := inf{t > 0 : R(t) ≥ K}.

Recall that P_K is the steady-state probability that an arriving customer is (partially) rejected. The main result in this section is the following theorem.

Theorem 2.1: For the GI/G/1 queue, we have

In the remaining part of this section, we present two proofs of Theorem 2.1. In the first proof, to be presented in Section 2.1, we take a direct approach, using the representation

and the above-mentioned definition of the cycle maximum. Equivalence is then shown using the machinery developed in [7].

The second proof, given in Section 2.2, establishes a link between the loss rate and the cycle maximum using an insightful regenerative argument. In particular, we utilize the fact that the number of losses in a cycle, given that at least one loss occurs, is geometrically distributed. The main step in this approach is the computation of the success parameter of that distribution. This is, again, established by results in [7].

2.1. Direct Approach

As mentioned, to determine the tail distribution of the cycle maximum in an infinite-capacity model, we may also assume that the workload is uniformly bounded as described earlier. So, consider one regeneration cycle of the process

(or equivalently

) and let a customer enter the system at time 0. Since the workload process has peaks at time epochs just after an arrival instant, we may write

Observe that the right-hand side of (3) corresponds to a hitting probability; starting in state K, (3) may be interpreted as the probability that state 0 is reached before R(t) hits state K again. Note that the process

embedded at points T_n is also recursively defined by the interarrival times and the service requirements. These two observations allow us to rewrite this embedded process as a monotone stochastic recursion with two absorbing states (0 and K): We define R₀ = K,R_n+1 = g(R_n,U_n), where U_n := (S_n+1,T_n) and

Thus, we start our recursion with initial reserve K, after which it evolves as an unrestricted random walk, until it leaves (0,K]. Moreover, it is always checked ahead whether a downward jump will not cause a negative workload, leading to absorption in state 0.

Now, Example 4 of Asmussen and Sigman [7] gives the corresponding dual stochastic recursion {V_n}, which is defined as V_n+1 = f (V_n,S_n+1,T_n), where

This recursion corresponds to the workload right after a jump, or the sojourn time, of a finite GI/G/1 dam. Under i.i.d. assumptions, V_n weakly converges to a random variable V as n → ∞; see, for example, Cohen [11, Chap. III.6]. Let

denote the first exit time of (0,K]. Then, Corollary 3.1 of [7] yields the following fundamental result:

Thus, the distribution of V can be written as a first-passage probability. Using (3) and taking x = K in (4), we have

Hence,

which completes the proof.

2.2. Regenerative Approach

Let L_K be the number of not fully accepted customers and let N_K be the total number of customer arrivals during a regeneration cycle. A basic regenerative argument yields

The denominator follows easily by

where I(·) is the indicator function. The numerator may be rewritten as

Moreover, observe that whenever the workload reaches level K and a customer is (partially) rejected, the process continues from level K starting with a new interarrival time, which clearly is independent of the past. Then the probability of an additional customer loss in the regeneration cycle is equal to the probability that the workload process reaches level K again before the end of the busy cycle. Denoting τ_K := inf{t > 0 : D(t) ≥ K|D(0) = K}, this leads to

Iterating this argument, we conclude that L_K|L_K ≥ 1 is geometrically distributed with success parameter 1 − q_K. Since the expectation of such a geometric distribution equals 1/(1 − q_K), we have to show that

to complete the proof. To do so, we use a similar construction of the “risk-type” process

as we did in the first proof. Note that (8) corresponds to the probability that from initial level 0, R(t) reaches level 0 again before it hits level K. Again, this can be transformed into a monotone stochastic recursion with two absorbing barriers, 0 and K: Define R_n+1 = g(R_n,S_n+1,T_n), with

Thus, starting from level 0, R_n evolves as an unrestricted random walk until it leaves (0,K]. Note that it is indeed checked ahead whether the workload increases above level K before the next downward jump.

Now, another example of Asmussen and Sigman [7] provides the dual stochastic recursion {V_n}. In particular, Example 3 of [7] gives the dual function

defining the dual recursion V_n+1 = f (V_n,S_n+1,T_n). This recursion corresponds to the workload right before a jump (or the waiting time) in a finite GI/G/1 dam. Use Corollary 3.1 of [7] and take x = ε > 0 in (4) to show that

Recall that the V_n corresponds to the waiting time of the nth customer, and V thus represents the waiting time in steady state. Combining (5)–(9) completes the proof.

Remark 2.1: Both proofs rely on computing the dual of a recursion driven by a specific function f (x,z), which is monotone in x for every z. In general, the driving function f and its dual g are related by

We refer to [7] (in particular, Eq. (2.4)) for details.

3. DAMS WITH STATE-DEPENDENT RELEASE RATES

In this section, we consider the GI/G/1 dam with general release rate. We start with introducing some definitions and a description of the driving sequence of the queuing process. Next, we state the main result and give two proofs, analogous to the proofs in Section 2.

Consider the model of Section 2, but let the release rate be r(x) when the workload equals x. We assume that r(0) = 0 and that r(·) is strictly positive, left-continuous, and has a strictly positive right limit on (0,∞). Also, define

representing the time required for a workload x to drain in the absence of arrivals. We assume that θ(x) < ∞, 0 < x < ∞, indicating that state 0 can be reached in a finite amount of time. This ensures that C_max is well defined. Note that θ(·) is strictly increasing and we can, thus, unambigously speak of θ⁻¹(t). Similar to [14,19], we define

Then q(u,t) represents the workload level at time t if we start off from level u at time 0 and no arrivals have taken place in between.

Denote the workload process of the GI/G/1 queue with finite buffer K and general release rate function r(·) by

. Let T₀ = 0 and D^r(·)(0) = x. Between jump epochs, the workload process is defined recursively by (cf. [19])

and at the (k + 1)st jump epoch after time 0,

To exclude trivial cases where the workload is bounded from below, we assume that

, for all x > 0. Combined with the finite capacity and θ(x) < ∞ for all finite x, this ensures that the workload process

is still regenerative with customer arrivals into an empty system as regeneration points.

Define

, and let all random variables X^r(·) and

correspond to the model with release rates

, respectively, if the process is at level x. Similar to Section 2, we construct a “risk-type” process

by taking

. In between (the downward) jumps, the newly defined process is governed by the input rate function

and satisfies

Also, the risk-type process starts at

. In addition, if

starts at y and no jumps occur for t time units, its value increases, similar to the decrease in the workload process, to

Here,

, represents the time required to move from zero to x in the absence of negative jumps, with inverse

. Note that, for finite K,

, meaning that state 0 can be reached in a finite amount of time and the cycle maximum is also well defined in this case.

Theorem 3.1 For the GI/G/1 queue with general release rate, we have

or, alternatively,

We use a direct approach to show (10), thereby extending the proof in Section 2.1. To show (11), we follow the lines of Section 2.2, using an insightful regenerative argument and noting that the number of losses in a cycle, given that at least one loss occurs, has a geometric distribution. Let us start with (10).

Proof of (10): As noted earlier, the workload process

is still regenerative with customer arrivals into an empty system as regeneration points. The observation that the workload process has peaks at epochs right after an arrival instant, together with (3) and the construction of the process

, leads to

The probability in (12) can be interpreted as the probability that state 0 is reached before

hits state K again, starting off from level K. Define R₀ = K and

, with

Following [7], we construct the dual function corresponding to the described process

, yielding

and define {V_n} recursively by

. This process corresponds to a GI/G/1 queue with release rate

if the workload equals x, embedded at epochs right after a jump. We now complete the proof of (10) by combining the duality (4) between storage and risk processes with the expression (1) for P_K:

Next we turn to (11), which we show following the lines of Section 2.2.

Proof of (11): As mentioned earlier, the workload process is still regenerative, and we consider the total number of (partially) rejected customers during a regeneration cycle. We apply the same regenerative argument as in Section 2.2 and note that customers are rejected if and only if the process reaches level K before the end of the cycle (which happens with probability

. Moreover, after a customer rejection, the process continues from level K, starting with a new interarrival time. This implies that the probability of an additional customer loss is independent of the past or, equivalently, that K is also a regeneration point. Therefore, we may conclude that, given that at least one loss occurs and the process starts off from level K, the additional number of customer rejections is geometrically distributed with success parameter

. Thus, we have to show that

and combine (5)–(8) to complete the proof.

We start with the construction of the “risk-type” process

defined at the beginning of the section. We rewrite 1 − q_K as the probability that, starting from level

hits level 0 again before it reaches level K. Interpreting our process as a monotone stochastic recursion with two absorbing barriers, we define

, where

Again, using [7], it can be seen that the dual recursion is defined as

, with

The latter recursion corresponds to the workload at time epochs right before a jump. As the speed of the server is determined by the general release function, this does not equal the waiting time.

Finally, using Corollary 3.1 of [7] once more, we obtain

Hence, by combining (5)–(8), and (13), we also have shown the second part of the result. █

Remark 3.1: The constant

in (10) can easily be interpreted. As the interarrival times in both systems follow the same distribution, using (6), the constant equals the ratio of the respective cycle lengths.

Remark 3.2: A sample path argument can also provide some intuition into the equivalence between (10) and (11). First, the process

can easily be interpreted as the available buffer capacity of a dam with release rate r(x) when the content equals x. Second, to convert the risk-type process into a queuing process again, we use a reversibility argument, as in Asmussen and Kella [4] and Asmussen and Schock Petersen [6]. The sample path of this queuing process can essentially be obtained by time-reversing the sample path of

, resulting in a queuing process with service speed

when the workload equals x.

4. APPLICATIONS

In this section, we state some exact and asymptotic results for P_K by applying results for C_max, which are available in the literature. Given the results derived earlier, this leads to more transparent proofs of existing results and to results that are new.

4.1. Exact Expressions for P_K

In the literature, there are several studies devoted to the distribution of C_max for a variety of queuing models. We refer to Asmussen [2] for a survey of these results. The M/G/1 case has already been treated in [23]. Here, we give an analogous result for the GI/M/1 queue.

Corollary 4.1: Consider the finite GI/M/1 dam with ρ < 1 and service rate μ. Then

where H(x),x ≥ 0, is a function with Laplace–Stieltjes transform (LST)

with α(s) the LST of the interarrival time distribution.

Proof: The result follows immediately from Theorem 2.1 and formula (7.76) of Cohen [11], stating that for the GI/M/1 queue,

with H(x),x ≥ 0, defined as earlier. █

4.2. Asymptotics

Van Ommeren and De Kok [22] derived asymptotics for P_K in the GI/G/1 queue under light-tailed assumptions. They conclude, after a lengthy argument, that (under their assumptions)

, where f (x) ∼ g(x) denotes f (x)/g(x) → 1 as x → ∞. Asymptotics for the latter are due to Iglehart [16]: Under certain regularity conditions (see [16]), it holds that

for certain positive constants γ and D. Using Theorem 2.1, the proof of the main result of [19] is now trivial: Just combine Theorem 2.1 with (14) to (re-)obtain

For more details concerning specific assumptions and expressions for γ and D we refer to [16,22].

We conclude by giving results for the heavy-tailed case: Consider, again, the GI/G/1 queue, but assume now that service times belong to the subclass

of the class of subexponential distributions (see, e.g., Embrechts, Klüppelberg, and Mikosch [13] for a definition). This class contains all heavy-tailed distributions of interest, such as the Pareto, lognormal, and certain Weibull distributions.

Asymptotics for the cycle maximum can be found in [3]. If we combine these asymptotics with Theorem 2.1, we obtain (with N being the number of customers served in one busy cycle in the infinite buffer version of the GI/G/1 queue) the following corollary.

Corollary 4.2: If ρ < 1 and the service time

, then

Also, in case of Poisson arrivals, this result can be extended to queues with general service speeds; see [3] for details. Note that (10) and (11), combined with Remark 3.1, indeed result in the same asymptotics.

4.3. Poisson Arrivals and Takács' Formula

The equivalence in Theorem 2.1 can also be used the other way around: Given information on P_K, we derive a new identity for the distribution of C_max for queues with a general release rate. For the special M/G/1 case, the distribution of C_max is known through Takács' formula. We combine the results of Section 3 with an identity for P_K, which is valid under the additional assumptions of Poisson arrivals, and a stationary (embedded) workload distribution in case of infinite-buffer capacity (see, e.g., [1,9] for details). Under these assumptions, the steady-state distribution of the amount of work in the system found by a customer W^K,r(·) satisfies the following proportionality result:

Here, W^r(·) is the steady-state amount of work in the system with K = ∞ (assuming it exists). For the M/G/1 queue, this result is well known; see, for example, Takács [21], Cohen [11], and Hooghiemstra [15]. For a rigorous proof of (15) in the case of a general release rate, we refer to Asmussen [1, Chap. XIV, Prop. 3.1].

Writing

, conditioning on S, applying (15), and deconditioning on S then results in

Combining this result with (11) then results in the following corollary.

Corollary 4.3: Assume that the M/G/1 queue with infinite buffer size and general release rate has a stationary (embedded) workload distribution. Then

This is an extension of the classical formula for the distribution of C_max in the M/G/1 queue, which is due to Takács [21] (see also Cohen [10], and Asmussen and Perry [5] for alternative proofs). His result can be easily recovered from Corollary 4.3, since, for the M/G/1 queue, we have

. This yields the well-known formula

Related results for first-exit probabilities as well as expressions for the distribution of W^r(·) in terms of Volterra functions can be found in Harrison and Resnick [14] and Bekker [8]. Although Corollary 4.3 does not give a very explicit formula for the distribution of C_max in general, we expect that this representation may be useful to obtain asymptotics and/or bounds. Asymptotic results in the light-tailed case are hardly known; see Asmussen [2,3].