Loss probability calculations and asymptotic analysis for finite buffer multiplexers.
In this paper, we propose an approximation for the loss probability, PL (x), in a finite buffer system with buffer size x. Our study is motivated by the case of a high-speed network where a large number of sources are expected to be multiplexed. Hence, by appealing to Central Limit Theorem type of arguments, we model the input process as a general Gaussian process. Our result is obtained by making a simple mapping from the tail probability in an infinite buffer system to the loss probability in a finite buffer system. We also provide a strong asymptotic relationship between our approximation and the actual loss probability for a fairly large class of Gaussian input processes. We derive some interesting asymptotic properties of our approximation and illustrate its effectiveness via a detailed numerical investigation.
Introduction
loss probability is an important QoS (Quality of
Service) measure in communication networks. While
the overflow probability, or the tail of the queue length dis-
tribution, in an infinite bu#er system has been extensively
studied [1], [2], [3], [4], [5], [6], [7], there have been relatively
few studies on the loss probability in finite bu#er
systems [8], [9], [10], [11].
In this paper, we propose a simple method to estimate
the loss probability PL (x) in a finite bu#er system from
the tail of the queue length distribution (or tail probabil-
of an infinite bu#er system. We estimate
PL (x) by making a simple mapping from P{Q > x}. Hence,
we consider both a finite bu#er queueing system and an infinite
bu#er queueing system. We model both systems by
a discrete-time fluid queue consisting of a server with constant
rate c and a fluid input #n . Both queues are fed with
the same input. Let -
Qn and Qn denote the queue length
in the finite queue and in the infinite queue at time n, re-
spectively. We assume that #n is stationary and ergodic
and that the system is stable, i.e., E{#n } < c. Under this
assumption, it has been shown that Qn converges to a stationary
and ergodic process [12]. It has also been shown
that -
Qn converges to a stationary process when the system
is a GI/GI/m/x type of queue [13], [14], and when the system
is a G/M/m/x type of queue [15]. Since proving the
convergence of -
Qn is not the focus of this paper, and more-
over, practical measurements of PL (x) and P{Q > x} are
based on "time averaging" assuming ergodicity (see (1) and
(2)), we assume that both -
Qn and Qn started at
and that they are ergodic and stationary. 1 The time index
H.S.Kim and N.B.Shro# are with the School of Electrical and Computer
Engineering, Purdue University, West Lafayette, Indiana
We refer the interested reader to our technical report [17], where
we have studied the relationship between finite and infinite bu#er
queues without assuming ergodicity of -
Qn and derived similar asymp-
n is often omitted to represent the stationary distribution,
The loss probability, PL (x), for a bu#er size x is defined
as the long-term ratio of the amount of fluid lost to the
amount of fluid fed. It is expressed as
and where the second equality
is due to the ergodicity assumption. The tail probability
(or tail of the queue length distribution, also sometimes
called the overflow probability) P{Q > x} is defined as the
amount of time the fluid in the infinite bu#er system spends
above level x divided by the total time. It is expressed as:
now on, when we write "loss probability" it will only be
in the context of a finite bu#er system, and when we write
"tail probability" it will only be in the context of an infinite
bu#er system. Note that since P{Q > x} is averaged by
time, and PL (x) is averaged by the input, in general there
is no relationship between these two quantities. However,
PL (x) is often approximated as:
This approximation usually provides an upper bound
(sometimes a very poor bound) to the loss probability,
although in general this cannot be proven, and in fact
counter-examples can easily be constructed. What we have
learned from simulation studies is that the curves PL (x)
versus x and P{Q > x} versus x exhibit a similar shape
(e.g., see Fig. 1), which motivates this work. Further, it
has been shown in [16] that for M/Subexponential/1 and
GI/Regularly-varying/1 with i.i.d. interarrival times and
i.i.d. service times, P{Q > x}/PL (x) converges to a con-
stant, as x #.
Hence, it seems reasonable that if we have a good estimate
of the tail probability P{Q > x} and a way to calculate
PL (a), the loss probability for some bu#er size a, then
totic results to Equation (22) in this paper. However, this involves
mathematical technicalities that take away from the main message
in this paper, i.e., developing a simple approximation for the loss
probability.
we can calculate the loss probability PL (x) as
PL (a)
In particular, we will choose a = 0 because this allows us
to compute the loss probability (PL (0)) quite easily. This
is the basic idea that drives this paper. In addition to developing
a methodology to calculate the loss probability,
we will also show that asymptotically the loss probability
and the tail probability curves are quite similar, and if they
diverge, they do so slowly, which is an interesting result by
itself.
For our study in this paper, we focus on the case when
the aggregate tra#c can be characterized by a stationary
Gaussian process. Recently, Gaussian processes have
received significant attention as good models for the arrival
process to a high-speed multiplexer [3], [18], [19], [20],
[21], [22], [23]. There are many reasons for this. Due to
the huge link capacity of high-speed networks, hundreds
or even thousands of network applications are likely to
be served by a network multiplexer. Also, when a large
number of sources are multiplexed, characterizing the input
process with traditional Markovian models results in
computational infeasibility problems [24] that are not encountered
for Gaussian processes. Finally, recent network
tra#c studies suggest that certain types of network traffic
may exhibit self-similar or more generally asymptotic
self-similar type of long-range dependence [25], [26], and
various Gaussian processes can be used to model this type
of behavior. Hence, our motivation to study the case when
the input process #n can be characterized by a Gaussian
process.
This paper is organized as follows. In Section II, we
review the maximum variance asymptotic (MVA) results
for the infinite bu#er queue, and then demonstrate how
to obtain similar results for the loss probability. Then,
we compare our approach to an approach based on the
many-sources asymptotics. In Section III, we validate our
result with several numerical examples, including those for
self-similar/long-range dependent tra#c. In Section IV, we
find the asymptotic relationship between the loss probability
and our approximation. In Section V, we describe the
applicability of our approximation for on-line tra#c mea-
surements. We finally state the conclusions in Section VI.
II. Maximum Variance Asymptotic (MVA)
Approximation for Loss
Remember that the first component in our development
of an approximation for PL (x) is to find a good estimate
of P{Q > x}. Fortunately, this part of the problem has
already been solved in [20], [21], [27]. By developing results
based on Extreme Value Theory, it has been found
that the Maximum Variance Asymptotic (MVA) approach
(first named in [20]) provides an accurate estimate of the
tail probability. We briefly review it here. As mentioned
before, we focus on the case when the aggregate tra#c can
be characterized by a Gaussian process, hence #n , the input
process to the queue is Gaussian. Let -
The queue length Qn (or workload) at time n in the
infinite bu#er system is expressed by Lindley's equation:
We define a stochastic process Xn as
We assume that #n is stationary and ergodic and that the
system is stable, i.e., E{#n } < c. Then, it has been shown
that the distribution of Qn converges to the steady state
distribution as n # and that the supremum distribution
of Xn is the steady state queue distribution [12]:
Let C # (l) be the autocovariance function of #n . Then, the
variance of Xn can be expressed in terms of C # (l). For
each x > 0, define the normalized variance # 2
x,n of Xn as
x,n :=
where # := c- #. Let m x be the reciprocal of the maximum
of # 2
x,n for given x, i.e.,
x,n
and we define n x to be the time n at which the normalized
variance
Although the estimate
2 called the Maximum Variance Asymptotic (MVA)
approximation has been theoretically shown to be only an
asymptotic upper bound, simulation studies in di#erent papers
have shown that it is an accurate approximation even
for small values of x [27], [18], [20], [28].
Now, for some a, we need to evaluate the ratio
PL (a)/P{Q > a} given in (4). As mentioned earlier, it
is easy to find PL (a) for a = 0, hence what we need to do
is to first estimate P{Q > 0} from the MVA result. For a
given x both n x and m x in the MVA approximation cannot
generally be obtained in a simple closed form, hence
search algorithms 2 are likely to be used to evaluate them.
may not be unique especially for a small value of
x. However, when 0, we can obtain them right away
as demonstrated in the following proposition.
Proposition 1: Let n x be the value of n at which # 2
x,n
attains its maximum # 2
. (10)
Simple local search algorithms starting at #x
(2-#
are good enough
to find nx within a small number of iterations.
Proof of Proposition 1:
To prove the proposition, it su#ces to show that
sup
. (11)
. (12)
, we have (11).
Now, we show how to calculate PL (0). Since #n is assumed
Gaussian, the mean and the variance provide su#-
cient information to calculate PL (0), i.e.,
c
As long as the number of input sources
is large enough for the aggregate tra#c to be characterized
as a Gaussian process, (13) gives an accurate estimate (ex-
act for a Gaussian input) and is often called the Gaussian
approximation [29]. Note that C #
in (10). From (4), (10), and (13), we have
where
exp  (c - #) 2
c
We call this above approximation the MVA approximation
for loss. The MVA approach is based on the large bu#er
asymptotics and it also applies in the context of the many-
sources asymptotics [20], [28]. We next compare this approach
with an approximation based on the many-sources
asymptotics.
The many-sources asymptotics have been widely studied
and can be found in many papers on queueing analysis
using large-deviation technique [5], [30], [31], [32]. Most
of the papers deal with the tail distribution rather than
the loss probability. In [9], the authors developed the first
result on the loss probability based on the many-sources
asymptotics. We call this the Likhanov-Mazumdar (L-M)
approximation for loss. Since the L-M result was obtained
for a fairly general class of arrival processes and is much
stronger than typical large-deviation types of results, we
feel that it is important to compare our result with the
result.
Consider N i.i.d. sources, each with input rate # (i)
It is assumed that the moment
generating function of # (1)
exists, and that the input rate
n is bounded. The L-M approximation has the following
and is theoretically justified by
where N is the number of sources, NC is the link ca-
pacity, NB is the bu#er size, - #
is a value of # such that #
#n (#)
log #n (# n ), and - n is a value of n that maximizes I n (C, B),
for a given C and B. becomes exact as N #.
Consider the numerical complexity of (16). Suppose that
we calculate (16) for given N,C,B, and # (1)
n . In general,
since there are no closed-form solutions for # n and - n, we
have to find them numerically. Two iteration loops are
nested; The inner loop iterates over # to find # n for given
n, and the outer loop iterates over n to find - n. Hence, it
can take a long time to find a solution of (16) by numerical
iteration. However, the MVA approximation requires only
an one-dimensional iteration over n to find n x at which m x
is minimized.
There is another problem in applying the L-M approximation
for control based on on-line measurements. When
the distribution of a source is not known beforehand, in the
L-M approach the moment generating function of a source
should be evaluated for the two dimensional arguments, (#,
n), whereas only the first two moments are evaluated for
the one argument, n, in the MVA approach (see Section V).
Note that one could avoid the above problems by making
a Gaussian approximation on the aggregate source
first, and then using the the L-M approximation given by
(16). Specifically, if we assume that the input process is
Gaussian, we have a closed-form solution for # n , i.e., as
k } and
k }, we have
Cn +B -m(n)
. (17)
Hence for given C and B both I n (C, B) and # 2
NB,n (the normalized
variance of Xn ) are expressed in terms of n, m(n),
and v(n), we can avoid the two dimensional evaluation of
the moment generating function.
3 This expression is just a rewriting of equation (2.6) in [9].
The only problem is that the theoretical result that says
that the L-M approximation in (16) becomes exact as the
number of sources N becomes large, is not proven for unbounded
(e.g. Gaussian) inputs. Still, since making this
approximation reduces the complexity of the search space,
it would be instructive to also investigate the performance
of such an approximation. In Section III, we will numerically
investigate our MVA approximation for loss, the L-M
approximation, and some other approximations developed
in the literature.
III. Numerical Validation of the MVA
Approximation for Loss
In this section, we investigate the accuracy of the proposed
method by comparing our technique with simulation
results. In all our simulations we have obtained 95% confidence
intervals. However, to not clutter the figures, the
error bars are only shown in the figures when they are
larger than -20% of the estimated probability. To improve
the reliability of the simulation, we use Importance
Sampling [33] whenever applicable. 4 We have attempted
to systematically study the MVA approximation for various
representative scenarios. For example, we begin our
investigation with Gaussian input processes. Here, we only
check the performance of our approximation (not compare
with other approximations in the literature), since other
approximations are not developed for Gaussian inputs. We
then consider non-Gaussian input sources and compare our
MVA approximation for loss with other approximations in
the literature. Specifically, we consider MMF sources which
have been used as representative of voice tra#c in many different
papers (e.g. [34], [35]) and also consider JPEG and
MPEG video sources that have been used in other papers
in the literature (e.g. [20], [36]).
A. Gaussian Processes
We begin by considering the simple case when the input
is a Gaussian Autoregressive (AR) process with autocovariance
(note that AR processes have
been used to model VBR video [22]). In Fig. 2 one can see
that the simulation and MVA-Loss result in a close match
over the entire range of bu#ers tested.
The next example, in Fig. 3, covers a scenario of multi-
time scale correlated tra#c. Note that multiple-time scale
correlated tra#c is expected to be generated in high-speed
networks because of the superposition of di#erent types
of sources [37]. In this case, the autocovariance function
of the Gaussian input process is the weighted sum of three
di#erent powers, i.e., C #
. One can see from Fig. 3 that because
of the multi-time scale correlated nature of the input, the
loss probability converges to its asymptotic decay rate only
at large bu#er sizes. This observation is consistent with
observations made on the tail probability when fed with
multi-time scale correlated tra#c [20]. Again, it can be
4 For interesting readers, the software used for the analysis and simulation
will be available upon request.
seen that the analytical result tracks the simulation results
quite closely.
The next example, deals with a well known input pro-
cess, the fractional Brownian motion process, which is the
classical example of a self-similar process [23]. 5 The results
are shown in Figs. 4 and 5, demonstrating the accuracy of
MVA-Loss, even for self-similar sources. Due to the di#-
culty in applying importance sampling techniques to obtain
loss probabilities for self-similar tra#c, in Figs. 4 and 5, we
show probabilities only as low as 10 -6 . In Fig. 4, the input
tra#c is characterized by a single Hurst parameter. How-
ever, even if the tra#c itself is long-range dependent, due to
the heterogeneity of sources that high-speed networks will
carry, we expect that it will be di#cult to characterize the
tra#c by simply one parameter, such as the Hurst param-
eter. Hence, we also run an experiment for a more realistic
scenario, i.e., the input process being the superposition of
fractional Brownian motion processes with di#erent Hurst
parameters. The numerical result is shown in Fig. 5. One
can see from Figs. 4 and 5 that MVA-Loss works well for
self-similar sources.
B. Non-Gaussian Processes
In this section we will compare the performance our
MVA-loss approximation with simulations and also with
other schemes in the literature. We call the Likhanov-
Mazumdar technique described earlier "L-M," or "L-
M:Gaussian" when further approximated by a Gaussian
process, the Cherno# dominated eigenvalue technique in
[38] "Cherno#-DE," the average/peak rate method in [39]
"Ave/Peak," the analytical technique developed in [24]
"Hybrid," and the famous e#ective bandwidth scheme "Ef-
fective BW" [40].
We now consider the practically important case of multiplexed
voice sources. The input MMF process, which has
widely been used to model voice tra#c source [34], [35],
has the following state transition matrix and rate vector:
Input rate vector :  0 cells/slot
cells/slot
These values are chosen for a 45 Mbps ATM link with 10
time slot and 53 byte ATM cell. In this example,
we assume that 2900 voice sources are multiplexed on a
Mbps ATM link with 10 msec time slot and 53 byte
ATM cell. As shown in Fig. 6, the MVA-Loss obtains the
loss probability calculations accurately and better than the
other techniques.
5 For computer simulations, since continuous-time Gaussian processes
cannot be simulated, one typically uses a discrete-time version.
In the case of fractional Brownian Motion, the discrete-time version
is called fractional Gaussian noise and has autocovariance function
given by:
is the Hurst parameter.
We next investigate the accuracy of our approximation
when the sources to the queue are generated from actual
MPEG video traces. The trace used to generate this simulation
result comes from an MPEG-encoded action movie
(007 series) which has been found to exhibit long-range
dependence [36]. In Fig. 7, 240 MPEG sources are multiplexed
and served at 3667 cells/slot (OC - 3 line), where
we assume 25 frames/sec and a 10 msec slot size. The loss
probability versus bu#er size result in this case is shown in
Fig. 7. Again, it can be seen that the MVA-Loss approximation
tracks the simulation results quite closely.
C. Application to Admission Control
The final numerical result is to demonstrate the utility of
MVA-Loss as a tool for admission control. We assume that
a new flow is admitted to a multiplexer with bu#er size x
if the loss probability is less than the maximum tolerable
loss probability #.
In this example, we consider multiplexed voice sources
on a 45Mbps link (Fig. 8(a)) or multiplexed video sources
(Fig. 8(b)) for an admission control type of application.
The QoS parameter # is set to 10 -6 . For each voice source
in Fig. 8(a), we use the same MMF On-O# process that
was used for Fig. 6. For each video source, we use the
same MPEG trace that was used in Fig. 7 (with start times
randomly shifted). Then, the admission policy using MVA-
Loss is the following. Let -
# and v(n) be the mean and the
variance function of a single source, i.e., Let - # := E{# (1)
and v(n) := Var{
are
currently serviced, a new source is admitted if
where # is defined as in (14). In Fig. 8(a) and (b), we
provide a comparison of admissible regions using di#er-
ent methods. It can be seen that MVA-Loss curve most
closely approximates the simulation curve in both figures.
In Fig. 8(a), the L-M approximation performs as well, and
the Cherno# DE approximation only does slightly worse.
In Fig. 8(b), however, the Cherno# DE approximation in
this case is found to be quite conservative. This is because
for sources that are correlated at multiple time-scales (such
as the MPEG-video sources in Fig. 8(b) shown here), the
loss probability does not converge to its asymptotic decay
rate quickly (even if there exists an asymptotic decay rate),
and hence approximations such as the Cherno# DE scheme
(or the hybrid scheme shown earlier) perform quite poorly.
Admission control by MVA-Loss can be extended to a
case where heterogeneous flows are multiplexed. The link
capacity is 622.02Mbps (OC - 12 line), the bu#er size x
is fixed to 20000 cells, and the QoS parameter # is 10 -6 .
In this system, the input sources are of two types; JPEG-
video and voice. As a video source, we use a generic model
that captures the multiple-time scale correlation observed
in JPEG video traces. It is a superposition of an i.i.d.
Gaussian process and 3 two-state MMF processes:
State transition matrices :
0.999 0.001
0.9999 0.0001
Input rate vectors [cells/slot] :
Mean of i.i.d. Gaussian : 82.42
Variance of i.i.d. Gaussian : 8.6336
Then, the admission policy is the following. Let -
be the mean and the variance function of a single
voice source. Let - # 2 and v 2 (n) be the mean and the variance
function of a single video source. When (N 1 -1) voice
and N 2 video flows are currently serviced, a new voice flow
is admitted if
The boundary of the admissible region is obtained by finding
maximal N 1 satisfying (19) for each N 2 .
As one can see in Fig. 9, the admissible region estimated
by simulations and via MVA-Loss is virtually indistinguish-
able. In fact, the di#erence between the two curves is less
than 1% in terms of utilization.
IV. Asymptotic Properties of the MVA
Approximation for Loss
We now find a strong asymptotic relationship between
the loss probability and the tail probability. More specifi-
cally, under some conditions (to be defined later in Theorem
5), we find that
log
means that lim sup |f/g| < #. Equation
tells us that the divergence between the approximation
#e -mx/2 given in (14), and the loss probability is slow if at
all (this may be easier to see if we rewrite (20) in the form
log PL (x) - log #e
In [27] and [28], under a set of general conditions it has
been shown for the continuous-time case that
log P{Q > x}
We will obtain (20) by finding a relationship between PL (x)
and P{Q > x}, i.e.,
log P{Q > x} - log PL
under the set of conditions given in Theorem 5 (PL (x) will
be bounded from above and below by some expressions
in terms of P{Q > x}), and then by applying (21) and
some properties of m x . Note, that finding the asymptotic
relationship (22) between P{Q > x} and PL (x) is by itself
a valuable and new contribution.
We first list a set of conditions for which (21) holds
in the discrete-time case that are equivalent to the set
of conditions in [27] defined for the continuous-time
case. Let v n :=Var{Xn}, #(n) := log v n , and # :=
lim n#(n)/ log n (assuming that the limit exists).
The notation f(n) n#
# g(n) means that lim n#
1.
The parameter # cannot be larger than 2 due to the stationarity
of #n , and # (0, 2) covers the majority of non-trivial
stationary Gaussian processes. The Hurst parameter H is
related to # by We now state the following results
that are the discrete-time versions of the results in
[27], [28], [41]. The proofs for these results are identical to
those given in [27], [28], [41], with trivial modifications accounting
for the discrete-time version, and, hence, we omit
them here. These results are stated as Lemmas here, since
we will be using them to prove our main theorem.
Lemma 2: Under hypotheses (H1) and (H2),
x#
x 2-# .
Lemma 3: Under hypotheses (H1) and (H2),
log P{Q > x}
It is easier for us to work with conditions on the autocovariance
function of the input process rather than conditions
(H1) and (H2). Hence, we first define a condition on the
autocovariance function C # (l) which guarantees (H1) and
l=-n
# S#n #-1 .
Note that condition (C1) is quite general and is satisfied
not only by short-range dependent processes but also by
a large class of long-range dependent processes including
second-order self-similar and asymptotic self-similar processes
[42].
Lemma 4: If the autocovariance function C # (l) of #n satisfies
(C1), then (H1) and (H2) hold.
Proof of Lemma 4:
Let h(n) :=
(l). Note that
and that v n+1 - v First we show condition (H2).
Since both v n and n # approach #, lim n#
vn
should be
equal to lim n#
vn+1-vn
, if it exists (this is the discrete
version of L'Hospital's rule). Hence,
lim
where lim n#
vn
we show that (H1) also follows
from (C1). Since h(n)
that Note that a function g(x) is o(x) if
lim x# g(x)/x # 0. Now,
vn
vn
(by Taylor Expansion)
#S -S
The loss probability is closely related to the shape of the
sample path, or how long Qn stays in the overflow state.
Before we give an illustrative example, we provide some
notation. We define a cycle as this period, i.e., an interval
between time instants when Qn becomes zero. We let S x
denote the duration for which Qn stays above threshold x
in a cycle to which n belongs. Formally, let:
. Un := sup{k time of the
current cycle to which n belongs).
. Vn := inf{k time of the
next cycle).
. Wn := Vn -Un (Duration of a cycle to which n belongs).
. Zn := Vn - n (Residual time to reach the end of cycle).
. S x
k=Un
(Duration for which Q k > x in a
cycle containing n).
Note that if Qn > 0, Zn is equal to the elapsed time to
return to the empty-bu#er (or zero) state. Since Qn is
stationary and ergodic, so are the above. Hence, their expectations
are equal to time averages.
Consider two systems whose sample paths look like those
in Fig. 10. The sample paths are obtained when the input
is a deterministic three-state source which generates fluid
at rate c and 0, at state 1, 2, and 3, respectively.
The duration of each state is the same, say b. Use the
superscript (1) and (2) to represent values for the upper
and the lower sample path. Set a
2b (1) . Then, both cases have the same overflow probability.
Now, consider a time interval from 0 to 3b (2) . The amount
of fluid generated for that interval is clearly the same for
both cases. But, the amount of loss in the upper case is
exactly the twice of that in the lower case, hence, the upper
case has the larger loss probability. We can infer from this
that the loss probability is closely related to the length of
n and the slope of the sample path. Since loss happens
only when Qn is greater than the bu#er size x, we consider
the condition that Qn > x. Since it is di#cult to know
the distribution of S x
n , and since S x
n is determined by the
sample path, we use a stochastic process defined as
Here we have chosen 0 as the origin, but, because of sta-
tionarity, the distribution of Yn does not depend on the
origin. Note that if Q 0 > 0, Yn will be identical to Qn till
the end of cycle. We want to know the distribution of Yn
given is Gaussian, the distribution of
Yn can be characterized by the mean and the variance of
Yn . However, since Q 0 is the result of the entire history
up to time 0 and the future is correlated with the past, it
is di#cult to find an explicit expression of the mean and
the variance of Yn given Q 0 > x. Hence, we introduce
upper-bound types of conditions on the mean and the variance
of Yn as (26) and (27). For notational simplicity, let
be the
expectation and the variance under P x , respectively.
We now state our main theorem.
Theorem 5: Assume condition (C1). Further assume
that for any # > 0, there exist x 0 , K,M, and # such that
for all x # x 0 and n # Mx # . Then,
-# < lim inf
Though the conditions of Theorem 5 look somewhat
complex, they are expected to be satisfied by a large class
of Gaussian processes. If the input process is i.i.d. with
it can be easily checked
that
and (C1), (26), and (27) are satisfied with
# , and 1. It has been shown that Gaussian
processes represented by the form of finite-ordered Autoregressive
Moving Average (ARMA) satisfy (26) and (27)
[17]. Since the autocovariance function of a stable ARMA
process is in the form of C #
it satisfies (C1) with 1. So Theorem 5 is applicable to
Gaussian ARMA processes.
More generally, E{ P n
# Sn # under (C1). Thus, for each x,
#n and Var x {Yn } n#
and we can find
#, x) as small as
possible. If sup x K(#, x), sup x M(#, x), and sup x #, x) are
finite, then (26) and (27) hold. We conjecture that they are
all finite for a large class of stationary Gaussian processes,
and we are trying to show it.
Note that the rightmost inequality (limsup part) in (28)
holds without conditions (26) and (27), and it agrees with
empirical observations that the tail probability curve provides
an upper bound to the loss probability curve.
Before we prove the theorem, we first define the derivative
of m x with respect to x, m #
x . Recall (9), or m
vnx
. Since n x is an integer value, m x is di#erentiable
except for countably many x at which n x has a jump. Let
x is not di#erentiable}. Note that D has measure
zero, and that the left and right limits of m #
x
exist for all x # D. For simplicity, abuse notations by setting
z and m #
z for x # D. The
reason we set the (right) limit is that we will find the similarity
relation (29) in Lemma 6, which is useful in proving
Theorem 5. In fact, we may take the left limit to have the
same asymptotic behavior. By building m #
x in this
way, it directly follows from Lemma 2 that m #
x # bx -# for some constants a > 0 and b.
We now state three lemmas which are useful in proving
the theorem (Their proofs are in Appendix).
Lemma Under hypotheses (H1) and (H2),
x
y
dy x#
2x K
x
where K is a constant.
Lemma 7: If P{Q > x} > 0 and E{Z|Q > x} < # for
all x,
#PL (x). (30)
Lemma 8: Under conditions (26) and (27), E{Z|Q >
Now, we are ready to prove Theorem 5.
Proof of Theorem 5:
First of all, we find expressions in terms of P{Q > x}
which are greater than or less than -
#PL (x). If P{Q >
would contradict the asymptotic
relation in Lemma 3. Hence, P{Q > x} > 0 for all x.
If E{Z|Q > would contradict the
asymptotic relation in Lemma 8. Hence, E{Z|Q > x} < #
for all x. Thus, by Lemma 7 we have (30). Now, since
x
By Lemma 4, (C1) implies (H1) and (H2). Hence, by
Lemma 3, we have (21). Equation (21) means that there
are x 0 , K 1 and K 2 such that
Note that since E{Z|Q >
we can choose K 3 > 0 such that E{Z|Q > x} # K 3 x # for
all x # x 0 . Combining with (30) and (31), integrate all
sides of (32) to get
dy #PL (x)
x
with the constant a > 0, by Lemma 6,
there exist x 1 # x 0 , K 4 > 0 and K 5 > 0 such that
dy,
and
x
From (33), (34) and (35),
Take logs and rearrange to get
log  K 4
Divide by log x and take x #. Then, the theorem follows

V. Applications to On-line Measurements
In this section, we describe how to apply the MVA approach
for the estimation of the loss probability, based on
on-line measurements. In many practical situations, the
characteristics of a flow may not be known beforehand or
represented by a simple set of parameters. Hence, when
we use a tool for the estimation of the loss probability,
parameter values such as the moment generating function
and the variance function should be evaluated from on-line
measurements. Then, the question is what range of
those parameters should be evaluated. If an estimation
tool needs, for example, the evaluation of the moment generating
function for the entire range of (#, n), the tool may
not be useful. This is fortunately not the case for the MVA
approximation for loss.
Note that the MVA result has the form #e -mx/2 . The
parameter m x is a function of c, -
#, x, and v(n), where -
and v(n) is the mean and the variance of the input, i.e.,
Hence, by measuring
only the first two moments of the input we can estimate
the loss probability. Recall that m
that v(n)
(c-
is maximized at This means that the
result only depends on the value of v(n) at This
value of n x corresponds to the most likely time-scale over
which loss occurs. This is called the dominant time scale
(DTS) in the literature [43], [20]. Thus, the DTS provides
us with a window over which to measure the variance func-
tion. It appears at first, however, that this approach may
not work because the DTS requires taking the maximum
of the normalized variance over all n, which means that we
would need to know v(n) for all n beforehand. Thus, we
are faced with a chicken and an egg type of problem, i.e.,
which should we do first: measuring the variance function
v(n) of the input, or estimating the measurement window
n x . Fortunately, this type of cycle has recently been broken
and a bound on the DTS can in fact be found through
on-line measurements (see Theorem 1 and the algorithm
in [44]). Thus, since our approximation is dependent on
the DTS, we only need to estimate v(n), for values of n up
to a bound on the DTS (given in [44]), thereby making it
amenable for on-line measurements.
VI. Concluding Remarks
We have proposed an approximation for the loss probability
in a finite queue by making a simple mapping from
the MVA estimate of the tail probability in the corresponding
infinite queue. We show first via simulation results that
our approximation is accurate for di#erent input processes
and a variety of bu#er sizes and utilization. Since the loss
probability is an important QoS measure of network tra#c,
this approximation will be useful in admission control and
network design. Another feature of the approximation is
that it is given in a single equation format and hence can
easily be implemented in real-time. We have compared
our approximation to existing methods including the effective
bandwidth approximation, the Cherno# dominant
eigenvalue approximation, and the many-sources asymptotic
approximation of Likhanov and Mazumdar.
In this paper we also study the theoretical aspects of our
approximation. In particular, we provide a strong asymptotic
result that relates our approximation to the actual
loss probability. We show that if our approximation were
to diverge (with increasing bu#er size) from the loss prob-
ability, it would do so slowly. For future work we plan
on simplifying the conditions given in Theorem 5 and to
extend the approximation result to a network of queues.
VII.

Appendix


Proof of Lemma
x
x#
x /2. Hence, to prove the lemma, it
su#ces to show that
x
e -f(y) dy x#
e -f(x) . (36)
x is not di#erentiable}. For x # D,
d
dy
e -f(y)     y=x
e -f(x) . (37)
Since D has measure zero, R [x,#)-D
(-)dy and
we may assign any values to f # (x) and f # (x) for all x # D.
Recall
z and m #
z for x # D. Set
let x be any value. Integrating both sides of (37)
from x to #, we have
e -f(x)
x
e -f(y) dy - Z #
x
e -f(y) dy. (38)
Note that m #
a > 0 and b. Since f #
x
# (0, 1). We can find x 0 such that    f # (x)
x
e -f(y) dy # Z #
x
e -f(y) dy
x
e -f(y) dy
x
which means that1
x
e -f(y) dy
and the result follows.
Proof of Lemma 7:
Recall the notations:
. Un := sup{k time of the
current cycle to which n belongs).
. Vn := inf{k time of the
next cycle).
. Wn := Vn -Un (Duration of a cycle to which n belongs).
. Zn := Vn - n (Residual time to reach the end of cycle).
. S x
k=Un
(Duration for which Q k > x in a
cycle containing n).
one more:
. R x
k=n
1 {Qk>x} . (Residual duration for which
x in a cycle containing n)
Since Qn is stationary and ergodic, so are the above.
Hence, their expectations are equal to time averages. Since
we are interested in the behavior of Qn after loss happens,
we consider the conditional expectations:
R x
Clearly, E{R x
And it can also
be easily checked that 2E{R x
where the inequality is due to that n is discrete. 6 Since
< c, there are infinitely many cycles for a sample
path. Index cycles in the following manner:
. A (i)
. S (i)
. -
x
Now, we prove the lemma in two steps:
. 1) Derive
x-
.
The amount of loss in cycle i is greater than or equal
to the di#erence between the maximum value of the queue
level Qn in cycle i and the bu#er size x of the finite bu#er
queue, i.e.,
k#A (i)
x
k#A (i)
x
I(S (i)
y > 0)dy.
Take summation over i and divide by the total time,
denotes the number of elements
6 Since n is discrete, for given n such that Qn > x, R x
n and S x
(positive) integer values. If Sn is, for example 2, Rn can be either 1
or 2, and its expectation is 1.5 which is greater than 2/2.
of A (i) . Then,
x
I(S (i)
|A (i) |
dy
x
y
y
dy
x
sup
l#m
y
y
dy.
Recalling (1) and (2),
-# PL (x),
- #,
y
sup
l#m
y
as m #. Since all components are nonnegative, by
Fatou's Lemma, (44) becomes
x-
Step 2) For better understanding, we first show
lim sup
m#m
x
Note that all components are nonnegative. Let am :=2m+1 P m
lim sup am , and b . For any # > 0, we can choose
M such that aM - a # and |b # - b M | < #. Then,
since
x
x
x
Since # is arbitrary, we have b # a # .
Now, we will verify that
x
Construct a new sequence {T (i)
x } by removing zero-valued
elements of {S (i)
x }. Then, as in 45,
lim sup
m#m
x
Note that
lim sup
m#m
x
x
x
for all
x and |B (i)
x ,
xk
x
x |
x
x
x
x
Combining (47), (48) and (49), we have (46).
At last, we have
from which (30) follows.
Proof of Lemma 8:
. #(x, n) := P x {Yn > 0},
. V
The proof will be done in two steps:
. 1) Find x 1 > x 0 such that #(x, n) # n -2 for all (x, n) #
. 2) Using 1), show that E{Z|Q 0 > x} is O(x # ).
# be so small that -# < 0. Then, we
choose x 0 , M , and # satisfying (26) and (27). Let m(n) :=
Then, the moment generating
function of Gaussian Yn is given by e #m(n)+ 1
From (26) and (27), m(n) #)n and v(n) # Kn #
for all (x, n) # V
where #. Let
for all (x, n) # V
Kn 2#-(2-#)  . (52)
Note that # > 2# - (2 - #). Since the coe#cient of the
leading term, -# , is negative and its order, #, is positive,
we have for all (x, n) # V
Kn 2#-(2-# 0. (53)
Note that in (53) # , K, and # are fixed constants for all
there exists x 2 such that
Now, we choose x 1 > x 0 such that Mx #
Step
From the definition of Z, Z > n implies Yn > 0. Thus,
Therefore, we have
or
Obviously
as shown in Step 3), #(x, n) # n -2 for all n # Mx # .
Applying this and (55),
#(x, n)
#(x, n)
x#
where #x# denotes the smallest integer which is greater
than or equal to x. Since E x {Z} is nonnegative, E x



--R

"Stochastic Theory of a Data Handling System with Multiple Sources,"
"Asymptotics for steady-state tail probabilities in structured Markov queueing models,"
"An Approximation for Performance Evaluation of Stationary Single Server Queues,"
"Stability, Queue Length, and Delay of Deterministic and Stochastic Queueing Networks,"
"Large deviations and overflow probabilities for the general single server queue, with appli- cation,"
"Squeezing the Most Out of ATM,"
"Logarithmic asymptotics for steady-state tail probabilities in a single-server queue,"
"Loss Performance Analysis of an ATM Multiplexer loaded with High Speed ON-OFF Sources,"
"Cell-loss asymptotics in bu#ers fed with a large number of independent stationary sources,"
"Improved Loss Calculations at an ATM Multiplexer,"
"Investigation of Cell Scale and Burst Scale E#ects on the Cell Loss Probability using Large Deviations,"
"The Stability of a Queue with Non-independent Inter-arrival and Service Times,"
The Single Server Queue
"Limits for Queues as the Waiting Room Grows,"
Stationary Stochastic Mod- els
"A fluid queue with a finite bu#er and subexponential input,"
"On the Asymptotic Relationship between the Overflow Probability in an Infinite Queue and the Loss Probability in a Finite Queue,"
"A Central Limit Theorem Based Approach to Analyze Queue Behavior in ATM Networks,"
"A New Method to Determine the Queue Length Distribution at an ATM Multiplexer,"
"A Central Limit Theorem Based Approach for Analyzing Queue Behavior in High-Speed Networks,"
"On the supremum distribution of integrated stationary Gaussian processes with negative linear drift,"
"Performance Models of Statistical Multiplexing in Packet Video Communication,"
"On the Use of Fractal Brownian Motion in the Theory of Connectionless Networks,"
"Improved Loss Calculations at an ATM Multiplexer,"
"Long- range dependence in variable-bit-rate video tra#c,"
"On the Self-Similar Nature of Ethernet Tra#c (Extended Version),"
"Queueing Analysis of High-Speed Multiplexers including Long-Range Dependent Arrival Processes,"
"Use of Supremum Distribution of Gaussian Processes in Queueing Analysis with Long-Range Dependence and Self-Similarity,"
"Multiplexing gains in bit stream mul- tiplexors,"
"Large deviations, the shape of the loss curve, and economies of scale in large multiplexers,"
"Economies of scale in queues with sources having power-law large deviation scaling,"
"Large deviations approximation for fluid queues fed by a large number of on-o# sources,"
"E#ective bandwidth and fast simulation of ATM intree net- works,"
"Models for Analysis of Packet Voice Communication Systems,"
"Characterizing Superposition Arrival Processes in Packet Multiplexer for Voice and Data,"
"Second Moment Resource Allocation in Multi-Service Networks,"
"Statistical Multiplexing of Multiple Time-scale Markov Streams,"
"Fundamental bounds and approximations for ATM multiplexers with applications to video teleconferencing,"
"Design of a real-time call admission controller for ATM networks,"
"E#ective Bandwidth of General Markovian Tra#c Sources and Admission Control of High Speed Networks,"
Queueing Analysis of High-Speed Networks with Gaussian Tra#c Models
"Self-similar processes in communications networks,"
"On the Relevance of Time Scales in Performance Oriented Tra#c Characterization,"
"The measurement-analytic frame-work for QoS estimation based on the dominant time scale,"
--TR
Limits for queues as the waiting room grows
Effective bandwidth of general Markovian traffic sources and admission control of high speed networks
On the self-similar nature of Ethernet traffic (extended version)
Effective bandwidth and fast simulation of ATM intree networks
Multiplexing gains in bit stream multiplexors
Design of a real-time call admission controller for ATM networks
Second moment resource allocation in multi-service networks
Improved loss calculations at an ATM multiplexer
A central-limit-theorem-based approach for analyzing queue behavior in high-speed networks

--CTR
Han S. Kim , Ness B. Shroff, The notion of end-to-end capacity and its application to the estimation of end-to-end network delays, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.48 n.3, p.475-488, 21 June 2005
Mahmoud Elhaddad , Rami Melhem , Taieb Znati, Analysis of a transmission scheduling algorithm for supporting bandwidth guarantees in bufferless networks, ACM SIGMETRICS Performance Evaluation Review, v.34 n.3, p.48-63, December 2006
Aimin Sang , San-qi Li, Measurement-based virtual queue (VQ): to estimate the real-time bandwidth demand under loss constraint, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.4, p.519-539, 15 November 2004
Ness B. Shroff, A predictive flow control scheme for efficient network utilization and QoS, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.161-172, February 2004
Jzsef Br, Loss ratio approximations in buffered systems with regulated inputs, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy
maximum variance asymptotic;asymptotic relationship;queue length distribution;loss probability