Transcript ppt

Griffin Update: Towards an Agile,
Predictive Infrastructure
Anthony D. Joseph
UC Berkeley
http://www.cs.berkeley.edu/~adj/
Sahara Retreat, January 2003
Outline

Griffin
–
–
–

Tapas Update
–
–
–
–
2
Motivation
Goals
Components
Motivation
Data preconditioning-based network modeling
Model accuracy issues and validation
Domain analysis
Near-Continuous, Highly-Variable
Internet Connectivity

Connectivity everywhere: campus, in-building, satellite…
–

Most applications support limited variability (1% to 2x)
–
–

–
–
–
–

Design environment for legacy apps is static desktop LAN
Strong abstraction boundaries (APIs) hide the # of RPCs
But, today’s apps see a wider range of variability
–
3
Projects: Sahara (01-), Iceberg (98-01), Rover (95-97)
35 orders of magnitude of bandwidth from 10's Kb/s 1 Gb/s
46 orders of magnitude of latency from 1 sec 1,000's ms
59 orders of magnitude of loss rates from 10-3  10-12 BER
Neither best-effort or unbounded retransmission may be ideal
Also, overloaded servers / limited resources on mobile devices
Result: Poor/variable performance from legacy apps
Griffin Goals

Users always see excellent ( local, lightly loaded)
application behavior and performance
–
–
–

Help legacy applications handle changing conditions
–
–

–
4
Analyze, classify, and predict behavior
Pre-stage dynamic/static code/data (activate on demand)
Architecture for developing new applications
–

Independent of the current infrastructure conditions
Move away from “reactive to change” model
Agility: key metric is time to react and adapt
Input/control mechanisms for new applications
Application developer tools
Leverage Sahara policies and control mechanisms
Griffin: An Adaptive, Predictive
Approach

Continuous, cross-layer, multi-timescale introspection
–
–
–

Convey app reqs/network info to/from lower-levels
–
–

Break abstraction boundaries in a controlled way
Challenge: Extensible interfaces to avoid existing least
common denominator problems
Overlay more powerful network model on top of IP
–
–
5
Collect & cluster link, network, and application protocol events
Broader-scale: Correlate AND communicate short-/long-term
events and effects at multiple levels (breaks abstractions)
Challenge: Building accurate models of correlated events
–
Avoid standardization delays/inertia
Enables dynamic service placement
Challenge: Efficient interoperation with IP routing policies
Some Enabling Infrastructure
Components

Tapas network characteristics toolkit
–
–
–

REAP protocol modifying / application building toolkit
–
–
–

Introspective mobile code/data support for legacy / new apps
Provides dynamic placement of data and service components
MINO E-mail application on OceanStore / Planet Lab
Brocade, Mobile Tapestry, and Fault-Tolerant Tapestry
–
6
Measuring/modeling/emulating/predicting delay, loss, …
Provides Sahara with micro-scale network weather information
Mechanism for monitoring/predicting available QoS
–
Overlay routing layer providing Sahara with efficient
application-level object location and routing
Mobility support, fault-tolerance, varying delivery semantics
Outline

Griffin
–
–
–

Tapas Update
–
–
–
–
7
Motivation
Goals
Components
Motivation
Data preconditioning-based network modeling
Model accuracy issues and validation
Domain analysis
Tapas Motivation

Accurate modeling and emulation for protocol design
–
–
–

Creating models/artificial traces that are statistically
indistinguishable from traces from real networks
–
–
–
8
Very difficult to gain access to new or experimental networks
Delay, error, congestion in IP, GSM, GPRS, 1xRTT, 802.11a/b
Study interactions between protocols at different levels
Such models have both predictive and descriptive power
Better understanding of network characteristics
Can be used to optimize new and existing protocols
Tapas

Novel data preconditioning-based analysis approach
–

More accurately models/emulates long-/short-term dependence
effects than classic approaches (Gilbert, Markov, HMM, Bernoulli)
Analysis, simulation, modeling, prediction tools:
–
–
MultiTracer: Multi-layer trace collection and analysis (download)
Trace analysis and synthetic trace generator tools

–
–
–


