Transcript ppt - the Prescience Lab

An Empirical Study of the
Multiscale Predictability of
Network Traffic
Yi Qiao
Jason Skicewicz
Peter A. Dinda
Prescience Laboratory
Department of Computer Science
Northwestern University
Evanston, IL 60201
1
Talk in a Nutshell
In-depth trace-based study of predictability of
link bandwidth at different resolutions
– Binning and wavelet approximations
• Generalizations very difficult to make
• Aggregation often helps
• Predictability does not monotonically
increase with decreasing resolution
• Predictability largely independent of
mechanism
• Simple models sufficient
2
Outline
• Motivation and Related Work
– MTTA
• Traces
• Binning Approximations and Wavelet
Approximations
• Results
• Conclusions
3
Background
• Why study predictability of network
traffic?
– Adaptive applications
– Congestion Control
– Admission Control
– Network management
• Eventual goal
– Providing application level network traffic
queries to adaptive applications
• Fine-grain app, e.g., Immersive audio
• Coarse-grain app. e.g., Scientific app on grids
4
Message Transfer Time Advisor
(conf_lower, conf_upper, conf_expected) =
MTTA::PredictTransferTime(src_ip_address,
dest_ip_address,
message_size,
transport_protocol,
conf_level);
Target API
Application Query
MTTA
Time for transferring a 10MB
message, confidence level
=0.95 ?
Query Answer
Expected transfer time is 50
seconds, confidence interval
is [45.9 54.1] seconds
• Our contributions here
– Predicting aggregate background traffic
– Dealing with a wide range of time resolutions
5
Our Approach
High-Resolution
Sensor Bandwidth Signal
Network
Predictor
Low-Resolution
Prediction
App
Application
Query
MTTA
Resolution Selection
Query
Answer
High-Resolution
Prediction
6
Multiresolution Views of Resource Signals
• Two Different Approaches
– Binning
• Commonly used by existing network measurement
tools
– Wavelets
• N-level streaming wavelet transform yielding detail
signals and approximation signals
• Wavelet domain enables many useful analyses
7
Questions For This Study
• What is the nature of predictability of
network resource signals?
• How does predictability depend on
resolution?
• What predictive models should be used?
• What are the implications for the MTTA?
8
Tools And Data
• RPS: Resource Prediction System
Toolkit for Distributed Systems
• Tsunami: Wavelet Toolkit for Distributed
Systems
(Publicly Available From Us)
• NLANR Trace Archive
• Internet Traffic Archive
(Publicly Accessible)
9
Relevant Previous Work
• Groschwitz, et al, ARIMA models to predict
long-term NSFNET traffic growth
• Basu, et al, Modeling of FDDI, Ethernet LAN,
and NSFNET entry/exit point traffic
• Leland, et al, Self-similarity of Ethernet traffic
• Wolski, et al, Network Weather Service
• Sang and Li: Multi-step prediction of network
traffic using ARMA and MMPP
– Both aggregation and smoothing increase
predictability
– Our finding: predictability often does not increase
monotonically with smoothing
10
Outline
• Motivation and Related Work
– MTTA
• Traces
• Binning Approximations and Wavelet
Approximations
• Results
• Conclusions
11
Trace Classification and Analysis
Time-series
ACF
Classification
Scheme
Histogram
PSD
Repeated the analysis for a wide-range of resolutions
Conclusions
Large number and high variety of traces
Y. Qiao, and P. Dinda, Network Traffic Analysis, Classification,
and Prediction, Technical Report NWU-CS-02-11, Department
of Computer Science, Northwestern University, January, 2003
12
Traces
Name
NLANR
Number of
Range of
Raw Traces Classes Studied Duration Resolutions
180
1,2,4,…,
1024ms
.125,.25,…,
1024s
12
39
90s
AUCKLAND 34
8
34
1d
BC
4
N/A
4
1h, 1d
7.8125 ms
to 16s
Totals
218
N/A
77
90s
to 1d
1 ms
to 1024 s
13
Outline
• Motivation and Related Work
– MTTA
• Traces
• Binning Approximations and Wavelet
Approximations
• Results
• Conclusions
14
Binning Approximations
• Methodology
– Commonly used by existing network measurement
tools
– Averages over N non-overlapping, power-of-two
bins
1S
8S
128 S
Increasing Bin Sizes
1024 S
15
Wavelet Approximations
• Parameterized by a wavelet basis function
– Equivalent to binning approach when using the
Haar wavelet
Level 2
• Methodology
– N-level streaming wavelet transform
– D8-wavelet were used for our study
Level 1
Level 0
Increasing
Approximation Level
16
Binning
Component
Binning Prediction
Methodology
Prediction
Component
17
Wavelet Prediction Methodology
Wavelet
Component
Prediction
Component
18
Outline
• Motivation and Related Work
– MTTA
• Traces
• Binning Approximations and Wavelet
Approximations
• Results
• Conclusions
19
One-step Ahead Predictions
now
High Resolution
One-step ahead prediction
Low Resolution
One-step ahead prediction
Lower Resolution => Longer Interval Into Future
20
Predictability Ratio
• Predictability ratio = Variance of error
2
signal over variance of resource signal =  e /  2
– Fraction of the “surprise” in the signal left after
prediction
• The smaller the ratio, the better
predictability we have
Resource signal =[1 4 10 9]
Prediction =[2 3 9 10]
Error signal =[1 -1 -1 1]
  18
2
 e  1.33
