Transcript PowerPoint Presentation on Networks

Trends
•
•
Information technology allows us to create systems
with bewildering complexity.
Networking which is:
–
–
–
•
•
Ubiquitous, pervasive
Convergent, heterogeneous
Hierarchical, multiscale
Biology is shifting from an exclusive focus on the
molecular basis of life to systems questions.
Modeling, analysis, and simulation of complex
systems.
Trends
•
•
•
•
•
“Anything we can imagine, we can build.”
Robustness and reliability become the dominant
design challenges.
Theoretical foundation is fragmented into fairly
isolated technical disciplines: computational
complexity, information theory, control theory,
dynamical systems.
“New science of complexity” lacks rigor and
relevance.
But the need for a new science remains.
New science of complexity?
•
•
•
•
Much attention has been given to “complex adaptive
systems” in the last decade.
Popularization of not just information and entropy, but
phase transitions, criticality, fractals, self-similarity,
power laws, chaos, emergence, self-organization, etc.
Aim is to find universal characteristics of complexity.
From Physics: an emphasis on emergent complexity
via self-organization of a homogeneous substrate near
a critical or bifurcation point (SOC/EOC).
New science of complexity?
•
•
•
•
•
The Web/Internet, perhaps more than any other
complex system, can be described readily and
convincingly in these terms.
Provides a convenient starting place for a critical
evaluation of the status of complex systems theory.
Reveals interesting features of the Web/Internet.
Introduce a view (HOT) of complex systems which is
radically different from complex-adaptive-systemsedge-of-chaos-self-organized-criticality
(CAS/EOC/SOC).
See also next week’s theory seminar by Jean Carlson,
Physics, UCSB (Friday, 2pm)
Highly
Optimized
Tolerance (HOT)
•
•
•
•
•
Complex systems in biology, ecology, technology,
sociology, economics, …
are driven by design or evolution to highperformance states which are also tolerant to
uncertainty in the environment and components.
This leads to specialized, modular, hierarchical
structures, often with enormous “hidden” complexity,
with new sensitivities to unknown or neglected
perturbations and design flaws.
“Robust, yet fragile!”
Motivating
examples
•
•
•
•
•
•
•
•
Web/Internet and convergent, ubiquitous networking
Power and transportation systems
Simulation-based design of complex systems
Biological regulatory networks and evolution
Turbulence in shear flows
Ecosystems and global change
Financial and economic systems
Natural and man-made disasters
Uncertainty
and
Robustness
Complexity
Interconnection/
Feedback
Dynamics
Hierarchical/
Multiscale
Heterogeneous
Nonlinearity
Uncertainty
and
Robustness
Complexity
Interconnection/
Feedback
Dynamics
Hierarchical/
Multiscale
Heterogeneous
Nonlinearity
Turbulent
Shear flows
coupling
Tight
Telephone
system
Organisms
Power
grid
Ecosystems
Internet
Post
office
Loose
Ideal
gas
Homogeneous
Socioeconomic
systems
Heterogeneous
Turbulent
Shear flows
coupling
Tight
Telephone
system
Organisms
Power
grid
Ecosystems
Internet
Post
office
Loose
Ideal
gas
Homogeneous
Socioeconomic
systems
Heterogeneous
Uncertainty
and
Robustness
Complexity
Interconnection/
Feedback
Dynamics
Hierarchical/
Multiscale
Heterogeneous
Nonlinearity
Uncertainty
and
Robustness
Complexity
Interconnection/
Feedback
Dynamics
Hierarchical/
Multiscale
Heterogeneous
Nonlinearity
Complexity
Robustness
Interconnection
Aim: simplest
possible story
Control
Theory
Computational
Information
Theory
All
design
Theory of
Complex systems?
Complexity
None
Statistical
Physics
Dynamical
Systems
1
dimension

Control
Theory
Computational
Information
Theory
All
design
Internet
Complexity
None
Statistical
Physics
Dynamical
Systems
1
dimension

