Transient loss performance of a class of finite buffer queueing systems.
Performance-oriented studies typically rely on the assumption that the stochastic process modeling the phenomenon of interest is already in steady state. This assumption is, however, not valid if the life cycle of the phenomenon under study is not large enough, since usually a stochastic process cannot reach steady state unless time evolves towards infinity. Therefore, it is important to address performance issues in transient state.Previous work in transient analysis of queueing systems usually focuses on Markov models. This paper, in contrast, presents an analysis of transient loss performance for a class of finite buffer queueing systems that are not necessarily Markovian. We obtain closed-form transient loss performance measures. Based on the loss measures, we compare transient loss performance against steady-state loss performance and examine how different assumptions on the arrival process will affect transient loss behavior of the queueing system. We also discuss how to guarantee transient loss performance. The analysis is illustrated with numerical results.
Introduction
For a queueing system with finite buffer, loss performance
is usually of great interest. One may want to know
the probability that loss of workload occurs, or the expected
workload loss ratio, due to buffer overflow. In the
existing literature, this issue is typically addressed under
the assumption that the stochastic process modeling the
phenomenon of interest is already in steady state. This
assumption is, however, not valid if the life cycle of the
This work was supported by Academia Sinica and National Natural
Science Foundation of China.
phenomenon under study is not large enough, since usually
a stochastic process cannot reach steady state unless
time evolves towards infinity. For example, let us consider
performance guarantee for real-time communications
in high-speed networks, where performance must be defined
on a per-connection basis [10]. Since the duration
of any connection in a real-world network is always finite,
the performance of the connection is in fact dominated by
transient behavior of the underlying traffic process carried
by the connection. Therefore, it is important to address
performance issues in transient state. In this work, we
assume that arrival processes are stationary. For a non-stationary
process, both steady state and transient state
are meaningless.
Previous work in transient analysis of queueing systems
usually focuses on Markov models, for example, see [1, 17].
Due to complexity involved in analysis, one may have to re-sort
to simulation. Nagarajan and Kurose have examined
transient loss performance defined on an interval basis for
packet voice connections in high-speed networks by simulation
[13]. They observed that in transient state, voice
connections experienced more serious performance degra-
dations. Our work is different from the previous work in
that we analyze transient loss performance of a class of
finite buffer queueing systems that may not be necessarily
Markovian.
Now let us consider a finite buffer queueing system
fed by a two-state fluid-type stochastic process, where the
state of the arrival process represents the arrival rate of
workload to the system, that is, the amount of workload
arrived per time unit. When the arrival process is in a
given state, the arrival rate is a constant. The server of
the system processes workload in the queue at a constant
service rate unless the queue is empty. This queueing system
is not necessarily Markovian. Fig. 1 shows a typical
scenario illustrating such a system. The notations in Fig.
are explained as follows, which will also be used in the
following sections.
ffl R(t): the arrival process representing the amount of
workload arrived per time unit at time t.
ffl r1 and r0 : the arrival rates associated with the states
of the arrival process where r1 ? r0 - 0.
ffl ON and OFF: we use ON and OFF to refer to states
corresponding to r1 and r0 , respectively, and assume
OFF ON ON
OFF
time

Figure

