On the propagation of long-range dependence in the Internet.
This paper analyzes how TCP congestion control can propagate self-similarity between distant areas of the Internet. This property of TCP is due to its congestion control algorithm, which adapts to self-similar fluctuations on several timescales. The mechanisms and limitations of this propagation are investigated, and it is demonstrated that if a TCP connection shares a bottleneck link with a self-similar background traffic flow, it propagates the correlation structure of the background traffic flow above a characteristic timescale. The cut-off timescale depends on the end-to-end path properties, e.g., round-trip time and average window size. It is also demonstrated that even short TCP connections can propagate long-range correlations effectively. Our analysis reveals that if congestion periods in a connection's hops are long-range dependent, then the end-user perceived end-to-end traffic is also long-range dependent and it is characterized by the largest Hurst exponent. Furthermore, it is shown that self-similarity of one TCP stream can be passed on to other TCP streams that it is multiplexed with. These mechanisms complement the widespread scaling phenomena reported in a number of recent papers. Our arguments are supported with a combination of analytic techniques, simulations and statistical analyses of real Internet traffic measurements.
INTRODUCTION
Statistical self-similarity and long-range dependence are important
topics of recent research studies. Both phenomena
are related to certain scale-independent statistical proper-
ties. Statistical self-similarity can be detected when trafc
rate
uctuates on several timescales and its distribution
scales with the level of aggregation. Long-range dependence
means that the correlation decays slower than in traditional
tra-c models (e.g., Markovian), i.e., it decays hyperboli-
cally. A number of authors have argued that self-similarity
in data networks can be induced by higher layer protocols
[4] [5] [19] [21] [23] [24]. In this paper we do not discuss
the roots of self-similarity, instead, we demonstrate how the
induced self-similarity is propagated and spread in the net-work
by lower layer adaptive protocols, in particular, by
TCP, which represents the dominant transport protocol of
the Internet.
The phenomenon of self-similarity was observed in data networks
in [11] [12], followed by several experimental papers
showing fractal characteristics in other types of networks
and tra-c, e.g., in video tra-c [2] [9] or in ATM networks
[15]. A comprehensive bibliographical guide is presented in
[25]. These observations have seriously questioned the validity
of previous short memory models when applied to net-work
performance analysis [19]. The impact of self-similar
models on queuing performance has been investigated in a
number of papers [3] [6] [16].
Considerable eort has been made to explore the causes
of this phenomenon. In [4] the authors argue that self-similarity
is induced by the heavy-tailed distribution of le
sizes found in Web tra-c. In [24] Ethernet LAN tra-c was
modeled as a superposition of independent On/O processes
with On and O periods having heavy-tailed distributions.
An important related theoretical result [21] proves that the
superposition of a large number of such independent alternating
On/O processes converges to Fractional Gaussian
Noise.
To prove the validity of this model in TCP/IP networks,
several papers have investigated the connection between application
level le sizes, user think-times, and the On/O
model. As there are several layers between the application
and the link layer, it is of primary importance to investigate
how protocols convert and transfer heavy-tails through
the protocol stack down to lower layers. The eect of TCP
and UDP transport protocols are investigated in [7] [17] [18]
and it is found that TCP preserves long-range dependence
(LRD) from application to link-layer.
Based on this result, the authors of [7] and [8] argue that
transport mechanisms aect strongly the short timescale behavior
of tra-c, but they have no impact in large timescales.
In this paper we demonstrate that this statement is valid
only for the local behavior of TCP when only the tra-c of a
single link is investigated. In contrast, in the network case
a surprisingly complex mechanism is present.
TCP uses an end-to-end congestion control algorithm to
continuously adapt its rate to actual network conditions.
If network conditions are governed by large timescale
uc-
tuations, then TCP will \sense" this and react accordingly.
This paper shows that TCP adapts to tra-c rate
uctua-
tions on several timescales e-ciently. Moreover, we demonstrate
that TCP can be modeled as a linear system above
a characteristic timescale of a few round-trip times, which
implies that the correlation structure of a background tra-c
stream is taken over faithfully by an adaptive TCP
ow. In
particular, it is shown that TCP can inherit self-similarity
from a self-similar background tra-c stream. Since TCP has
an end-to-end control, while adapting to these
uctuations,
it propagates self-similarity encountered on its path all along
from the source to the destination host.
We also demonstrate that if a TCP stream is multiplexed
with another one, it can pass on self-similar scaling to the
other TCP stream, depending on network conditions. In
our model the network is regarded as a mesh of end-to-end
adaptive streams. Intertwined TCP streams can spread self-similarity
throughout the network contributing to global
scaling. By analyzing the eects from a network point of
view we argue that, on one hand, TCP plays an important
role in balancing and propagating global scaling. On
the other hand, it keeps local scaling intact where it is already
strong. This way we complement results reported in
[7]. The main purpose of this paper is to analyze the basic
mechanisms behind these phenomena.
To clarify our terminology, we brie
y summarize the definition
of a few basic concepts.
be a weakly stationary process representing the amount of
data transmitted in consecutive short time periods. Let
aggregated
process. X is called exactly self-similar with self-similarity
parameter H if Xk d
k and the equality
is in the sense of nite-dimensional distributions. In the
case of second-order self-similarity, X and m 1 H X (m) have
the same variance and autocorrelation. Second-order self-similarity
manifests itself in several equivalent ways, one of
them is that the spectral density of the process decays as
1 2H at the origin as f ! 0.
Throughout the paper we use the term \self-similarity" to
refer to scaling of second-order properties over some specic
timescales or asymptotically in large timescales, which is
equivalent to long-range dependence if H > 0:5 [14] [22].
We note that certain statements of the paper are also valid
in the sense of exact statistical self-similarity.
The ns-2 simulator 1 was used for the network simulations.
Several variants of TCP were investigated (Tahoe, Reno,
however, we found that the conclusions are invariant
to the TCP version.
The paper is organized as follows. A TCP measurement
is analyzed showing self-similar scaling for the tra-c of a
single long TCP connection, and a possible explanation is
presented based on a few simple assumptions in Section 2.
Section 3 investigates how TCP adapts to
uctuations on
dierent timescales, and it is shown that TCP in a bottleneck
buer can be modeled as a linear system above a
characteristic timescale of a few round-trip times. In Section
4 we investigate how an aggregate of TCP sessions with
durations of heavy-tailed and light-tailed distributions propagates
self-similarity of a background tra-c stream. Finally,
in Section 5, we present results about the spreading of self-similarity
in the network case when TCP has to pass multiple
hops and compete for resources with other TCP streams.
2. ADAPTIVITYOFTCP:APOSSIBLECAUSE
OF WIDESPREAD SELF-SIMILARITY
We carried out the following experiment. A large le was
downloaded (a tra-c trace le from the Internet Tra-c
Archive) from an FTP server (ita.ee.lbl.gov) to a client host
hops away in Hungary (serv1.ericsson.co.hu), passing
several backbone providers and even a trans-Atlantic link.
At the client side there was no other tra-c present. The
client was directly connected to an ISP by a 128 kbps leased
line. All packets were captured at the client side with the
utility 2 . The amount of bytes received was 50 Mbyte
and it was logged with a resolution of 50 ms during the le
transfer for 6900 s. The average throughput, which takes
into account the retransmissions and the TCP/IP overhead,
was about 58 kbps, i.e., some congestion were experienced
in the network. The average round-trip delay between the
server and the client was 208 ms. From the packet trace we
concluded that the version of the TCP was Reno.
Tests were performed for the presence of self-similarity. Here
we present three tests, the rst and second ones are based
on the scaling of the absolute moments (also called absolute
mean and variance-time plots [20]), and the third one is a
wavelet-based analysis [1], see Figure 1. The result of the
tests suggests asymptotic self-similarity with Hurst parameter
around 0:75.
During the experiment, there was only one connection active
on the link, so explanations based on the superposition
of heavy-tailed On/O processes or chaotic behavior [23]
are not applicable. However, the investigated TCP connection
traversed several backbone links where, due to the large
tra-c aggregations, self-similarity could arise either because
of heavy-tails or chaotic competition. Presumably, whatever
the reason for self-similarity was, the TCP connection
ns (version 2)
http://www-mash.CS.Berkeley.EDU/ns
2 Tcpdump is available at http://www-nrg.ee.lbl.gov/
log10(m)4.55.5
log10(Absval)
log10(m)9.011.0log10(Var)
Octave
Logscale Diagram

Figure

1: Scaling analysis of the tra-c generated by
a le transfer logged at the client side. a) Absolute
mean method H  0:76. b) Variance-time plot H
0:77. c) Wavelet analysis H  0:74 [0.738, 0.749].
Bottleneck buffer
Host A
LRD traffic
Host B
bottleneck
Network before
bottleneck
Network after
Router R
LRD
LRD