Assumptions
Hopefully, you are familiar with:
• Internet protocols, HTTP/TCP/IP
• Source coding for data compression
or
• Statistical self-similarity and renormalization,
-stable distributions, power laws, fractal
noise, etc,
High-level
functionality
How are complex
systems structured?
Physical
implementation
Building complexity
High-level
functionality
Layers of
rules and
protocols
Physical
implementation
Building complexity
High-level
functionality
Transparent to the user
• mostly for robustness
• easy to ignore from outside
Physical
implementation
Early computing.
High-level
functionality
Layers of
rules and
protocols
Physical
implementation
Machine code
Logic
Transistors
Modern computation.
High-level
functionality
User interface
Applications
Layers of
rules and
protocols
Applications
OS
Computer
Physical
implementation
Board
VLSI
VLSI design
User interface
Instructions
Applications
Logic
Applications
Topology
OS
Geometry
Computer
Timing
Board
Fabrication
VLSI
Silicon
Designed versus generic
Instructions
Logic
Topology
Climate
Weather
Navier-Stokes
Geometry
Boltzmann dist
Keep only
Timing
sets of
measure
Fabrication
zero.
Throw away
particle
dynamics
sets
of
measure
Quantum
mech.
zero.
Silicon
???
Network protocols.
HTTP
TCP
IP
Network protocols.
HTTP
TCP
IP
Routers
Network protocols.
HTTP
Transparent to the user
Network protocols.
Network protocols.
Network protocols.
Transparent to the user
Danger: It is easy to weave
intriguing but impossible
notions about how this works.
It often requires great internal
complexity to create a robust,
simple interface.
web traffic
Is streamed out
on the net.
Web
client
Web
servers
Creating
internet traffic
Network protocols.
HTTP
TCP
IP
Routers
Network protocols.
HTTP
Files
TCP
IP
packets
packets
packets
packets
packets
packets
Routers
web traffic
Let’s look at some
internet traffic
Is streamed out
on the net.
Web
client
Web
servers
Creating
internet traffic
Notices of the AMS, September 1998
Poisson
Measured
Internet traffic
Standard Poisson
models don’t capture
long-range correlations.
(Tn X )i 
1
1/ 
n
(i 1) n1
Xj
j in
 1
“bursty” on all
time scales
web traffic
Let’s look at
some web traffic
Is streamed out
on the net.
Web
client
Web
servers
Creating
internet traffic
10
WWW files
Mbytes
Cumulative
10
(Huffman)
(Crovella)
4
Frequency
10
Data
compression
6
-1
-1/2
Forest fires
1000 km2
2
(Malamud)
10
0
10
-6
10
-4
10
-2
10
0
Size of events
(codewords, files, fires)
10
2
3
10
2
10
Frequency
of outages
>N
x
1
1
10
US Power outages
1984-1997
0
10
4
10
5
10
6
10
7
10
N= # of customers affected by outage
10
3
Raw data
Frequency
of outages
>N
10
10
2
1
10
2
(li,Pi = i)
1
0
10
4
10
5
10
6
10
7
N= # of customers affected by outage
10
Frequency
of outages
>N
10
10
3
2
1
August 10, 1996
10
0
10
4
10
5
10
6
10
7
N= # of customers affected by outage
Size of events vs. frequency
log(probability)
p  s--1
log(Prob > size)
Ps

log(size)
10
Raw data
6
DC
(li,Pi )
Cumulative
WWW
10
4
Frequency
FF
10
10
2
0
10
-6
10
-4
10
-2
10
0
Size of events
10
2
18 Sep 1998
Forest Fires: An Example of Self-Organized
Critical Behavior
Bruce D. Malamud, Gleb Morein, Donald L. Turcotte
Examples of fat tail distributions
•
•
•
•
•
•
•
•
•
•
•
Power outages, forest fires, web files
UNIX files, CPU utilization
Meteor impacts, earthquakes
Deaths and dollars lost due to man-made disasters
Deaths and dollars lost due to natural disasters
Word rank in English (Zipf’s law)
Income and wealth of individuals and companies
Variations in stock prices and federal budgets
Masses or sizes of objects in this room
Ecosystem and specie extinction events?
All of these involve frequencies of “events”
Large scale phenomena is extremely
non-Gaussian
• The microscopic world is largely exponential
• The laboratory world is largely Gaussian
because of the central limit theorem
• The large scale phenomena has heavy tails
(fat tails) and power laws
Robust
Good
(small events)
Log(freq.)
cumulative
Robust,
yet
fragile
Bad
(large events)
Gaussian,
Exponential
Log(event sizes)
yet
fragile
Power laws and fat tail distributions
• We need a clear picture of the origin and
nature of power laws and fat tails.
• And how various notions of self-similarity
are connected.
Stable laws
Consider a sequence of i.i.d. random variables
X 


