Application and evaluation of large deviation techniques for traffic engineering in broadband networks.
Accurate yet simple methods for traffic engineering are important for efficient dimensioning of broadband networks. The goal of this paper is to apply and evaluate large deviation techniques for traffic engineering. In particular, we employ the recently developed theory of effective bandwidths, where the effective bandwidth depends not only on the statistical characteristics of the traffic stream, but also on a link's operating point through two parameters, the space and time parameters, which are computed using the many sources asymptotic. We show that this effective bandwidth definition can accurately quantify resource usage. Furthermore, we estimate and interpret values of the space and time parameters for various mixes of real traffic demonstrating how these values can be used to clarify the effects on the link performance of the time scales of burstiness of the traffic input, of the link parameters (capacity and buffer), and of traffic control mechanisms, such as traffic shaping. Our approach relies on off-line analysis of traffic traces, the granularity of which is determined by the time parameter of the link, and our experiments involve a large set of MPEG-1 compressed video and Internet Wide Area Network (WAN) traces, as well as modeled voice traffic.
Introduction
The rapid progress and successful penetration of broadband
communications in recent years has led to important new
problems in traffic modeling and engineering. Among oth-
ers, call admission control and network dimensioning for
cases of guaranteed QoS (which is one of the most important
features supported by the ATM technology) have attracted
the attention of researchers. Successful approaches
are closely related to the ability of quantifying the usage
This work was supported in part by the European Commission
under ACTS project CASHMAN (AC-039).
y Also with the Dept. of Computer Science, University of Crete.
In Proc. of ACM SIGMETRICS '98/ PERFORMANCE
Joint International Conference on Measurement and
Modeling of Computer Systems, Madison, Wisconsin,
June 24-26, 1998.
of resources, on the basis of traffic modeling and measurements

For example, statistical analysis of traffic measurements
[11, 14, 7] has shown a self-similar or fractal behavior; such
traffic exhibits long range dependence or slowly decaying
autocorrelation. Although the implications of such long
range dependence is still an open issue (e.g., see [6, 8] and
the references therein), recent work [16, 8] has shown that
these implications can be of secondary importance to the
buffer overflow probability when the buffer size is small,
which applies to the case where real time communication is
supported. This example motivates the need for a methodology
to understand the impact of the various time scales of
the burstiness of real broadband traffic on the performance
of the network and on its resource sharing capabilities. In
particular, some basic questions for which the network engineer
must provide answers are the following: How much
does the cell loss probability decrease when the link capacity
or buffer size increases? How does traffic shaping 1 affect
the multiplexing capability of a link and the amount of resources
used by a bursty source? What is the necessary
granularity of traces in order to capture the information
that is important for performance analysis and network di-
mensioning? What are the effects of the composition of
the traffic mix on the multiplexing capability of a link?
Traditional queueing theory, which requires elaborate traffic
models, cannot be applied to answer such questions in
the context of large multi-service networks; for such cases
asymptotic methods are more appropriate. In this paper
we answer such questions by applying and evaluating the
many sources asymptotic and the effective bandwidth based
on this asymptotic, for real broadband traffic. This traffic
consists of MPEG-1 compressed video, Internet Wide Area
Network (WAN) traffic, and traffic resulting from modeled
voice.
Problems related to resource sharing have often been
analyzed using the notion of effective bandwidth, which is a
scalar summarizing resource usage depending on the statistical
properties and Quality of Service (QoS) requirements
of a source. Effective bandwidths are usually derived by
means of asymptotic analysis, which is concerned with how
the buffer overflow probability decays as some quantity in-
creases. If this quantity is the size of the buffer, we have the
large buffer asymptotic [5, 10]. If the buffer per source and
capacity per source are kept constant, and we are interested
Related work on how traffic smoothing affects the multiplexing
capability of a link can be found in [18] and the references therein.
in how the overflow probability decays as the size of the
system (the broadband link and the multiplexed sources)
increases, then we have the many sources asymptotic; this
asymptotic regime has been investigated in [4, 1, 17].
Effective bandwidth definitions based on the large buffer
asymptotic were found, in some cases, to be overly conservative
or too optimistic [2]. This occurs because the large
buffer asymptotic does not take into account the gain when
many independent sources are statistically multiplexed to-
gether. On the other hand, the effective bandwidth defined
according to the many sources asymptotic [9, 3] depends
not only on the statistical properties and Quality of Service
(QoS) requirements of a source, but also on the statistical
properties of the other traffic it is multiplexed with and
the parameters (capacity and buffer) of the multiplexing
link. Only recently [9, 3] has it been understood how to
incorporate such information into the definition of the effective
bandwidth. This work has shown that the effective
bandwidth of a source depends on the link's operating point
through two parameters, called the space and time parame-
ters, which in turn depend on the link parameters (capacity
and buffer) and the statistical properties of the multiplexed
traffic. These parameters can be computed using the many
sources asymptotic and, as we will demonstrate with real
broadband traffic, have important applications for traffic
engineering. Since the effective bandwidth gives the amount
of resources that must be reserved for that source in order
to satisfy its QoS requirements, it helps simplify problems
in traffic engineering and network dimensioning.
The rest of this paper is structured as follows. In Section
2 we review basic results from the theory of effective
bandwidths, as developed in [9], and the theory of many
sources asymptotics [4, 1, 17]. In Section 2.2 we discuss the
application of this framework to traffic engineering, giving
emphasis on the interpretation of the space and time
parameters. In Section 3 we present a detailed series of experiments
which aim to evaluate the accuracy of the above
framework for link capacities and buffer sizes anticipated for
broadband networks and for real broadband traffic which
consists of MPEG-1 compressed video and Internet WAN
traces, in addition to modeled voice traffic. Finally, Section
4 summarizes the results of the paper and identifies
areas for future research.
2 The Many Sources Asymptotic and its Implications
In this section we summarize the key results of the many
sources asymptotic and their implications for traffic engineering