2
Predictability
Ratio =1.33/18
=0.07389
21
Wide Range of Prediction Models
• Simple Models
– MEAN – long term mean of signal
– LAST – last observed value as prediction
– BM(32) – average over a history window of optimal size
• Box-Jenkins Models
–
–
–
–
AR(8), AR(32) – pure autoregressive
MA(8) – pure moving average
ARMA(4,4) – autoregressive moving average
ARIMA(4,1,4), ARIMA(4,2,4) – integrated ARMA
• Long-range dependence model
– ARFIMA(4,-1,4) – “Fractionally integrated” ARMA
• Nonlinear model
– MANAGED AR(32) – TAR variant
22
Binning Study on NLANR Traces
LAST
BM(32)
With AR Comp
– Generally unpredictable
– Predictability worse at coarser
granularities
Log Scale
23
Binning Study On BC Traces
– Weak predictability
– Predictability not always
LAST
monotonically increasing
MA(8)
with smoothing
With AR Comp
24
Results for AUCKLAND Traces
• General predictability of traces
• How predictability changes with different
resolutions
3 different behaviors for binning study, and
4 different behaviors for wavelet study
• Relative performance of different
predictive models
25
AUCKLAND Behavior 1 - Binning
– 14 of 34 traces
– Predictability converges to a
high level with increasing bin
size
– Commensurate with
conclusions from earlier papers
LAST
BM(8)
MA(8)
With AR Comp
26
AUCKLAND Behavior 1 - Wavelet
– 7 of the 34 traces
– Generally shows monotonic
relationship with approximation
levels except outliners
– Relatively uncommon behavior
LAST
MA(8)
With AR Comp
27
AUCKLAND Behavior 2 - Binning
– 15 of 34 traces
– Presence of sweet spot - optimal bin
size that maximizes predictability
– Contradicts earlier work
MA(8)
Sweet Spot
LAST
BM(8)
With AR Comp
Max
Predictability
28
AUCKLAND Behavior 2- Wavelet
– 13 of the 34 AUCKLAND traces
– a sweet spot at a particular
scale
– Contradicting earlier work
Sweet Spot
MA(8)
LAST
With AR Comp
Max
Predictability
29
AUCKLAND Behavior 3 - Binning
MA(8)
LAST BM(8)
With AR Comp
– 11 of the 34 traces
– Non-monotonic relationship between
scale and predictability
– Predictability weaker than behavior 1
and 2
30
AUCKLAND Behavior 3 - Wavelet
– Uncommon, 5 of 34 traces
– Multiple peaks and valleys at
different approximations
– Predictability not as strong
as the earlier two classes
MA(8)
MA(8)
LAST
With AR Comp
31
AUCKLAND Behavior 4 - Wavelet
– 3 of the 34 traces
– Predictability ratio plateaus and becomes
more predictable at coarsest resolutions
– Behavior did not occur in binning study
LAST
MA(8)
With AR Comp
32
Conclusions
In-depth trace-based study of predictability of
link bandwidth at different resolutions
– Binning and wavelet approximations
• Generalizations very difficult to make
• Aggregation often helps
• Predictability does not monotonically
increase with decreasing resolution
• Predictability largely independent of
mechanism
• Simple models sufficient
33
Implications for Message
Transfer Time Advisor (MTTA)
• Online multiscale prediction system to
support MTTA is feasible
– Likely to be more accurate for WAN traffic
• Often a natural time scale for prediction
– Adaptation likely best here
• Prediction system must itself adapt to
changing network behavior
34
Current and Future Work
Wide-area TCP throughput characterization and prediction
D. Lu, Y. Qiao, P. Dinda, and F. Bustamante, Characterizing and Predicting
TCP Throughput on the Wide Area Network, Technical Report NWU-CS-04-34,
Department of Computer Science, Northwestern University, April, 2004.
Wide-area Parallel TCP throughput modeling and prediction
D. Lu, Y. Qiao, P. Dinda, and F. Bustamante, Modeling and Taming Parallel
TCP on the Wide Area Network, Technical Report NWU-CS-04-35, May, 2004
Tsunami Wavelet Toolkit
J. Skicewicz, P. Dinda, Tsunami: A Wavelet Toolkit for Distributed Systems,
Technical Report NWU-CS-03-16, Department of Computer Science,
Northwestern University, November, 2003.
35
For More
Information
• Prescience Lab
– http://plab.cs.northwestern.edu
• Tsunami and RPS Available for Download
– http://rps.cs.northwestern.edu
• Contact
– [email protected]
36
AUCKLAND Behavior 1-Binning
– 14 of 34 traces
– Predictability converges to a high
level with increasing bin size
– Commensurate with conclusions
from earlier papers
37
AUCKLAND Behavior 1-Wavelet
– 7 of the 34 traces
– Generally shows monotonic relationship
with approximation levels except outliners
– Relatively uncommon behavior
38
AUCKLAND Behavior 2-Binning
– 15 of 34 traces
– Presence of sweet spot, an optimal
bin size that maximize predictability
– Contradicts the conclusion of earlier
works
39
AUCKLAND Behavior 2-Wavelet
– 13 of the 34 AUCKLAND traces
– a sweet spot at a particular
approximation scale for maximum
predictability
– Contradicting earlier work
40
AUCKLAND Behavior 3-Binning
– Uncommon, 5 of 34 traces
– Multiple peaks and valleys at
different bin sizes
– Predictability not as strong as the
earlier two classes
41
AUCKLAND Behavior 3-Wavelet
– 11 of the 34 traces
– Non-monotonic relationship between the
approximation scale and the predictability
– Predictability weaker then class 1
42
AUCKLAND Behavior 4-Wavelet
– 3 of the 34 traces
– The predictability ratio reaches plateaus and
becomes more predictable at coarsest resolutions
– A behavior not happened for binning study
43