1: A finite buffer queueing system fed by a general
two-state fluid-type stochastic process.
that the initial state of the process is ON. Note that
when R(t) is in the OFF state, r0 may not necessarily
be zero.
ffl Sn and 1: the lengths of the nth ON
and OFF intervals, respectively. For the time being,
we assume that both Sn and are i.i.d. random
variables with arbitrarily given distributions. So we
can also denote Sn and Tn by S and T , respectively.
ffl B: the buffer size of the queueing system measured
by the maximum amount of workload that can be
accommodated by the buffer.
ffl C: the service rate of the server measured by the
amount of workload processed per time unit.
In this paper, our aim is to investigate loss performance
of such a class of queueing systems. Instead of loss performance
defined in idealized steady state, we are interested
in transient loss performance. For example, we want to
know the probability that loss of workload occurs during
the nth ON interval, or the expected workload loss ratio
of the nth ON interval, for arbitrary n - 1. We have
obtained closed-form loss performance measures defined
in transient state. Based on the performance measures,
we can therefore contrast transient loss performance with
steady-state loss performance and compare transient loss
behaviors of the queueing systems fed by different stochastic
processes. For some applications, performance guarantee
is important. So we will also discuss how to guarantee
transient loss performance. The results obtained are
useful, since many interesting phenomena in performance-oriented
studies can be modeled by two-state fluid-type
stochastic processes, and the application of our results can
also be extended to multiple-state processes.
In the following, we first present our analysis regarding
how to define, compute and guarantee transient loss performance
(Section 2). To compare transient loss against loss
in steady state, we also describe how to compute steady-state
limits of the loss measures (Section 3). Then we use
numerical results to illustrate the analysis (Section 4). After
a brief discussion on some implications and application
of the results (Section 5), we conclude the paper and point
out some issues to be explored further (Section 6).
Transient Loss Performance Analysis
For a finite buffer queueing system fed by a two-state
fluid-type stochastic process with arrival rates r1 ? r0 , if
the service rate C of the system is greater than r0 but
less than r1 , then loss of workload due to buffer overflow
can only occur when the arrival process is in the ON state
In fact, this is the only non-trivial case that
should be considered. If C - r0 , then loss performance will
be out of control in transient state. On the other hand, if
loss will never occur for certain. Therefore, in
the following, we assume r0 ! C ! r1 , and consider only
loss measures defined for ON intervals of an arrival pro-
cess. Since transient performance of the queueing system
depends on temporal behavior of the system state, before
we derive transient loss measures, we shall first investigate
dynamical evolution of system state variables.
2.1 Stochastic Dynamics of the Queueing System
The state variables of interest regarding the queueing
system are Wn and Qn , which represent the amounts of
workload in the buffer at the beginning and the end of
the nth ON interval of the arrival process, respectively.
Suppose that initially
where w1 is a given constant between 0 and B. According
to flow balance, the evolution of Wn and Qn is as follows.
ae
ae
where n - 1. Since S and T are random variables, Wn
and Qn are also random variables. Denote by 'n(w) and
/n(q) the probability density functions of Wn and Qn , re-
spectively. Evidently, 'n(w) and /n(q) can be viewed as
a solution of the above evolution equations in the probabilistic
sense, which can be readily obtained by recurrence.
and
where for
is the probability density function of Qn conditioned on
is the probability density function of S,
is the probability density function of Wn conditioned on
is the probability density function of T ,
and ffi(\Delta) is the Dirac delta function. In general, the Dirac
function is defined by
ae
An important property of the Dirac delta function is
is a function
defined for x 2 (\Gamma1; 1). It is easy to verify that the
above probability density functions are nonnegative and
normalizable.
The process Wn has significant impact on transient loss
performance of the queueing system. To reach steady state
for realizing steady-state performance, the system needs
time to forget its history characterized by the initial condition
and the distributions of Wn for
2.2 Transient Loss Measures
We consider two transient loss measures defined for ON
intervals of an arrival process. In the following, we denote
an arrival process R(t) by R(n) when t is in the nth ON
interval where n - 1. Our first transient loss measure is the
probability that loss of workload occurs during the nth ON
interval due to buffer overflow, denoted by
r1 g. The second transient loss measure is the expected
workload loss ratio of the nth ON interval, denoted by
We first compute the loss probability.
In order to derive g, we consider
of exposition, denote the nth ON interval by [0; S).
We use w(t) to represent the amount of workload in the
buffer at t where t 2 [0; S). Given the event that
loss of workload due to buffer overflow occurs in the interval
is equivalent to existing - 2 [0; S) such that
depends on w, we express such
dependence by -(w). It is easy to see
Therefore, for
For simply use
as transient loss measure since w1 is a constant. For
we have
where 'n (w) can be readily obtained by recurrence as
shown in the previous subsection.
Now we consider the expected workload loss ratio. Denote
by ' the fraction of workload lost due to buffer overflow
in the nth ON interval. We assume first
since in [0; S),
loss of workload due to buffer overflow begins only after
reaches -(w). If S ? -(w), then the amount
of workload lost in [0; S) equals the amount of workload
arrived in [0; S) minus the amount of workload accepted in
[0; S), which is r1S \Gamma (CS
where
Therefore,
ae
\Theta

' depends on S, we can also denote ' by '(S).
where FS (s) is the probability distribution function of S.
Denote '(s) by u, we have
s
and
When equivalent
to Therefore, for
Z u 0P
ae
oe
du:
Since w1 is a constant, for simply use
Z u 0P
ae
oe
du
as transient loss measure. For n - 2, we have
Note that for n - 2, the loss probability and the expected
loss ratio depend on the distributions of both S and T since
'n(w) depends on the distributions of not only S but also
2.
2.3 Investigating Transient Loss Behavior
We can investigate transient loss behavior of the queueing
system by computing the loss measures for any given
- 1. But it is not necessary for us to do so. In fact, we
can focus only on a series of a small number of ON and
OFF intervals. Since both ON and OFF intervals have
impact on transient loss performance, such a series must
contain at least two ON intervals and one OFF interval
between them, as shown in Fig. 2.
ON OFF ON

Figure

2: An ON-OFF-ON series of the arrival process.
Now let us consider such an ON-OFF-ON series. Without
loss of generality, the two ON intervals in the series can
be numbered by 2. Since loss behavior of the
queueing system during the first ON interval in the series
cannot capture the impact of the OFF interval, we examine
loss behavior of the system in the second ON interval.
Using the results in the previous subsections, we have
dqdw
dw
dq
and
Z BZ u 0P
ae
oe
dqdudw
Z BZ u 0P
ae
oe
Z u 0P
ae
oe
du
dq
Z u 0P
ae
oe
du: (2)
Before the ON-OFF-ON series begins, the history of the
system is summarized by As time evolves, the
ON-OFF-ON series will probabilistically duplicate itself,
that is, this pattern will appear repeatedly with lengths
of ON and OFF intervals drawn from the same distribu-
tions. At the beginning of each such duplication, there is
an amount of workload w1 left in the buffer, reflecting the
impact of the history of the system. Therefore, in order
to investigate transient loss performance of the queueing
system, it is sufficient to consider or
only for examine the behavior
of the loss measures as w1 varies between 0 and B. In
fact, by focusing only on this simple pattern, we can observe
any possible transient loss behavior of the queueing
system.
2.4 Stochastically Bounding Transient Loss
For some applications, users may require statistically
guaranteed loss performance. For example, it may be required
that the loss probability or the expected loss ratio
should not exceed some given number. This is an important
issue for real-time communications in high-speed networks
and has been addressed typically under the assumption
of steady state. Here we discuss how to guarantee
loss performance in transient state for queueing systems
with two-state fluid-type arrival processes. It may not be
convenient to use the loss measures defined for individual
ON intervals directly for transient loss performance guar-
antee. Instead, we consider some upper bounds on the loss
measures.
For arbitrary n ? 1, if at the end of the (n \Gamma 1)th
ON interval, the buffer has been full already, that is, if
then for the nth ON interval, the loss measures
will be relatively larger compared to the case of
since a smaller Qn\Gamma1 will likely result in a smaller Wn and a
smaller Wn implies a relatively less chance of buffer overflow
and a relatively smaller expected loss ratio. There-
fore,
and B]. The
probability density function of Wn under the condition
0; otherwise.
Accordingly,
and
Now we show that the upper bounds also hold for the
first ON interval if the buffer is initially empty, that is,
In this case, we have of course
? 1. This is because
to Wn - W1 . Therefore, during the nth ON interval, the
queueing system is likely to suffer more severe loss than it
does in the first ON interval.
Based on the upper bounds on the transient loss performance
measures, we can determine the buffer size B and
the service rate C such that
or
is a given loss performance parameter. By
doing so, the loss measures defined for individual ON intervals
will not exceed the given loss performance parameter
if initially the buffer is empty.
In the above, we have assumed that both Sn and are
i.i.d. random variables, so we can use S and T to represent
Sn and respectively. Now we can allow Sn to have
different distributions for different n. In this case, S can
be viewed as a random variable with an arbitrarily given
distribution and stochastically greater than all Sn , that is,
Similarly, we can
also allow Tn to have different distributions. In this case,
T can be viewed as a random variable with an arbitrarily
given distribution and all are stochastically greater
than T , that is, PfTn ? tg - PfT ? tg for all t - 0. The
intuition behind the above arguments is that a stochastically
larger S or a stochastically smaller T will likely lead
to a larger Wn and will therefore result in a larger loss
probability and expected loss ratio. So the above bounds
on transient loss measures are still valid.
3 Steady-State Limits of Transient Loss Measures
To compare transient loss against loss in steady state,
we need to compute the steady-state limits of the loss
measures. The loss measures in steady state are defined
by Pflossg
For a given stationary arrival process, we have the following
limiting conditional probability density functions
and limiting probability density functions
regarding the state variables of the queueing system. To
compute the steady-state loss measures, we need to know
the steady-state probability density function '(w).
Now we show how to compute '(w). Since in steady
state we have by definition
Z B'(wjy)/(y)dy and
Z B/(yjx)'(x)dx
we see that '(w) satisfies a homogeneous Fredholm integral
equation of the second kind
Z BK(w;x)'(x)dx (7)
with kernel
R B'(wjy)/(yjx)dy. We can see
readily
where
and H(w;x) can also be obtained readily.
In general, the Fredholm integral equation can be solved
numerically. However, due to the singularity of K(w;x)
caused by the Dirac delta function ffi(w) at
solve (7) directly. The singularity caused by the Dirac
function ffi(w) at in '(w).
Since this singularity in '(w) is intrinsic and cannot be
removed from '(w), the functional form of '(w) will be
where '0 (w) and v(w) are unknown functions. Due to
the property of the Dirac delta function ffi(w), only v(0)
rather than the whole v(w) will appear in the steady-state
loss measures. In the following, we outline a procedure for
computing '0(w) and v(0). Substituting (9) and (8) into
(7), we have
Z BK0(w;x)'0(x)dx
Z BH(w;x)'0(x)dx
Comparing both sides of the above equation, we see
Z BK0(w;x)'0(x)dx: (10)
Note that
where j is a small positive variable. To avoid the trivial
case of
unknown, we let
and divide both sides of (10) by v(0), so
The above equation is a non-homogeneous Fredholm integral
equation of the second kind in ' 0 (w) with kernel
K0(w;x) and can be solved numerically with the standard
method [4].
obtained by solving (12), now we can determine
v(0) as follows. Since by definition
integrating both sides of the above equation from 0 to B,
we have
R Bv(w)ffi(w)dw
Therefore,
Substituting (13) into (11), we obtain finally
Based on the above results, the steady-state loss measures
now can be computed as follows,
and
-Z u 0P
ae
oe
du
Z BZ u 0P
ae
oe
4 Numerical Studies
In this section, we numerically investigate the following
issues: 1) transient loss behaviors of the queueing system
with different arrival processes, 2) transient loss versus
steady-state loss, 3) the tightness of the upper bounds on
the transient loss measures, and 4) the reliability of transient
loss performance guarantee with system resources determined
according to the upper bounds on the transient
loss measures. For simplicity, we assume that S and T are
identically distributed and all arrival processes considered
have the same E[S] and E[T ]. We consider exponential
distribution as well as two heavy-tailed distributions for S
and T . The first heavy-tailed distribution is
which is a variant of the conventional Pareto distribution.
The reason for us to use this variant form of the Pareto
distribution is that the random variable of interest in our
study takes values from [0; 1) while for the conventional
Pareto distribution, the random variable takes values from
heavy-tailed distribution is
defined by the following probability density function
ae
ffe \Gammaff A ff t \Gamma(ff+1) t ? A
2:
The arrival processes determined by (16) and (17) are long-range
dependent (LRD) processes [2, 5, 12], henceforth
referred to as LRD process I and LRD process II, respec-
tively. Clearly, the arrival process determined by exponentially
distributed S and T is a Markov process. Therefore,
the queueing system with such a Markov arrival process
can also be modeled by a Markov process. However, the
queueing system with an LRD arrival process is not Markovian
anymore.
For simplicity, we let
Under the assumption that all arrival processes considered
have the same E[S] and E[T ] and S and T are identically
distributed, the expectations determined by (16) and (17)
are the same. So the parameter A in (17) can be determined
by the above parameters.
As shown in Subsection 2.3, we can investigate transient
loss behavior of the queueing system by considering
only for 2.
are functions
of w1 , in the following, we simply use w to represent
and denote by P (w) and
by E(w) for convenience of exposition.
4.1 Transient Loss of Different Arrival Processes
We consider three arrival processes determined by the
distributions of S and T as described above. The assumption
that all arrival processes considered have the same
E[S] and E[T ] implies that the marginal state distributions
of the arrival processes are the same. We assume first
that the buffer size and the service rate
all the arrival processes. Then, we compare transient loss
behaviors of the arrival processes based on the functions
P (w) and E(w) defined by (1) and (2), respectively. Note
that w in P (w) and E(w) is previously denoted by w1 in
(1) and (2).
We observe that even though the marginal state distributions
of the arrival processes are the same, the transient
loss measures of the arrival processes can be significantly
different (Fig. 3). The difference in transient loss behavior
is only due to the distributions of S and T . We notice in
Fig. 3 (b) that if w exceeds some critical value, then the expected
loss ratio of the Markov process is less than that of
LRD process I. This is due to the effect of the heavy-tailed
distributions of S and T . Such effect becomes more significant
if C (or B) is large. For example, suppose that we
Fig. 3 (c) and (d). Note
that a large C implies a stringent loss performance require-
ment. In this case, we observe that for any w 2 [0; B], both
the loss measures of the Markov process are less than those
of LRD processes I and II. This is because for the Markov
process, the transient loss measures decay exponentially
fast as C or B increases, but for the LRD processes, the
loss measures decay only hyperbolically.
O O O
O
O
O
O
O
O
O O
E(w)
(b)
(d)
O O
O O
O
O
O
O
O
O O
O O O O O
O
O
O
O
O
O
O O O O O O O
O
O
O
O
(a)
(c)0.09580.0025810.034P(w) E(w)
Markov Process LRD Process II
O
Process I