X i i 
(white noise)
(We’ll assume zero mean, symmetric distributions.)
Fix  > 0. For each n  1, define transformations
Tn X  


(Tn X )i i 
(Tn X )i 
1
n1/ 
(i 1) n1
Xj
j in
2
1
0
-1
-2
0
5
10
15
20
25
30
35
40
45
50
  1, n  10
4
2
0
-2
-4
5
10
Tn X  
15
20


(Tn X )i i 
25
30
(Tn X )i 
35
40
1
n1/ 
45
(i 1) n1
Xj
j in
50
Ordinary central limit
theorem, Gaussian,  = 2
-stable laws are fixed
points with 0 <   2
Tn X  X
Tn , n  1
Renormalization (semi-) group
with critical exponent 1/
Tmn  TmTn
Tn X  


(Tn X )i i 
(Tn X )i 
1
n1/ 
(i 1) n1
Xj
j in
General central limit theorem: 0 <   2
Tn X  X
-stable laws are fixed
points with 0 <   2
-stable laws have:
• normal distribution for
=2
• infinite variance for
1<<2
• infinite mean for
0<1
(Tn X )i 
1
X

j
1/ 
n
-stable distributions: 0 <   2 (-sd)
have characteristic functions

Eexp iX   exp  
P( X  x)  x
P( X  cx)  c




as x   (  2)
P( X  x) as x   (  2)
Self-similar with
exponent 
(Tn X )i 
1
X

j
1/ 
n
-stable distributions: 0 <   2 (-sd)
Have self-similar probability distributions.
EX
EX
P( X  cx)  c

p
p
   0  p 
   p 
P( X  x) as x   (  2)
Self-similar with
exponent 
(Tn X )i 
1
X

j
1/ 
n
10
Cumulative
10
10
= 2
WWW
DC
4
Frequency
10
= 1
6
= 1/2
FF
2
0
10
-6
10
-4
10
-2
10
0
Size of events
10
2
-stable distributions: 0 <   2 (-sd)
• Produces power law tails via central limit
theorem with fat tail distributions.
• Many other mechanisms yet to come…
• Still need know where fat tails originate.
• Also many more mechanisms.
One mechanism for power laws
(Astrom 1965)
•
•
•
•
•
•
•
dx/dt = -(1+w ) x+ n
w and n are Gaussian white noise
 = 0  x Gaussian
  0  x power law
Gaussian case is very brittle
When x is large  power laws
Many others yet to come….
Other types of self-similarity
and power laws
• Allometric scaling
• Fractal geometry
• Time series (long-range
dependence)
• Critical phenomena
• HOT
web traffic
Back to
internet traffic
Is streamed out
on the net.
Web
client
Web
servers
Creating
internet traffic
Poisson
Measured
Internet traffic
Standard Poisson
models don’t capture
long-range correlations.
(Tn X )i 
1
1/ 
n
(i 1) n1
Xj
j in
 1
“bursty” on all
time scales
Recall that for i.i.d. random variables (white noise)
-stable laws are fixed
points with 0 <   2
Tn X  X
Tn , n  1
Renormalization (semi-) group
with critical exponent 1/
Tmn  TmTn
Tn X  