Figure

2: Network model
adapted to the background tra-c stream at the bottleneck
link, and the eect of the adaptation was that self-similarity
was propagated to the measurement point. Next a simple
analytic model is introduced supporting this argument.
All relevant components of the simplied network model are
depicted in Figure 2. A single greedy TCP connection sends
data between host A and host B. The path of the connection
consists of three parts: a network cloud before and after
router R and a bottleneck buer in router R, where the connection
has to share service capacity and buer space with
a self-similar background tra-c
ow. Self-similarity of the
background tra-c can be induced, for example, by large aggregations
of innite variance On/O streams as suggested
in [4]. In the analytic model it is assumed that TCP can
adapt ideally to a background tra-c stream in a bottleneck
buer. Under \ideal adaptivity" we mean that the TCP
connection is able to consume all remaining capacity unused
by the background tra-c stream. It is also assumed
that the TCP connection does not have any eect on the
background tra-c. The generality of this assumption covers
several practical cases, for example, if the background
ow is a large aggregate consisting of a large number of con-
nections. The limits of these assumptions are analyzed later
in the paper.
Denote the background tra-c rate by B(t), 0  B(t)  C,
where C is the service rate of the bottleneck buer in bit
per seconds. If TCP congestion control is \ideal" and its
eect on the background tra-c is neglected, then the TCP
connection will utilize all unused service in the bottleneck.
The rate of the \ideal" TCP
ow is denoted by A(t):
The resulting process is simply a shifted and inverted version
of B(t), which implies that the correlation structure of
processes A(t) and B(t) are the same. In other words, TCP
\inherits" the statistical properties of the background pro-
cess. In particular, let us model the background tra-c rate
as Fractional Gaussian Noise
aNH (t) (1)
where m is the average rate in bit per seconds [bps], a is the
variance, and NH (t) is a normalized FGN process with Hurst
parameter H. Note that FGN is a discrete time process, so
the rate at time t is approximated by the amount of bytes
sent during su-ciently small constant duration time periods.
Based on the arguments above, the adapting TCP will also
be an FGN with the same statistical self-similarity exponent
H. As TCP congestion control works end-to-end, the same
tra-c rate can be measured along the path before and after
router R as well. This implies that TCP propagates self-similarity
or LRD to parts of the network where otherwise
it would not be present.
The result above is based on a simple scenario using a few as-
sumptions, such as ideal TCP adaptivity, single bottleneck,
and assuming that the TCP
ow does not modify the background
tra-c characteristics. However, if the implications
of this simple scenario are valid in real TCP/IP networks,
the consequences for tra-c engineering are far reaching. Regarding
this, we are going to address the following important
questions:
1. What are the limitations of TCP adaptation, i.e., how
\ideal" is TCP congestion control when propagating
self-similarity or other statistical properties?
2. A single long-living connection was used in the simple
network model and in the measurement. Can self-similarity
be propagated by short duration TCP connections