Figure

3: Transient loss behaviors of different arrival pro-
cesses. (a) The loss probability with
(b) The expected loss ratio with
The loss probability with 0:95. (d) The
expected loss ratio with
4.2 Transient Loss versus Steady-State Loss
Based on (1), (2), (14) and (15), we can compare transient
and steady-state loss measures for different arrival
processes with different buffer size B and service rate C.
We first fix B and let C take several different values (Fig.
4). Then, we fix C and let B take different values (Fig. 5).
The loss measures in steady state are computed according
to the procedure outlined in Section 3.
Unlike the steady-state loss measures, which are simply
some constants, the transient loss measures are functions
of the initial value w that summarizes the history of the
system. For all the arrival processes considered, we observe
that as the initial value varies, the transient loss measures
will become greater than the corresponding steady-state
loss measures. That is, steady-state loss measures can underestimate
actual loss in transient state. As the buffer
size B or the service rate C increases, we can still observe
such underestimates. Although increasing B or C can decrease
the probability for w to take larger values, due to
the randomness of ON and OFF periods, it is still possible
for w to take values greater than some critical value
beyond which the steady-state loss measures will underestimate
transient loss. We even observe that if C (or B) is
large enough, then for all w 2 [0; B], the steady-state loss
measures are strictly less than the corresponding transient
loss measures, for example, see the case of C = 0:9 in Fig.
4.3 Upper Bounds on Transient Loss Performance
We compute upper bounds (3) and (4) on transient
(a)0
E(w)
E(w)
E(w)w w
(d)
(b)0.002
Markov Process
LRD Process
LRD Process II
Steady-State Loss Performance Transient Loss Performance

