Transcript Document

Nonlinear Dynamics in TCP/IP networks
Ljupco Kocarev
Institute for Nonlinear Science
University of California San Diego
Outline
• What is nonlinear time series analysis?
• Evidence of nonlinear behavior in TCP/IP networks
• Conclusions and open problems
R. E. Kalman, 1956
“Nonlinear aspects of sampled-data control systems”
xn1  f ( xn )
xn+1
Markov process with transition probabilities:
1
1/2
1
1/3
0
1
S
2/3
1/3
0
0
1/3
2/3
1
0
S
1
xn
hKS
3
2
   ln 3  ln 2
7
7
1/2
Fact: Deterministic chaos as a fundamental concept is by
now well established and described in literature. The mere
fact that simple deterministic systems generically exhibit
complicated temporal behavior in the presence of
nonlinearity has influenced thinking and intuition in many
fields.
What is nonlinear time series analysis?
Nonlinear time series analysis is a tool for study of compex
and nonlienar dynamics from measurements
• H. D. I. Abarbanel, “Analysis of Observed Chaotic Data”
Springer, New York (1996)
• H. Kantz and T. Schreiber, “Nonlinear Time Series Analysis”
Cambridge University Press, Cambridge (1997)
• Software package TISEAN (publicly available)
Phase space representation: Delay coordinates, Embedding parameter,
Principal components, Poincaré sections, SVD filters
Visualization, non-stationarity: Recurrence plots, Space-time separation
plot
Nonlinear prediction: Model validation, Nonlinear prediction, Finding
unstable periodic orbits, Locally linear prediction, Global function fits
Nonlinear noise reduction: Simple nonlinear noise reduction, Locally
projective nonlinear noise reduction, Nonlinear noise reduction
Lyapunov exponents: Maximal exponent, Lyapunov spectrum
Dimensions and entropies: Correlation dimension, Information dimension
Testing for nonlinearity: Surrogate data, Iterative Fourier transform
method, General constrained randomization, Measuring weak nonlinearity
• 1982 first attempt to apply chaos theory to power grids
• 1997 connection between chaos and blackouts began to tighten
when researchers started to work with actual blackout data
• 2004 The Unruly Power Grid – cover story of the August issue
of Spectrum
Two opposite classes of systems:
Nonlinear and fully deterministic systems
Stochastic systems
Assumption: The bulk of real world time series falls in neither of these
limiting categories because they reflect nonlinear and deterministic
responses and effectively stochastic components at the same time.
Evidence of nonlinear behavior in
TCP/IP networks
Complex Dynamics in Communication Networks
(Edited by L. Kocarev and G. Vattay)
to be published by Springer 2005
Nonlinear Dynamics of TCP and its Implications
to Network Performance
A. Veres and M. Boda
• The model consists of two end-hosts, both running Linux kernel
version 2.4
• Two hosts can be far from each other: the propagation delay in the
lab experiment is emulated by the NIST Net network emulator
• tcptrace utility: for calculating the window size as a function of
time
TCP congestion window dynamics at increasing speeds.
Each figure shows both TCP window processes one on top of the other.
Buffer size 20 packets
Propagation delay 100ms
Impact of a perturbing packet (which happens exactly at 60sec)
on TCP window dynamics at different service rates.
Rate 960kbps
TCP rate processes at different buffer sizes
(service rate 1200 kbps, delay 100 ms)
• When the buffer size is 10 packets, the
traffic looks random and shows short
timescale variations
• When the buffer size is 5 and 20 packets,
we see long, alternating periods of high and
low transmission rates
Variance-time plot
Spatio-tempral graph of 30 TCP window processes sharing a single bottleneck. Time flows
from left to right, light shades represent large windows, dark shaded represent low windows.
Spatio-temporal graph of the original system (top). Spatio-temporal graph of the perturbed
system (middle). Difference between the two systems (bottom).
The difference between the two systems increase
at an average rate of
every second
Dynamics of Congestion Control
A. C. Gilbert
Many experiments and the intuitive explanations of these experiments
show that TCP sources competing for bandwidth on a congested link
will synchronize through the weak coupling inherent in congestion
control.
The graphs show the evolution of packet arrival rates and queue occupancies at a
bottleneck link shared by 50 TCP sources sending an infinitely long file. On the
top are results for a drop-tail policy; on the bottom are those for RED.
There is strong aggregate periodic behavior, made more clear by the strong
component in the discrete Fourier transform of the arrival rate (below each figure).
The more pronounced periodic behavior caused by RED is counter to the
commonly held intuition that a randomized drop-policy would prevent periodic
behavior by ‘desynchronizing’ TCP sources.
Aggregate arrival rate shows periodic behavior
with fixed RTTs with both drop-tail and RED
In this figure RTT is 140ms: aggregate rate still
fluctuates with a period of about 2 seconds, and
the periodicity is more prominent with RED
Statistical Properties of Chaos in
Communication Networks
G. Vattay et al.
On Dynamics of Transport Protocols
Over Wide-Area Internet Connections
N. S. V. Rao, J. Gao and L. O. Chua
Number of traces using single and two competing TCP streams on two different connections
from ORNL to Georgia Institute of Technology (GaTech) and to Louisiana State University
(LSU) are collected
First connection: high-bandwidth (OC192 at 10Gbps) with relatively low backbone traffic
and a round-trip time of about 10 milliseconds
Second connection: much lower bandwidth (10 Mbps) with higher levels of traffic and a
round trip-time of about 26 milliseconds
Power spectral analysis of these data does not show any dominant peaks, and hence, the
dynamics are not simply oscillatory
Data was measured on the Internet with ‘live’ background traffic, it is apparently more
complicated and realistic than ns-2 traces
are vectors constructed from a scalar
time series using the embedding theorem
Brackets denote the ensemble average of all possible (Vi,Vj)
pairs
For low-dimensional chaotic systems, the curves
for
different shells form a common envelope, and the slope of the
envelope is an estimate of the largest positive Lyapunov
exponent.
•
The dynamics cannot be characterized as pure deterministic
chaos, since in no case can we observe a well-defined linear
envelope. Thus the random component of the dynamics due
to competing network traffic is evident and can not simply
be ignored.
•
The data is not simply noisy, since otherwise we should
have observed that
is almost flat when k > (m-1)L.
Thus, the deterministic component of dynamics which is
due to the transport protocol plays an integral role and must
be carefully studied.
•
The features (ii) and (iii) indicate that the Internet transport
dynamic contains both chaotic and stochastic components.
Conclusions and open problems
There exist plenty of theoretical and simulation evidences of
nonlinear dynamics and chaos in TCP/IP networks
There exist only a few measurement evidences of nonlinear
dynamics and chaos in TCP/IP networks
In terms of actual Internet traffic the question of the
deterministic (chaotic) nature of transport dynamics is still open