(Tn X )i i 
(Tn X )i 
1
n1/ 
(i 1) n1
Xj
j in
Allow nontrivial correlations, but make Gaussian.
Fractional Gaussian noise is fixed
points with Hurst parameter H.
Tn X  X
Tn , n  1
Renormalization (semi-) group
with critical exponent H
Tmn  TmTn
Tn X  


(Tn X )i i 
(Tn X )i 
1
nH
(i 1) n1
Xj
j in
2
1
0
-1
-2
0
5
10
15
20
25
30
35
40
45
50
H  1, n  10
4
2
0
-2
-4
5
10
Tn X  
15
20


(Tn X )i i 
25
30
(Tn X )i 
35
40
1
nH
45
(i 1) n1
Xj
j in
50
Tn X  X
Fixed points of
renormalization group
• -stable laws are the white noise fixed points with
exponent 1/ and 0 <   2 (heavy tails)
• Fractional Gaussian noises are the Gaussian fixed
points with Hurst parameter (and exponent)
0 < H  1 (long range correlations)
• Their intersection is Gaussian white noise with
 = 2 and H=1/2
• Both (and combinations) can create “burstiness”
Tn X  X
Long range correlations
• Fractional Gaussian noises with H  1/2 has power
law autocorrelation and spectrum:
2( H 1)
r (k )  k
12 H
s ( )  
as k  
as   
Fractal
Measured
Internet traffic
Fractional Gaussian
(fractal) noise models
measurements well.
“bursty” on all
time scales
Heavy tails in networks?
Heavy tails are everywhere in networks.
There is a large literature since 1994:
Leland, Taqqu, Willinger, Wilson
Paxson
Crovella and Bestavros
Harchol-Balter,…
Universal network behavior?
throughput
Congestion
induced
“phase
transition.”
Similar for:
• Power grid?
• Freeway traffic?
• Gene regulation?
• Ecosystems?
• Finance?
demand
Control
Theory
Computational
Information
Theory
All
design
Internet
Complexity
None
Statistical
Physics
Dynamical
Systems
1
dimension

Features of networks?
• Self-similar, fractal traffic
– Power law web file transfers
– Long range correlations in network traffic
• Congestion-induced “phase transitions” in
queues? Suggestive of criticality?
• Chaos in TCP mechanisms
• Self-organization, emergence?
• Complex adaptive systems!!!!
• How to publish in Science!
Internet: Emergent self-organization
at the edge of chaocritiplexity
In this paper, we show that the Internet
self-organizes to the edge of chaos,
exhibiting emergent complexity,
with ubiquitous and universal self-similarity,
fractals, and power laws
as the classic hallmarks of criticality.
Networks
log(thru-put)
Making a “random network:”
• Remove protocols
– No IP routing
– No TCP congestion control
• Broadcast everything
 Many orders of magnitude
slower
random
networks
Broadcast
Network
log(demand)
Networks
real
networks
log(thru-put)
HOT
random
networks
Broadcast
Network
log(demand)
The yield/density curve
predicted using random
ensembles is way off.
designed
Yield,
flow, …
HOT
random
Densities, pressure,…
Similar for:
• Power grid
• Freeway traffic
• Gene regulation
• Ecosystems
• Finance?
Turbulence
streamlined
pipes
Log(flow)
HOT
random
pipes
log(pressure drop)
Typical web traffic
Heavy tailed
web traffic
 > 1.0
log(freq
> size)
Is streamed out
on the net.
Web
servers
Creating fractal
Gaussian
internet traffic
p  s-
log(file size)
3 
H
2
Fat tail
web traffic
time
Is streamed
onto the
Internet
creating long-range
correlations with
3 
H
2
Heavy tails in networks?
• Advocates argue that traditional queuing
theory is misleading and underestimates
required buffer sizes and/or router speeds.
• Many heavy tails in networks can be traced
to heavy tails in web sites and other files.
• Why do file sizes on websites
have heavy tails?
web traffic
Back to web
traffic
Is streamed out
on the net.
Web
client
Web
servers
Creating
internet traffic
10
WWW files
Mbytes
Cumulative
10
Data
compression
6
(Huffman)
(Crovella)
4
Frequency
10
Forest fires
1000 km2
2
(Malamud)
10
0
10
-6
10
-4
10
-2
10
0
Size of events
10
2
document
split into N files
to minimize
download time
A toy website model
(= 1-d grid HOT design)
Forest fires?
Fire suppression
mechanisms must
stop a 1-d front.
Burnt regions are 2-d
d-dimensional
li = volume enclosed
ri = barrier density
li   , ri 
d
pi = Probability
of event

