Transcript ppt

TAPAS:
A Research Paradigm for the Modeling,
Prediction and Analysis of Non-stationary
Network Behavior
Almudena Konrad
PhD Candidate at UC Berkeley
[email protected]
Sahara Retreat, June, 2002
Advisor: Anthony Joseph
Outline
•
•
•
•
Introduction
The Problem
Existing Work
Our Solution
– Modeling of Network Measurements Through Data Preconditioning
• Modeling Methodology Applied to Wireless Networks
• Work in Progress
• Summary
2
Introduction
This talk will demonstrate that
the modeling of network characteristics
through data preconditioning,
will provide accurate network models and
optimal network protocol design compared to
traditional approaches.
3
The Problem
Modeling of Network Characteristics:
Application of Traditional Models
• Network characteristics experience
– Complex patterns and dynamic time varying statistics
• Traditional models require stationary statistics
– Non-time varying statistics
• Current approach generates poor model approximations
4
Example of the Modeling Problem
Modeling Wireless Error
• Design and evaluation of wireless protocols and applications
– On “live” networks (eg:GPRS)
– Simulators: accurate models for the error and loss process
• Traditional approach to channel modeling
– Application of traditional DTMC to collected error traces
• Markov models require stationary statistics
– Wireless channels experience time varying effects
• Traditional channel models
– Bernoulli: Independent model
– Gilbert: two-state DTMC
– Higher order Markov: N states
5
Existing Work on Modeling of
Network Measurements
Modeling IP Losses
• Bolot et al. (INRIA,1999)
– Model loss process of audio packets to determine error control
schemes
– Use Gilbert model
• Yajnik et al. (University of Massachusetts, 1999)
– Use third order Markov chain to model packet loss in multicast
networks
– Remove part of the data that experience non stationary error
behavior
6
(Continuation) Existing Work
Modeling Wireless Errors
• Nguyen et al. (UC Berkeley, 1996)
– WLAN error traces
– Improve two-state Markov model
• Zorzi et al. (UC San Diego, 1998)
– Use Gilbert model
– Claim that higher order Markov models are not necessary
– Results are drawn by applying models to artificial traces
• Willig et al. (Tech U of Berlin, 2001)
– Special class of Markov models
– Industrial WLAN traces
– High complexity, 24 states
7
Our Solution:
Propose Modeling Methodology
Modeling through data preconditioning
• Collect network characteristic trace
• Identify data patterns (stationary behavior)
• Precondition the data to fit traditional models
– Associate a state with each pattern
– Calculate probability distribution for each state
– Determine transition probabilities among states
Collected
Trace
Sub-trace 1
Sub-trace 2
Sub-trace 3
8
Outline
• Introduction
• The Problem
• Existing Work
• Our Solution
– Modeling Through Data Preconditioning
• Modeling Methodology Applied to Wireless Networks
• Work in Progress
• Summary
9
Modeling Methodology
Applied to Wireless
• Collect and analyze error & delay traces at the wireless
layer
…0000000 10101111 00000000000…
• Develop a modeling algorithm
(MTA: A Markov-based Trace Analysis Algorithm)
– Examine non-stationary behavior of a trace by doing pattern
recognition
– Precondition trace
• Divide non-stationary trace into stationary subtraces
• Characterize the transition between subtraces
• Apply Markov models to stationary subtraces
• Apply MTA to collected wireless traces
– GSM, WLAN, GPRS, Sensor Networks
10
The MTA Algorithm
• Divide wireless trace into two stationary sub-traces
–
–
–
–
–
Lossy and error-free states
Form lossy and error-free sub-traces
Show lossy sub-trace is stationary
Model lossy sub-trace as DTMC
Calculate best fitting distribution for the state length (EXP fitting)
States:
Trace:
Lossy sub-trace:
Lossy
Error-free
C
…10001110011100….0
Lossy
C
0000…0000 11001100…00
Error-free
00000..000...
...10001110011100….0 11001100…00 ...
Error-free sub-trace:
… 0000…0000 00000..000...
11
Applications of the Model
• Synthetic trace generation
– Use to evaluate models by exploring distribution
– Artificial traces can be used in simulators
• Develop feedback algorithm
– Uses the MTA model statistics
– Identify change of state => notifies the application
– Allows application adpatation
12
Outline
• Introduction
• The Problem
• Existing Work
• Our Solution
– Modeling Through Data Preconditioning
• Modeling Methodology Applied to Wireless Networks
– Applying the MTA Algorithm to GSM & WLAN error traces
– Applying the MTA Algorithm to GSM delay traces
– Evaluation
• Work in Progress
• Summary
13
MTA Models for Error Traces
• GSM error trace: 576,021 frames with FER=0.058
• WLAN error trace: 288,804 frames with FER=0.063
– (802.11b collected by Andreas Willig, TU of Berlin)
• MTA:
– Lossy and error-free states
– Form lossy sub-trace -> DTMC
– GSM:
• Lossy state length distribution
• Error-free state length distribution
– WLAN:
• Lossy state length distribution
• Error-free state length distribution
~Exp(0.037)
~Exp(0.04)
~Exp(0.076)
~Exp(0.059)
14
Intuition for Stationary Behavior
• Burst length analysis of “GSM Error Trace”
• Error-free bursts much longer than error bursts
• Error-free burst
100
Burst Length (Frames)
90
– mean:
115
– st deviation: 551
80
Error Burst
Error-Free Burst
70
• Error burst
60
– mean:
6
– st deviation: 14
50
40
• Long error-free bursts
destroy error cluster
statistics
• Non-stationary behavior
30
20
10
0
0
50
100
150
200
Burst Transition
15
Test for Stationarity : The “Runs Test”
• Apply the “Runs Test” to GSM trace
• Runs Test: Bendat and Piersol in 1986
–
–
–
–
Compute median run value of the trace (run=error burst)
Divide trace into equal size segments
Plot histogram: runs not equal to median value in each segment
Too few or too many runs is a sign of non-stationarity
4000
Frequency (segments)
3500
For stationarity:
~ 90% of the distribution
must lie between boundary
points (0.05% and 90%)
Only 17% of the segments lie
between 0.45 and 8.53
3000
2500
2000
1500
1000
500
0
0
1
2
3
4
5
6
7
8
9
Number of Runs
16
Stationarity of “Lossy Sub-trace”
The Runs Test
Burst Lengths in “Lossy Sub-trace”
200
100
180
Error Burst
Error-free Burst
80
Frequency (segments)
Burst Length (Frames)
90
70
60
50
40
30
20
10
87% of the segments lie
between 0.7 and 13.3
160
140
120
100
80
60
40
20
0
0
0
50
100
150
Burst Transition
200
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Number of Runs
“Lossy Sub-trace” is stationary
17
14
Modeling “lossy sub-trace” as DTMC
• Order of the Markov chain
70
Order 6
Complexity (States)
60
50
40
30
Order 5
20
Order 4
10
Order 3
Order 2
0
0.52
0.525
0.53
accuracy
0.535
0.54
0.545
Order 1
0.55
0.555
0.56
0.565
Conditional Entropy
• Calculate transition probabilities
18
Outline
• Introduction
• The Problem
• Existing Work
• Our Solution
– Modeling Through Data Preconditioning
• Modeling Methodology Applied to Wireless Networks
– Applying the MTA Algorithm to GSM & WLAN error traces
– Applying the MTA Algorithm to GSM delay traces
– Evaluation
• Work in Progress
• Summary
19
MTA Model for GSM Delay Trace
• Multimedia applications tolerate a max delay
– Max delay is application dependent
– Packets arriving with delay greater than max value are discarted
• Model losses due to packet delays
• GSM delay trace: 2,580 UDP packets of video stream
– UDP connection over reliable GSM link
– Choose delay threshold of 2 sec
• Apply MTA to GSM delay trace
20
Model Evaluation Metrics
• Traditional approach to model evaluation
– Generate synthetic traces
– Measure FER and throughput
– Problem: Not correlated to error distribution
• Our approach:
– Generate synthetic traces
• Calculate error burst distribution
• Compare traces’ error distribution to “original traces”
– Protocol design under various models
• Calculate optimal frame size
• Calculate throughput for various frame sizes
• Optimal frame sizes are highly correlated with error
distribution
21
Evaluation:
GSM Error Burst Distributions
• GSM, MTA experience similar error burst characteristics
• Gilbert and 3rd order don’t reproduce large error burst
Cumulative Density Function
1.0
mean st dev max
0.9
0.8
0.7
GSM: 6
14
126
0.6
MTA: 7
8
82
3rd M: 2.3
1.4
8
Gilbert: 1.8
0.4
4
0.5
GSM
0.4
Gilbert
0.3
MTA
0.2
3rd Markov
0.1
0.0
0
10
20
30
40
Error Burst Length (Frames)
50
22
Evaluation:
WLAN Error Burst Distributions
• GSM, MTA experience similar error burst characteristics
• Gilbert and 3rd order don’t reproduce large error burst
Cumulative Density Function
1.0
0.9
mean st dev max
0.8
WLAN: 2.8
0.7
0.6
3.1
42
2.8
33
3rd M: 2
1.2
8
Gilbert: 1.6
0.5
6
MTA: 3.2
0.5
W LAN
0.4
Gilbert
0.3
MTA
0.2
3rd Markov
0.1
0.0
0
5
10
15
20
25
30
Error Burst Length (Frames)
35
40
23
Evaluation:
GSM Trace Delay Burst Distributions
• Delay burst length => sequences of packets with delay greater
than threshold (2 sec)
• MTA experience best burst characteristics
Cumulative Density Function
1.0
mean st dev max
0.9
0.8
0.7
GSM: 20.5
12.7
38
0.6
MTA: 24
9.7
38
3rd M: 3.5
Gilbert: 1.7
1.4
0.7
4
2
0.5
GSM_delay
0.4
Gilbert
0.3
MTA
0.2
3rd Markov
0.1
0.0
0
5
10
15
20
25
30
Delay Burst Length (Packets)
35
40
24
Model Evaluation : Protocol Design
•
•
•
•
Generate error traces from various models
Calculate optimal RLP frame size (size that yields max throughput)
Real GSM distribution => optimal size is 210 Bytes
Traditional models’ distributions => wrong frame size
1500
Gilbert
150B
Throughput (Bytes/sec)
1400
GSM
Gilbert
MTA
EED
3rd Markov
3rd Markov
180B
1300
Standard Error from
GSM distribution
GSM and
MTA, 210B
1200
EED
Gilbert
3rd Markov
MTA
1100
EED
60B
1000
= 48
= 22
= 10
=8
900
30
150
270
390
510
630
750
870
990
1110 1230 1350
1470
RLP Frame Size (Bytes)
25
Outline
• Introduction
• The Problem
• Existing Work
• Our Solution
– Modeling Through Data Preconditioning
• Modeling Methodology Applied to Wireless Networks
• Work in Progress
– WSim
• Summary
26
WSim: Wireless Simulator
• Implements error channel model based on data
preconditioning models
– Explores impact of high FER on applications
– Tests various transport protocol configuration for different FER
• Provides feedback algorithm
– UDP connection sends information on channel conditions from
base station to the application
• Provides non reliable transport and radio link
27
Sender Module
WSim Modules
Sender Socket Interface
RTP Packet
Receiver Module
Receiver Socket Interface
RTP Packet
UDP/IP/PPP
..
..
UDP/IP/PPP
554B PPP
Frames
Radio Link:
Fragmentation/Reassembly
..
..
RL Module
554B PPP
Frames
..
MTA Model
Statistics
Feedback
Algorithm
30B Radio
Frames
Radio Link and Base Station
Fragmentation/Reassembly
Feedback Message:
Fragmented PPP Frame
28
Summary
•
New modeling research methodology
– Preconditioning of data to fit traditional models
• Apply modeling methodology to error and delay processes
of wireless links
– Develop the MTA algorithm to model error and delay processes in
wireless
• More accurate models => more accurate emulations =>
better protocol design
29
Work in Progress
• Provide a less threshold-oriented way to decide state
changes
– Wavelet analysis to do pattern recognition
• Define domain for which MTA works
– Define FER, error density and distribution
– When do current models break down?
• Apply MTA model to
– GPRS networks traces (Ericsson Lab)
– Sensor networks traces
• Improve predictive feedback algorithm
– Use time series forecasting to predict future behavior
• Implement Wsim in Java
– Evaluate MTA models
– Explore ways to send feedback during high error periods
30
Thank you :-)
Tapas Web Page:
http://www.cs.berkeley.edu/~almudena/tapas
31