Figure

4: Transient loss versus steady-state loss for
and 0:9. (a) The loss probability of the
Markov process. (b) The expected loss ratio of the Markov
process. (c) The loss probability of LRD process I. (d)
The expected loss ratio of LRD process I. (e) The loss
probability of LRD process II. (f) The expected loss ratio
of LRD process II.
loss measures for different arrival processes with the same
buffer size 0:8. Then we simulate
actual transient loss performance with 95% confidence
intervals. The results are shown in Table 1. We observe
that the upper bounds on transient loss performance for
all the arrival processes are quite tight. Of course increasing
will affect the tightness of the upper bounds, since
for a large B, it is seldom for Qn\Gamma1 to reach B while a
tight bound implies that the actual value of Qn\Gamma1 is close
to B. The service rate C and the arrival process will also
affect the tightness of the upper bounds. If we increase C,
then the actual loss probability or expected loss ratio will
decrease faster than the corresponding upper bound does.
Accordingly, the bound will become loose. However, the
decay of the actual loss measures also depends on the distributions
of S and T that determine the behavior of the
arrival process. In contrast, decreasing B or C will lead to
tighter upper bounds.
4.4 Transient Loss Performance Guarantee
Some applications need loss performance guarantee. As
shown in Subsection 4.2 (Fig. 4 and Fig. 5), transient
(a)0
E(w)
E(w)
E(w)(d)
(b)
Markov Process
LRD Process I
LRD Process II
Steady-State Loss Performance Transient Loss Performance