3. The background LRD tra-c
ow used was non-adaptive.
Is self-similarity still propagated if the background traf-
ow is an aggregate of adaptive
4. We considered a single bottleneck on the TCP path.
On the other hand, in most cases TCP connections
traverse multiple routers and buers multiplexing with
multiple self-similar inputs. What are the characteristics
of the end-to-end TCP
ow in this case?
5. Is self-similarity propagated between adaptive connec-
tions, i.e., can self-similarity be inherited from one
TCP to another one that has no direct contact with
the source of self-similarity?
3. TCP AS A LINEAR SYSTEM
In the previous section it was assumed that TCP congestion
control is \ideal", which, as a matter of course, cannot be
the case in real networks. The consequence of self-similarity
is that
uctuations are not limited to a certain timescale.
When analyzing how \real" TCPs propagate self-similarity,
the adaptation of TCP to
uctuations on several timescales
should be investigated. In this section it is shown that TCP
in a bottleneck buer can be modeled as a linear system, i.e.,
takes over the correlation structure of the background
tra-c through a linear function.
TCP is an adaptive mechanism, which tries to utilize all free
resources on its path. Adaptation is performed as a complex
control loop called the congestion control algorithm.
Of course, full adaptation is not possible, as the network
does not provide prompt and explicit information about the
amount of free resources. TCP itself must test the path
continuously by increasing its sending rate gradually until
congestion is detected, signaled by a packet loss, and then it
adjusts its internal state variables accordingly. Using this al-
gorithm, TCP congestion control is able to roughly estimate
the optimal load in a few round trip times. Since congestion
control was introduced in the Internet [10], it has proved its
e-ciency in keeping network-wide congestion under control
in a wide range of tra-c scenarios.
background stream
Measurement point

Figure

3: Simulation model for the test of
TCP adaptivity to a self-similar background tra-c
stream. The two buers are identical: service rates
propagation delays
buer sizes
In this section we analyze the adaptivity of TCP, and conclude
that a simple network conguration, which consists of
a single bottleneck buer shared by a \generator"
ow and
a \response" TCP
ow, can be well modeled as a linear system
above a characteristic timescale. The cut-o timescale
depends on the path properties of the connection. The linear
system transforms certain statistical properties, e.g., au-
tocovariance, between the \generator" stream and the \re-
sponse" tra-c stream through a transform function, which
is characteristic of the network conguration.
3.1 Measuring the Adaptivity of TCP on Several
Timescales
In the rst analysis a single, long, greedy TCP stream is
mixed with random background tra-c streams. See Figure
3 for the conguration. The background streams are
constructed in a way, such that they
uctuate on a limited,
narrow timescale. To limit the timescale under investiga-
tion, the background tra-c approximates a constant amplitude
sine wave of a given frequency f : Abackground (f;
a sin(2ft +)+m where  is a uniformly distributed random
variable between [0; 2]. The process Abackground (f; t)
is a stationary ergodic stochastic process with correlation
The power spectrum of this process
consists of a single frequency component at f . In the
simulation the background process had to be approximated
by a packet stream (packet size of 1000 bytes), with the result
that the spectrum is not an impulse but a narrow spike,
see

Figure

4.
If TCP is able to adapt to the
uctuations of the background
tra-c
ow, the same frequency f should appear as
a signicant spike in the power spectrum of the TCP tra-c
rate process as well. The ratio of the amplitudes of this frequency
component in the spectra is a measure of the success
of TCP adaptation on this timescale. Denote the measure
of adaptivity at frequency f by D(f)
where Sbackground (f) is the spectral density of the background
tra-c rate process at frequency f and Stcp(f) is
the spectral density of the adapting TCP rate process at
the same frequency.

Figure

4 depicts an experiment with a background signal of
0:01[1=s]. The top part of the gure shows the spectrum
of the background tra-c approximating a sine wave of
frequency f . The bottom part is the measured spectrum of
the TCP response. The spectrum of the response has a sig-
0Spectral
density
density

Figure

4: Frequency response to a sine wave of
TCP response). In this conguration the measure
of adaptivity is D(0:01)  1.
frequency [1/s]0.20.61measure
of
adaptivity
Tahoe
Reno
New Reno
Reno w delayed Ack

