Transcript Large vs. small

Building a Campus Network
Monitoring System
for Research
Sue B. Moon
EECS, Division of CS
Is Campus Network
a Good Place to Monitor?
 1GE/10GE/100GE link speed
comparable
to backbone networks
• BcN (Broadband convergence Network) will turn
access networks to backbone networks.
• B/W distinction between access and backbone may
no longer exist.
 Source of “innovation”
research
communities “invent” new things
• first users of new applications
• new attacks / vulnerable machines
• extreme types of usage
2
Speed Comparison
Last
hop
1980
1990
2000
LAN/MAN
Long-Haul
T1/T3
64Kbps 10/100M
OC-3 ~ OC-12
Ethernet
FDDI rings
10
100M/1GE/10G OCMbps
E
48/192/768
(2.5/10/40G)
3
Is Campus Network
a Good Place to Monitor?
 Bureacratic overhead
Lower
bar to tap (or so I believe)
 Less sensitive to business
4
Goals
 Share data with researchers
Gigascope
with AT&T, UMass, ...
KISTI
5
Data to Collect
 Data Plane
Packet
traces
NetFlow data
Sink hole data
 Control Plane
Routing
protocol tables/updates
Router configuration
SNMP statistics
6
Monitoring System Infrastructure
 Components
DAGMON
PCs
Storage
Analysis
platform
7
Projects in Mind
 Port scanning activities
 General study on security attacks
8
Overview
 Definition and implications of small-time
scaling behaviors
 Queueing delay vs. Hurst parameter
 Observations from high-speed links
 Flow composition
Large
vs. small
Dense vs. sparse
 Summary
 Future directions
9
Scaling Behaviors of
Backbone Traffic
 What does it mean?

Fluctuations in traffic volume over time
• e.g. measured in 10ms, 1s or 1min intervals
 Large-time scale (> 1 sec): Hurst parameter
0.5 <= H < 1, measure of “correlation” over time
 H > 0.5, long-range dependent or asym. selfsimilar

 Small-time scale (1-100 ms):

Important to queueing performance, router
buffer dimensioning
10
How to Represent Time Scales
 Dyadic time index system
 Fixing a reference time scale T0
j
 At scale j (or –j): Tj = T0 / 2
 t j,k = (k Tj, (k+1) Tj)
 W j,k = 2j/2 (Tj+1,2k - Tj+1,2k+1)
11
Scaling Exponent and Wavelet
Analysis
 Energy function: E j  E[W j ,k ]
 Energy Plot: log 2 E j vs. -j
2
 Second-order (local) scaling exponent: h

Suppose spectrum density function has the form
Γ (ν) ~ | ν |12 h , in frequency range ν [ν1,ν2 ]
then log 2 E j ~  j  (1  2h)  constant, j  [ j2 , j1 ]
 Long range dependence (asym. self-similar)
process:
log 2 E j ~  j  (1  2 H )  constant, j   with H  0.5
 Fractional Brownian Motion: single h for all
scales
12
Hurst Parameter & (Avg.)
Queueing Delay

Poisson model
D

