Exponential bounds with applications to call admission.
In this paper, we develop a framework for computing upper and lower bounds of an exponential form for a large class of single resource systems with Markov additive inputs. Specifically, the bounds are on quantities such as backlog, queue length, and response time. Explicit or computable expressions for our bounds are given in the context of queuing theory and numerical comparisons with other bounds and exact results are presented. The paper concludes with two applications to admission control in multimedia systems.
Introduction
We are witnessing a phenomenal growth in the deployment and usage of networked multimedia
applications. Numerous networked teleconferencing applications have recently been introduced,
[40, 58, 30, 41]. In addition, there are plans to deploy large-scale multimedia servers in the not too
distant future, [55]. All of these applications share the need for a minimal quality of service (QoS)
guarantee in the form of either an end-to-end delay constraint or a maximum tolerable fraction of
loss. Providing QoS guarantees to these applications poses one of the most challenging problems
facing designers of multimedia systems and applications.
In this paper we focus on a single resource and develop a framework within which to obtain computable
upper and lower bounds on the tail of the distributions of quantities such as backlog, delay
and queue length at that resource. These bounds are exponential in nature when the combined
arrival and service processes (to be made precise) can be described by a Markov chain and the
system is stable. In addition to obtaining distributional bounds, we also apply these results to the
problem of call admission in a network and in a multimedia server setting.
More precisely, we consider the behavior of a single server as described by the recursion
with a.s, where the real-valued increments (U n ) n are modulated by a Markov chain (Y n
such that (Y n+1 ;
Additive (MA) process [39]. In our context, one application
is when X n represents the waiting time of the n-th customer in a First-In-First-Out (FIFO) G/G/1
single server queue, U are the service requirement and interarrival
time sequences, respectively.
Our primary objective is to compute exponential upper and lower bounds for the tail distribution
of X n , both for every n - 0 and for the stationary regime X of X n (when it exists), namely, to -nd
strictly positive constants a, a n , b, b n and ' such that
a
a e \Gamma'x -
for all x - 0, n - 0.
In the particular case where (oe n ) n and (- n ) n are two mutually independent renewal sequences
(GI/GI/1 queue), Kingman [44, 45] showed that a exp(\Gammajx) -
and x - 0, where j is the unique solution in (0; 1) of the equation E[exp(' (oe
the stability condition E[oe re-nement of Kingman's upper bound was proposed by
Ross [57]; see also [8, p. 139]). Our results can be considered as an extension of Kingman's result
to stochastic recursions of the form (1.1) where (X n ) n is no longer a Markov chain.
As mentioned before, our work is motivated by the need to characterize the response time distribution
and/or backlog distributions in multimedia systems. Many multimedia applications have
real time constraints (e.g., voice, video) for which it is important to characterize the response time
distribution at a single resource, whether it is a hop in a network or the I/O system at a server.
Although such applications have real time constraints, they are able to tolerate a small fraction of
packets missing their deadlines (approx. 1% for voice). Bounds on the tail distribution of quantities
such as buoeer occupancy and response times can be used by designers to size systems. Furthermore,
bounds can be used to develop policies for controlling the admission of new applications (sessions)
to the network.
Previous work in this area falls into three categories. First, a considerable amount of work has
focussed on the development of algorithms for computing the response time distribution of a statistical
multiplexer being fed by a Markovian Modulated Process (MMP) pioneered by Neuts [53] (see,
in particular, the works by Regterschot and de Smit on the M/G/1 queue with Markov modulated
arrivals and services [56] and by Lucantoni, et al. on the transient analysis of the BMAP/G/1 queue
[51], as well as [29] for a recent survey of this area). These computations are often very expensive
and do not easily yield the tail probability distribution. Consequently, there has been considerable
interest in the development of approximations or asymptotics. These include methods which approximate
the arrival processes by simple Markovian models, (e.g., [36]) or AEuids, (e.g., [3]), are
based on asymptotic properties of statistical multiplexers (e.g., [2]) or on dioeusion processes, (e.g.,
[31]). The problem with these methods is that there is no way of knowing how accurate they are
in any one application. This has motivated interest in the development of performance bounds for
general arrival processes. This is exempli-ed by the works of Asmussen and Rolski [7], Chang [12],
Cruz [18, 19], DuOEeld [22], Kurose [46], and Yaron and Sidi [62]. With the exception of the work
of Asmussen and DuOEeld these papers make very few assumptions regarding the arrival processes
and the resulting bounds are very loose.
Previous work most closely related to ours include those of Asmussen and Rolski [7] and DuOEeld
[22]. Asmussen and Rolski derived bounds in the context of risk theory and Asmussen [6] showed
how they can be mapped into bounds on the tail of the queue length distribution of an MMPP/G/1
queue. Our techniques apply to a larger class of systems. Moreover, as will be described later,
our bounds are, in general, better than those in [7]. The mapping described in [6] can be used to
apply our bounds to risk theory. DuOEeld uses a martingale approach (similar to [44] for the G/G/1
queue) to obtain upper bounds similar to ours for a Markovian environment. This approach does
not appear easily to yield lower bounds. Neither of the two approaches reported in [7, 22] appear
easily to yield bounds on the transient behavior.
We apply our bounds to several systems that have received considerable prior attention. These
include the MMPP/EN /1 queue, the MMPP/D/1 queue and the -xed rate discrete time queue
fed by a homogeneous population of on/ooe sources. For the -rst two models we present easily
computable bounds on the tail of the response time distribution and compare them with the bounds
in [7, 22] and the exact distribution. We observe from a large number of examples (see Sections 3.4
and 3.5) that our bounds are usually better than those in [7]. We also observe that the dioeerence
between the upper and lower bounds is always smaller than that of [7]. For our examples with
homogeneous two-state MMPPs, the times to compute these bounds dioeer from the times to
compute the distribution exactly by two or more orders of magnitude. For the discrete time model,
we present easily computable bounds which are then used to address the call admission problem.
Comparisons are made with the eoeective bandwidth approach [35] which illustrate the conservative
nature of the latter.
The organization of the paper is as follows. Upper and lower bounds are derived in Section 2.
This section includes a derivation of the largest exponential decay rate and a treatment of both
transient and stationary regimes. It concludes with a demonstration of the tightness of the bounds.
Applications of the bounds to queues operating in a Markovian environment are found in Section
3 along with comparisons to the bounds developed in [7, 22]. Applications to discrete time queues
and to call admission in multimedia systems are found in Section 4.
Exponential Bounds
In this section we derive exponential upper bounds (Section 2.2) and lower bounds (Section 2.3) for
the tail distribution of X n as well as for the tail distribution of its stationary regime X (Section 2.4).
We establish these results by extending the approach of Kingman [45] to the multidimensional case
using matrix analysis techniques. Prior to deriving the bounds, we introduce some notation.
2.1 Notation and Assumptions
Throughout this paper we assume that the real-valued increments (U n ) n are modulated by a Markov
chain (Y n ) n such that
(A) U n and Y n+1 conditioned on (X depend only on Y n .
We shall assume for the sake of simplicity that the Markov chain (Y n ) n has a -nite state-space
Kg. The extension of our results to general state-spaces can be found in [47].
For any Borel set \Gamma of (\Gamma1; 1),
the kernel of the MA process (Y n+1 ;
its transform
F
e
With a slight abuse of notation, F ij (x) will correspond to F ij ((\Gamma1; x]).
We assume the Markov chain (Y n ) n is homogeneous, aperiodic and irreducible, with transition
(note that (1)). The irreducibility of P implies that Perron-Frobenious
theory applies to F   (') for all ' 2 D [39, Section 7(ii)]. Here D is de-ned as
As a result, we know that the matrix F   (') has a unique left eigenvector z
with strictly positive components, corresponding to its largest eigenvalue ae(') and such that
Theorem 8.4.4] (throughout this paper upper case boldface will denote matrices
and lower case underlined will denote vectors). In the sequel we will assume that ' 2 D.
To avoid triviality we further assume that the set M ae S 2 de-ned by
is nonempty, as otherwise X a.s. as n goes to 1.
Last, we denote by - the probability distribution
vector at time n and the stationary probability distribution vector, respectively, of the Markov chain
mentioned, the initial probability distribution vector - 0 is arbitrary in the
sense that we do not assume stationarity of the Markov chain (Y n ) n .
2.2 Exponential Upper Bounds
In this section, we derive upper bounds for the tail distribution of X n . Let (fl n
1), be a set of functions such that
The following result holds:
Proposition 2.1 Let Pm denote the property that
for all x - 0, j 2 S.
If P 0 is true, then Pm is true for all m - 1.
Proof. We use an induction argument on m. Assume that Pm is true for
us show that P n+1 is true.
We have for all x - 0, j 2 S,
where (2.7) follows from the induction hypothesis, and where (2.6) is a consequence of assumption
(A).
The following result provides an upper bound for P
Proposition 2.2 (Exponential upper bound)
If ae(') - 1 and if
with
0-m-n
z k (')
x
e '(u\Gammax) F kj (du)
Sg.
In particular,
Proof. De-ne
Thanks to Proposition 2.1 it suOEces to prove that the functions in (2.12) satisfy (2.4) to establish
(2.
x
F
x
F kj (du)
F
where (2.13), (2.14) and (2.15) follow from the de-nition of C n ('), the identity z (')
ae(') z ('), and the inequalities ae(') - 1 and C n - C n+1 , respectively. This proves (2.9).
Summing up over all j in S both sides of (2.9) and using the normalizing condition
yields (2.11).
We conclude this proof by showing that the constant C n (') is always -nite. This property follows
from the obvious inequalities
0-m-n
0-m-n
-m (j)
where the last inequality follows from the positiveness of the eigenvector vector z (').
1g. An interesting issue is to determine when '   ? 0 or,
equivalently, when does an exponential upper bound exist for the tail distribution of X n . In the
case when the set D is open, the answer is provided by DuOEeld [22, Lemma 2] who showed that
only if the stability condition denotes the expectation
operator associated with a stationary Markov chain (Y n This result in turn implies
that an exponential upper bound exists for P (X n ? x) if and only if the system is stable (see Remark
2.1). In that case, '   is the largest exponential decay rate among all positive decay rates such that
ae(') - 1. However, this leaves open the question whether '   is the best possible decay rate over all
aOErmative answer to this question again follows from DuOEeld [22] (see also Glynn and
Whitt [33, Theorem 1]) who established that
lim
log
when the set D is open. The results in [22] require that the recurrent condition (3.2) in [39] be
satis-ed. However, this condition is automatically ful-lled when the Markov chain (Y n ) n has a
-nite state-space, as observed by Iscoe et al. [39, Section 7(ii)], which therefore validates the use
of DuOEeld's results here. In the case when the state-space is general, then condition (3.2) in [39]
must be assumed.
As mentioned above, the results in [22] also require that the set D be open. While it is not diOEcult to
contruct examples where this assumption is violated, it turns out that a large class of distributions
yields an open set D. This class includes the distributions with rational Laplace transforms (e.g.
phase-type distributions).
Large deviation results for queues like (2.17) have also been obtained lately by Abate et al. [2],
Chang [12], Courcoubetis and Weber [17], de Veciana et al. [21], DuOEeld and O'Connell [23],
Elwalid and al. [27], Kesidis et al. [38], Parulekar and Makowski [54], Simonian and Guibert [59],
among others.
Remark 2.1 When the Markov chain (Y n ) is stationary, the stability condition
from Loynes [50]. In the non-stationary case one may use a coupling argument due to Borovkov
and Foss [9] to prove that also the stability condition or, in other words, that there
exists an almost -nite r.v. X such that X n converges in law to X as independently of the
joint distribution of X 0 and Y 0 .
2.3 Exponential Lower Bound
In this section we address the problem of computing an exponential lower bound for the tail distribution
of X n .
Proposition 2.3 (Exponential lower bound)
Assume that ae('
where
0-m-n
z k ('   )
x
In particular,
Proof. Let (ffi n
be a set of functions such that
be the property that
for all x - 0, n - 0, j 2 S. Mimicking the proof of Proposition 2.1 we can prove that Q n is true
for all n - 0 if Q 0 is true.
De-ne now the functions ffi n
By using the same arguments as in the
proof of Proposition 2.2 and the identity ae('   easily checked that the functions ffi n
satisfy (2.22), from which (2.19) and (2.21) follow.
The equation has one and only one solution when the set D is
open. This follows from the strict convexity of ae(') on D (which itself is a consequence of the strict
convexity of log ae(') [39, Lemma 3.4(i)]), of lim '!ffiD Corollary 3.1], of
of ae 0
2.4 Bounds for the Stationary Regime
In this section we determine upper and lower bounds for P (X ? x), the stationary tail distribution
of X n , and we discuss cases when the lower bound is not trivial.
Proposition 2.4 (Stationary lower and upper bounds)
Assume that the stability condition holds (see Remark 2.1). If ae(') - 1 then
for all 0 - '   , where
z k (')
x
e '(u\Gammax) F kj (du)
Furthermore, if ae('
where
z k ('   )
x
The proof of Proposition 2.4 follows from Propositions 2.2 and 2.3 and from the result that P (X n ?
independently of the joint distribution of X 0 and Y 0 whenever the stability
condition discussed in Remark 2.1.
It is simple to construct examples where the constant B in (2.25) is equal to 0. However, we expect
practice. In the rest of this section we discuss two cases where B ? 0: the case when the
increments (U n ) n are bounded from above, and the case when they have phase-type distributions.
Our discussion will be based on the following technical lemma whose proof is given in Appendix A.
Lemma 2.1 For (j; (see (2.3) for the de-nition of
M). If for every pair of states (j; de-ned by
x
is strictly positive, then B ? 0.
An immediate corollary of this lemma is that B ? 0 when the increments (U n ) n are bounded from
above, that is, when
We now address the case where F kj (x) has a polynomial-exponential density function. A probability
density function f(x) of a (0; 1)-valued r.v. is polynomial-exponential if it has the form
a
where a i 's are nonzero real numbers, m i 's nonnegative integers and fi i 's are strictly positive real
numbers. The set of r.v.'s with polynomial-exponential density functions is quite large and includes,
in particular, the set of r.v.'s with phase-type distributions (e.g., Coxian distributions - see [5, pp.
74-75]). Recall that the latter set is dense in the set of probability distributions on (0; 1) [5,
Theorem 6.2, p.76]. The following result, proven in Appendix A, holds:
Corollary 2.1 If for every (k; jk (x) has a polynomial-exponential
density function, then B ? 0.
Instances where F kj has a polynomial-exponential density function and \Delta may be found in
Section 3.2 and 3.3, respectively.
3 Application to Queues and Comparison with Other Bounds
In this section we specialize the recursion (1.1) to the case when the increments (U n ) n are in the
In this setting (X n ) n typically represents the
waiting time process in a FIFO G/G/1 queue with interarrival times (- n ) n and service requirements
equation (1.1) is called the Lyndley's equation. Our aim is to give explicit formulae
for the coeOEcients C(') and B that appear in the upper bound (2.24) and in the lower bound
(2.26), respectively, and to numerically compare these bounds with bounds that have been recently
proposed in the literature. This section is organized as follows: in Section 3.1 we derive lower
and upper bounds for the tail distribution of the stationary waiting time for queues in Markovian
environment; in Sections 3.2 and 3.3 these bounds are specialized to the case of MMPP/EN /1
and MMPP/D/1 queues, respectively; in Section 3.4 we review bounds proposed by Asmussen and
Rolski [7] and DuOEeld [22] and place them into the context of the queueing models introduced in
Section 3.1; Section 3.5 concludes with numerical results and a discussion on the tightness of the
various bounds presented in Sections 3.2-3.4.
3.1 Bounds for Queues in Markovian Environment
We assume that customers arrive at a FIFO single server queue according to a Markov modulated
Poisson process (t n ) n [29]. More precisely, we assume that the arrival process is a doubly stochastic
Poisson process with arrival rate - Z(t) at time t, where (Z(t); t - 0) is an irreducible Markov
process on the set rate matrix
diag
Service requirements (oe n ) n are also modulated according to the Markov process (Z(t); t -
in the sense that the probability distribution of the service requirement of the n-th customer,
may depend on Z(t n \Gamma). We denote by H i
the probability distribution and the Laplace transform of oe n , respectively,
given that Z(t n \Gamma) = i. We also assume that the service requirements are mutually independent
r.v.'s, and that the service requirement oe n is independent of the state Z(t \Gamma
assume that the queue is stable [29].
In order to apply the results in Section 2 we need to identify the Markov chain (Y n ) n , the kernel
(2.1) and its transform (2.2). In this setting, it is easy to see that the Markov chain (Y n ) n must be
chosen as the Markov chain embedded in at arrival instants, that is Y Its
transition matrix P is given by (see [29])
Let us determine the kernel F ij (x). We -rst observe that F ij (x) needs only to be determined for
as the supremum and the in-mum in (2.24) and (2.26), respectively, are only taken over
nonnegative values of x. We have, for x - 0,
x
or, in matrix notation,
x
with It is
known (see [29, formula (5)] for instance) that
so that, from (3.3),
x
where I stands for the identity matrix. This, in turn, implies that
x
by using the identity (  \Gamma
We are now in position to write down the coeOEcients C(') and B (see Proposition 2.4). In matrix
these coeOEcients become by using (3.5) and (3.6)
with
x
z (')
x
is the vector whose components are 0 except the j-th one which is equal
to 1:
Let us now determine the matrix F   (') for ' 2 D " [0; 1). Since, for all n - 0, oe n is independent
of - n , given Y n , we clearly have
F
Z 1e \Gamma' x dG(x)
with H   diag (H
follows from (3.4).
From (3.9) we may compute the left-eigenvector z (') of F   (') corresponding to the largest eigenvalue
ae('), and derive the optimal exponential decay rate '   as the unique solution in (0; 1) of the equation
We conclude this subsection by brieAEy discussing the case when the interarrival and customer
requirement sequences are mutually independent renewal sequences (GI/GI/1 queue). In this case,
our lower bound (2.25) reduces to the lower bound found by Kingman [45] and the upper bounds
(2.23) reduce to the upper bounds derived by Ross [57] (see also [60]). In particular, the lower
bound and the upper bound in (2.25) are equal when the service times are exponentially distributed
(GI/M/1 queue).
3.2 Bounds for the MMPP/EN /1 Queue
We consider the queueing model de-ned in Section 3.1 but we now assume that the service requirements
sequence, independent of the arrival process, with common distribution
function H(x) given by an N-stage Erlang probability distribution (MMPP/EN /1 queue), namely,
This assumption implies, in particular, that (cf. (3.9)) F
Recall the de-nition of g j (x; ') (see (3.8)). Straightforward algebra yields
z
where
l
(- \Delta) N \Gamma1\Gammal
and use the identity
The complexity of computing C(') (resp. B('   )) is dominated by the search for the value of x that
yields the supremum (resp. in-mum) in the expression (3.7). In the case of the Erlang distribution,
it is easily shown that no more than values of x (possibly including need
to be checked and that, except for are the positive real roots of the polynomial
dx
dx
which can be shown to be of degree 2(N \Gamma 2).
For the case does not depend on x and we have
min
z ('   )
For the case is a constant and we have been able to establish that the supremum
(resp. in-mum) of g j (x; '   ) over x in [0; 1) is always achieved at 0). For the
case N ? 2 (MMPP/EN /1 queue) we conjecture that OE j (x) has no positive real roots. We further
conjecture that the supremum (resp. in-mum) of g j (x; '   ) over x in [0; 1) is always reached at
These conjectures have always checked true in all the numerical experiments
we have performed using the Maple V 1 software for symbolic computation. When the last conjecture
holds, then
z ('   )
min
z ('
3.3 Bounds for the MMPP/D/1 Queue
We now specialize the queueing model in Section 3.1 to the case when the service requirements
are all equal to the same constant s (MMPP/D/1 queue). Then, cf. (3.9), F
In this case, it is not diOEcult to
show that
z (')
Again, we conjecture that the supremum (resp. in-mum) in g j (x; '   ) is always reached for
as this has always been observed through our experiments. In particular, it is true
for the M/D/1 queue. When this is true, then C('   ) takes the simple form
3.4 Other Bounds for Queues in a Markovian Environment
In this section we review bounds recently proposed by Asmussen and Rolski [6] and DuOEeld [22].
The bounds proposed by Asmussen and Rolski [7] have been derived in the context of risk theory.
In the queueing setting of Section 3.1 Asmussen and Rolski's bounds read [7, Corollary 4.1], [6,
Theorem 3.8]:
Maple V is a registered trademark of Waterloo Maple Software.
with
sup
x
x
Note that bounds in [5] are only available for the stationary regime and for Markov chains (Y n ) n with
a -nite state-space. To de-ne the unknown quantities fl   and h k (fl   ) in (3.15)-(3.17), introduce the
diag (- i (H
is the in-nitesimal generator of the reversed Markov process (Z(t); t -
0). Let be the right-eigenvector of the matrix M(fl) corresponding to the
eigenvalue -(fl) with the largest real part. Then, when the queue is stable, fl   is the unique solution
in (0; 1) of the equation It can be shown that '  . Note that this result directly
follows from inequalities (2.25) and (3.15) whenever B ? 0 and
when the service times are either deterministic or taken from an Erlang distribution, it can be shown
that the sup and inf in (3.16) and (3.17) are achieved at
In [22] DuOEeld derived a set of upper bounds for the tail distribution of the stationary regime X of
a stochastic process (X n ) de-ned by the recursion (1.1) under the assumptions that (Y n ;
is a MA process (same assumption as ours) and that the Markov chain (Y n ) n is stationary (we do
not impose this condition). Specializing DuOEeld's bounds to the queueing model of Section 3.1
yields, for
for all ' 2 [0; '   ], with
where r j (') is the j-th component of the unique vector r (') satisfying the relations F   (') r
ae(') r (') and
Observe that D(') - 1 (since
as opposed to the coeOEcients in Asmussen and
Rolski's upper bound and in ours which may be smaller than one (see numerical results in Section
3.5 for
However, it is diOEcult in general to analytically compare the bounds in [7] and in [22] to ours since
they appear in very dioeerent forms (see (2.25) where B and C(') are given in (3.7)-(3.8), (3.15),
and (3.18)), which is a consequence of the fact that they have been derived using very dioeerent
techniques: risk theory and Lundberg's inequalities for Asmussen and Rolski, martingales and large
deviations for DuOEeld, and the extension of Kingman's method for our bounds. A comparison
based on numerical results is presented in the next section.
Other (upper) bounds have also been recently obtained by Chang [12], and Yaron and Sidi [62],
for queues with very general arrival patterns. These bounds, based on Chernooe's inequality, are in
general not as tight as our bounds.
3.5 Numerical Results and Discussion
In this section we report numerical experiments performed for various queueing models with MMPP
arrival processes. More precisely, we assume that the arrival process is the superposition of M
25 in the tables) independent, homogeneous, two-state MMPP's. Observe that the superposition of
independent MMPP's is again an MMPP (see [29] for instance) so that the results obtained so far
in this section apply.

Tables

1-4 display our lower and upper bounds (LNT l.b/u.b.; see Sections 3.2, 3.3) and Asmussen
and Rolski's lower and upper bounds (AR l.b./u.b.; see (3.15)) for the tail distribution, P (X ? x),
of the stationary waiting time for MMPP/M/1, MMPP/E 2 /1, MMPP/E 5 /1, and MMPP/D/1
queues respectively. These bounds have been computed for dioeerent values of the traOEc intensity ae
(ae 2 f0:4; 0:75; 0:95g) and for various values of x. In each case, the mean service time is 1.
Before commenting on the numerical results we -rst describe an eOEcient way to compute '   and
z ('   ) as a brute force approach may not be applicable for large values of M . The optimal decay
rate '   was computed by using the ieoeective bandwidth decompositionj for MMPP/GI/1 queues
fed by M independent MMPP's, that is, when (Q;
. In this case the
optimal decay rate '   satis-es the equation
where H   (') is the Laplace-Stieltjes transform of the service times (as usual pf(A) denotes the
Perron-Frobenius eigenvalue of the matrix A). Equation (3.20) follows (for instance) from [61, eq.
(6.22) and Proposition 14] (see also [26] and [43] among others).
In the case that the arrival process is the superposition of M independent homogeneous two-state
MMPP's each with in-nitesimal generator and rate matrix given by
respectively, then (3.20) reduces to
r
with H   eOEcient numerical procedures can
be used for computing '   from (3.21).
Let us now turn to the computation of z ('   ). Depending on the dimension of the matrix F   (') (see
here F   our notation) various approaches (including a
brute force approach and an iterative approach) may be used for computing z ('   ), the (normalized)
left-eigenvector of F   ('   ) associated with the eigenvalue 1. In the case that the input process is
the superposition of M independent homogeneous two-state MMPP's then the input process can
be modeled as a (M + 1)-state MMPP with in-nitesimal generator
diag
This corresponds to aggregating all MMPP's into a single MMPP with arrival rates depending on
the number of MMPP's in state 2 at any time in the initial system. In this case, z ('   ) can be
computed explicitly as brieAEy discussed below.
We -rst observe from the de-nition of z ('   ) that z ('   the equation
. By noting that M as the same structure as the
matrix M in [3, p. 1875] a similar analysis to that in [3, Section 2.1] allows us to obtain the
j-th component (1 - of the vector OE as the coeOEcient of x j \Gamma1 in the polynomial
(assuming that OE are the roots of the polynomial
(see [3]) is given
by
)). The vector z ('   ) is now obtained by
normalizing the vector OE T   so that its components sum up to one.
In general, we observe that the tightness of the bounds increases as the traOEc intensity and the
variability of the service times increase and, in particular, our bounds appear to be very tight for
the MMPP/M/1 queue. Although our lower bound is always better than Asmussen and Rolski's,
our upper bound is sometimes looser (in the case of deterministic service times). We observe that
the gap between our lower and upper bounds is always (occasionally considerably) smaller than
the corresponding gap for Asmussen and Rolski's bounds. Last, we omitted DuOEeld's upper bound
because we have always observed it to be worse than ours and that of Asmussen and Rolski.
We also include exact results obtained by inverting the Laplace transform of the tail of the wait
time distribution [29, 15]. The inversion is performed using the EULER algorithm described in [1]
using parameter values 11. The third parameter of the algorithm, n was set to
100 in the case of exponential and Erlang distributions. Because we had diOEculty determining a set
of parameter values with which to generate the exact solution for a deterministic service time, we
approximate it by an Erlang random variable with 8192 stages. For this case, we set the parameter
n to be 200. We found the our bounds valuable in helping us to set these values (see [1] for a
further discussion on the use of bounds for computing exact distributions). Our experience has
been that the time required to calculate P (X ? x) exactly for 8-12 values of x is 100 to 600 times
more expensive than calculating the bounds for the systems presented in Tables 1-4. The exact
calculation of a larger number of values is even more expensive as the cost is linear in the number
Exact
Exact
Exact

Table

1: Bounds and exact value for P (X ? x) for MMPP/M/1 queue with 25 homogenous two
state sources; (a)
of values whereas it is essentially constant (the cost of calculating B and C('   )) for the bounding
methods.
Similar observations regarding the quality of the bounds hold for other values of the number of
sources. We have not compared the costs of computing our bounds with those of computing the
distribution exactly in the case of a heterogeneous population of sources. However, if it consists
of independent two-state sources, the computation requirements will not increase signi-cantly as
it dioeers from that described above in the determination of the eigenvector z ('   ); it must now be
obtained by solving a set of linear equations. Although the computation costs for an exact solution
will not change, they will still remain signi-cantly greater than for the bounds.
We conclude this section by noting that even more striking dioeerences in computation costs have
been observed when our bounding approach was adapted to a heterogeneous population of Markov
on/ooe AEuid sources [4].
AR u.b . 0:973 3:464
Exact
Exact
Exact

Table

2: Bounds and exact values for P (X ? x) for MMPP/E 2 /1 queue with 25 homogenous 2
AR l.b.
Exact
Exact
Exact

Table

3: Bounds and exact values for P (X ? x) for MMPP/E 5 /1 queue with 25 homogeneous 2
Exact
Exact
Exact

Table

4: Bounds, approximations and exact values for P (X ? x) for MMPP/D/1 queue with 25
4 Applications to Call Admission in Multimedia Systems
The aim of this section is to present various applications of our results to the problem of call
admission in a multimedia system such as a network or a server. A call admission algorithm
aims at admitting a new multimedia application (session) into a network or a server only if it can
be guaranteed a minimal quality of service (QoS) without violating the QoS of other applications
already in the system. In the case of a network, there is the additional constraint that the algorithm
must be simple enough so that the decision to accept or to reject a new session can be carried out
on-line.
Consider the network setting. A call admission algorithm must typically be concerned with guaranteeing
an end-to-end QoS over a path that may contain two or more hops. This is a diOEcult
problem and one approach taken is to divide the end-to-end QoS requirement among all of the hops
and perform call admission at each hop (e.g., [35, 28, 52]). Thus, if any one hop decides not to
admit the call, the call is not admitted end-to-end. Under this approach, it suOEces to consider the
call admission problem for a single channel. Note that, in the case of call admission to a multimedia
server, the server can also be modeled as a single resource [20].
Consider a communication channel equipped with a buoeer of -nite or in-nite size, that can transmit
up to c units of information (e.g., c ATM cells) per unit of time. When the buoeer is of in-nite size
a typical performance criterion is may represent either the buoeer content
at arrival epochs in steady state or the packet delay in steady state. Observe that if X is the
steady-state content of a buoeer of in-nite size, then q implies that, for the case of a
buoeer with -nite capacity b, the cell loss probability does not exceed q.
Using the bounds established in Section 2, we obtain bounds on the number of calls that can be
admitted to a single resource system. We will observe that use of the upper bound on the tail of
the backlog distribution for the purpose of call admission results in a larger number of admitted
calls than the popular eoeective bandwidth approach [35].
In the following, we will only consider a buoeer of in-nite size. The resource (communication channel
in a network, I/O system in a server) will be modeled as a single server queueing system with service
capacity c.
4.1 Markov Arrival Process
Consider an irreducible, aperiodic Markov chain (Y n ) n with state space S :=
matrix P. Let be a sequence of f0; :g-valued r.v.'s such that
chain with transition kernel G kj Then, the process
is called a Markov Arrival Process (MAP). In the following, a MAP will be represented by the
4-tuple there is a need to specify the Markov environment associated with
it; otherwise, we will simply say that
Assume now that the increments (U n ) n in (1.1) are given by U
and c is a nonnegative constant. From the de-nition of a MAP it is seen that the sequence (U n
assumption (A) in Section 1 so that all of the results obtained in Section 2 will apply to
Consider now N independent MAP's,
be the process
resulting from the superposition of these MAP's, namely, A
. It is known that
(\Omega denotes the Knonecker product of matrices). By
using elementary properties of Kronecker product of matrices [11, 34] together with the independence
assumption of MAP's
easily seen that the spectral radius ae(') of the matrix F   (')
is given by
Y
is the spectral radius of the matrix with (k; j)-entry given by E[exp(' A
Therefore, we deduce from Proposition 2.4 that
log(-
The quantity c i is called the eoeective bandwidth of the process
A similar result was presented by Chang and Cheng in [13, Example 3.4] but with a dioeerent
coeOEcient C('). The coeOEcient in [13], denoted as \Gamma('), is given by
is the (positive) right eigenvector of the matrix F   (') associated with its
spectral radius ae('). In general, the bound in [13] appears to be looser that ours. In particular,
\Gamma(') is always larger than 1 for ' ? 0 unlike C(') which maybe smaller than 1 (see Section 4.1.1).
Example 4.1 (Computation of C(') for discrete time on/ooe sources)
Consider the case when is the superposition of N independent and identical 2-state MAP's
such that
where p kj is the (k; j)-entry of the transition matrix P i , and F k
Assume that F 1 In other words,
each MAP
is a discrete time on/ooe source which emits packets at rate - in state 2 and does
not emit any packet in state 1. Then, it can be shown [49] that
l 0
-l-N
e -l'
ff ir
with
the probability that r sources are on at time n given that i sources were on at time
l
l
\Gammar\Gammal :Consider now the performance criterion P (X ? x) - exp(\Gamma' x) for x !1. The following holds:
Proposition 4.1 If the stability condition is satis-ed, and if the set D is open, then,
for all ' 2 D " (0; 1)
lim
log
x
- \Gamma' if and only if
Proof. Assume that and that the set D is open. Therefore, '   ? 0 (cf. discussion after
the proof of Proposition 2.2), which in turn implies from the strict convexity of ae('), the identity
(see the discussion at the end of Section 2.3) that the condition ae(') - 1,
or, equivalently,
c from (4.1), holds if and only if 0 - '   . From this and (2.17) we
conclude that
Proposition 4.1 is not new, as the same result was announced by Kesidis et al. [43] (but proved
through a heuristic argument). This proposition was mainly stated for future reference (see Section
4.1.1) and the proof we gave was presented for the sake of completeness. The same result can also
be obtained in an even more general context (see Assumptions (C1)-(C3) in [12]) from the work
of Chang [12, Proposition 3.9] by using the same arguments as ours. In particular, Chang showed
that c i
Example 3.3], which provides a nice
interpretation of the eoeective bandwidth of a source.
We now consider two applications of the above analysis to call admission in multimedia systems.
The -rst is to the admission of voice calls to a single channel. The second is to the
admission of viewers to a video server.
4.1.1 Call admission in a network
Consider a single serving a population of voice sessions. For simplicity we discretize
time into 16ms. segments and model each voice source as discrete time on/ooe source as de-ned
in Example 4.1. We assume that these sources are mutually independent and all identical, with
common transition matrix
The mean of on and ooe periods correspond to 352ms and 650 ms, respectively. The service rate of
the channel is taken to be which corresponds to each source generating data at a peak rate
of 32Kbs. Observe that there is no contention if the number of sources N is less than 49 and that
the system is unstable whenever N ? 134.
We ask ourselves the following question: what is the number of voice sessions that can be supported
by the channel such that P (X ? b) - q? Here X is the backlog (measured in ms. of data), b the
tolerable delay and q a tolerance. Let N max denote this number. The distribution bounds in (4.2)
and (2.25) can be used to obtain bounds on N max - namely
where
where for each  is the unique solution in (0; 1) of the equation
The coeOEcient C('   ) has been computed from (4.3) for various values of b, q and r. It is worth
noting that C(') has always been found smaller than 1, ranging from 1:03 10 \Gamma20 for 49 sources
to 0:9995 for 134 sources. The coeOEcient B has also been computed from (4.3) after substituting
imaxj for iminj and ' for '   .

Table

5 reports N lb and N ub as a function of the tolerable delay, b, for tolerances of 0:1%, 1% and
5%, Also included are the number of sessions N eb that can be supported based on the eoeective
bandwidth approach, namely, N eb
Proposition 4.1). We observe
that the quality of the bounds increases as b and/or q increase. In particular, the relative error
r e := (N ub \Gamma N lb )=N ub is such that r e - 0:25 for b - 20, r e - 0:2 for b - 50 and r e - 0:05 for
In addition, the eoeective bandwidth approach turns out to be very conservative for small
delay constraints (say, for b - 100) and lies between the bounds only for large b (b - 500). The fact
that the eoeective bandwidth yields conservative admission controls has been observed elsewhere as
well (see [35]) where enhancements have been proposed.
4.1.2 Call admission in a video server
We consider requests to a video server for movies. Sources are homogeneous, independent, and
behave as follows. Each source cycles between playback of a movie during which it requires 1
resource unit and pause during which it releases its resource. For simplicity, time is divided into
1/2 second (s) segments. Each source is modeled as a discrete time on/ooe source as in Example
4.1, with common transition matrix
The playback period has an average length of minutes and the pause period has average length
of 5 minutes. Last, we assume that the video server has 100 resource units. Hence it can handle a
minimum of 100 and a maximum of 116 viewers (stability condition).
We again consider the question - how many viewers can this system handle such that the start
of playback is not delayed beyond b time units with probability that exceeds q. Using the same
approach as with the voice application, we have determined upper (N ub ) and lower (N lb ) bounds
for N max for :5s - b - 60s for tolerances of 1, 5, and 10%. For the range given above, the bounds
obtained on N max do not depend on b and is presented in Table 6. Also included are the number
of sessions that can be supported as predicted by the eoeective bandwidth approach (N eb ). Observe
that the eoeective bandwidth approach yields the same number of sessions as can be supported
through a peak rate allocation.
Concluding Remarks
In this paper we have presented upper and lower bounds of an exponential form for the tail distribution
of both X n and of its stationary regime X, in the case where (X n ) n is de-ned by the
stochastic recursion (1.1). Applications to queues have been discussed and our bounds have been
numerically compared to other bounds and to the exact distribution. Last, we have provided an
application of our results in the setting of admission control. Our work has been lately extended in
several directions including more general stochastic recursions in the max-plus framework [48] and
more general admission control criteria related to the probability that k or more customers within a
group of n arrive to -nd the buoeer occupancy greater than some level, [49]. Also, it has been used
to derive upper and lower bounds on the tail distribution of the stationary backlog in a multiplexer
fed by independent and nonhomogeneous Markov on/ooe AEuid sources [4].

Acknowledgments

: The authors would like to thank Alain Jean-Marie for useful discussions
during the course of this work, and Zhi-Li Zhang for the numerical calculations in Section 4.1.1.
The authors are also very grateful to the reviewers for their comments - especially for pointing out
the generalization of the early results to Markov additive processes and for bringing [7] and [33] to
our attention.
eb 48 58 69 78 86 93 110 121 129 131
eb 48 63 78 90 98 103 117 125 130 132
eb 48 72 90 101 108 113 123 128 132 133

Table

5: Supportable number of voice sessions
eb 100 100 100

Table

Supportable numbers of video sessions
A Proofs of Lemma 2.1 and Corollary 2.1
Proof of Lemma 2.1: De-ne the set g. Observe that
G is a nonempty set thanks to the assumption that the set M (see (2.3)) is nonempty.
From the de-nition of B (see (2.26)) it is easily seen that
z k ('   )
z k ('   )
z k ('   )
(j;k)2M
z k ('   )
z k ('   )
where g kj
x exp('
On the other hand, we deduce from assumption (2.27) that when \Delta there exist constants
This observation readily implies that
z k ('   )
z k ('   )
z k ('   )
z k ('   )
e \Gamma'
z k ('   )
oe
0: (A.2)
Combining (A.1) and (A.2) yields B ? 0.
Proof of Corollary 2.1: Thanks to Lemma 2.1 it suOEces to show that - kj ? 0 when F jk (x) has
a polynomial-exponential density function for (k; since in this case \Delta kj = 1.
For all
a
be the density function of F kj (x), where a kj;i 's are nonzero real numbers, m kj;i 's are nonnegative
integers and fi kj;i 's are strictly positive real numbers. Assume without loss of generality that for
all
, and that if fi As
f kj (x) - 0 for all x ? 0, it is easy to see (by letting x go to in-nity) that a kj;1 ? 0 for all
It then follows that for all x - 0,
x
F kj (du)
x
a kj;i
x
a kj;i
x
e \Gammafi kj;i
x a kj;i m kj;i !
x l
e \Gammafi kj;i
x a kj;i m kj;i !
x l
Dividing both the numerator and the denominator in the r.h.s. of (A.3) by a kj;1 x m kj;1 e \Gammafi kj;1 x and
using the fact that the couple (fi kj;1 ; \Gammam kj;1 ) is the smallest in the lexicographic order among all
couples (fi kj;i ; \Gammam kj;i ), we obtain that
lim
where the strict positiveness is a consequence of the fact that together
with the de-nition of '   . The proof is thus completed.



--R

iThe Fourier-series Method for Inverting Transforms of Probability Dis- tributionsj
iAsymptotics for Steady-State Tail Probabilities in Structured Markov Queueing Modelsj
iStochastic Theory of a Data-Handling System with Multiple Sourcesj
iUpper and Lower Bounds for the Multiplexing of Multiclass Markovian On/Ooe Sourcesj

iStationary Distributions via First Passage Timesj.
iRisk Theory in a Periodic Environment: the Cramer-Lundberg Approximation and Lundberg's Inequalityj
Stochastic Processes in Queueing Theory
Siberian Advances in Mathematics
the Shape of the Loss Curve and Economies of Scale in Large Multiplexersj
iKronecker Products and Matrix Calculus in System Theoryj

iComputable Exponential Bounds for Intree Networks with Rout- ingj
iThe Application of Eoeective Bandwidth to Fast Simulation of Communication Networksj
iSqueezing the Most out of ATMj
iOn the Performance of an Eoeective Bandwidth For- mulaj
iBuoeer OverAEow Asymptotics for a Switch Handling Many TraOEc Sourcesj.
iA Calculus for Network Delay
iA Calculus for Network Delay
iScheduling Policies for an On-Demand Video Server with Batchingj
iDecoupling Bandwidth for Networksj
iExponential Bounds for Queues with Markovian Arrivalsj



iEoeective Bandwidth of General Markovian TraOEc Sources and Admission Control of High Speed Networksj
iFundamental Bounds and Approximations for ATM Multiplexers with Applications to Video Teleconferencingj
iA Scheme for Real-Time Channel Establishment in Wide-Area Networksj
iThe Markov-Modulated Poisson Process (MMPP) Cook- bookj


iEoeective Bandwidths for the Multi-Type UAS Channelj
iLogarithmic Asymptotics for Steady-State Tail Probabilities in a Single-Server Queuej
Kronecker Products and Matrix Calculus with Applications.

iA Markov Modulated Characterization of Packetized Voice and Data TraOEc and Related Statistical Multiplexer Performancej
Matrix Analysis.
iEoeective Bandwidth for Multiclass Markov Fluids and Other ATM Sourcesj


iUsing the LBL Network Whiteboardj
iEoeective Bandwidths at Multi-Class Queuesj
iEoeective Bandwidths for Multiclass Markov Fluids and Other ATM Sourcesj
iA Martingale Inequality in the Theory of Queuesj
iInequalities in the Theory of Queuesj
iOn Computing per-Session Performance Bounds in High-Speed Multi-Hop Computer Networksj
iOn a Generalization of Kingman's Boundsj.
iBounds on the Tail Distribution of Markov-Modulated Stochastic Max-Plus Systemsj
i Bounds on Finite Horizon QoS Metrics with Application to Call Admissionj
iThe Stability of a Queue with Non-Independent Inter-Arrival and Service Timesj
iThe transient BMAP/G/1 queue
iLocal allocation of end-to-end quality-of-service in high-speed networksj

iBuoeer OverAEow Probabilities for a Multiplexer with Self-Similar TraOEcj
Communications of the ACM
Smit, iThe Queue with Markov Modulated Arrival and Servicesj
iBounds on the Delay Distribution in GI
iVoice Communication Across the Internet: a Network Voice Terminal

Comparison Methods for Queues and Other Stochastic Models.
iTail Probabilities with Statistical Multiplexing and Eoeective Bandwidths in Multi-Class Queuesj
iPerformance and Stability of Communication Networks Via Robust Exponential Boundsj
--TR
Matrix analysis
Large deviations of uniformly recurrent Markov additive processes
The queue M/G/1 with Markov modulated arrivals and services
Effective bandwidths at multi-class queues
Effective bandwidths for the multi-type UAS channel
On computing per-session performance bounds in high-speed multi-hop computer networks
The Fourier-series method for inverting transforms of probability distributions
Effective bandwidth of general Markovian traffic sources and admission control of high speed networks
Performance and stability of communication networks via robust exponential bounds
The Internet and interactive television
Effective bandwidths for multiclass Markov fluids and other ATM sources
The Markov-modulated Poisson process (MMPP) cookbook
Risk theory in a periodic environment
Effective bandwidth and fast simulation of ATM intree networks
Diffusion based statistical call admission control in ATM
Upper and lower bounds for the multiplexing of multiclass Markovian on/off sources
Local Allocation of End-to-End Quality-of-Service in High-Speed Networks
Computable exponential bounds for intree networks with routing
Decoupling Bandwidths for Networks: A Decomposition Approach to

--CTR
N. Gautam , V. G. Kulkarni, Applications of SMP Bounds to Multi-class Traffic in High-speed Networks, Queueing Systems: Theory and Applications, v.36 n.4, p.351-379, December 2000
N. Gautam , V. G. Kulkarni , Z. Palmowski , T. Rolski, BOUNDS FOR FLUID MODELS DRIVEN BY SEMI-MARKOV INPUTS, Probability in the Engineering and Informational Sciences, v.13 n.4, p.429-475, October 1999
Zbigniew Palmowski, A Note on Bounds in the SMP Fluid Models, Queueing Systems: Theory and Applications, v.38 n.1, p.77-89, May 2001
markov additive process;call admission control;queues;markov chain;exponential bound;ergodicity;large deviation principle;matrix analysis;effective bandwidth;tail distribution