Figure

5: Measure of adaptivity D(f) as a function
of the frequency for several TCP variants.
nicant spike at f , but it also contains a few smaller spikes
at higher frequencies caused by the congestion control.
Conducting the experiment for a wide range of frequencies
f , it is possible to plot the adaptivity curve of TCP. Figure 5
shows the result for several versions of TCP. Note that the
shape of the function only slightly depends on the TCP ver-
sion. It can be seen that TCP adapts well to frequencies
below f0  0:15[1=s], but it cannot adapt e-ciently to
uc-
tuations on higher frequencies in this conguration.
At f0 a resonance eect can be observed, at this frequency
TCP is more aggressive, and gains even higher throughput
than what is left unused by the non-adaptive background
ow. This frequency is equal to the dominant frequency of
the TCP congestion window process when there is no background
tra-c present (idle frequency), see Figure 6. In [13] a
macroscopic model for TCP connections was published. It is
derived that if every p th packet is lost for a TCP connection,
then the congestion window process traverses a periodic saw-
frequency [1/s]2.06.010.0
Spectral
density

Figure

Spectrum of TCP congestion window process
when no background tra-c is present.
tooth and the length of the period is
RTT is the round-trip time of the path in seconds and W
is the maximum window size in packets. In our case we can
approximate is the buer size in
packets, C is the service rate in packets per second, and d is
the total round-trip propagation delay in seconds. The maximum
window size is Cd, which is the maximum
number of packets in the pipe (buer and link). This gives
an estimate of 0:15[1/s]. The
result agrees with the measured resonance frequency f0 , and
conrms our argument that the resonance eect observed in
the measure of adaptivity function D(f) is due to the TCP
window cycles (see Figure 4b).
The characteristic timescale of the TCP window cycles ranges
in relatively wide ranges in real networks, and the relation
of T  RTT  W=2 can be used for an approximation. For
example, if the round-trip time, which in the previous simulation
was approximately 0.33 s, is rather in the range of
a few tens of milliseconds, the cut-o timescale drops below
Even below this timescale TCP adapts to
uctuations,
though the eectiveness is limited, as shown by the transmission
curve; f0 approximately separates tra-c dynamics
to \local" and \global" scales, above f0 it is the background
process which shapes the spectrum, below f0 the spectrum
is a result of TCP control dynamics and external stochastic
processes has less impact on it.
In the next section we analyze the case when the background
tra-c stream is more complex and contains
uctuations on
several timescales.
3.2 Tests for Linearity
In real networks background tra-c is not limited to a single
timescale. In the following we analyze the case when several
frequencies are present and test whether TCP is able to
adapt to
uctuations on these timescales or not. The motivation
is to prove that TCP can adapt to
uctuations on
1e+062e+06
spectral
density
spectral
density
background

Figure