(1  ρ 
~
1
FBM model
(Fractional Brownian Motion)
H: Hurst parameter
Var ( X
D
~
( m)
)~m
(1  ρ 
2 H 2
 H
1 H
H =0.5 => Poisson
13
Traces
 Collected from IPMON systems
OC3
to OC48 links
Peer, customer, intra-POP inter-router, interPOP inter-router links
GPS timestamps
40 bytes of header per packet
Trace 1: domestic tier-2 ISP (OC12-tier2dom)
Trace 2: large corporation (OC12-corp-dom)
14
Energy Plots
Trace 1
Trace 2
15
Observations
 Large time scale
 Long-range
dependent
 asymptotically “self-similar”
 Small time scale: more “complex”
 Majority
traces: uncorrelated or nearly
uncorrelated
• Fluctuations in volume tend to be
“independent”
 Some
traces: moderately correlated
16
Traffic Composition
 How is traffic aggregated?
By
flow size
• Large vs. small
By
flow density
• Dense vs. sparse
17
Flow Composition: Large vs. Small
18
Byte Contribution
19
Impact of Large vs. Small Flows on
Scalings
large: flow size > 1MB; small: flow size < 10KB
Flow size alone does not determine small-time scaling
behaviors
(cf. large-time scaling behaviors)
20
Dense vs. Sparse Flows
 Density defined by inter-arrival times
21
PDF of packet inter-arrival times
22
Impact of Dense vs. Sparse Flows on
Scalings

dense: dominant packet inter-arrival time 2ms;
sparse: > 2ms
Flow density is a key factor in influencing small-time
scalings!
23
Effect of Dense vs. Sparse Flow
Traffic Composition
Semi-experiments using traces: vary mixing of dense/sparse flows
OC12-tier2-dom
OC12-corp-dom
24
Where Does Correlation in
Traffic Come From?
 Effect of TCP window-based feedback control
 Sparse flows:

packets from small flows arrive “randomly”
 Dense flows:
Packets
injected into network in bursts (window)
Burst of packets arrive every round-trip-time(RTT)
 Speed and location of bottleneck links matters!
Larger
bottleneck link => larger bursts
Deeper inside the network => more corr. flows
25
So Within Internet Backbone Network …
 Facts about today’s Internet backbone
networks
bottleneck links reside outside backbone networks
 bottleneck link speeds small relative to backbone
links

High degree of aggregation of mostly independent
flows!
 Consequences:

Queueing delay likely negligible!

Can increase link utilization
• And easier to model and predict
• More so with higher speed links (e.g., OC192)
 Only
higher degree of aggregation of
independent flows
Be cautious with high-speed “customer” links!
26
Will Things Change in the Future?
 But what happens if

More hosting/data centers and VPN customers
directly connected to the Internet backbone?
• have higher speed links, large-volume data transfers

User access link speed significantly increased?
• e.g., with more DSL, cable modem users

Larger file transfer?
• e.g. distributed file sharing (of large music/video files)

UDP traffic increases significantly?
• e.g. Video-on-Demand and other real-time applications
27
Status Quo of IP Backbone
 Backbone network well-provisioned
High-level
of traffic aggregation
• Negligible delay jitter
Low
average link utilization
• < 30%
Protection
in layer 3
 QoS?
Not
needed inside the backbone
Is it ready for VoIP/Streaming media?
• Yet to be decided
28
Future Directions in
Networking Research
 Routing
No
QoS with current routing protocols
 Performance issues
BcN:
bottleneck moves closer to you!
 Wired/wireless integration
Sensitivity
to loss
E2e optimization
 Security
IPv6
vs NAT
29
Fraction of Packets in Loops
30
Single-Hop Queueing Delay PDF
31
Multi-Hop Queueing Delay CCDF
Data Set 3, Path 1
32
Multi-Hop Queueing Delay
Data Set 3
33
Impact of Bottleneck Link Load
90
34
Variable Delay Revisited: Tail
Data Set 3, Path 1
35
Peaks in Variable Delay
36
Closer Look
 Queue
Build up &
Drain
37
Backup Slides
Impact of RTT
39
Impact of Traffic Composition
Trace 1
Trace 2
40
Small-Time Scalings of
Large vs. Small Flows
41
Small-Time Scalings of
Dense vs. Sparse Flows
42
Small-Time Scalings of
Dense/Sparse Large Flows
43
Small-Time Scalings of
Dense/Sparse Small Flows
44
Fourier Transform Plots
Trace 1
Trace 2
45
Gaussian?
 Backbone traffic
close
to Gaussian due
to high-level of
aggregation
 Kurtosis
Close
to 3
 Skewness
Close
to 0
Trace 1
46
Illustrations of Small Time Scale
Behaviors
NYC  Nexxia (OC12)
(Nearly) Uncorrelated
@Home  PEN (OC-12)
Moderately Correlated
47
What Affect the Small-Time
Scalings?
 composition of small vs. large flows
 “correlation structure” of large flows
48
Flow (/24) Size & Byte Distribution
in 1-min Time Span
49
Where Does Correlation in Traffic
Come From?
 Effect of TCP window-based feedback control
 Small flows:

packets from small flows arrive “randomly”
 Large flows:
Packets
injected into network in bursts (window)
Burst of packets arrive every round-trip-time(RTT)
 Speed and location of bottleneck links matters!
Larger
bottleneck link => larger bursts
Deeper inside the network => more corr. flows
50
Three Distinct Time Scales: HTTP
TCP Flows
51
Avg. Rate Distribution of Large TCP Flows
52
So Within Internet Backbone
Network …
 Facts about today’s Internet backbone networks
bottleneck
links reside outside backbone networks
bottleneck link speeds small relative to backbone links
High degree of aggregation of (mostly) independent flows!
 Consequences:
Queueing
delay likely negligible!
• And easier to model and predict
• More so with higher speed links (e.g., OC192)
Can increase link utilization (while ensure little queueing)
• Only higher degree of aggregation of independent flows
Be cautious with high-speed “customer” links!
53
Will Things Change in the Future?
 But what happens if

More hosting/data centers and VPN customers
directly connected to the Internet backbone?
• have higher speed links, large-volume data transfers

User access link speed significantly increased?
• e.g., with more DSL, cable modem users

Larger file transfer?
• e.g. distributed file sharing (of large music/video files)

UDP traffic increases significantly?
• e.g. Video-on-Demand and other real-time applications
54
How Large Flows Affect
Small Time Scalings?
55
Degree of Aggregation & Burst Sizes
over Time Scales
56
Autocovariance of “Active” Flows
over 1ms
57
Effect of TCP: Large vs. Small
Flows
 Three Distinct Time Scales



Session time scale: on-off sessions
• file sizes, applications
RTT Time Scale:
• TCP window-based feedback
control
• window size: burst of packets
• RTT: prop. delay (+ random
variable)
Inter-packet time scale
• packet sizes
• TCP: ack-paced packet injection
 Bottleneck Link & Queueing



session duration
clustered bursts, RTT
inter-packet arrival times
58
Effect of Aggregation:
(In-)dependence?
 aggregating different (presumably independent) flows
 intermixing bursts and packets from different flows
Introduce independence (randomness) in the
aggregate,
but also can induce “correlation” (due to TCP)!

depending on where bottleneck link is!
 different effects may manifest in different time
scales!
59
Summary: Time and Space of
Observation
 What time scale we observe traffic matters!
 Where we observe traffic also matters!
 Large vs. small time scale behaviors
Large time scale:
• superposition of many independent on-off
sessions
• heavy-tail file size distribution => self-similar
scaling
Small
time scale: more “complex”!
• degree of aggregation
• composition of large vs. small flows
• correlation structure of bursts (of large flows)
60
Small-Time Scaling
Behaviors of
Internet Backbone
Traffic
Zhi-Li Zhang
U. of Minnesota
Joint work with
Vinay Ribeiro (Rice U.), and
Sue Moon, Christophe Diot (Sprint ATL)
Scaling Exponent and Wavelet
Analysis
 Energy function: E j  E[W j ,k ] Energy log
Plot:
2 E j vs. -j
2
 Second-order (local) scaling exponent: h

Suppose spectrum density function has the form
Γ (ν) ~ | ν |12 h , in frequency range ν [ν1,ν2 ]
then log 2 E j ~  j  (1  2h)  constant, j  [ j2 , j1 ]
 Long range dependence (asym. self-similar)
process:
log 2 E j ~  j  (1  2 H )  constant, j   with H  0.5
 Fractional Brownian Motion: single h for all
scales
 e.g., h for j  J (small - time), and H for j  J (large - time)
 Multi-scale Fractional Brownian: multiple h’s
62
Importance of Scaling
Exponents

Poisson model
D




~
(1  ρ 
1
FBM model
(Fractional Brownian
Motion)
H: scaling
t 2H
exponent
 H
~ (1 ~ρ  1 H
D Var(t)
H =0.5 => Poisson
63
Observations on
OC3/OC12/OC48 Links
 Large time scale
 Long-range
similar
dependent, asymptotically self-
 Small time scale: more “complex”
behavior
 Majority
traces: (nearly) uncorrelated
• fluctuations in volume almost “independent”
 Some
traces: moderately correlated
 Small time scaling behavior: link
specific
 (mostly)
independent of link utilization
64
Illustrations of Scaling
Behaviors
OC3-tier1-dom
OC48-bb-1
(Nearly) Uncorrelated
Slightly Correlated
65
Illustrations of Scaling
Behaviors (cont’d)
OC12-tier2-dom
(Nearly) Uncorrelated
OC12-corp-dom
Moderately Correlated
66
Relation between SDF and
Scaling Exponent
OC12-tier2-dom
OC12-corp-dom
67
Multi-Fractal Scaling Analysis
Based on wavelet partition functions: S j (q)  E | W j ,k |q
log 2 S j (q) ~  j q  q  constant ,  q   q  q / 2, hq   q / q
OC12-tier2-dom
OC12-corp-dom
Linearity of  q => Monofractal scaling
68
Multi-Fractal Scaling Analysis
(cont’d)
Marginal distributions over 4 ms time scale
Kurtosis: 3.04
Skew: 0.2
OC12-Tier2-Dom
Kurtosis: 2.86
Skew: 0.24
OC12-Corp-Dom
Gaussian marginals => Monofractal scaling
69
What affect the small-time
scalings?
 Internet traffic comprised of many individual
flows

e.g., 5-tuple flows
 Flow classifications, based on
Flow size: total bytes belonging to a flow in a time
span
• small vs. large flows
 Flow density: dominant inter-packet arrival times
of a flow
• dense vs. sparse flows

 Traffic composition analysis

Separate aggregate into large/small, dense/sparse
70
Large vs. Small Flows
Based on 5 1-min segment of packet traces, each one hour apart
71
Dense vs. Sparse Flows
“cumulative” packet inter-arrival
times of all flows
72
Impact of Large vs. Small Flows on
Scalings
large: flow size > 1MB; small: flow size < 10KB
Flow size alone does not determine small-time scaling
behaviors
(cf. large-time scaling behaviors)
73
Impact of Dense vs. Sparse Flows on
Scalings

dense: dominant packet inter-arrival time 2ms;
sparse: > 2ms
Flow density is a key factor in influencing small-time
scalings!
74
Effect of Dense vs. Sparse Flow
Traffic Composition
Semi-experiments using traces: vary mixing of dense/sparse flows
OC12-tier2-dom
OC12-corp-dom
75
Where does correlation in
traffic come from?
 Aggregation of relatively large proportion
of dense flows
OC12-corp-dom: >2% dense flows, >15% total
bytes
 OC12-corp-dom: <1% dense flows, < 4% total
bytes

 Density of flows:
 likely
due to bottleneck link speed
coupled with TCP window-based feedback
control

“fatter” bottleneck links => more dense flows
 OC12-corp-dom: connect more high-speed
users
76
So Within Internet Backbone
Network …
 Facts about today’s Internet backbone
networks
bottleneck links reside outside backbone networks
 bottleneck link speeds small relative to backbone
links
High degree of aggregation of (mostly) independent
flows!

 Consequences:

queueing delay likely negligible!

can increase link utilization (while ensure little
queueing)
• and (relatively) easier to model and predict
• more so with higher speed links (e.g., OC192)
• only higher degree of aggregation of independent
77
Will Things Change in the
Future?
 But what happens if
 More
hosting/data centers and VPN
customers directly connected to the
Internet backbone?
• have higher speed links, large-volume data
transfers
 User
access link speed significantly
increased?
• e.g., with more DSL, cable modem users
 Larger
file transfer?
• e.g. distributed file sharing (of large music/video
files)
 UDP
traffic increases significantly?
78