Subexponential loss rates in a GI/GI/1 queue with applications.
Consider a single server queue with i.i.d. arrival and service  processes, \{A,\ A_n,n\geq 0\} and \{C,\ C_n,n\geq  0\}, respectively, and a finite buffer B. The queue content  process \{Q^B_n,\ n\geq 0\} is recursively defined as  Q^B_{n+1}=\min((Q^B_n+A_{n+1}-C_{n+1})^+,B),  q^+=\max(0,q). When \mathbb{E}(A-C)<0, and  A has a subexponential distribution, we show that the stationary  expected loss rate for this queue  \mathbb{E}(Q^B_n+A_{n+1}-C_{n+1}-B)^+ has the following explicit  asymptotic characterization:  \mathbb{E}(Q^B_n+A_{n+1}-C_{n+1}-B)^+\sim \mathbb{E}(A-B)^+ \quad  \hbox{as} \ B\rightarrow \infty, independently of the server process  C_n. For a fluid queue with capacity c,  M/G/\infty arrival process A_t, characterized by  intermediately regularly varying on periods \tau^{\mathrm{on}},  which arrive with Poisson rate \Lambda, the average loss rate  \lambda_{\mathrm{loss}}^B satisfies  {\lambda_{\mathrm{loss}}^B}\sim \Lambda  \mathbb{E}(\tau^{\mathrm{on}}\eta-B)^+ \quad \hbox{as}\ B\rightarrow  \infty, where \eta=r+\rho-c,   r) is the rate at which the fluid is arriving during an on period.  Accuracy of the above asymptotic relations is verified with extensive numerical  and simulation experiments. These explicit formulas have potential application  in designing communication networks that will carry traffic with  long-tailed characteristics, e.g., Internet data services.
Introduction
An increasing body of literature on statistical data analysis has demonstrated the presence of
long-tailed/subexponential characteristics in communication network traffic streams. Early
discoveries on the long-tailed nature of Ethernet traffic was reported in [32]. Long-tailed
characteristics of the scene length distribution of MPEG video streams were explored in
[25, 29]. The implications of transporting Internet data applications over the traditional
Public Switched Telephone Network were investigated in [22].
These empirical findings have encouraged theoretical developments in the modeling and
analysis of long-tailed (heavy-tailed) phenomena. In this area there have been two basic
approaches: self-similar processes and fluid renewal models with long-tailed renewal distri-
butions. The investigation of queueing systems with self-similar long-range dependent arrival
processes can be found in [16, 18, 33, 36, 39, 42].
In this paper we focus on fluid renewal models. Basic tools for the analysis of these types
of models with a single long-tailed arrival stream are the classical results on subexponential
asymptotic behavior of the waiting time distribution in a GI/GI/1 queue [13, 37, 43] (e.g.,
these results were used in [2, 24]). Asymptotic expansion refinements of these results can be
found in [1, 15, 44]. Generalizations to queueing processes, or equivalently random walks,
with dependent increments were investigated in [4, 5, 27].
Queueing models with multiple long-tailed arrival streams are of particular interest for
engineering communication networks. Unfortunately, the analysis of these models is much
more difficult due to the complex dependency structure in the aggregate arrival process [24].
An intermediate case of multiplexing a single long-tailed stream with exponential streams
was investigated in [8, 28, 41].
For the case of multiplexing more than two long-tailed arrival processes general bounds
were obtained in [10, 35]. In [8] a limiting process obtained by multiplexing an infinite number
of On-Off sources with regularly varying on periods was explored. This limiting arrival
process, so called M/G/1 process [38], appears to be quite promising for the analysis. In
[28] an explicit asymptotic formula for the behavior of the infinite buffer queue length distribution
with M/G/1 arrivals was derived. In the same paper it was shown with simulation
experiments that the derived asymptotic formula yields a good approximation for multiplexing
finitely many long-tailed On-Off sources. An asymptotic expression for the expected
value of the first passage time in a fluid queue with M/G/1 arrivals was derived in [23]. A
recent survey of results on fluid queues with long-tailed arrival processes can be found in [9].
All of the previously mentioned results in the literature on stationary queueing analysis
assume an infinite buffer queue. This assumption is applicable to queueing systems that are
designed with very large buffers such that the losses are essentially zero. The queue length
distribution can be used in this situation as an indication of the delay experienced in the
system. However, in engineering network switches it is very common to design them as loss
systems. The main performance measures for these systems are loss probabilities and loss
rates. Obtaining asymptotic approximations for these performance measures under the assumption
of subexponential arrival sequences is the primary motivation for the investigation
of this paper.
The main contributions of the paper, presented in Theorems 4 and 5, are explicit asymptotic
characterizations of the loss rates in finite buffer queues with subexponential arrival
sequences. Theorem 5, in combination with the results from [28, 40], yields a straightforward
asymptotic formula for the loss rate in a fluid queue with long-tailed M/G/1 arrival
processes (see Theorem 7). Accuracy of the theoretical asymptotic results is demonstrated
with many numerical and simulation experiments. We believe that the exactness and explicit
nature of the derived approximate expressions will make them useful tools in designing
efficient and reliable network switches.
The rest of the paper is organized as follows. First, in Section 2, we present a preliminary
discussion of subexponential distributions and infinite buffer queueing analysis. Section 3
investigates a discrete time finite buffer queue. The main results are summarized in Theorems
4 and 5. The fluid aspect of the problem is explored in Section 4, Theorems 6 and 7.
Numerical and simulation examples that illustrate the efficacy of our approximations are
contained in Section 5. The paper is concluded in Section 6. To simplify the reading process,
the majority of the proofs are given in Section 7.
Subexponential Distributions and GI/GI/1 Queueing
Analysis
This section presents a preliminary discussion of long-tailed/subexponential distributions and
the asymptotic analysis of an infinite buffer queue under the assumption of subexponentiality.
We say that a nonnegative random variable A (or its distribution function (d.f.)) is
long-tailed
lim
A (or its d.f.) is said to be subexponential
lim
where A n ; n - 1, is a sequence of independent copies of A. The following subclass of
subexponential random variables was introduced in [30]. If A has a finite mean, then A (or
its d.f.) is said to be in S   if
lim
This class of subexponential distribution is closed under the tail integration, i.e., if A e is the
remaining life time random variable of A with its d.f. defined as P[A e -
implies A e 2 S   . A general relationship between the previous
three classes of long-tailed random variables is S   ae S ae L. For a brief introduction to
long-tailed and subexponential distributions the reader is referred to the Appendix of this
special issue of Queueing Systems. A recent survey on subexponential distributions can be
found in [21]. Well known examples of subexponential distributions incorporate regularly
varying distributions (in particular Pareto), some Weibull and Log-normal distributions.
Subexponential random variables have played a role in queueing theory since the classical
results of Cohen [13] and Pakes [37] on the asymptotic behavior of the waiting time process in
a GI/GI/1 queue. Here, we give a formal definition of a GI/GI/1 queue waiting time process.
be two independent sequences of nonnegative i.i.d.
random variables. Then for any initial condition Q 0 the queueing process fQ
uniquely defined by the following (Lindley's) recursion
There are two customary interpretations of this recursion. First, if
one assumes that A n are customers' service requirements and C are their
inter-arrival times, then Q n represents the waiting time process in a GI/GI/1 queue. Second,
if one refers to (4) as being an infinite buffer discrete time queue with A n representing the
amount of work that arrives at time n and C n the amount of work that is served at time n,
then Q n represents the queue length process for this queue. We will refer to Q
the infinite buffer queueing process and to A n and C n as the arrival and service processes,
respectively.
According to the classical result of Loynes [34], under the stability condition EA
the recursion in (4) admits a unique stationary solution, and for any initial condition
converges to the stationary distribution P[Q - x]. For the rest of this paper,
unless otherwise indicated, we will assume that all queueing systems under consideration are
in their stationary regimes.
Often, it is easier to conduct numerical computations with lattice valued random variables
than with continuous ones. In this context one may be interested in computing queue
occupancy probabilities. The following result gives an approximation of these probabilities
under the subexponential assumption on the arrival sequence. Note that the result does not
follow directly from Pakes' result [37], since the asymptotic behavior of P[Q ? i] does not
imply the asymptotics of Throughout the paper, for any two real functions f(x) and
g(x), we use the standard notation f(x) - g(x) as x !1 to denote lim x!1
or equivalently
Theorem 1 If A; C, are integer valued, A 2 S   , P[C -
the queue occupancy probabilities satisfy
Proof: Given in Section 7.1.
If one is only interested in the tail of P[Q ? x], then under more general assumptions
Pakes [37] has derived the following result.
Theorem 2 (Pakes) If A e 2 S and EA ! EC, then the tail of the queue length-distribution
satisfies
3 Finite Buffer Queue
In this section we present our results on a discrete time finite buffer queue. The results are
stated in Theorems 3, 4 and 5.
as in the previous section, be two independent
sequences of nonnegative i.i.d. random variables. The evolution of a finite buffer queue is
defined with the following recursion
where B is the buffer size. It is clear that Q B
n is a discrete time Markov process with
state space [0; B]. By excluding a trivial situation of C n j A n , i.e., by assuming that
Chapter III.4 of [14] it was shown that this Markov process has a unique
stationary distribution, and that for all initial conditions Q B
n converges to that stationary
distribution. Unless otherwise indicated we will assume that the recursion (5) is in its
stationary regime. Similarly as in (4), Q B
n -s can be interpreted as the uniformly bounded
customer waiting times in a GI/GI/1 queue (see Chapter III.4 of [14]).
In the proofs of Lemmas 1 and 2 and Theorem 3 we will restrict our attention to A n
and C n being lattice valued. Without loss of generality we can assume that A n and C n
are integer valued. Next, denote the corresponding probabilities with a
In addition, assume that
C n has a bounded support P[C n -
be the probability generating functions (p.g.f.) for A n , C n and X n ,
respectively. By exploiting the recursion in (5), it is easy to show that the stationary queue
occupancy p.g.f. q B
is equal to
where
In order to prove our main results we need the following two technical lemmas. Let
represents the infinite buffer case).
there exists a positive constant K 1 ,
such that for all B - 0
Remark: Note that this lemma does not require subexponentiality of A.
Proof: Let us first prove the case c = 1. Observe that q B
the following
set of B independent equations
i is uniquely defined by the
preceding set of equations. Similarly, q 1
exactly the same set of equations
and therefore - B
This proves the case c = 1.
The case c ? 1 is much more involved and is presented in Section 7.2. 3
In order to make the preceding lemma useful we need the following bound on the buffer
overflow probability.
(Recall that P[A e -
R x
Proof: Given in Section 7.3. 3
Theorem 3 If A e 2 S, EA ! EC, and P[C -
as B !1.
Remark: Observe that in the case P[C - implies the following identity
Thus, the theorem follows directly from Theorem 2, i.e., Lemma 2 is not needed. A similar
identity exists when C is exponentially distributed (see equation (3.6) in [46]). 3
Proof: By combining Lemmas 1 and 2 we compute
which is equivalent to
Application of Theorem 2 shows that P[A e ? B] is asymptotically proportional to P[Q 1 ?
B], which, when replaced in (9), yields the lower bound
The upper bound can be proved in exactly the same manner. We omit the details. This
proves the first two equalities of the theorem. The third equality follows from
This finishes the proof of the theorem. 3
Now we are ready to present our first main result.
Theorem 4 If A e 2 S and EA ! EC, then the stationary loss rate E(Q B
satisfies
Remarks: (i) In this theorem we do not assume that A and C are lattice valued. (ii) From
the theorem we can derive the probability that the work is lost p(B)
in conjunction with (10) can be expressed in the following compact
(iii) This theorem is a significant improvement of a theorem from the original version of the
paper [26] which was proved under the assumption of A being regularly varying P[A ?
l(x)=x ff with index ff ? 2. 3
Proof: Assume first that A n and C n are integer valued and that P[C n -
From Lemma 1 it follows that for any fixed i
Next, by using the flow conservation law in the queue steady state regime (loss rate=arrival
rate-departure rate) we compute
c
c
c
which in conjunction with (11) yields
Combining the expression above with a similar expression for we arrive at
which together with Theorem 3 and completes the proof of
the theorem for the case A n and C n being integer valued and C n being bounded.
In general, we can easily obtain a lower bound
for the last asymptotic relation we have used A e 2 L (see Lemma 5.2 in the Appendix of
this special issue). If A n and C n are integer valued and C n is unbounded we can always
choose a truncated service variable C c
being sufficiently large such that
. Let Q B;c
n be the queueing process that corresponds to the arrival process A n
and a modified service process C c
n . It is clear that Q B;c
n is stochastically larger than Q
n , and
that the corresponding loss rates satisfy
Now, (12) and (13) imply the conclusion of the theorem for A and C being integer, or in
general lattice valued.
When A and C are non lattice, we can approximate them with lattice valued random
variables A 0 and C 0 in the following way. First, for any \Delta ? 0 such that EC \Gamma EA+
we define the d.f.s for A 0 and C 0 as
From these definitions it easily follows that for all x - 0
which implies that A stochastically larger than
and Z 1
Next, let fA 0
be two independent i.i.d. sequences whose d.f.s
are equal to the d.f.s of A 0 and C 0 , respectively, and consider a queue with buffer B which
corresponds to sequences A 0
. From the preceding discussion, the losses in this newly
constructed queue are larger than the losses in the original queue and are asymptotically
proportional to E(A 0
1. Hence, this yields an upper bound
which in combination with the lower bound in (12) completes the proof. 3
The following recursion, similar to the one in (5), will be useful in analyzing fluid queues
in the following section
Under the same non-triviality condition as in the discussion of recursion (5), in Chapter
III.5 of [14] it was shown that the Markov process W B
n has a unique stationary distribution,
and that for any initial condition W B
n converges to that stationary distribution. Again,
we assume that (14) operates in its stationary regime. Historically, recursion (14) has been
studied in the context of finite dams (see Chapter III.5 in [14]).
The next theorem shows that the loss rates for both queues (5) and (14) are asymptotically
equivalent.
Theorem 5 If A e 2 S and EA ! EC, then
Remark: This theorem generalizes a result from [46] which is true for A being regularly
varying, and also for the case of C being exponential and A subexponential.
Proof: The proof of the lower bound is immediate
In order to prove the upper bound, by using a simple inductive argument, one can show that
for the same initial condition W B
n is bounded by Q
. Hence, in stationarity
Next, assume that C n is bounded, i.e., P[C n -
which, by Theorem 4, implies
where the last asymptotic relation follows from E(A
A e being long-tailed.
For the case when C n is not bounded we can always choose a truncated service variable
similarly as in the proof of Theorem 4, with c being sufficiently large such
that
. Let W B;c
n be the queueing process that corresponds to the arrival process
A n and modified service process C c
n . It is clear that W B;c
n is stochastically larger than W B
and that the corresponding loss rates satisfy
Thus, (15) and (19) conclude the proof of the theorem. 3
4 Finite Buffer Fluid Queue
This section contains our results on fluid queues with finite buffers and long-tailed arrivals.
In Theorem 6 we characterize the asymptotic behavior of the loss rate of a fluid queue with
a single On-Off arrival process. An explicit asymptotic formula for the loss rate of a fluid
queue with M/G/1 arrival sequences is presented in Theorem 7. This result is of special
interest for designing communication network switches because the M/G/1 arrival process
represents a good aggregate model for multiplexing a large number of On-Off sources (see
[28]).
The physical interpretation of a fluid queue is that at any moment of time, t, fluid is
arriving to the system at rate a t and is leaving the system at rate c t . We term a t and c t to
be the arrival and service processes, respectively. The evolution of the amount of fluid in
the queue, q B
t , is represented by
or (q B
or (q B
and dq B
In the following two sections we will study two important special
cases of fluid queues. Our analysis is based on observing the process q B
t at the beginning of
the arrival process activity periods. A recent investigation of the stationary behavior of q B
and its relationship to the process observed at the beginning of the activity periods can be
found in [46].
4.1 Single On-Off Arrival Process
Consider a fluid queue with capacity c and an On-Off arrival process with On arrival rate
r ? c. Lengths of On and Off periods are assumed to be independent i.i.d. sequences
f- on ; - on
sequence of random times representing the beginning of On periods in the arrival On-Off
process;
. Now, a formal construction of the On-Off arrival process is
a
for some n - 0, and a By observing the queue process q B
t at the beginning
of On periods, the queue length
evolves according to
Note that, by taking A
n and C
n , the preceding recursion reduces to the
recursion in (14). We assume that (21) operates in stationarity.
Our primary object of study is the long time average loss rate for this fluid queue defined
as
loss
where L(0; t) =famount of fluid lost in (0; t)g. Next, we show that this limit exists and is
equal to
Let L n
be a sequence of random variables representing
the losses in the renewal intervals [T respectively. If N
then
The strong law of large numbers for renewal processes (e.g., see Theorem 5, p. 151, [45])
yields
lim
almost surely: (25)
Similarly, (25) and Birkhoff's strong law of large numbers (see Theorem 2.1, p. 465, [17])
imply
lim
almost surely: (26)
Consequently, by dividing (24) with t, letting t !1 and using (25) and (26) we derive (23).
Finally, (23) and Theorem 5 yield the following asymptotic characterization of - B
loss . Let
- on
e be the residual life time random variable of - on with its distribution equal to P[- on
R xP[- on ? u]du=E- on .
Theorem 6 If r ? c, (r \Gamma c)E- on ! cE- off and - on
4.2 Long-Tailed M/G/1 Arrival Process
In this section we consider a fluid queue with capacity c and M/G/1 arrival process. An
M/G/1 process, a 1
t , is defined by a Poisson point process with rate   whose points, T n ,
indicate the beginning of On periods. Each On period, after its activation at time T n , brings
fluid at rate r to the queue for a random independent period of time - on . (For a more formal
definition of an M/G/1 process see [28]).
Next, consider an indicator On-Off process 1(a 1
If I on
n and I off
n denote the lengths
of the nth On and Off periods, respectively, then it can be computed (see [28]) that
EI off
n =EI on
(e \LambdaE- on
In addition, let D c
R Tn+I on
(a 1
increment during the nth
activity period and assume that c - r. Now, the queue length V B
n which is observed at
the beginning of the nth activity period of the arrival process a 1
evolves according to the
following recursion
This recursion also has the same form as (14). Similarly, we use (22) to define the loss rate
loss for this fluid queue. Again, by the same arguments as in (24)-(26) we compute
EI off
Now, we need to determine the asymptotic behavior of P[D c
is known for - on being intermediately regularly varying (- on 2 IR); a nonnegative random
variable - on is in IR if
lim
lim inf
P[- on ? jx]
P[- on ? x]
In the sequel we will use the facts that - on 2 IR; E- on ! 1 implies - on
and that
t , Theorem 1 in [40] (see
also Theorem 6 in [28]) yields
P [- on j ? x] as x !1; (31)
Finally, the combination of (28), (30), (31) and Theorem 5 yields the
following theorem.
Theorem 7 Let
and - on 2 IR, then
5 Numerical and Simulation Results
This section demonstrates, with numerical and simulation experiments, the accuracy and
analytical tractability of our approximation results. The following two numerical examples
buffer size i
-5
buffer size i
-5

Figure

1: Illustration for Example 1.
will illustrate Lemmas 1, 2 and Theorem 4. For the case of M/G/1 arrivals, due to the complexity
of the model, we were unable to obtain a numerical solution. Thus, in exemplifying
Theorem 7 we resort to simulation in the following subsection.
Observe that if P[A - i] - c=i ff as then the combination of Lemmas 1
and 2 imply that for any ffl ? 0 there exists B 0 such that for all
is the same as in Lemma 1. The above estimate suggests that, except for i close
to B, q 1
i is a good approximation of q B
. Hence, Theorem 1 and (32) yield an approximation
~
which is expected to be good for all i far
enough from 0 and B. This is demonstrated in the following example.
Example 1 Consider a discrete time finite buffer queue with constant service process C n j
3, and arrival distribution 1:0947. For
the maximum buffer size 100 the queue occupancy probabilities are plotted with a solid
line on the left-hand side of Figure 1. Based on (32) and Theorem 1 we easily compute the
suggested approximation ~
This approximation is plotted with
dashed lines on the same figure. We can see that, with the exception of buffer sizes close to
zero and 100, the approximation is very good. In fact, the relative error j~q B
was smaller than 1% for the buffer sizes i 2 [58; 93]. Bound (32) further states that the
portion of the buffer where the approximation is good increases as the maximum buffer
size B increases. In addition, the length of the buffer around the boundaries where the
approximation is not good stays approximately constant. To illustrate this we repeat the
same experiment with the maximum buffer size 300. Now, the relative error between the
actual and approximate probabilities was smaller than 1% for the buffer sizes i 2 [60; 291].
The next example demonstrates the accuracy of Theorem 4.
O
O
O
O
O
O
O
buffer size B
Log(10,loss
rate)
100 200 300 400 500 600 700
approximation

Figure

2: Illustration for Example 2.
Example and an arrival distribution
0:5553. Here, we numerically compute the expected loss rate
for the maximum buffer sizes 7. The results are presented
with "o" symbols in Figure 2. Note that for we needed to solve a system of
700 linear equations. In contrast, Theorem 4 readily suggests an asymptotic approximation
~
. The approximation is presented on the same figure with "+" symbols.
An excellent match is apparent from the figure. In fact, relative error j ~
loss
loss
loss is
plotted in Figure 3, from which we can see that even for the smallest buffer size
the relative error was less than 4%.
5.1 Fluid Queue with M/G/1 Arrival Processes
In this section we provide several simulation experiments to illustrate Theorem 7. For
simulation purposes we assume that the time is slotted with the length of a single slot
being equal to one. The number of On periods that arrive per unit of time (slot) has a
Poisson distribution with parameter  . The distribution of On periods is taken to be Pareto
parameterized as
P[- on -
From this it immediately follows that
~
loss
\LambdaE (- on
P[- on j ? u]du -
we run two simulation experiments.
O
O
O
O
O
O O
buffer size B
relative
error
100 200 300 400 500 600 7000.020.04

Figure

3: Illustration for Example 2.
Example 3 Choose  which results in E- on = 2:41642 and ae = 0:845747.
We simulate the losses for the maximum buffer sizes 25. The results
are presented with a solid line in Figure 4. In order to obtain reasonable accuracy in the
experiment it was necessary to run the simulation for 2 \Theta 10 9 units of time, which resulted
in several days of computer processor time. Needless to say, the approximation ~
loss -
0:921=B 1:5 can be computed almost instantly from equation (33). The approximation ~ - B
loss
is plotted in the same figure with dashed lines. From this figure we can see that already for
the buffer size B - 140 the approximation becomes almost identical to the simulated results.
Example 4 We repeat the same experiment as the preceding one with ff changed to
which yields E- on = 2:24304 and ae = 0:785065. The approximate loss rate computes to
~
loss - 0:508=B 2 . An almost perfect match between the approximation and simulation
results is demonstrated in Figure 5. In this case the approximation becomes accurate even
for smaller buffer sizes (B - 80).
6 Conclusion
In this paper we have considered several queueing systems with finite buffers and long-tailed
arrivals. For these queueing systems we have derived explicit asymptotic formulas for approximating
loss rates. The accuracy of the suggested approximate formulas is demonstrated
on various numerical and simulation experiments. Overall, we expect that these approximate
expressions, both for reasons of their explicit nature and accuracy, will be useful tools in designing
modern communications switches that will be able to efficiently carry non-traditional
long-tailed ("bursty") traffic.
buffer size B
Log(10,loss
rate)
50 100 150 200 250
-5
simulation
approximation

Figure

4: Illustration for Example 3.

Acknowledgments

The author is grateful to Bert Zwart for pointing out an error in the original draft of the
paper and sharing the preprint of his work. We are also thankful to an anonymous reviewer
for valuable suggestions.
buffer size B
Log(10,loss
rate)
50 100 150 200
-5
simulation
approximation

Figure

5: Illustration for Example 4.
7 Proofs
In this section we provide the proofs of Theorem 1 and Lemmas 1 and 2. Without loss of
generality we assume that the set of integers that supports the distribution of X
is aperiodic and that P[X additional assumptions, Theorem 5.2,
p. 214 in [3] shows that
exactly one simple root at on the unit circle
inside the unit circle 1g.
This fact will be repeatedly used in the following proofs.
7.1 Proof of Theorem 1
First, we define subexponential probabilities (see p. 429 in [6]). Let p \Lambda2
\Lambdan
two-fold and n-fold convolution of p i , respectively.
non-negative sequence fp called long-tailed if for any integer k,
lim
If, in addition, fp is a probability sequence (
lim
we say that
It is easy to check that for an integer valued random variable A for which A 2 S   , the
probability sequence belongs to S d .
By using a well known connection between the queue length distribution and the supremum
of the corresponding random walk with increments X , the p.g.f. q(z) of
can be represented as (see Chapter XII of [20] or Chapter VII of [3])
is the generating function of a strictly ascending ladder height
random variable for which Equation (34) can be written in its
equivalent form
where g \Lambda0
is a unit mass at zero. In the subexponential framework, the asymptotic behavior
of the random sum in (35) is characterized as follows.
lim
Remark: An equivalent result for random sums of continuous subexponential densities can
be found in [31].
Proof: Follows from Lemma 5 in [11], Lemma 2 in [19], and the Dominated Convergence
Theorem. 3
At this point, it is clear that in order to establish the asymptotic connection between the
arrival distribution and the queue length distribution we need to investigate the asymptotic
behavior of g +i . This is presented in the following lemma.
Lemma 4 If P[A ? i] is long-tailed, P[C -
Proof: Standard derivation in queueing theory which exploits Lindley's recursion shows
that the p.g.f. q(z) of Q n satisfies
recall
has a simple root at on the unit circle
inside the unit circle (jzj ! 1). Since q(z) is an analytic function in the unit circle, these
roots must be zeros of the numerator in (36), i.e.,
for some constant h. Next, using (37) in evaluating the right hand side of (36) (by l'Hospital's
rule) and equating it to
Further, by equating (34) and (36) we obtain
Now, examine the coefficients of the analytic function
The coefficients x 1
i of the analytic expansion of x 1 are positive and
c
from which, by the assumption that P[A ? i] is long-tailed, it easily follows that
Next, we investigate the coefficients x 2
i of the analytic expansion of
where z 1 is already defined to be one of the roots from the unit circle. By expanding 1=(z \Gamma z 1 )
into an analytic series in the strip
we arrive at
z
which, after comparing the coefficients on the left and right-hand side, yields
Here, for any constant K 2
where in the last inequality we have used the monotonicity of x 1
2. Inequality (41) in combination with (40) readily implies
lim
Similarly, by repeating this procedure for the remaining c \Gamma 2 roots, we derive the asymptotic
behavior of the coefficients of x Note that for j - 2, a similar bound
as in (41) can be obtained using jx j
and the monotonicity of x 1
Thus, we derive
as i !1: (42)
By combining (42) with (38) and equating the coefficients on the left and right-hand side in
we obtain the conclusion of the lemma. 3
Finally, the proof of Theorem 1 follows from Lemmas 3 and 4. 3
7.2 Proof of Lemma 1
The case c ? 1 is quite involved due to the more complicated boundary conditions. Define
is an analytic
function for jzj - 1, it follows that the numerator and denominator of (6) have exactly the
same zeros. Recall from Claim 1 that z c \Gamma z c has a simple zero at
zeros inside the unit circle (z i 6= 0). Assume that l; l - of the zeros from within the unit
circle are distinct with multiplicities
satisfy the following set of c \Gamma 1 equations
where s B(n)
with s 1(n) . By subtracting (43) from (44) we obtain that (- 1
a solution to
Next, let \Delta- and R be two column vectors with corresponding elements
and R B(n) (z k )=q B
and Z be matrices with rows equal
to
and ' d
(z c
respectively. Then, (45) can be expressed in the following compact form
Here, observe that by using the basic properties of determinants,
for the case when all of the roots are distinct
Y
z
Y
When some of the roots have multiplicities bigger than one (i.e., l ! c \Gamma 1), the determinant
of Z can be computed by taking the corresponding derivatives in (47) and then equating the
appropriate roots. This elementary computation, the details of which have been omitted,
yields
l
Y
Y
Therefore, X and Z are nonsingular matrices and from (46) we
derive
Furthermore, R B (z k ), as defined in (7), and its derivatives satisfy
Also, the stochastic dominance P[Q 1
Therefore, by replacing (49) and (50) in (48) we arrive at
Next, from (6), q B (z) can be rewritten as
q 1=
Note that the first B+1 coefficients in the analytic expansion
of the expression on the left side of the equation in (52) are equal to - B
Thus, an estimate of the coefficients in the analytic expansion of the expression on the right-hand
side of (52) will yield a bound on j- B
k j. This estimate will be obtained in the
remainder of the proof.
First, observe that R B (z) has a zero of multiplicity c at z = 0 and s 1 (z) is a
polynomial of degree c with no zeros at z = 0. Consequently, R B (z)=s 1 (z) is analytic in
some neighborhood of z = 0 and it has a zero of order at least B + c at z = 0. Therefore,
its analytic expansion R(z)=s 1
z i at
equal to zero, i.e.,
Similarly, \Deltas B (z)=s 1 (z) is analytic in some neighborhood of z = 0 with its analytic expansion
denoted as
. Now, we intend to bound the coefficients b 2i
(51) it easily follows that
\Deltas B (z)
O
Next, notice that \Deltas B
of
D kn . Using this, we arrive at
\Deltas B (z)
l
\Deltas B(z)
and it can be expanded at into an
analytic series
\Deltas B(z)
By replacing the
z kX
in (56) and then equating the coefficients next to z both sides of (56) we compute
By combining equations (49) and (58) we conclude that for i - c
Thus, (54), (55) and (59) yield
Finally, from (52), (53) and (60) we compute
This finishes the proof of the lemma. 3
7.3 Proof of Lemma 2
The idea for proving this lemma is to stochastically bound the finite buffer queue length
random variable Q
n with an infinite buffer queue having truncated arrivals. More precisely,
let us define a sequence of truncated random variables
Let Q B;B
n be a queueing process characterized with a finite buffer B and truncated arrival
process A B
n . Then, by assuming that Q B;B
0 , and by using induction in n
it follows that Q B;B
Furthermore, if we denote by Q 1;B
queueing process of an infinite buffer queue with truncated arrival sequence A B
again by induction in n, it follows that
Thus,
Therefore, by passing n !1 in (63), we conclude that in stationarity
Hence, the proof of Lemma 2 will follow if we show that the stationary distribution of Q 1;B
satisfies
Now, in order to prove (64) we first need to derive preliminary Lemmas 5 and 7.
Similarly as in equation (36), the p.g.f. q 1;B (z) of Q 1;B
. The above expression can be written
in its equivalent form (the same as in (34))
(1)
z i is the p.g.f. of a strictly ascending ladder height random variable.
Lemma 5 If EA ! EC and P[C - there exists a universal constant
such that for all B - 0,
Proof: Again, Claim 1 shows that z c \Gamma z c x B has a simple zero at
strictly inside the unit circle. These zeros are also the zeros of
the polynomial in the numerator of (65) which we denote as
note that x B
since the d.f. of A B converges to the d.f. of A as B ! 1, Theorem 1, p. 219 of [7] implies
that for any fixed k
are the queue stationary probabilities that correspond to the (non-truncated)
arrival sequence A n . Therefore
1. Hence, the zeros of N B (z) from within the unit circle converge to the corresponding
of N(z) which are also inside the unit circle. If
large enough such
that for all all of the zeros z i are in the ffl neighborhood of one of
the zeros z This implies that sup B-B 0
since all of the zeros for are strictly within the unit circle, we conclude that there
exists a constant 1, such that
sup
Next, observe that by equating (66) with (65) we compute
where
and the constant
Hence, we can obtain g B
(z) by canceling the zeros in the numerator and denominator of
(70). First, let us examine the coefficients of the polynomial
x
The coefficients of this polynomial x B;1
are positive and satisfy
c
Next, we investigate the coefficients of
x
x B;1 (z)
already defined to be one of the roots from inside the unit circle. By expanding
into an analytic series in the strip we arrive at
z
which, after comparing the coefficients on the left and right-hand side yields
x B;2
This equality readily implies
Finally, the monotonicity of P[A - i] yields
Consequently, by repeating this procedure for the remaining c \Gamma 2 roots we derive
jx B;c
Finally, by combining the preceding bound and (70) we derive
Furthermore, by (71) and (68)
lim
and therefor 1=h which when replaced in (72) completes the proof of Lemma 5. 3
At this point, in order to prove Lemma 7, we will need the following estimate on the
distribution of a sum with uniformly bounded summands.
be a sequence of nonnegative i.i.d. random variables and let
then for any fixed n; c ! 1
1-i-n
Proof: Observe that P[S n - B] can be decomposed as follows
1-i-n
From the definition of subexponential distributions it follows that
Next, note that
Also,
Finally, by replacing (74), (75), and (76) in (73) we obtain
which concludes the proof of the lemma. 3
At this point, let fX
1g be a family of integer valued positive i.i.d. random
variables with probabilities
i]. For each B, X B has a finite support P[X B -
fixed constant c.
1. If for all B, g B
and A e 2 S then
(i) for any fixed n
(ii) for any ffl ? 0 there exist a finite constant K ffl such that for all B and n - 1
be sequence of nonnegative, integer valued random variables with
probability mass function P[X
easily follows
1-i-n
where the last asymptotic relation follows from Lemma 6. This completes the proof of (i).
To prove (ii) let us construct a sequence fY k ; k - 1g of integer valued i.i.d. random
variables in the following way. First, choose an integer n 0 such that
Then, assign to each Y k the following distribution
ae 1 for
Clearly, Y k is stochastically larger then X B
k for all B, i.e.,
and Y k 2 S. Thus,
where the last inequality follows from Lemma 2.10 of the Appendix of this special issue of
Queueing Systems. This concludes the proof of Lemma 7. 3
Finally, we are ready to provide the proof of Lemma 2. Recall that the proof will
follow if we show that (64) holds. First, observe that g B
monotonically
increases to g 1
is the workload of an infinite
buffer queue with (non-truncated) arrival sequence A n . Hence, for any ffi 2 such that
1, we can choose B 0 such that for all
Next, let us choose a d.f. for random variables in Lemma 7 to be P[X B
it follows that for all
where K 3 is the same as in Lemma 5. Thus, the condition of Lemma 7 is satisfied.
Then, from equation (66), similarly as in (35), P[Q 1;B ? B] can be represented as
(1))X
(1)
Hence, by (77), for all sufficiently large B
Thus, by applying Lemma 7 (with ffl ? 0 such that (1+ ffl)(g 1
and the Dominated
Convergence Theorem to the sum in (79) we derive
which concludes the proof of the Lemma 2. 3



--R


On the sojourn time of sessions at an ATM buffer with long-range dependent input traffic
Applied Probability and Queues.
Large claims approximations for risk processes in a Markovian environment.
Tail probabilities for non-standard risk and queueing processes with subexponential jumps
Regular Variation.
Asymptotic Methods in Queueing Theory.
Regular variation in a multi-source fluid queue
Fluid queues with long-tailed activity period distributions

Functions of probability measures.
Intermediate regular and - variation
Some results on regular variation for distributions in queueing and fluctuation theory.
The Single Server Queue.
On the M/G/1 queue with heavy-tailed service time distributions
On the supremum from Gaussian processes over infinite horizon.
Stochastic Processes.
Large deviations and overflow probabilities for the general single-server queue with applications
A limit theorem for the tails of discrete infinitely divisable laws with applications to fluctuation theory.
An Introduction to Probability Theory and its Application
Subexponential distributions.
Overview of Internet traffic issues on the PSTN.
Patterns of buffer overflow in a class of queues with long memory in the input stream.
Heavy tails and long range dependence in on/off processes and associated fluid models.
Source models for VBR broadcast-video traffic

Subexponential asymptotics of a Markov-modulated random walk with queueing applications
Asymptotic results for multiplexing subexponential on-off processes
The effect of multiple time scales and subexponentiality of MPEG video streams on queueing behavior.
Subexponential distributions and integrated tails.
Subexponential distributions and characterizations of related classes.
On the self-similar nature of Ethernet traffic
"fractal"
The stability of a queue with non-independent inter-arrival and service times
Asymptotic behavior of a multiplexer fed by a long-range dependent process
A storage model with self-similar input
On the tails of waiting-time distribution
Tail probabilitites for M/G/1 input processes (I): preliminary asymptotices.
Performance decay in a single server queueing model with long range dependence.
Activity periods of an infinite server queue and performance of certain heavy tailed fluid queues.
Asymptotics of palm-stationary buffer content distribution in fluid flow queues
Heavy traffic analysis for a multiplexer driven by M/GI/1 input processes.
Asymptotic behavior of Wiener-Hopf factors of a random walk
Asymptotic expansion for waiting time probabilities in an M/G/1 queue with long-tailed service time
Teicher H.
A fluid queue with a finite buffer and subexponential input.
--TR

--CTR
Shahram Teymori , Weihua Zhuang, Queue analysis and multiplexing of heavy-tailed traffic in wireless packet data networks, Mobile Networks and Applications, v.12 n.1, p.31-41, January 2007
Sem Borst , Bert Zwart, Fluid Queues with Heavy-Tailed M/G/ Input, Mathematics of Operations Research, v.30 n.4, p.852-879, November 2005
Ward Whitt, Heavy-Traffic Limits for Loss Proportions in Single-Server Queues, Queueing Systems: Theory and Applications, v.46 n.3-4, p.507-536, March-April 2004
Weixin Shang , Liming Liu , Quan-Lin Li, Tail asymptotics for the queue length in an M/G/1 retrial queue, Queueing Systems: Theory and Applications, v.52 n.3, p.193-198, March     2006
A. Surez-Gonzlez , J. C. Lpez-Ardao , C. Lpez-Garca , M. Fernndez-Veiga , R. Rodrguez-Rubio , M. E. Sousa-Vieira, A new heavy-tailed discrete distribution for LRD M/G/ sample generation, Performance Evaluation, v.47 n.2, p.197-219, February 2002
Predrag Jelenkovi , Petar Momilovi, Finite buffer queue with generalized processor sharing and heavy-tailed input processes, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.40 n.3, p.433-443, 22 October 2002
long-range dependency;finite buffer queue;M/G/infty process;long-tailed traffic models;fluid flow queue;network multiplexer;subexponential distributions