7: TCP frequency response to the superposition
of 10 random phase sine waves. top) background
tra-c, bottom) TCP response.
several timescales independently of each other, more pre-
cisely, we want to show that TCP control forms a linear
system in this conguration.
By linear system we mean that if the background tra-c
rate is given by B(t), and the adapting TCP tra-c rate
A(t) is expressed using a function , then
where is a linear function of B, i.e., (a1B1
In case of ideal adaptivity, takes
the simple form of and the TCP rate is obtained
simply as 2. If the background
tra-c is a superposition of streams
then the rate of TCP is given by
This construction provides us with a simple test on linearity:
we investigate the response to the superposition of several
streams and investigate the spectrum of the response.

Figure

7 shows the spectral density of the background and
the TCP response when the background is a composition
of 10 random phase sine waves equidistantly spaced in a
logarithmic scale (the nonzero widths of the spikes are due
to the fact that the background mix only approximates sine
waves with varying packet spacing). It can be observed that
was able to adapt to all frequency components in the
mix below
To test whether TCP really adapts to
uctuations indepen-
dently, a wide range of tra-c mixes were simulated consisting
of two frequencies f1 and f2 . A large number of simulations
were performed, covering a whole plane with the
two frequencies, in the range of [0:05; 500][1=s]. Then, the
adaptivity measure for one of the frequencies (D(f1
calculated. If the system is linear, the measure of adaptivity
function at frequency f1 should be independent of the
measure
of
adaptivity

Figure

8: Measure of TCP adaptivity D(f1 ) when
the background process is composed of two frequencies
f1 and f2 .
other frequency f2 . The results of the simulations support
our conclusions, see Figure 8.
3.3 Response to White Noise
In the previous analysis the background processes were limited
to superpositions of sine wave processes. In real networks
background tra-c streams cannot be modeled by just
a few frequency components, it is more appropriate to model
background tra-c streams as \noises".
Two types of special noises are most relevant in tra-c mod-
eling: the White Noise (WN) process and the Fractional
Gaussian Noise (FGN) process. The White Noise process is
the appropriate signal for analyzing the frequency response
of a system and the Fractional Gaussian Noise process frequently
appears as the limit process of tra-c aggregations
[21].
If TCP is a linear system, then it should transform the correlation
of any complex stochastic process, e.g., WN or FGN
through the same transform function. In this section the
response of TCP to a WN process is analyzed. WN is a
special noise as it has constant spectral density. If TCP is
linear, then it should respond with the characteristic curve
obtained previously. The result is depicted in Figure 9. The
similarity of the curve to our previous test-signal based test
supports the linearity argument. In addition, the constant
at range, which starts at a characteristic timescale and
spans several timescales upwards, provides us with information
about the timescale limitation of TCP adaptivity. Note
that this mechanism behaves like a low-pass lter.
4. TCP ADAPTATION TO SELF-SIMILAR
BACKGROUND TRAFFIC
Once we have investigated the linearity of TCP and have
shown that the transform function is
at below a characteristic
frequency, it is quite obvious to expect that TCP,
while adapting to signals of complex frequency content, reproduces
the same spectral density as the original signal
above a timescale, which depends on the path properties
(round-trip time, size of the pipe, etc.
density

Figure

9: a) TCP's frequency response to white
noise, spectral density (dots) and its smoothed version
(line). b) Measure of adaptivity D(f), see also

Figure

If, for example, TCP traverses a link where the tra-c shows
self-similarity, it will adapt to it with a spectral response
equal to the spectrum of the self-similar tra-c (asymptoti-
cally). As TCP is end-to-end control, this property is \prop-
agated" all along the TCP connection path. A visual test
can be seen in Figure 10, where tra-c rates of a self-similar
stream and an adapting TCP
are depicted. The gure shows that on larger timescales the
trace mirrors the FGN trace.

Figure

11 shows the power spectrum of the TCP and FGN
traces of Figure 10 at an aggregation level of 10ms. As suggested
in the previous section, TCP shows the same spectrum
as FGN at timescales above 1-10s, i.e., TCP tra-c
shows asymptotically second-order self-similarity with the
same scaling parameter
4.1 Can Adaptive SRDTraffic Propagate Self-Similarity

So far we have analyzed cases when long greedy TCP sessions
were mixed with background tra-c. It has been shown
that the distribution of le sizes in Web tra-c is heavy-tailed
[5]. This increases the probability of the occurrence of
such long TCP connections. Nevertheless, it is investigated
whether short duration TCPs (durations with light-tailed
distributions) have the same adaptivity property to LRD
tra-c or not. A positive answer increases the generality of
our argument. Based on previous work [21] we would expect
that if On and O durations are light-tailed, the aggregate
tra-c is short-range dependent (SRD). This section demonstrates
that TCP streams have LRD properties in spite of
the short-range dependent result suggested by the On/O
model.
During the simulation we established k parallel sessions.
Within each session TCP connections were generated independently
and the durations of TCP connections were exponentially
distributed (with mean TOn) followed by exponentially
distributed silent periods (TOff ). The simulation
was started from the equilibrium state of the process. (See
time [s]500015000bytes
per
100ms
trace
100 120 140 160 180 200500015000bytes
per
100ms
FGN trace
2000 2500 3000 3500 4000
time [s]5e+05bytes
per
1s
trace
2000 2500 3000 3500 40005e+05bytes
per
1s
FGN trace

Figure

10: Traces of FGN adapting
ows at two aggregation levels. a) 100ms aggregation
aggregation

Figure

12.) Let's denote the number of active TCPs at time
t by N(t), 0  N(t)  k. With this construction N(t) is a
stationary Markov process and it is short-range dependent.
See the self-similarity tests for N(t) in Figure 13 (H  0:5).
On the other hand, if these sessions are mixed with LRD
background tra-c, the aggregate TCP tra-c, i.e., the amount
of bytes transmitted by all TCPs, is LRD (Figure 13). The
reason is that the superposition of short duration TCPs can
e-ciently adapt to a background LRD process just like one
long duration TCP connection.
A real network measurement also supports our argument.
Short les (90 kbyte) were downloaded using the wget utility
from serv1.ericsson.co.hu to locke.comet.columbia.edu (round-
time RTT  180 ms, average download rate r  160 kbps,
SACK TCP) 3 . Whenever the download ended, a new down-load
was initiated for the same le. The experiment lasted
for an hour, and the le was downloaded about 800 times.
The tra-c was captured with tcpdump at the client host.
The Variance-Time plot shows that the tra-c rate dynamics
was self-similar, inspite of the short le-sizes, see Figure
14. As a new download does not use any memory from
3 Note that the access speed at the serv1.ericsson.co.hu side
was increased to 256 kbps during this measurement.
log10(f) [1/s]2.06.0log10(S(f))
log10(f) [1/s]2.06.0log10(S(f))

Figure

11: a) Power spectrum of background tra-c
spectrum of TCP tra-c adapting
to the FGN, estimated
a previous TCP connection, long-range correlations can be
explained only by the long-memory dynamics of the net-
work. In case of smaller les, TCP's capability to adapt to
changing network conditions decreases. Although 90 kbyte
is larger than the current average le size in the Internet, it
has to be emphasized that a subset of connections is enough
to propagate self-similarity. Furthermore, if HTTP 1.1 replaces
HTTP 1.0, persistent TCP connections will be able
to adapt better to tra-c
uctuations, eventually improving
the propagation eect; similarly, if a TCP implementation
preserves some state from a previous connection, the propagation
eect is improved.
4.2 Discussion on SRD TCP Streams
For simplicity, rst assume that there is only one session
with On/O TCP connections multiplexed with LRD tra-c.
In this case N(t) takes the values 0 or 1 for exponentially
distributed durations. Assuming ideal adaptivity, when the
session is active (a TCP is active) it can grab all capacity
left unused by the background LRD tra-c. Then the tra-c
rate during the active periods of the On/O session can be
expressed by
(bit rate) left by the self-similar background tra-c, F (t)
is an FGN process, see Section 2. During inactive periods
Thus the tra-c rate of the TCP controlled On/O
background stream
On/Off TCP streams
Router 1 (C1,B1,d1)