d 1
li
Resource/loss relationship:
l r
d
PLR optimization
Minimize
expected loss
J
 pili  ri  R
P: uncertain events
with probabilities pi
R: limited
resources ri
L: with
loss li
P
L
R
DC
source
codewords decodability
WWW
user access
files
web layout
FF
sparks
fires
firebreaks
PLR optimization
Minimize
expected loss
J
 pili  ri  R
P: uncertain events
with probabilities pi
L: with
loss li
Resource/loss
relationship

r

l (r ) 
c

R: limited
resources ri

1
 d
PLR optimization
J
 pili  ri  R
l (1)  0
l (r )  cr
Set amplitudes and
small scale cutoff
  1
l (r ) 

r

c


1
 d
PLR optimization
J
=0
=1
=2
=
“dimension”
 pili  ri  R
data compression
web layout
forest fires
l (r ) 

r

c


1
 d
PLR optimization
J
=0
 =0 is
Shannon
source coding
 pili  ri  R
data compression

  log( r )

l (r )  
 c 
  r 1



 0
 0
Minimize average cost using
standard Lagrange multipliers
J 
 pili  ri
 R
Leads to optimal solutions for
resource allocations and the
relationship between the
event probabilities and sizes.
With optimal
cost
R  c 1
 pi  1
  log( r )

l (r )   c  
r 1
 


 0
 0




1 /(1  ) 



Rp i
c


li  

1
   p1j /(1  ) 


 j






  pi log( Rp i )   pi log(  pi )

J 
1 
 c
1





 R  p 1    p 



i
i

  




 0
 0
Minimize average cost using
standard Lagrange multipliers
J 
 pili  ri
 R
Leads to optimal solutions for
resource allocations and the
relationship between the
event probabilities and sizes.
With optimal
cost
R  c 1
 pi  1
  log( r )

l (r )   c  
r 1
 


 0
 0




1 /(1  ) 



Rp i
c


li  

1
   p1j /(1  ) 


 j





  pi log( pi )
 0


1 
J  

1


1
   pi 1  
 1   0

  


 
To compare with data.
plot
sizes
from
data
l , Pˆ 
i
i
compute
using
model
Cumulative
order
li  li 1




1 /(1  ) 



Rp i
c


li  

1
   p1j /(1  ) 


 j




Solve for p(l) gives
pˆ i  c1 li  c2 
 (11 /  )
ˆ i li  li 1 
Pˆi   p
k i
10
6
DC
HOT WWW
10
10
10
4
HOT FF
2
0
10
-6
10
-4
10
-2
10
0
10
2
10
6
DC
HOT WWW
10
10
10
4
HOT FF
2
SOC FF
0
10
-6
10
-4
10
-2
10
0
10
2
6
10
5
10
4

5
4
10
4

3
3
10
2
10

5

4
1

3

4
1
10
0
10 -6
10
-4
10
-2
10
0
10
2
10
18 Sep 1998
Forest Fires: An Example of Self-Organized
Critical Behavior
Bruce D. Malamud, Gleb Morein, Donald L. Turcotte
4 data sets
3
10
HOT FF
=2
2
10
1
10
SOC FF
0
10
-2
10
-1
10
0
10
1
10
2
10
Additional 3 data sets
3
10
4
10
SOC
HOT
d=1
SOC
d
d
d=1
HOT
10
DC and WWW
are prescriptive.
6
DC
HOT WWW
10
10
4
HOT FF
2
SOC FF
Why are
the HOT PRL
0
10
-6
-4
predictions
10 so good?
10
10
-2
10
0
10
2
Forest fires?
Fire suppression
mechanisms must
stop a 1-d front.
Burnt regions are 2-d
Forest fires?
Geography could make
 <2.
