Transcript No Slide Title

SAMAN: Simulation
Augmented by Measurement
and Analysis for Networks
John Heidemann
28 September 2000
PIs: Heidemann, Deborah Estrin, Ramesh Govindan, Ashish Goel
Students: Kun-chan Lan, Xuan Chen, Debojyoti Dutta
USC/ISI and UCLA
NMS Albuquerque PI Meeting / Sep. 2000
1
SAMAN Challenge
• Network robustness is a key challenge
facing the Internet:
– Understanding, predicting and avoiding failures
– Understanding, predicting and avoiding
cascading failures
– Planning failure recovery strategies
• SAMAN will apply network simulation to
address these problems
NMS Albuquerque PI Meeting / Sep. 2000
2
“the Internet”
Example Scenario 1
C1
C2
Clients
Network
Provider
• What if the blue link
becomes overloaded?
– Today: discover the
symptom (high loss found
through manual monitoring)
• SAMAN will help identify
the cause:
– Change in C2 traffic mix?
– Interactions between C1
and C2 traffic?
 Need good traffic models
NMS Albuquerque PI Meeting / Sep. 2000
3
“the Internet”
Example Scenario 2
C1
C2
Clients
Network
Provider
• What if the green router
goes down? (DDoS?)
• May produce cascading
failure (blue link)
• SAMAN will support
prediction, understanding,
and avoidance of
cascading failures
 Need to explore correct