Figure

12: Simulation model of SRD driven TCP
tra-c multiplexed with self-similar background trafc
5ms, sessions
with exponentially distributed On and O periods
with means
log10 (m)3.05.0
log10
log10 (m)5.07.09.0
log10

Figure

13: a) Absolute mean test for the On/O
process N(t) (H  0:5) and the aggregate TCP tra-c
(H  0:73). b) Variance-time plots, H  0:5 and
H  0:72, respectively.
session for all t can be written in explicit form as
Assuming that the sessions are independent of the background
process (N(t) and F (t) are independent), the auto-covariance
of A(t):
F (5)

Figure

14: Variance-time plot of tra-c generated
by short le transfers from serv1.ericsson.co.hu to
locke.comet.columbia.edu, logging resolution 100 ms,
H  0:7.
The left hand side of the product is
The same holds for F (t), and so the covariance can be written
as
F
Finally,
F
If F (t) is LRD, its autocovariance decays asymptotically as
F ()    F as  !1, where 0  F < 1. On the other
hand, if N(t) is SRD, its autocovariance decays asymptotically
faster than   N where N  1.
Consequently, the covariance of A(t) decays asymptotically
at the lower rate, in this case at the rate of the background
LRD process since F <
If the On/O process is LRD as well, e.g., the On and/or
O times are heavy-tailed, then asymptotically the larger
Hurst exponent is measured on the path. In practice, the
border of the scaling region depends on the actual shape of
the covariances and the means mA and mF .
If there are more than one On/O streams sharing the bottleneck
buer with a self-similar background tra-c stream,
takes higher values than 1 as well. However, for the
adaptivity of the aggregate it is su-cient to have at least
one active connection as it was shown in Section 4.1. The
aggregate tra-c of multiple On/O streams adapting to a
background stream may be approximated by
where (:) is the Heaviside-function,
and 0 otherwise). [N(t)] itself is also an On/O process.
Router 1 Router N

Figure

15: A TCP connection traversing multiple
hops with independent background LRD (H i ) inputs

If the On/O processes are independent and they are exponentially
distributed, then N(t) forms a Markov process
([N(t)] is the indicator process for the empty state of this
Markov chain) and it is SRD.
The conclusion of this section is that if the end-to-end service
uses TCP connections, then the tra-c generated by the
service is also adaptive, and in this case the adaptivity of
the end-to-end service is su-cient to \propagate" LRD to
other parts of the network. Moreover, if N(t) is LRD, then
the larger Hurst exponent max(HN ; HF ) is propagated.
5. SPREADING OF SELF-SIMILARITY IN
Previously we analyzed the case when a TCP connection
shares a single bottleneck buer with LRD background traf-
c, and it was only this bottleneck that aected the rate of
TCP. In this section the network case is discussed.
Two aspects are analyzed. The rst one deals with the case
when the path of an adaptive connection passes through several
buers with self-similar inputs. These buers are candidates
to become bottlenecks occasionally during the lifetime
of the connection. The second one investigates whether self-similarity
can spread from one adaptive connection to the
other causing widespread self-similarity in a network area.
The presented results are intended to highlight the basic
mechanisms, so the investigated scenarios are simplied for
the ease of discussion.
5.1 Discussion of the Multiple Link Case
A wide area TCP connection usually spans 10-15 routers
along its path, out of which there are usually several back-bone
routers with high level of aggregated tra-c, see Figure
15. A TCP connection has to adapt to the whole path.
The capacity of the end-to-end path, at time t, depends on
which buer is the bottleneck at this time. Because of tra-c
uctuations, the location of the bottleneck moves randomly
from one router to the other.
Assuming ideal end-to-end adaptivity, the rate of the adaptive
TCP connection is equal to the free capacity of the
bottleneck link at time t:
where N is the number of links and F i (t) denotes the free
capacity of the i th link on the path.
For simplicity, assume that the crossing background LRD
streams on the links are independent and the link at time
t is either empty: F i
F3 FGN H=0.6