2.1 Effective Bandwidths
Suppose the arrival process at a broadband link is the superposition
of independent sources of J types.
be the number of sources of type j, and let
(note that the n j s are not necessarily integers). This system
can be viewed as having N sources of the same type, where
a single source consists of a proportion of the J source types
and can be characterized by the vector n. The broadband
link has a shared buffer of size link capacity
Parameter N is the scaling parameter (size of the
system), and parameters b; c are the buffer and capacity
per source, respectively. We suppose that after taking into
account all economic factors (such as demand and com-
petition) the proportions of traffic of each of the J types
remains close to that given by the vector n, and we seek
to understand the relative usage of network resources that
should be attributed to each traffic type.
Furthermore, let X j [0; t] be the total load produced by
a source of type j in the time interval (0; t], which feeds the
above link. We assume that X j [0; t] has stationary incre-
ments. Then, the effective bandwidth of a source of type j
is defined as [9]
st log E
\Theta e sX j [0;t]
where s; t are system parameters which are defined by the
context of the source, i.e., the characteristics of the multiplexed
traffic, their QoS requirements, and the link resources
(capacity and buffer). Specifically, the time parameter
(measured in, e.g., milliseconds) corresponds to
the most probable duration of the busy period of the buffer
prior to overflow [4]. The space parameter s (measured
in, e.g., kb \Gamma1 ) corresponds to the degree of multiplexing
and depends, among others, on the size of the peak rate
of the multiplexed sources relative to the link capacity. In
particular, for link capacities much larger than the peak
rate of the multiplexed sources, s tends to zero and ff j (s; t)
approaches the mean rate of the source, while for link capacities
not much larger than the peak rate of the sources,
s is large and ff j (s; t) approaches the maximum value that
the random variable X j [0; t]=t can attain.
P(overflow) be the probability
that in an infinite buffer which multiplexes
sources and is served at rate C = Nc, the queue
length is above the threshold Nb. The following holds
for Q(Nc;Nb;Nn) [4]:
lim
log
sup
st
where I is called the asymptotic rate function. The last
equation is referred to as the many sources asymptotic, and
has been proved for continuous time in [1] and for a special
case in [17]. A similar asymptotic holds for the proportion
of workload lost through the overflow of a finite buffer of
size Nb. Due to equation (2), the overflow probability can
be written as which leads to the
following approximation when N is large:
The accuracy of the above approximation and, more im-
portantly, the achievable link utilization for MPEG-1 compressed
video and Internet WAN traffic is investigated in
Section 3.1.
Consider the QoS constraint on the overflow probability
to be P(overflow) - e \Gammafl , and assume
be a subset of Z J
such that
vice versa), i.e., the QoS constraint on the overflow probability
is met. Due to this property, A(N called
the acceptance region. The region A(N
to compute. However, for the scaled acceptance region, the
following holds [9]:
lim
where
s
st
Hence, the scaled acceptance region
can be approximated by
A.
If is on the boundary of the region A and
the boundary is differentiable at that point, then the tangent
plane determines the half-space [9]
s
where (s; t) is an extremizing pair in equation (2) and c   is
the "effective capacity" per source. The case for two source
types shown in Figure 1.
the scaled acceptance region
Approximation A of
A 3

Figure

1: Approximation A of the scaled acceptance region
three values of t in (4).
To the extent that A(N can be approximated
by NA, it follows from (5) that a point
can be taken to satisfy
s
where, as in (5), (s; t) is an extremizing pair in equation
(2), and C   is the "effective capacity" of the system at the
operating point (s; t).
The effective bandwidth ff j (s; t) provides a relative measure
of resource usage for a particular operating point of the
link, expressed through parameters s; t. For example, if a
source of type j1 has twice as much effective bandwidth as
a source of type j2 , then, for this particular operating point
of the link, one source of the first type can be substituted
by two sources of the second type, while still satisfying the
QoS constraint. The above measure of resource usage differs
from the ordinary measure that is usually reported (i.e.,
the mean rate), which corresponds to Note that the
QoS guarantees are encoded in the effective bandwidth definition
through the value of fl, which appears on the right
hand side of (6) and influences the form of the acceptance
region.
The asymptotics behind the above results assume only
stationarity of sources. Illustrative examples discussed in
[9] and [16] include periodic sources, fractional Brownian
input, policed and shaped sources, and deterministic multiplexing

Unlike the above definition of the effective bandwidth
which takes into account the effects of statistical multi-
plexing, the effective bandwidth based on the large buffer
asymptotic depends solely on the source's characteristics
and the QoS constraint. Specifically [5, 10], consider the
QoS constraint P(overflow) - e \GammaffiB , where B is the total
buffer. Then, the effective bandwidth based on the large
buffer asymptotic of a source of type j, and the corresponding
constraint is
s lim
\Theta e sX j [0;t]
Observe that (7) is a special case of (1) for t ! 1. Indeed,
equation (7) becomes accurate when the buffer of the system
is large, in which case the time parameter t becomes
large. However, for finite buffer sizes, equation (7) can lead
to significant underutilization or even overutilization of link
capacity [2]. The experiments in Section 3 include results
which compare the performance of the large buffer asymptotic
with that of the many sources asymptotic.
Using the Bahadur-Rao theorem, the authors of [12] extended
the proof of the many sources asymptotic in [4] to
show that as N !1, the following holds:
e \GammaN I
where (s; t) is an extremizing pair of (2) and oe 2 is given by
log
\Theta e sX j [0;t]
\Theta e sX j [0;t]
is the moment generating func-
tion. Based on (8), we have the following approximation:
We will refer to the above equation as the many sources
asymptotic approximation with the Bahadur-Rao improve-
ment. The term 1log(2-N oe 2 s 2 ) can be approximated by2
log(4-NI) [13]. Hence, equation (9) does not require any
additional computations compared to (3).
It can be seen with some algebra that the many sources
asymptotic with the Bahadur-Rao improvement (equation
gives the following effective bandwidth constraint in
the neighborhood of the extremizing pair (s; t) of (2)
s
where
2fl ). It is important to note
that the same formula for the effective bandwidth, given by
equation (1), is used in both (6) and (10). The Bahadur-
Rao improvement only affects (increases) the amount of effective
capacity C
while the parameters s; t are
computed using the same formula (2).
2.2 Implications to Traffic Engineering
In this subsection we discuss the interpretation of the space
s and time t parameters, and how they can be used for
traffic engineering.
For any traffic stream, the effective bandwidth ff j (s; t)
in (1) is a template that must be filled with the system operating
point parameters s; t in order to provide the correct
measure of effective usage by the stream for that particular
operating point. Although the operating point also
depends on the individual stream, for a large system, due
to heavy multiplexing, this dependence is ignored. Such an
engineering approach simplifies considerably the analysis
because there is no circle in the definitions of the effective
bandwidth and the operating point. Furthermore, as we
will see in Section 3.3, the values of s; t are, to a large ex-
tent, insensitive to small variations of the traffic mix. It
has been observed that in networks serving a large number
of sources, the traffic mix exhibits a strong cyclic behav-
ior. Hence, we can assign particular pairs (s; t) to periods
of the day during which the traffic mix remains relatively
constant. The values of s; t corresponding to a particular
period of the day can be computed off-line using the supinf
formula (2) and the effective bandwidth formula (1), where
the expectation in (1) is replaced by the empirical mean;
the latter can be computed from traffic traces taken during
that period of the day.
Recall that the time parameter t corresponds to the
most probable duration of the busy period prior to buffer
overflow. As we will discuss now, this parameter also identifies
the time scales that are important for buffer over-
flow. Assume that a link is operating at a particular operating
point, expressed through parameters s; t. In the
effective bandwidth formula (1) the statistical properties of
the source appear in X j [0; t], which is the amount of work-load
produced by the source in an interval of length t. If two
sources have the same distribution of X j [0; t] for this value
of t, then they will both have the same effective bandwidth.
A case of practical interest where this result can be applied
is traffic smoothing: To have an effect on the amount of
resources used by a source, traffic smoothing must be performed
on a time scale larger than t, since only then does
it affect the distribution of X j [0; t]. We will investigate this
with real broadband traffic in Section 3.3.
The time parameter t also indicates the granularity that
traffic traces must have 2 , since given a value for t it would
be sufficient to choose the granularity to be a few times
smaller than this value. Traditionally, the granularity of
traces was chosen in a rather ad-hoc manner.
By setting equal to the right hand
side of (2) and taking the derivative with respect to B and
C, we get the following expression for the space parameter
s and the product st [3]:
and st = @fl
Thus, the space parameter s equals the rate at which the
logarithm of the overflow probability decreases with the
buffer size, for fixed capacity C, whereas the product st
equals the rate at which the logarithm of the overflow probability
decreases with the link capacity, for fixed buffer B.
Here, by trace granularity we mean the time window in which
we measure the amount of load produced by a source.
3 Experiments with Real Traffic
In this section we apply and evaluate the traffic engineering
framework discussed in the preceding sections for real
broadband traffic. The specific issues we address are the
ffl Compare the overflow probability and link utilization
using the many sources asymptotic and its Bahadur-
Rao improvement to the actual cell loss probability
and the maximum utilization estimated using simula-
tion. (Section 3.1)
ffl Compare the values of parameters s; t computed by
theory to the values estimated using simulation. (Sec-
tion 3.2)
ffl Estimate and interpret typical values of parameters
s; t for real broadband traffic. (Section 3.2)
ffl Investigate how the values of s; t, and subsequently
the effective bandwidth, depend on the traffic mix.
(Section 3.3)
Our experiments involve MPEG-1 compressed video and
Internet WAN traces, as well as modeled voice traffic. The
sequences, made available 3 by O. Rose [15], have
been encoded using the UC Berkeley MPEG-1 software encoder
with the frame pattern IBBPBBPBBPBB. Each sequence
consisted of 40,000 frames (approximately
utes). For Internet Wide Area Network (WAN) traffic we
used the Bellcore Ethernet trace BC-Oct89Ext which has
been made available 4 by W. Leland and D. Wilson [11].
The trace had duration 122797.83 seconds. For voice traffic
we use an on-off Markov modulated fluid model with peak
rate 64 Kbps and average time spent in the "on" and "off "
states 352 msec and 650 msec, respectively. Finally, we consider
link capacities 34 Mbps, 155 Mbps, and 622 Mbps,
and buffers introducing delay of up to 50 msec for MPEG-1
traffic, and up to 150 msec for Internet WAN traffic.
3.1 Overflow Probability and Link Utilization
In this section we compare the overflow probability and
link utilization using the many sources asymptotic and its
Bahadur-Rao improvement with the actual cell loss probability
and the maximum utilization estimated using simu-
lation. We also derive a simple heuristic for computing the
actual cell loss probability from the overflow probability.
3.1.1 Overflow probability

Figure

compares, for a fixed number of sources, the overflow
probability estimated using the many sources asymptotic
and its Bahadur-Rao improvement with the cell loss
probability and frame overflow probability estimated using
simulation; the latter is the probability that at least one
cell of a frame is lost. Both the cell loss probability and the
frame overflow probability are measured using a discrete
time simulation model with an epoch equal to one frame
In these and subsequent simulations,
we report the average from a total of 80 independent simulation
runs, each with a random selection of the starting
frame for every source (we assume that frame boundaries
are aligned). Each simulation run had duration 5 times the
3 Available at http://ftp-info3.informatik.uni-wuerzburg.de/pub/
4 Available at The Internet Traffic Archive,
size of the trace. Both the number of runs and the duration
of each run were chosen empirically.
For each method, the base-10 logarithm of the overflow
probability is plotted against the buffer size (measured in
milliseconds), while the link utilization remains the same.
In

Figure

2, first observe that for small buffer sizes there
is a relatively fast decrease of the overflow probability as
the buffer size increases. However, this stops to occur after
some buffer size (e.g., 5 \Gamma 8 msec for a 155 Mbps link). Further
increase of the buffer has a smaller effect on the overflow
probability. Furthermore, the logarithm of the overflow
probability in both of these regimes is almost linear with
the buffer size.
Second, observe that although the many sources asymptotic
overestimates the Cell Loss Probability (CLP) by approximately
2-3 orders of magnitude, it qualitatively tracks
its shape very well. The Bahadur-Rao improvement overestimates
the CLP by 1-2 orders of magnitude. On the other
hand, the large buffer asymptotic, in addition to overestimating
the CLP by many orders of magnitude, also fails to
track its shape.
The actual cell loss probability differs from the overflow
probability estimated using the many sources asymptotic
and its Bahadur-Rao improvement because the latter is not
a measure of the CLP, but a measure of the probability that
in an infinite buffer the queue length becomes greater than
B. This probability is closer in spirit to the frame overflow
probability, i.e., the probability that at least one cell of
a frame is lost. Indeed, as Figure 2 shows, the overflow
probability estimated using the many sources asymptotic
with the Bahadur-Rao improvement is very close to the
frame overflow probability. 5
To further explain the above, we derive a simple expression
for the cell loss probability in terms of the frame
overflow probability L f . If one observes a large number of
frames, say M , the average number of frames in which we
have at least one lost cell is ML f . Let x be the average
number of cells that are lost when a frame overflow occurs.
Then the average number of cells that are lost in M frames
is ML f x. Since there is a total of MF cells in these frames,
where F is the average number of cells in a frame, we can
approximate the cell loss probability with the percentage of
lost cells, namely
From the last equation we see that the cell loss probability
differs from the frame overflow probability by a correction
We assume that when an overflow
occurs only a few cells are lost. This is expected for small
loss probabilities, since the probability of loosing cells in a
buffer of size B+ ffl is exponentially harder than loosing cells
in a buffer of size B. In particular, we will assume that only
one cell is lost, hence Lc - 1=F , and since the average number
of cells in one frame is 25 we get Lc -
This heuristic agrees with the difference between the frame
overflow probability and the cell loss probability shown in

Figure

2.

Figure

3 shows the cell loss probability estimated using
(12), where . Observe that the cell loss probability
using this heuristic matches the cell loss probability
estimated using simulation extremely well.
5 This is the case only when the simulation epoch equals the frame
time.
3.1.2 Link utilization
Nm=C be the link utilization, where N is the
number of sources, m is the mean rate, and C is the link
capacity. Figure 4 compares, for a range of buffer sizes
and for overflow probability 10 \Gamma6 , the link utilization using
the many sources asymptotic and its Bahadur-Rao improvement
with the maximum achievable utilization (estimated
using simulation). The utilization is computed by increasing
the number of multiplexed sources in order to find the
maximum number such that the overflow probability (3),
computed using (1) and (2), is less than the target overflow
Similar to our observations regarding the overflow prob-
ability, there are significant gains in increasing the size of
the buffer up to a certain value. Increasing the buffer size
above this value has a very small effect on the link utilization

Recall that the many sources asymptotic overestimated
the CLP by 2-3 orders of magnitude. However, as Table 1
shows, it performs much better in estimating the maximum
utilization. In particular, for
1 msec, the many sources asymptotic achieves a utilization
which is approximately 79% of the maximum utilization.
The Bahadur-Rao improvement increases this percentage
to 88%. Furthermore, this percentage increases for larger
link capacities; e.g., for
the many sources asymptotic achieves a utilization which
is 90% of the maximum (Table 1(b)). Of course, as Figure
5 shows, using the heuristic based on (12), we achieve a
utilization which almost coincides with the maximum utilization

Buffer Utilization %
msec (cells) Simulation MSA MSA
(a)
Buffer Utilization %
msec (cells) Simulation MSA MSA

Table

1: Link utilization: theory vs. simulation for
Star Wars traffic. The parenthesis contain the percentage
of the maximum utilization (second column). MSA: Many
Sources Asymptotic, B-R: Bahadur-Rao. [ P(overflow) -
Finally, Figure 6 shows the link utilization in the case
of Internet WAN traffic. Observe that while for Star Wars
traffic the gains of increasing the buffer decrease abruptly,
for Internet WAN traffic the gains of increasing the buffer
decrease smoother as the buffer size increases. This indicates
that there are more time scales in Internet traffic
which, for different buffer sizes, become important for buffer
overflow.
3.2 Space and Time Parameters
The space s and time t parameters characterize a link's
operating point and depend on the characteristics of the
multiplexed traffic. In this section we compare the values
of these parameters computed using the supinf formula
(2) to the corresponding values estimated using simulation.
Furthermore, we compute and interpret typical values of
these parameters, demonstrating how they can be used for
traffic engineering.
3.2.1 Space and time parameters: theory vs. simulation
Recall from our discussion in Section 2.2 that the space
parameter s equals the rate at which the logarithm of the
overflow probability decreases with the buffer size, equation
(11). Motivated by this equation, we can estimate s using
the following ratio of differences:
sim is the cell loss probability
estimated using simulation. Figure 7(a) shows that
the value of parameter s computed using the supinf formula
(2) is in good agreement with the value computed using
(13). Note that the "steps" in the value computed using
the supinf formula are expected since the many sources
asymptotic (and large deviations theory in general) captures
only the most likely way overflow can occur. On the
other hand, the curve labeled "simulation" in Figure 7(a)
represents an average over all the events that contribute to
overflow.
Recall from our discussion in Section 2.1 that the time
parameter t can be interpreted as the most probable duration
of the busy period prior to buffer overflow. Figure
7(b) compares the value of parameter t computed using
the supinf formula to the average value of the busy period
prior to buffer overflow. As was the case for parameter s,
the agreement between the two curves is good.
3.2.2 Typical values and interpretation of the space and
time parameters
Next we investigate how parameters s; t and the product
st depend on the link capacity and buffer size. The values
of s; t are computed using the supinf formula for a target

Figure

8 shows the values of parameter s as a function of
the buffer size, for various link capacities (Figure 8(a)) and
for various video contents (Figure 8(b)). In Figure 8(a), the
explanation of the steep decrease of the value of s is similar
to the explanation of the knee of the curves in Figures 2
and 4. Specifically, according to equation (11), s equals
the rate at which the logarithm of the cell loss probability
decreases (i.e., the quality of service improves), when the
buffer size increases. Up to some value, the buffer is used
to smooth the fast time scales of the multiplexed traffic.
Thus, increasing the buffer has a large affect on the overflow
probability, and the value of s is high. Once the fast
time scales have been smoothed, the slow time scales govern
the buffer overflow. Thus, increasing the buffer has a very
small effect on the overflow probability, and the value of s is
small. Also, observe in Figure 8(a) that the steep decrease
of the value of s occurs for smaller buffer sizes (measured
in milliseconds) as the link capacity increases. Finally, see

Figure

8(b), similar behavior is observed for MPEG-1 traffic
with various contents. This indicates that the dependence
of s on the link capacity and buffer size is related to the
frame structure.
The dependence of parameter t on the buffer size is
shown in Figure 9(a). Observe that the steep increase of its
value occurs for the same buffer size for which the increase
of the value of s occurs (Figure 8(a)). The small values of
t correspond to the regime where the fast time scales are
important for buffer overflow, whereas the large values of
t correspond to the regime where the slow time scales are
important for buffer overflow.
The product st, for different buffer sizes, is shown in

Figure

9(b). Once again we observe a steep increase of its
value, occurring at the same buffer sizes where the changes
in the values of s and t occur. However, the explanation
for the increase of the value of st is more subtle than the
explanation for the behavior of s; t. Recall from our discussion
in Section 2.2 that the product st equals the rate at
which the logarithm of the overflow probability decreases
with the link capacity, while the buffer size remains the
same; see equation (11). Comparing Figure 9(a) with Figure
9(b), we observe that the larger values of st correspond
to larger values of t. Larger values of t result in an averaging
effect in the amount of load X j [0; t] that appears in the
effective bandwidth formula (1). Hence, for the overflow
phenomenon, the traffic appears smoother. But for a link
which multiplexes smooth traffic and is operating with a
cell loss probability greater than zero, a change of the link
capacity has a greater effect on the overflow probability
compared to a link which multiplexes more bursty traffic.
This gives the intuition of why the value of st increases.

Figure

compares the values of s; t for Star Wars and
voice traffic. Figure 10(a) shows that as the buffer size in-
creases, the value of s for voice traffic decreases smoothly.
Furthermore, the rate of decrease is smaller for larger buffer
sizes. Comparing the value of s for MPEG-1 and voice traf-
fic, we conclude that for buffer sizes up to 2 msec and above
increasing the buffer has a larger effect for a net-work
carrying voice traffic compared to a network carrying
MPEG-1 traffic. This provides an example of how the space
parameter s can be used for buffer dimensioning.

Figure

10(b) shows that for voice traffic the time parameter
increases almost linearly with the buffer size. This
can be explained since for a high degree of multiplexing,
voice sources (which are modeled as on-off Markov fluids)
behave as Gaussian sources. For such sources, it can be
shown [4] that the time parameter t increases linearly with
the buffer size.

Figure

11(a) compares the value of parameter s for Star
Wars and Internet WAN traffic. For MPEG-1 traffic, the
values of s form two distinct regimes, where s is almost
constant, corresponding to the two distinct time scales that
are important for buffer overflow. On the other hand, for
Internet traffic, the values of s form more than two regimes,
indicating that for such traffic there are more time scales
which, for different buffer sizes, become important for buffer
overflow. Recall that this is also the reason behind the
smoother dependence of the link utilization on the buffer
size for Internet WAN traffic compared to Star Wars traffic

Figure

6). Finally, Figure 11(b) shows that parameter
s can take different values for different Internet traffic
segments, illustrating that different segments have different
statistical properties.
3.3 Effects of the Traffic Mix
As discussed in Section 2.1, periods of the day during which
the traffic mix remains relatively constant can be characterized
by corresponding pairs of (s; t). In this section we
investigate the dependence of these parameters, hence of
the effective bandwidth, on the traffic mix. The traffic mix
we consider consists of traffic of different types (MPEG-1
compressed video and voice), traffic with the same structure
but different contents (MPEG-1 compressed video with different
contents), and smoothed/unsmoothed traffic of the
same type and content.
3.3.1 Traffic mix containing Star Wars and voice traffic
We first consider the traffic mix containing Star Wars and
voice traffic. The horizontal axis in Figures 12(a) and 12(b)
depicts the percentage of voice connections, each containing
individual voice channels. The vertical axis of the above
figures depicts the effective bandwidth of the Star Wars
traffic stream. Observe that (1) the effective bandwidth, to
a large extent, changes slowly with the traffic mix, (2) the
dependence of the effective bandwidth on the traffic mix
is smaller for larger capacities and larger buffer sizes, and
(3) there are cases where increasing the percentage of voice
connections leads to a sharp decrease of the value of the
effective bandwidth.
The first observation supports the argument that pairs
of (s; t) can be assigned to periods of the day during which
the traffic mix remains relatively constant. However, the
third observation says that there are percentages of the
traffic mix where the effective bandwidth exhibits sharp
changes. If the link's operating point is close to such a
percentage, then we can estimate the average amount of
resources used by a source as a linear combination of the
effective bandwidth to the left and to the right of the sharp
change. The coefficients of the linear combination would be
determined by the percentage of the time the network was
operating on the left and on the right of the change.
The sharp decrease in the value of the effective band-width
identified above is due to the change of the time scale
that is important for buffer overflow. In particular, as indicated
above the curve for capacity 155 Mbps and buffer
size 4 msec in Figure 12(a), the time parameter t increases
finally 7 frames) for the same percentage
of voice connection at which the sharp decrease in
the value of the effective bandwidth occurs. The increase
of t produces an averaging effect (also discussed in Section
3.2.2) in the amount of workload X j [0; t] that appears
in the effective bandwidth formula (1); this averaging effect
results in a smaller effective bandwidth.
3.3.2 Traffic mix containing MPEG-1 traffic with different
contents
Up to now we investigated the case where the traffic mix
contains traffic of different nature. Next we investigate the
case where the traffic mix contains MPEG-1 video traffic
with the same encoding parameters but with different contents

Figures

13(a) and 13(b) show the effective bandwidth
of the Star Wars stream as a function of the percentage of
news and talk show streams, respectively. These figures
show that the content has a very small effect on the effective
bandwidth; this also implies that parameters s; t are
affected very little.
3.3.3 Traffic mix containing smoothed and unsmoothed
Star Wars traffic
Our final investigation deals with another important question
in traffic engineering: How does traffic smoothing affect
the network's operating point and the amount of resources
used by a source? We will see that parameter t shows the
time scale at which smoothing must be performed
in order for it to affect resource usage. Figure 14 shows
the effective bandwidth of the Star Wars stream for different
percentages of a traffic mix which consists of unsmoothed
and smoothed Star Wars traffic; the latter is
created by evenly spacing the cells belonging to two consecutive
frames. First, observe that the effects of the traffic
mix on the effective bandwidth decreases when the link capacity
and buffer size increases. Second, observe that there
are cases where increasing the buffer size has a very small
effect on the effective bandwidth, e.g., at
the curves for practically co-
incide. Third, observe that for some buffer sizes, smoothing
has no effect on the effective bandwidth (and on the net-
work's operating point), e.g., in Figure 14(a) the curve for
and in Figure 14(b) the
curves for are
flat. We explain this behavior next.

Figure

15 shows the effective bandwidth for both the
smoothed and the unsmoothed Star Wars stream. When
the percentage of smoothed traffic is small, the time parameter
smaller than the time interval
over which smoothing was performed (80 msec). For this
reason, the amount of workload X j [0; t] that appears in the
effective bandwidth formula (1) is smaller for the smoothed
stream than it is for the unsmoothed stream. Hence, the
effective bandwidth of the smoothed stream is smaller than
the effective bandwidth of the unsmoothed stream. For
some percentage of smoothed traffic (- 60%), the time parameter
t (= 80 msec) is no longer smaller than the time
interval over which smoothing is performed (80 msec). Because
of this, the amount of workload X j [0; t] is the same
for both the smoothed and the unsmoothed stream. Hence,
the effective bandwidth of both streams is the same.
Conclusions
In this paper we employ the recently developed theory of
effective bandwidths, and in particular the one based on the
many sources asymptotic, whereby the effective bandwidth
depends not only on the statistical characteristics of the
traffic stream, but also on a link's operating point. The
latter is summarized in two parameters: the space and time
parameters.
We have investigated the accuracy of the above frame-
work, and how it can provide important insight to the complex
phenomena that occur at a broadband link with a high
degree of multiplexing. In particular, we estimate and interpret
values of the space and time parameters for various
mixes of real traffic, demonstrating how these can be used to
clarify the effects on the link performance of the time scales
of burstiness of the traffic input, of the link parameters (ca-
pacity and buffer), and of traffic control mechanisms, such
as traffic smoothing.
Our approach is based on the off-line analysis of traffic
traces, the granularity of which can be determined by the
time parameter of the system. For the traffic mixes consid-
ered, the space and time parameters are, to a large extent,
insensitive to small variations of the traffic mix. This indicates
that particular pairs of these parameters can characterize
periods of the day during which the traffic mix
remains relatively constant. The above result has important
implications to charging, since simple charging schemes
which are linear in time and volume and have important incentive
properties can be created from tangents to bounds
of the effective bandwidth [3]. Furthermore, the above result
opens up some new possibilities for traffic modeling.
Rather than developing general models that try to emulate
real traffic in any operating environment, a new approach
would be to develop models that emulate real traffic according
to the particular operating point of the network. Such
models would be parameterized with the pair (s; t), would
be simple and efficient to implement, and can be the basis
for fast and flexible traffic generators.
The application of our approach for traffic engineering
and network dimensioning in a real multi-service network
environment that involves a large number of different source
types constitutes a promising area for further research. A
specific question is to investigate whether the number of
discontinuities of the time parameter, that we have identified
for a traffic mix containing two source types, increases
with the number of source types. A second area for further
work is to extend our investigations to links with priorities;
some results in this area are presented in [9].

Acknowledgements

The authors are particularly grateful to Frank P. Kelly for
his helpful discussions and insights, and thank the anonymous
reviewers for their constructive comments.



--R

Large deviations
On the effectiveness of effective bandwidths for admission control in ATM networks.

Buffer overflow asymptotics for a switch handling many traffic sources.
Effective bandwidth of general Markovian traffic sources and admission control of high speed networks.
Experimental queueing analysis with long-range dependent packet traf- fic

On the relevance of long-range dependence in network traffic
Notes on effective bandwidths.
Effective bandwidths for multiclass Markov fluids and other ATM sources.
On the self-similar nature of ethernet traffic
Cell loss asymptotics for buffers fed with a large number of independent stationary sources.
de Veciana.

Statistical properties of MPEG video traffic and their impact on traffic modeling in ATM systems.
The importance of the long-range dependence of VBR video traffic in ATM traffic engineering: Myths and realities
Large deviations approximations for fluid queues fed by a large number of on/off sources.
Smoothing, statistical multiplexing and call admission control for stored video.
--TR
Effective bandwidth of general Markovian traffic sources and admission control of high speed networks
On the self-similar nature of Ethernet traffic
Effective bandwidths for multiclass Markov fluids and other ATM sources
Analysis, modeling and generation of self-similar VBR video traffic
area traffic
Experimental queueing analysis with long-range dependent packet traffic
The importance of long-range dependence of VBR video traffic in ATM traffic engineering
On the relevance of long-range dependence in network traffic

--CTR
A. Courcoubetis , Antonis Dimakis , George D. Stamoulis, Traffic equivalence and substitution in a multiplexer with applications to dynamic available capacity estimation, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
C. Courcoubetis , V. A. Siris , G. D. Stamoulis, Network control and usage-based charging: is charging for volume adequate?, Proceedings of the first international conference on Information and computation economies, p.77-82, October 25-28, 1998, Charleston, South Carolina, United States
Jun Jiang , Symeon Papavassiliou, Providing End-to-End Quality of Service with Optimal Least Weight Routing in Next-Generation Multiservice High-Speed Networks, Journal of Network and Systems Management, v.10 n.3, p.281-308, September 2002
broadband networks;large deviations;effective bandwidths;traffic engineering;ATM