Transcript powerpoint - Virtuoso - Northwestern University

Free Network Measurement for Adaptive
Virtualized Distributed Computing
Ashish Gupta, Marcia Zangrilli, Ananth Sundararaj, Anne Huang,
Peter A. Dinda, Bruce B. Lowekamp
Overview
Virtual Machines
Virtual
Network
Physical
Network
Benefits of VMs:
transparent portability, adaptation, security
Contributions:
1. Online passive measurement of
physical layer’s available bandwidth
(Wren)
2. Integration of Virtuoso’s application
monitoring and Wren’s traffic monitoring
3. Adaptation algorithms that use passive
monitoring to solve challenging
adaptation problems
2
Adaptive Virtualized Distributed
Computing
• How can we efficiently utilize resources in a
virtual machine distributed system?
– Accurately monitor resource availability
– Transparently adapt to changing conditions
– Keep application portability simple
3
Claim
• Virtualization enables the broad application of
dream techniques…
– Adaptation
– Resource reservation
• … using existing, unmodified applications and
operating systems
– So everyone can use the techniques
4
Optimization of Virtual System
Environment
Three Main Components
VNET
VTTIF
WREN
Layer 2 virtual
overlay
networking
Runtime
Application
Topology
Inference
Online Passive
bw monitoring
and network
characterization
Benefit: Completely independent of application
or Operating System
5
Outline
• Virtuoso
– Overview of distributed VM system
– VTTIF
– VNET
• Wren
– Online Wren overview
– Wren performance
• Integration of Virtuoso and Wren
• Adaptation
– Algorithms
– Results
6
Virtuoso
Distributed computing environment composed of virtual machines interconnected
with virtual networks
1. Automatically infer application
demands (network/CPU)
2. Monitor resource availability
(bw/latency/CPU)
3. Adapt distributed application
for better performance/cost
effectiveness
4. Reserve Resources when
possible
7
Application communication
topology and traffic load;
application processor load
Vnetd layer can collect all
this information as a side
effect of packet transfers
and invisibly act
• VM Migration
• Topology change
• Routing change
• Reservation
Network bandwidth and
latency; sometimes
topology
VM
Layer
Vnetd
Layer
Physical
Layer
8
Virtual Topology and Traffic Inference
Framework (VTTIF) Operation
• Infers application topology and traffic load at
runtime
• Resistant to rapid fluctuations and provides
damped network view
• All local views aggregated to central proxy to
give global view of distributed application
9
Virtual Topology and Traffic Inference
Framework (VTTIF) Operation
Ethernet-level traffic monitoring
VNET daemons collectively aggregate
a global traffic matrix for all VMs
Application topology is recovered using
normalization and pruning algorithms
10
VNET
• Virtual overlay network → creates illusion of
LAN over wide area
– Network transparency with VM migration
– Ideal monitoring point for application monitoring
User’s LAN
VM
User
11
Watching Resources from the Edge of the
Network (Wren): A Hybrid Monitoring
Approach
Wren Design:
–
–
Kernel-level instrumentation to collect traces of application traffic.
Analysis and management of traces handled in user-level.
Wren capabilities:
1. Observes incoming/outgoing packets
2. Online analysis to derive latency/bandwidth information
for all host pair connections
3. Answers network queries for any pair of hosts
12
Wren Architecture
Grid
Application
UDP
Network
TCP
SOAP
Interface
bw measurements
WREN Analysis Thread
WREN Packet Tracer
Linux Kernel
IP
13
Wren Online Available Bandwidth
Algorithm
Applies self-induced congestion principle
–
–
If packets are sent at a rate larger than the available bandwidth, the queuing
delays will have an increasing trend.
Find the rate just before queuing delays are incurred
1. Identifies outgoing Maximal length trains with similar spaced
packets.
2. Calculates ISR ( Initial Sending Rate ) for these trains.
3. Monitors ACK return rate to determine trends in RTTs.
4. Increase trend indicates congestion, non increasing trend indicates
lower bound for bw.
14
Wren Performance
Controlled load/latency testbed
Nistnet → emulate WAN
environment with congestion
Latency : 20 to 100 ms , bw : 3 to
25 Mbps
Key Advantage :
WREN accurately reports available
bandwidth when application traffic
does not saturate the path
15
Integrating Virtuoso and Wren
Application
Guest OS Kernel
Virtual Machine
Virtual Machine Monitor
VADAPT Adaptation
VTTIF Application Inference
Layer 2 Network
Interface
TCP / UDP
Forwarding
Wren
Network
Inference
Host OS Kernel
LAN
Other VNET daemon
16
Adaptation Process
VM to HOST mapping
Network Availability
Application Demand
Provide Overlay Topology
Provide forwarding rules
17
What defines Good Adaptation?
• Various ways to define good adaptation
Current Metric : Maximum residual bottleneck
bandwidth
How can we map the processes and paths such
that (available bandwidth – demanded
bandwidth) is maximized ?  Maximum room for
performance improvement
18
Optimization Problem
• Given the
–
–
–
–
network traffic load matrix of the application
computational intensity in each VM
topology of the network
load on its links, routers and hosts
• What is the
–
–
–
–
mapping of VMs to hosts
overlay topology connecting the hosts
forwarding rules on that topology
required CPU and network reservations
• That
– maximizes the application performance?
19
Problem formulation
Measured data
Application
demands
Constraints
Objective function
20
Greedy Heuristic
Mapping
– Identifies Hosts which have good bandwidth
connectivity and maps VMs over them
Overlay paths
– Uses adapted Dijktra to find “widest” paths depending
on bandwidth demands of application process pairs
(sorted in decreasing order)
→ finds path which leaves maximum residual
bottleneck bandwidth
21
Simulated Annealing
Motivation : Search Space is very large → Huge
number of possibilities for mapping and overlay
paths
Approach
1. Start with an initial solution
2. Perturb current configuration and evaluate with a
cost function
3. Continue Controlled Perturbation until a good cost
function is achieved
Perturbation function and algorithm details in paper
22
Experimental Setup
• Evaluation conducted in simulation
• In each scenario the goal is
– to generate a configuration consisting of VM to Host
mappings
– paths between the communicating VMs
– Such that the total residual bottleneck bandwidth is
maximized
• We compare
–
–
–
–
greedy heuristic (GH)
simulated annealing approach (SA)
SA with the GH solution as the starting point (SA+GH).
Additionally we also maintain the best solution found so
far with (SA+GH), i.e. (SA+GH+B), where ’B’ indicates
the best solution so far.
23
Adaptation Results
Scenario 1 : Only a particular VM to Host mapping
yields good performance.
24
Scenario 1 Results
• Both Annealing and Greedy perform well.
• Annealing advantage : Multi-Constraint optimization
easy
25
Scenario 2 : Large 256 host topology. 32 potential
hosts, 8 Virtual Machines
•
•
Results for Multi Constraint Cost Function : Bandwidth and Latency
Annealing easy to adapt and finds good mappings compared to
heuristic
26
Conclusion
• Network measurements can be provided for free!
• These measurements can be used to improve
application performance through adaptation
• Virtuoso and Wren Integrated system
– Low overhead
– Provides application and resource measurements
– Allows transparent optimization of application performance
• Adaptation Strategies
– Greedy heuristic and simulated annealing approaches are able
to find good mappings/configurations
27
For More Information
• Please visit
– Prescience Lab (Northwestern University)
• http://plab.cs.northwestern.edu
– Wren: Watching Resources fro the Edge of the Network (William and Mary)
• http://www.cs.wm.edu/~lowekamp/wren.html
– Virtuoso: Resource Management and Prediction for Distributed Computing
using Virtual Machines
• http://virtuoso.cs.northwestern.edu
• VNET is publicly available from above URL
28