Figure

Variance-Time plots of F i FGN processes
of respectively (identical
mean rates and variance), and the end-to-end process
(t). The end-to-end path is characterized
by H  0:8 asymptotically.
simplication the rate of the adaptive connection can be
written as
Y
In the previous section it was shown that the product of
independent LRD processes is also LRD and it is asymptotically
characterized by the largest exponent:
Thus, in the multiple link case it is the largest Hurst exponent
among the background LRD streams on the links that
characterizes the TCP connection.
For a numerical example using more complex processes, four
FGN background samples were generated with equal mean
rates, but with dierent Hurst exponents, to model F i (t),

Figure

16. The end-to-end process A(t),
which is the minimum of the FGN processes, is asymptotically
second-order self-similar, and it has the same Hurst
exponent as the largest Hurst exponent among the F i (t) pro-
cesses, i.e., the result is the same as in the simple full/empty
case.
Another possible interpretation of (13) is that we consider
the F i (t) not as rate processes, but as indicator processes of
congestion. From the end user perspective it is important
to analyze whether the network is able to support the expected
service level requirements, for example, whether the
le transfer rate degrades below an acceptable level or not.
Let F i (t) be the indicator process of link i indicating whether
the link is congested and it cannot support the expected service
rate for the connection or is not congested
1). Thus, if the background congestion indicator
processes are LRD, then it is the largest Hurst exponent
that characterizes the end-to-end service characteristics of
the investigated TCP connection.
indirect stream
FGN stream
direct stream

Figure

17: Network model for the investigation of
self-similarity spreading.
5.2 Spreading of Self-Similarity among Adaptive
Connections in Multiple Steps
So far, in all analyzed cases, adaptive tra-c was in direct
contact with self-similar background tra-c. In this section it
is investigated whether self-similarity caused by adaptation
can be passed on to adaptive tra-c streams that have no
direct contact with the source of self-similarity. A few simple
conditions are given as well. Assuming that our argument
is valid, self-similarity can spread out from a localized area,
consequently, strong self-similarity is balanced throughout a
wider area of the network.
A simple network scenario is used for the investigation. An
adaptive tra-c stream (direct stream) shares a link with
self-similar FGN tra-c. The direct
stream is mixed with another adaptive stream on a second
link, which itself has no direct connection with the FGN
tra-c (indirect stream), see Figure 17. The data rate of the
direct stream is thus aected by two other streams, and also
the two adaptive streams have an eect on one another. We
are going to investigate the statistical properties of both the
direct and the indirect streams.
Assume ideal adaptivity and max-min fairness among the
adaptive streams. Also assume that the service rates of both
links are equal (C). If the background stream was inactive,
the bottleneck would be the rst buer and the adaptive
streams would share simply half the service rate, both sending
at a rate of C=2.
A dir
In the presence of the FGN stream
owing through the second
buer, the rates can still remain C=2, unless it is the second
buer which becomes the bottleneck, i.e., when the capacity
left unused by the FGN stream is C AFGN (t) < C=2.
In this case the direct stream can use at most A dir = C
AFGN (t), so the indirect stream can grab all remaining service
capacity in the rst buer A
In short:
A dir
A indir
Calculation of the autocovariance of A dir and A indir is dicult
because of the min and max operators. We consider two
simple, extreme cases. In the rst case, the rate of the background
LRD stream is always greater than C=2, simplifying
the expressions to A dir
AFGN (t), i.e., spreading of self-similarity is ideal. In the second
extreme case the rate of background process is always
smaller than C=2, leading to A dir
i.e., self-similarity disappears from both adaptive streams.
These results has been veried by simulations as well.
log10(d)13
log10(R/S)
log10(d)13
log10(R/S)

Figure

a) R/S plot of heavy-tailed stream
0:82. b) R/S plot of indirect stream
The investigated scenario demonstrates the simplest mechanism
of how adaptive connections may have eect on each
other. We simulated a more complex scenario, where the
synthetic FGN stream is replaced by an aggregate stream
of randomly generated short TCP le transfers. The distribution
of the le sizes is heavy-tailed. The direct and
indirect TCP streams are also replaced by aggregates, but
the le sizes within these aggregates are light-tailed.
The streams consist of nheavy tailed
sessions.The le size distributions are Pareto distributions
with the following parameters: the average le size is 40
kbyte for all streams, the average waiting time between les
is 20 sec. The shape parameters are aheavy tailed = 1:1 and
a both the le size and the waiting time
distributions. With these parameters only one stream has
heavy-tails (aheavy tailed < 2).
The results of the simulation experiment are depicted in