9
Markov-based Trace Analysis, Modified hidden Markov Model
WSim: Wireless link simulator (currently trace-driven)
Simple feedback algorithm and API
Domain analysis tool: chooses most accurate model for a metric
Error-tolerant radio / link layer protocols: RLPLite, PPPLite
Collected >5,000 minutes of TCP, UDP, RLP traces in
good/bad, stationary/mobile environments (download)
MultiTracer Measurement Testbed
Application
Packetization
RTP
Socket Interface
TCP/UDP (Lite)
Multi-layer trace collection
• RLP, UDP/TCP, App
• Easy trace collection
• Rapid, graphical analysis
Packetization
RTP
Socket Interface
TCP/UDP (Lite)
IP
IP
PPP/PPP Lite
PPP/PPP Lite
RLP / non RLP
RLP / non RLP
GSM Network
Mobile Host
Unix BSDi 3.0
10
Application
SocketDUMP
TCPdump
TCPstats
RLPDUMP
PSTN
Fixed Host
Unix BSDi 3.0
GSM
Base Station
MultiTracer
300 B/s
Plotting &
Analysis
SocketDUMP
TCPdump
TCPstats
Choosing the Right Network Model

Collect empirical packet trace: T = {1,0}*
–

1: corrupted/delayed packet, 0: correct/non-delayed packet
Create mathematical models based on T
real network
metric trace

artificial network
metric trace
Classic models don’t always work well (can’t capture variations)
MTA, M3 – Trace data preconditioning algorithms
–
–
–
11
network
model
T may be non-stationary (statistics vary over time)
–

trace analysis
algorithm
Decompose T into stationary sub-traces & model transitions
Stationary sub-traces can be modeled with high-order DTMC
Markov-based Trace Analysis (MTA) and Modified hidden Markov
Model (M3) tools accurately model time varying links
Creating Stationarity in Traces

Our idea for MTA and M3: decompose T into stationary sub-traces
–
–


Bad sub-traces B1..n = 1{1,0}*0c, Good sub-traces G1..n = 0*
C is a change-of-state constant: mean + std dev of length of 1*
MTA: Model B with a DTMC, model state lengths with exponential
distribution, and compute transitions between states
M3: Similar, but models multiple states using HMM to transition
Bad
Subtrace
c
Error Trace … 10001110011100….0
Bad Trace
12
Good Trace
Bad
Subtrace
c
Good
Subtrace
0000…0000
11001100…00
… 10001110011100….0 11001100…00 ...
Good
Subtrace
00000..000...
Model B with DTMC
… 0000…0000 00000..000...
Issues in Modeling

Evaluating the accuracy of a particular model
–

How much trace data do we need to collect to
accurately model a network characteristic?
–

How much work?
Can a model be used to accurately model a
network scenario?
–
13
How closely does it model a network characteristic?
I.e., can we model a case like poor fixed indoor
coverage and use the model to model conditions at
a later time?
Evaluating Model Accuracy


Determine CDFs of burst lengths in Lossy and
Error Free subtraces of a collected trace
Create Model
–


14
Use model to generate an artificial trace and
determine CDFs of Lossy and Error Free subtraces
Calculate correlation coefficient (cc) between
Lossy and Error-Free CDFs of collected and
artificial traces
Observation: Accurate models have cc > 0.96
Model Evaluation Methodology

What size collected trace is needed for accurate
model?
–
–
–

How representative is a model?
–
–
–
15
Sub-divide trace into subtraces of length len/2j
Compare cc values between subtraces and collected
trace
Trace lengths > max(EF burst size) yield cc > 0.96
–
Collect large trace, AB, and sub-divide into A and B
Create model from A
Use cc to compare model A with A, B, and AB
Representative models have all cc values > 0.96
Challenge: Domain Analysis

Which model to use?
–

Algorithm (applied to Gilbert, HMM, MTA, M3):
–
–

Collect traces, compute exponential functions for lengths of good
and bad state and compute 1’s density of bad state
For a given density, determine model parameters and optimal
model (best cc)
Experiment:
–
–
16
Gilbert, HMM, MTA, M3 have different properties
Apply to artificial network environment with varying bad state
densities
Plot optimal model as a function of the good and bad state
exponential values: Domain of Applicability Plot
Domain of Applicability Plot, Lden= 0.2
b
17
Domain of Applicability Plot , Lden= 0.7
18
Griffin Summary

On-going Tapas work:
–
–
–
–

Tapestry and MINO talks at retreat
–
19
Sigmetrics 2003 submission on domain analysis
Trace collection: CDMA 1xRTT, GPRS, & IEEE
802.11a, PlanetLab IP
Release of WSim
Dissertation (Almudena Konrad)
In joint and ROC/OS sessions
Griffin Update: Towards an Agile,
Predictive Infrastructure
Anthony D. Joseph
UC Berkeley
http://www.cs.berkeley.edu/~adj/
Sahara Retreat, January 2003