Figure

5: Transient loss versus steady-state loss for
0:8 and 4. The horizontal axis represents w
scaled by B. (a) The loss probability of the Markov pro-
cess. (b) The expected loss ratio of the Markov process.
(c) The loss probability of LRD process I. (d) The expected
loss ratio of LRD process I. (e) The loss probability of LRD
process II. (f) The expected loss ratio of LRD process II.
loss is significantly different from steady-state loss. Due
to the randomness of ON and OFF periods, w can take
any value between 0 and B and beyond some critical value
of w, transient loss measures P (w) and E(w) will exceed
the corresponding steady-state loss measures. Therefore,
loss performance guarantee based on steady-state loss measures
is not appropriate.
Suppose that the buffer size 0:01. Note that for a
given C, a small B implies a small delay. For a given
loss performance parameter, we can determine the service
rate C properly for guaranteeing transient loss performance
from (5) and (6) based on the upper bounds.
We consider both the loss probability and the expected
loss ratio. To be specific, we let the loss performance parameter
. The reliability of transient
loss performance guarantee based on the upper bounds
can be verified by simulation. Table 2 shows the service
rate C determined according to the upper bounds and the
transient loss performance measured from simulation with
95% confidence intervals for different arrival processes. We
see that transient loss performance guarantee based on the
upper bounds is indeed reliable.
loss probability
arrival process upper bound simulation result
Markov process 0.323 0.264 \Sigma4:590 \Theta 10 \Gamma3
LRD process I 0.294 0.176
LRD process II 0.269 0.181 \Sigma4:593 \Theta 10 \Gamma3
expected loss ratio
arrival process upper bound simulation result
Markov process
LRD process I 0.034 0.017 \Sigma5:477 \Theta 10 \Gamma4
LRD process II 0.028