California geography:
further irresponsible speculation
• Rugged terrain, mountains, deserts
• Fractal dimension   1?
5
10
California brushfires
4
10
=1
3
10
2
d=2
10
SOC FF
1
10
d=1
0
10
0
10
1
10
2
10
3
10
4
10
5
10
6
10
10
Power system
=1
10
10
10
3
2
1
0
10
4
10
5
10
6
10
7
More complete
website models
(Zhu, Yu)
Can solve this numerically
Almost any
distribution
of user demand
Unfortunately, it
doesn’t fit the PLR
framework, because
Optimize
Throughput
J   pi li
Power law
distribution
of files
 ri  R 
Both are functions of r
Power laws are inevitable.
Gaussian
log(prob>size)
Improved design,
more resources
log(size)
What can we learn from
this simple model?
• P: uncertain events with probabilities pi
• R: limited resources ri to minimize…
• L: loss li due to event i
J   pi li
 ri  R
l (r ) 

r   1

c

• Be cautious about simple theories that ignore design.
• Power laws arise easily in designed systems.
• If p1 >> pn, then
random J >> design J
uniform J >> design J
What can we learn from
this simple model?
• P: uncertain events with probabilities pi
• R: limited resources ri to minimize…
• L: loss li due to event i
J   pi li
 ri  R
l (r ) 

r   1

c

• If the pi are wrong, then maybe design J can be very
bad, and uniform may be better.
• Additional robustness to uncertain pi costs more.
• Exploiting assumptions, makes you sensitive to them.
• More robustness leads to sensitivities elsewhere.
• Robust, yet fragile.
“Robust, yet fragile”
• Robust to uncertainties
– that are common,
– the system was designed for, or
– has evolved to handle,
• …yet fragile otherwise
• This is the most important feature of
complex systems (the essence of HOT).
Example: Auto airbags
• Reduces risk in highspeed collisions
• Increases risk otherwise
• Increases risk to small
occupants
• Mitigated by new
designs with greater
complexity
• Could just get a heavier
vehicle
• Reduces risk without the
increase!
• But shifts it elsewhere:
occupants of other
vehicles, pollution
Biology (and engineering)
• Grow, persist, reproduce, and
function despite large uncertainties
in environments and components.
• Yet tiny perturbations can be fatal
– a single specie or gene
– minute quantities of toxins
• Complex, highly evolved organisms and
ecosystems have high throughput,
• But are the most vulnerable in large
extinctions.
• Complex engineering systems have
similar characteristics
Robustness
Complexity
Actuators Uncertainty
Actuators
Basic functionality
Sensors
Robustness
Sensors
Actuators Uncertainty
Actuators
Sensors
Basic functionality
Sensors
Complexity is dominated by
Robustness
(through regulatory feedback networks)
Scientific research has
focused almost
exclusively on this.
Basic functionality
Scientific research has
focused almost
exclusively on this.
Basic functionality:
Devices, components,
materials
Ators
Basic functionality:
Devices, components,
materials
Sensors
Actuators Uncertainty
Sensors
Basic functionality:
Devices, components,
Actuators
materials
It’s way past time to get some balance.
Turbulent
Shear flows
coupling
Tight
Telephony
Organisms
Power
grid
Ecosystems
Internet
Post
office
Loose
Ideal
gas
Homogeneous
Socioeconomic
systems
Heterogeneous
Uncertainty
and
Robustness
Complexity
Interconnection/
Feedback
Dynamics
Hierarchical/
Multiscale
Heterogeneous
Nonlinearity
Control
Theory
Computational
Information
Theory
Theory of
Complex systems?
Complexity
Dynamical
Systems
Statistical
Physics
Prospects
• Tremendous complex systems challenges in
engineering and biology.
• Unprecedented opportunities.
• Need for more coherent and integrated
theoretical framework.
• Past failures were (somewhat) necessary
explorations.
• We should be cautious but hopeful.
• What if we just do more of the same?