Transcript Alpha-Beta Network Model

Multiscale Traffic Processing Techniques
for Network Inference and Control
R. Baraniuk R. Nowak E. Knightly R. Riedi
V. Ribeiro S. Sarvotham A. Keshavarz
Rice University
NMS PI meeting
Rice University, SPiN Group
Chicago
November 2002
Signal Processing in Networking
spin.rice.edu
Objective: Reduced complexity, multiscale
link models with known accuracy
Innovative Ideas
Multifractal analysis
Multiplicative modeling
Multiscale queuing
Chirps for probing
Impact
Congestion control
performance improvement
Dynamical streaming
monitoring/anomaly detection
Rice University, SPiN Group
spin.rice.edu
Effort 1
Chirp Probing
always-on, non-intrusive
on-line decision
anomaly detection
Rice University, SPiN Group
spin.rice.edu
Efficient probing: PathChirp
• Traditional probing paradigm:
– Produce (light) congestion
– PacketPair:
• Sample the traffic
– Pathload:
flood at variable rate
• intolerable level of congestion
– TOPP:
• PacketPairs at variable spacing
• New:
– PathChirp:
• Variable rate within
a train of probes
• More efficient, light
Rice University, SPiN Group
spin.rice.edu
PathChirp Performance
• Real world tool available
• performs comparably to
– PathLoad
– PacketPair
– TOPP
• …at smaller probing rate
• …more robust to bursty traffic
conditions
• Ongoing work:
– Exploit dispersion information
to become robust against
multiple hops
Rice University, SPiN Group
spin.rice.edu
Non-intrusive: Queue Samplers
• Traffic arrival process and
Queue process equivalent
• Advantages of sampling the Queue
– Slim probe packets
• smaller probing rate or higher accuracy
– Robust to Multi-Hop
• Delay simply accumulates while
• …probe dispersion is vulnerable
(pair-compression at fast links)
• Delphi:
– further advantage through
Error against scale
Traffic error
Queue error
Traffic error
Queue error
• Model-based inference (MSQ)
• Overcomes uncertainty principle
• Uniform / Back2Back / variable rate
50% util
Traffic error
• Ongoing work:
– optimal probing pattern
30% util
Queue error
– optimal probing paradigm
• Traffic samplers / Queue samplers / Delphi
Delphi error
80% util
– Integration into network simulators
Rice University, SPiN Group
spin.rice.edu
Multiple Hops: Collaboration
• Monitor packets at intermediate point of path
– IP-tunneling
– Coordinated Measuremens (IPEX: Krishnan)
• Integrating probing tools into simulators
– JavaSim (UIUC: Hou)
– NS-2 (ISI: Heidemann)
• Probing buffer at core router
– Passive inference (Sprint Labs: Moon)
Rice University, SPiN Group
spin.rice.edu
Effort 2
Connection-level Analysis and
Modeling of Network Traffic
understanding the cause of bursts
control and improve performance
detect changes of network state
Rice University, SPiN Group
spin.rice.edu
Non-Gaussianity and Dominance
Systematic study: time series separation
• For each bin of 500 ms:
remove packets of the ONE strongest connection
• Leaves “Gaussian” residual traffic
99%
=
Mean
Overall traffic
Rice University, SPiN Group
+
1 Strongest connection
Residual traffic
spin.rice.edu
Origins of Alpha Traffic
• Mostly TCP
– flow & congestion controlled
• HTTP, SMTP, NNTP, etc.
• Several gateways, Abilene Core
• Alpha connections tend to have the same sourcedestination IP addresses.
• Any large volume connection with the same e2e IP
addresses as an alpha connection is also alpha.
 Systematic cause of alpha:
Large file transfers over high bandwidth e2e paths.
Rice University, SPiN Group
spin.rice.edu
Simple Connection Taxonomy
Bursts arise from large
transfers over fast links.
This is the only systematic reason
cwnd
bandwidth
RTT
Rice University, SPiN Group
spin.rice.edu
Cwnd or RTT?
Colorado State University trace, 300,000 packets
1/RTT (1/s)
10
10
10
Beta
10
Alpha
1
cwnd (B)
10
2
0
10
10
5
Beta
Alpha
4
3
peak rate
 cwnd