Table

1. Upper bounds on the loss measures versus the
corresponding simulation results.
Markov process
ffl C measured loss frequency
ffl C measured loss ratio
LRD process I
ffl C measured loss frequency
ffl C measured loss ratio
LRD process II
ffl C measured loss frequency
ffl C measured loss ratio

Table

2. Transient loss performance measured from simulation
and service rate C determined based on the upper
bounds.
Discussions
In this section we discuss briefly some implications of
our results, regarding the choice of loss performance measures
and the issue of network traffic modeling in the presence
of long-range dependence (LRD) [2, 5, 7, 8, 12, 14, 16].
We also outline a scheme for guaranteeing transient loss
performance for real-time communications.
5.1 Loss Performance and Modeling Issue
Our analysis and numerical results have shown that
transient loss is significantly different from steady-state
loss. In idealized steady state, the system has forgotten
its history. As a result, the steady-state loss measures are
only some constants. In contrast, transient loss measures
depend on the history of the system and therefore are vari-
ables. If the convergence towards steady state is not fast
enough or if the life cycle of the underlying physical process
is not large enough for the system to reach steady state,
then steady-state loss performance can fail to capture the
actual loss behavior in transient state. To use steady-state
loss measures to approximate transient loss performance,
it may be necessary to verify whether the system can approach
steady state fast enough within the life cycle of the
underlying physical process.
From the numerical results presented in Section 4, we
see that for a given arrival process, the loss probability is
greater than the expected loss ratio. This phenomenon
can be explained as follows. Let us focus on the nth
ON interval of an arrival process. According to the results
in Subsection 2.2, given the loss probability
equals
but the expected loss ratio is
since '(s) ! 1. Note that
if the loss probability is equal to 1, then it only means
that loss of workload due to buffer overflow will occur for
certain during the ON interval and does not necessarily
imply that all workload arrived in the interval is lost. As
a consequence, for a given loss performance parameter ffl,
requiring a loss probability less than ffl means a more stringent
loss performance guarantee and hence needs more resources
compared with the case of requiring an expected
loss ratio less than the same ffl. Therefore, for loss-tolerant
applications, it is more appropriate to use the expected loss
ratio as the performance measure, which requires fewer
resources. With the loss probability as the performance
measure, resource allocation for loss-tolerant applications
can be over-conservative and lead to poor utilization of
resources.
Within the framework of steady-state performance anal-
ysis, it is important to study the marginal state distribution
of the arrival process. However, the marginal distribution
is not important to transient loss performance. What
is important is the distributions of random variables such
as S and T that determine the behavior of the arrival pro-
cess. Our numerical results have shown that different two-state
fluid-type arrival processes with the same marginal
state distribution but different distributions of S and T
can experience significantly different transient loss.
The above conclusion may be helpful to resolve the controversy
regarding the relevance of LRD in network traffic
[5, 14, 18, 8, 7]. The issue is whether it is valid to
use Markov processes such as the well-known Markov fluid
models for traffic engineering in the presence of LRD. This
issue has been extensively investigated under the assumption
that the traffic process is already in steady state. Now
let us consider a two-state fluid-type stochastic process in
transient state. If the process is Markovian, then the distributions
of S and T are exponential. However, if S and T
obey some heavy-tailed distributions, then the two-state
fluid is an LRD process. Although in steady state, the
Markov model may still be used [7, 8, 18], transient loss
behaviors of the Markov and LRD processes are significantly
different due to different distributions of S and T .
Our numerical results imply that LRD can have significant
impact on loss performance in transient state. Therefore,
Markov models are not valid for loss performance analysis
in the presence of LRD in transient state. As shown in
Fig. 3 (c) and (d), if a Markov process is used to model
an LRD process, then the Markov model can indeed underestimate
transient loss of the LRD process even though
both processes have the same marginal state distribution.
5.2 Transient Loss Performance Guarantee for Real-Time
Communications
Now let us consider a real-time connection in a high-speed
network. Real-time communications are typically
delay-sensitive but tolerate some fraction of traffic loss
specified by a given loss performance parameter. Suppose
that the maximum allowed delay at a link is D (time
units). A simple way to meet the delay requirement is to
allocate a buffer DC to the connection where C is
the bandwidth to be determined. As a result, excessive
delay is turned into loss. Transient loss performance guarantee
then can be achieved by characterizing bandwidth
requirements properly such that the transient loss measure
will not exceed a given performance parameter. Since the
buffer size required by real-time communications is usually
very small due to the delay constraint, we can assume
that the buffer requirement can always be satisfied, so we
consider only bandwidth allocation.
For the traffic process carried by the connection, there
are two cases. In the first case, static bandwidth allocation
will still be relatively efficient in the sense that the
waste of bandwidth is not serious. In this case, we can
use a two-state fluid-type stochastic process to bound the
bit rate of the underlying traffic source where the state of
the two-state process represents the bit rate of the bounding
process and r0 ! C ! r1 . Note that C ! r1 implies
statistical multiplexing. By replacing B by DC in (5) or
(6), we can determine the bandwidth C according to the
performance parameter for guaranteeing transient loss performance