part of large space of
simulations
NMS Albuquerque PI Meeting / Sep. 2000
4
Specific Failure Conditions
• Fail-stop failures due to external events
– accidental (backhoes) or intentional
• Traffic overload
– Loss rates higher than p
• Good ISPs consider p>1% serious
– Loss rates map non-linearly into performance
degradation and load
– Benign (simple overload), unexpected (traffic shift), or
malicious (DDoS)
• Current challenge: failure propagation (cascades,
delayed convergence, etc.) [Shaikh00a,Labovitz00a]
NMS Albuquerque PI Meeting / Sep. 2000
5
goodput
Why Simulation?
load
Answer “what if?”
For protocols, scales, scenarios outside experimentation.
(But depends on good models in interesting part of space.)
NMS Albuquerque PI Meeting / Sep. 2000
6
Agenda
• Challenges
• SAMAN in NMS
– Applications
– Technologies
• Early results
• Potential collaborations
NMS Albuquerque PI Meeting / Sep. 2000
7
SAMAN Applications
• Failure prediction:
– Understanding and reproducing protocol
behavior under extreme conditions
– Network early warning system
– Tools to automatically generate models
NMS Albuquerque PI Meeting / Sep. 2000
8
Protocol Robustness
• Reliable networks demand reliable protocols
• How do individual protocols behave near the edge
of their operating limits:
– What conditions are important to study?
– Are simple protocol improvements possible?
• How do protocols interact in extreme conditions:
– How do individual and aggregate behavior relate?
– When does individual failure trigger cascading failure?
NMS Albuquerque PI Meeting / Sep. 2000
9
Network Early-Warning
Systems
• Tools to predict imminent network failures
– Trigger preventive or corrective actions
• Clear mappings from tools to specific failures
– Many current tools do local measurements
– Are measurements topologically or temporally related?
• Minimize control loop
– Performance, understandability, deployability…
NMS Albuquerque PI Meeting / Sep. 2000
10
Model Generation Tools
• Tools to automatically configure simulation
models from network measurements
– Integrate data from multiple network points
– Serve as input to other portions of work
– Validated across multiple time-scales
• Build on library of validated simulation
models
NMS Albuquerque PI Meeting / Sep. 2000
11
Agenda
• Challenges
• SAMAN in NMS
– Applications
– Technologies
• Early results
• Potential collaborations
NMS Albuquerque PI Meeting / Sep. 2000
12
SAMAN Technologies
• Just-in-time model generation
– Accurate traffic models
• Analysis-informed simulation
– Constrain parameter search space
• In a robust simulation environment
– Build on widely-used ns platform
NMS Albuquerque PI Meeting / Sep. 2000
13
Model Generation
• Application-driven (structural) models
– Capture application-level dynamics (feedback, user
behavior)
– Validated, applicable across range of time-scales
• Network measurements to parameterize models
– Integrate data from multiple measurement points
• Resulting in just-in-time models
– Network admins can measure and parameterize models
NMS Albuquerque PI Meeting / Sep. 2000
14
Analysis-Informed Simulation
• Failure analysis spans huge parameter space
– Most of space is uninteresting
• Analysis-informed simulation
– Rapid analytic pre-simulation pass categorizes
scenario as uninteresting (clearly out of scope)
or interesting
– Focus detailed simulation on interesting
scenarios
NMS Albuquerque PI Meeting / Sep. 2000
15
Ns Simulation Environment
• Builds on rich ns simulation environment
– Wired and wireless (radio and satellite)
– Robust protocol library: many TCP variants, multicast, …
– Validation experience and test suite
• 648 scenarios in 58 categories
– Multiple levels of abstraction
• packet-level and abstractions eliminating per-hop routing,
multicast tree formation, mixed abstract/detailed sims, etc.
– Emulation: mix real-world and virtual nodes
– Broad community support and use
• ns-users mailing list: >1000 hosts (~institutions), >8000 e-mail
addresses (~users)
NMS Albuquerque PI Meeting / Sep. 2000
16
Large Simulations
• Evaluating scalability in
single dimension very risky
– many dimensions: nodes, users,
multicast senders vs. recievers,
protocol agents, traffic volume
– understanding is often
bottleneck
• Parallelism
– sometimes key…if one
simulation has the answer
– don’t ignore free parallelism if
multiple simulations needed
(ex. vary parameters, replicate
results)
• Abstraction is critical to large
and fast network sim:
– ns went from 100s to 1000s by
tuning [on desktop hardware], but
1000s to 10000s with abstractions
– many abstractions:
• centralizing computations (unicast
and multicast routing, etc.)
• packet delivery abstraction (trains,
end2end delivery, fluid flow)
• protocols abstractions (FSA TCP,
etc.)
• mixed abstract/detailed sims
NMS Albuquerque PI Meeting / Sep. 2000
17
Agenda
• Challenges
• SAMAN in NMS
– Applications
– Technologies
• Early results
• Potential collaborations
NMS Albuquerque PI Meeting / Sep. 2000
18
Early Results
• Current focuses:
– Reproducing failure scenarios in simulation
– Multi-scale, application-driven traffic models
– Pre-simulation scenario filtering
NMS Albuquerque PI Meeting / Sep. 2000
19
Early Results
• Current focuses:
– Reproducing failure scenarios in simulation
– Multi-scale, application-driven traffic models
– Pre-simulation scenario filtering
NMS Albuquerque PI Meeting / Sep. 2000
20
Modeling Real-Audio Traffic
• Why real audio?
– Example of a streaming media protocol
– Very different from TCP
– Possibly representative of future streaming
media (certainly more representative than TCP)
• Why now?
– Help develop tools for multi-scale models
– Modeling protocol effects without source code
NMS Albuquerque PI Meeting / Sep. 2000
21
Basic R-Audio Behavior
• Constant bit-rate
time-sequence
plot of
single
flow
• … or not?
mean and quartiles
of 1200 flows
(mean is smooth,
quartiles at multiples
of 1.8s)
NMS Albuquerque PI Meeting / Sep. 2000
22
R-Audio Under the Microscope
• More complex internal
structure
• Demonstrates
importance of
studying protocols at
multiple time-scales
• Able to capture
internal structure after
iteration
bursts
NMS Albuquerque PI Meeting / Sep. 2000
1.8s inter-burst
interval
23
R-Audio: Time-Variance Plot
trace
model
noticeably less
variance at key scales
(1.8, 3.6, etc.)
NMS Albuquerque PI Meeting / Sep. 2000
24
R-Audio: Scaling Plot
trace
NMS Albuquerque PI Meeting / Sep. 2000
model
25
R-Audio Experiences and Plans
• Currently validating model
– stats seem promising
– validation against additional traces in progress
• Next steps:
– Rapid model parameterization
– Apply tools to complex models (mixed traffic)
– Apply models to NMS challenge problem
NMS Albuquerque PI Meeting / Sep. 2000
26
Early Results
• Current focuses:
– Reproducing failure scenarios in simulation
– Multi-scale, application-driven traffic models
– Pre-simulation scenario filtering
NMS Albuquerque PI Meeting / Sep. 2000
27
Agenda
• Challenges
• SAMAN in NMS
– Applications
– Technologies
• Early results
• Potential collaborations
NMS Albuquerque PI Meeting / Sep. 2000
28
Potential Collaborations
• NMS can use models (ex. real audio)
– In public ns releases now
– Could be ported to other simulators
• Model parameterization could use NMS
measurement tools
• Collaborative addition of NMS work into ns
– Traffic, topology models
– Simulation optimizations and abstractions
• Non-NMS projects (STRESS, etc.)
• Other opportunities?
NMS Albuquerque PI Meeting / Sep. 2000
29
More information
• http://www.isi.edu/saman/
NMS Albuquerque PI Meeting / Sep. 2000
30