1/RTT
2
-1
10
3
10
4
10
peak-rate (Bps)
5
10
Correlation coefficient=0.68
6
10 3
10
10
4
10
5
peak-rate (Bps)
10
Correlation coefficient=0.01
RTT has strong influence on bandwidth and dominance.
Rice University, SPiN Group
spin.rice.edu
6
Examples of Alpha/Beta Connections
one alpha connection
(96078, 196, 80, 59486)
one beta connection
1400
1400
1200
1200
packet size
size (bytes)
(bytes)
packet
1000
1000
800
800
600
600
forward direction
forward direction
400
400
200
200
0
0
reverse direction
-200
-200
0.4
0.6
41.3
0.8
1
reverse direction
1.2
41.35
1.4
1.6
1.8
41.4
2
2.2
2.4
41.45
packet arrival
arrivaltime
time(second)
(second)
packet
Alpha connections burst because of
short round trip time, not large TCP window
Appear to be flow (not congestion) controlled
Rice University, SPiN Group
spin.rice.edu
Alpha traffic:
Flow or Congestion Control?
• Alpha connection show
– unusually small advertised window
– drastic drop in advertised window (to zero)
– …which correlates with burst arrival
• Alpha connections with same END host
– Share same high peak rate
– End-host becomes bottleneck, network does not control
 TCP is known to be unfair to long RTT connections
 TCP appears to foster also the Alpha bursts
 What determines the alpha-peak rates?
Rice University, SPiN Group
spin.rice.edu
Modeling Alpha Traffic
• ON/OFF model revisited:
High variability in connection rates (RTTs)
Low rate = beta
+
High rate = alpha
+
+
=
=
fractional Gaussian noise
stable Levy noise
Impact: Network Simulation
• Simulation: ns topology to include alpha links
Simple: equal bandwidth
Realistic: heterogeneous
end-to-end bandwidth
• Congestion control
• Design and management
Rice University, SPiN Group
spin.rice.edu
Impact: Traffic simulation
- Classical ON/OFF model
captures only
- Gaussian Beta-component
- Large scale fluctuations
- Variable rate ON/OFF
captures also
- burstiness
Realistic traffic contains
ON/OFF sources with
heterogeneous rates
Rice University, SPiN Group
spin.rice.edu
Ongoing work: simulation
• Relate physical network parameters to traffic
dynamics
–
–
–
–
File size distributions
Network topology / RTT distribution
Network devices (links, servers)
Congestion control vs flow control
• Predict performance from simple set of parameters
• Integration into network simulators to abstract
network clouds
Rice University, SPiN Group
spin.rice.edu
Impact: Performance
• Beta Traffic rules the small Queues
• Alpha Traffic causes the large Queue-sizes
(despite small Window Size)
All Alpha Packets
Rice University, SPiN Group
Queue-size with Alpha Peaks
spin.rice.edu
Ongoing Work
• Total true Queue:
– Q = Qa+Qb (contributions from alpha and beta
component)
• Model assumption:
– Alpha=stable, Beta=fractional Brownian motion
• Optimal setup of two individual Queues
driven by alpha and beta components to
come closest to Qa and Qb
• quantify impact of components on queuing
Rice University, SPiN Group
spin.rice.edu
Separation on Connection Level
• Alpha connections: dominant. Properties:
–
–
–
–
–
–
Few, light load
Responsible for violent bursts
Responsible for large queuing delays
Peak rate > mean arrival rate + 1 std dev
Typically short RTT
Typically FLOW-CONTROLLED (limited at receiver)
• Beta connections: Residual traffic
– Main load
– Gaussian, LRD
– Typically bandlimited at bottleneck link
• C+ analyzer (order of sec)
Rice University, SPiN Group
spin.rice.edu
Summary: Goals
• Network/user-driven traffic model
– Obtain performance parameters directly
from network and user specifications
• Non-intrusive, always-on, global traffic estimation
– Anomaly detection in network (change in network state)
Collaborations & Tech Transfer
•Monitoring tool using chirps (Caida, SLAC, Sprint
•Verification/”internal” measurements using
[students])
–IP-tunneling, coordinated measurements (IPEX)
–Integration of PathChirp into network simulators (UIUC, ISI)
•Online traffic probing and analysis tools for
–Integrated demo (GaTech)
–Demystify self-similarity (UC Riverside)
Rice University, SPiN Group
spin.rice.edu
spin.rice.edu
Rice University, SPiN Group
spin.rice.edu