In the second case, however, static bandwidth allocation
will result in poor utilization of bandwidth due to
multiple time scales in the traffic process [6]. Therefore,
dynamic bandwidth allocation may be necessary to avoid
the waste of bandwidth. Dynamic bandwidth allocation
requires a mechanism for detecting transitions of the bit
rate of the underlying traffic process. In fact, the problem
of detecting the rate change has been extensively studied
and there have been different methods proposed to solve
the problem [9, 3]. In addition, dynamically increasing
or decreasing bandwidth requires a signaling mechanism.
Such signaling protocols exist. For example, the Dynamic
Connection Management scheme in the Tenet Protocol
Suite [15] or the ATM signaling protocol can be used for
this purpose [11]. Therefore, we can assume that the rate
transition can be effectively detected and dynamical band-width
increase or decrease can be effectively accomplished,
so in the following, we focus only on the issue of dynamic
bandwidth allocation.
The state space of a traffic process with multiple time
scales exhibits typically the following structure. The whole
state space consists of several subspaces. The transitions
between states within each subspace are much more frequent
than the transitions between states of any two sub-
spaces. Within each subspace, the underlying traffic process
can be modeled or bounded by a two-state fluid-type
stochastic process with r1 and r0 representing bit rates
. The two-state process depends on the sub-
space, that is, for different subspaces, the two-state processes
are different. For a given subspace, r0 bounds the
bit rates represented by some states of the subspace, and r1
bounds the bit rates represented by all other states of the
subspace that cannot be bounded by r0 . Now we can still
apply our results regarding two-state fluid-type stochastic
processes to allocate a bandwidth to the connection when
the underlying traffic process is in an arbitrarily given sub-
space. When the traffic process moves from a subspace to
another subspace, the bandwidth allocated to the connection
will also change accordingly. With such a scheme,
for multiple time-scale traffic, bandwidth utilization will
remain high while transient loss performance can still be
reliably guaranteed.
6 Conclusions and Future Work
Suppose that we model a physical process as an arrival
process to a finite buffer queueing system. If the life
cycle of the physical process is not large enough for the
queueing system to reach steady state, then it is necessary
to study loss performance of the system in transient state
rather than in idealized steady state. However, previous
work in transient analysis of queueing systems typically focuses
on Markov models. In this paper, we have presented
an analysis of transient loss performance for a class of finite
buffer queueing systems fed by two-state fluid-type
stochastic processes that may not be necessarily Marko-
vian. We have discussed how to define, compute and guarantee
transient loss performance and illustrated the analysis
with numerical results. Our work is useful since many
interesting phenomena in performance-oriented studies can
be modeled by two-state fluid-type stochastic processes,
and our results can also be used for multiple-state processes
with multiple time scales.
A lot of work remains to be done. For example, it may
be interesting to implement and demonstrate the scheme
of transient loss performance guarantee for real-time communications
outlined in Subsection 5.2 in an experimental
environment such as an ATM test bed. Another issue to
be explored further is to extend the analytical results to
more general stochastic processes.