Figure

18. As suggested in [4] the tra-c stream consisting
of heavy-tailed le downloads is LRD (H  0:82). Further-
more, the indirect tra-c stream, although it was created using
light-tailed distributions is LRD as well (H  0:71). The
cause is that long-range dependent
uctuations are propagated
via the indirect stream.
Performing the previous experiment using dierent param-
eters, we have found that depending on the tra-c mix, the
spreading between indirect and direct streams can be strong
but it can be weak as well. In certain cases, spreading to an
indirect stream does not happen at all, just like in the simple
analytic example assuming ideal TCP
ows and max-min
fairness. The exact requirements for spreading are subjects
for further study.
6. CONCLUSIONS
It was demonstrated how a TCP connection, when mixed
with self-similar tra-c in a bottleneck buer, takes on its
statistical second order self-similarity, propagating scaling
phenomena to other parts of the network. It is suggested
that the adaptation of TCP to a background tra-c stream
can be modeled by a linear system and the validity of our
approach is analyzed. It was shown that TCP inherits self-similarity
when it is mixed with self-similar background trafc
in a bottleneck buer through the transform function of
the linear system. This property was demonstrated for both
short and long duration TCP connections. We also investigated
TCP behavior in a networking environment. It was
found that if congestion periods are long-range dependent
in several hops on a connection's path, the largest Hurst
exponent characterizes the end-to-end connection. It was
also demonstrated that TCP
ows, in certain scenarios, can
pass on self-similarity to each other in multiple hops. The
presented mechanisms are basic \building blocks" in a future
wide-area tra-c model, and in real-life it is always their
combined eect that we can observe. The presented network
measurements are intended to highlight the basic mechanisms
in simplied network scenarios, when it can be assured
that only the network conditions and TCP's response
to network conditions are the cause of the investigated phe-
nomena. As thousands of parallel TCP connections continuously
intertwine the Internet, the mechanisms described in
this paper can provide us with a deeper insight why significant
and strong self-similarity is a general and widespread
phenomenon in current data networks.
7.



--R

Wavelet analysis of long-range-dependent tra-c

Heavy tra-c analysis of a storage model with long range dependent on/o sources


Experimental queuing analysis with long-range dependent packet tra-c
Dynamics of IP tra-c: A study of the role of variability and the impact of control
Data networks as cascades: Investigating the multifractal nature of Internet WAN tra-c

Congestion avoidance and control.
On the self-similar nature of Ethernet tra-c
On the self-similar nature of Ethernet tra-c (extended version)
The macroscopic behavior of the TCP congestion avoidance algorithm.


A storage model with self-similar input
On the relationship between
On the e
area tra-c: The failure of Poisson modeling
Estimators for long-range dependence: an empirical study
Proof of a fundamental result in self-similar tra-c modeling
On self-similar tra-c in ATM queues: De nitions
The chaotic nature of TCP congestion control.

A bibliographical guide to self-similar tra-c and performance modeling for modern high-speed networks
--TR
Congestion avoidance and control
On the self-similar nature of Ethernet traffic
On the self-similar nature of Ethernet traffic (extended version)
Analysis, modeling and generation of self-similar VBR video traffic
area traffic
Experimental queueing analysis with long-range dependent packet traffic
through high-variability
On self-similar traffic in ATM queues
Proof of a fundamental result in self-similar traffic modeling
The macroscopic behavior of the TCP congestion avoidance algorithm
Self-similarity in World Wide Web traffic
Data networks as cascades
Heavy-tailed probability distributions in the World Wide Web
Dynamics of IP traffic
On the relationship between file sizes, transport protocols, and self-similar network traffic

--CTR
W. Feng , P. Tinnakornsrisuphap, The failure of TCP in high-performance computational grids, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.37-es, November 04-10, 2000, Dallas, Texas, United States
H. Sivakumar , S. Bailey , R. L. Grossman, PSockets: the case for application-level network striping for data intensive applications using high speed wide area networks, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.37-es, November 04-10, 2000, Dallas, Texas, United States
Daniel R. Figueiredo , Benyuan Liu , Vishal Misra , Don Towsley, On the autocorrelation structure of TCP traffic, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.40 n.3, p.339-361, 22 October 2002
Guanghui He , Yuan Gao , Jennifer C. Hou , Kihong Park, A case for exploiting self-similarity of network traffic in TCP congestion control, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.6, p.743-766, 21 August 2004
Dan Rubenstein , Jim Kurose , Don Towsley, Detecting shared congestion of flows via end-to-end measurement, IEEE/ACM Transactions on Networking (TON), v.10 n.3, p.381-395, June 2002
Thomas Karagiannis , Michalis Faloutsos , Mart Molle, A user-friendly self-similarity analysis tool, ACM SIGCOMM Computer Communication Review, v.33 n.3, July
Vincenzo Liberatore, Circular arrangements and cyclic broadcast scheduling, Journal of Algorithms, v.51 n.2, p.185-215, May 2004
TCP congestion control;long-range dependence;TCP adaptivity;self-similarity