--R

"Transient analysis of Markovian queueing systems and its application to congestion-control modeling"
"Long range dependence in variable bit rate video traffic"
"Predictive dynamic bandwidth allocation for efficient transport of real-time VBR video over ATM"
Computational Methods for Integral Equations
"Exper- imental queueing analysis with long-range dependent packet traffic"
"RCBR: a simple and efficient service for multiple time-scale traffic"
"On the relevance of long-range dependence in network traffic"
"What are the implications of long-range dependence for VBR- video traffic engineering?"
"Quick detection of changes in traffic statistics: application to variable rate com- pression"
"On computing per-session performance bounds in high-speed multi-hop computer networks"
"An empirical evaluation of adaptive QOS renegotiation in an ATM net- work"
"On the self-similar nature of ethernet traffic (extended version)"
"On defining, computing and guaranteeing quality-of-service in high-speed networks"
"On the use of fractional Brownian motion in the theory of connectionless networks"
"Dynamic management of guaranteed performance multimedia con- nections"
"Wide-area traffic: the failure of Poisson modeling"
"Transient analysis of cumulative measures of Markov models"
"The importance of long-range dependence of VBR video traffic in ATM traffic engineering: myths and realities"
--TR
Computational methods for integral equations
On defining, computing and guaranteeing quality-of-service in high-speed networks
On computing per-session performance bounds in high-speed multi-hop computer networks
On the self-similar nature of Ethernet traffic (extended version)
Dynamic management of guaranteed-performance multimedia connections
area traffic
RCBR
Experimental queueing analysis with long-range dependent packet traffic
What are the implications of long-range dependence for VBR-video traffic engineering?
The importance of long-range dependence of VBR video traffic in ATM traffic engineering
On the relevance of long-range dependence in network traffic
stochastic modeling;transient loss performance;queueing systems