Transcript What is the Grid?

Uni Innsbruck Informatik - 1
Grid InterNetworking
Michael Welzl http://www.welzl.at
DPS NSG Team http://dps.uibk.ac.at/nsg
Institute of Computer Science
University of Innsbruck
GridNets 2006
San Jose, CA USA
1/2 October, 2006
Uni Innsbruck Informatik - 2
Outline
• Problem scope
• Proposed solutions
– Example 1: Network Measurement
– Example 2: Grid-Network-Simulation
– Example 3: QoS for the Grid
• Conclusion
Uni Innsbruck Informatik - 3
Problem scope
Shrinking the problem space
Uni Innsbruck Informatik - 4
What is the Grid?
• Metaphor: power grid
– just plug in, don‘t care where (processing) power comes from,
don‘t care how it reaches you
• Common definition:
The real and specific problem that underlies the Grid concept is coordinated
resource sharing and problem solving in dynamic, multi institutional virtual
organizations
[Ian Foster, Carl Kesselman and Steven Tuecke, “The Anatomy of the Grid – Enabling Scalable Virtual
Organizations”, International Journal on Supercomputer Applications, 2001]
• Common terms:
Virtual Team - members of one or several Virtual Organizations who use a Grid
• Most of the time...
– the real and specific goal is High Performance Computing
– virtual organizations and virtual teams are well defined
(as opposed to the SETI@Home usage scenario)
– i.e. not an „open“ system, security is a big issue
Uni Innsbruck Informatik - 5
Scope
• Grid history: parallel processing at a growing scale
–
–
–
–
Parallel CPU architectures
Multiprocessor machines
Clusters
(“Massively Distributed“) computers on the Internet
Size
• Traditional goal: processing power
– Grid people = parallel people; thus, goal has not changed much
• Broader definition (“resource sharing“)
Reasonable to
focus on this.
- reasonable - e.g., computers also have harddisks :-)
– New research areas / buzzwords: Wireless Grid, DataGrid, Pervasive Grid,
[this space reserved for your favorite research area] Grid
– sometimes perhaps a little too broad, e.g., “P2P Working Group“ is now
part of the Global Grid Forum
Uni Innsbruck Informatik - 6
Grid Workflow Applications
Grid Workflows
based on activities
Dynamic Instantiation
Service Orchestration
Quality of Service
Web Services
Service Description
Discovery, Selection
Deployment, Invocation
Components
Descriptor Generation
Component Interaction
Optimization, Adaptation
Legacy codes
OMP
MPI
MPI
HPF
OMP
HPF
MPI
Java
Legacy Codes
• Components are built, Web (Grid) Services are defined,
Activities are specified
• Activities (which may communicate with each other) should
automatically be distributed by a scheduler
Uni Innsbruck Informatik - 7
UIBK-DPS development: ASKALON
A Grid Application Development and Computing Environment
XML
Uni Innsbruck Informatik - 8
Grid requirements
• Efficiency + ease of use
– Programmer should not worry (too much) about the Grid
• Underlying system has to deal with
–
–
–
–
–
–
Error management
Authentification, Authorization and Accounting (AAA)
Efficient Scheduling / Load Balancing
Resource finding and brokerage
Naming
Resource access and monitoring
• No problem: we do it all - in Middleware
• de facto standard: “Globus Toolkit“
– installation of GT3 in our high performance system: 1 1/2 hours or so...
– yes, it truly does it all :) 1000s of addons - GridFTP, MDS, NWS, GRAM, ..
– this is just the basis - e.g., ASKALON is layered on top of Globus
Uni Innsbruck Informatik - 9
Grid-network peculiarities
• Special behavior
– Predictable traffic pattern - this is totally new to the Internet!
– Web: users create traffic
– FTP download: starts ... ends
– Streaming video: either CBR or depends on content! (head movement, ..)
• Could be exploited by congestion control mechanisms
– Distinction: Bulk data transfer (e.g. GridFTP) vs. control messages (e.g. SOAP)
– File transfers are often “pushed“ and not “pulled“
– Distributed System which is active for a while
• overlay based network enhancements possible
– Multicast
– P2P paradigm: “do work for others for the sake of enhancing the whole system (in
your own interest)“ can be applied - e.g. act as a PEP, ...
• sophisticated network measurements possible
– can exploit longevity and distributed infrastructure
• Special requirements
– file transfer delay predictions
• note: useless without knowing about shared bottlenecks
– QoS, but for file transfers only (“advance reservation“)
Uni Innsbruck Informatik - 10
Research gap: Grid-specific
network enhancements
Enriched with customised
network mechanisms
Original Internet technology
Bringing the Grid to its full potential !
Today‘s Grid
applications
Driving a racing car
on a public road
Traditional Internet
applications
(web browser, ftp, ..)
EC-GIN
EC-GIN enabled
Grid applications
Applications with special
network properties and
requirements
Real-time multimedia
applications (VoIP,
video conference, ..)
Uni Innsbruck Informatik - 11
What is EC-GIN?
• European project: Europe-China Grid InterNetworking
– STREP in IST FP6 Call 6
– 2.2 MEuro, 11 partners (7 Europe + 4 China)
– Networkers developing mechanisms for Grids
Uni Innsbruck Informatik - 12
Research Challenges
• Research Challenges:
– How to model Grid traffic?
• Much is known about web traffic (e.g. self-similarity) - but the Grid is different!
– How to simulate a Grid-network?
• Necessary for checking various environment conditions
• May require traffic model (above)
• Currently, Grid-Sim / Net-Sim are two separate worlds
(different goals, assumptions, tools, people)
– How to specify network requirements?
• Explicit or implicit, guaranteed or “elastic“, various possible levels of granularity
– How to align network and Grid economics?
• Combined usage based pricing for various resources including the network
– What P2P methods are suitable for the Grid?
• What is the right means for storing short-lived performance data?
Uni Innsbruck Informatik - 13
Some issues: application interface...
• How to specify properties and requirements
– Should be simple and flexible - use QoS specification languages?
– Should applications be aware of this?
 Trade-off between service granularity and transparency!
GIN API
GIN API
Traditional method
Our approach
Uni Innsbruck Informatik - 14
... and peer awareness
Data flow
Intermediary helper
Grid end system
Grid end system
(a) Traditional PEP
Grid end system
Grid end system
Intermediary helper
(b) NSG PEP
Uni Innsbruck Informatik - 15
Problem: How Grid folks see the Internet
• Abstraction - simply use what is available
Just like Web Service
community
– still: performance = main goal
Conflict!
• Existing transport system
(TCP/IP + Routing + ..) works well
• QoS makes things better, the Grid needs it!
– we now have a chance for that, thanks to IPv6
Absolutely not like Web
Service community !
Wrong.
• Quote from a paper review:
“In fact, any solution that requires changing the TCP/IP protocol stack is
practically unapplicable to real-world scenarios, (..).“
• How to change this view
– Create awareness - e.g. GGF GHPN-RG published documents such as
“net issues with grids“, “overview of transport protocols“
– Develop solutions and publish them! (EC-GIN, GridNets)
Uni Innsbruck Informatik - 16
A time-to-market issue
(Real-life)
coding begins
Research
begins
Typical Grid project
Thesis writing
Result: thesis + running code;
tests in collaboration with
different research areas
Real-life tests
begin
Ideal
Thesis writing
Research
begins
(Simulation)
coding begins
Typical Network project
Result: thesis + simulation
code; perhaps early real-life
prototype (if students did well)
Uni Innsbruck Informatik - 17
Machine-only communication
• Trend in networks: from support of Human-Human Communication
–
email, chat
• via Human-Machine Communication
–
web surfing, file downloads (P2P systems), streaming media
• to Machine-machine Communication
–
–
Growing number of commercial web service based applications
New “hype“ technologies: Sensor nets, Autonomic Computing vision
• Semantic Web (Services): first big step for supporting machine-only
communication at a high level
• So far, no steps at a lower level
–
This would be like RTP, RTCP, SIP, DCCP, ... for multimedia apps:
not absolutely necessary, but advantageous
Uni Innsbruck Informatik - 18
The long-term value of Grid-net research
• A subset of Grid-net developments will
be useful for other machine-only
communication systems!
Grid
Future
work
Web service
applications
Sensor nets
• Key for achieving this: change viewpoint from
“what can we do for the Grid“ to “what can the Grid do for us“
(or from “what does the Grid need“ to “what does the Grid mean to us“)
Uni Innsbruck Informatik - 19
Proposed solutions
Uni Innsbruck Informatik - 20
Example 1: Network Measurement
Uni Innsbruck Informatik - 22
NWS: The Network Weather Service
• Distributed system consisting of
–
–
–
–
Name Server (boring)
Sensor - actual measurement instance, regularly stores values in......
Persistent State
Forecaster (calculations based on data in Persistent State)
• Interesting parts:
Duration of a long
TCP transfer
– Sensor
Measured resources: availableCpu, bandwidthTcp, connectTimeTcp,
currentCpu, freeDisk, freeMemory, latencyTcp
RTT of a
small message
– Forecaster
Apply different models for prediction, compare with actual measurement
data, choose best match
Uni Innsbruck Informatik - 23
NWS critique
• Architecture (splitting into sensors, forecaster etc.) seems reasonable;
open source  consider integrating new work in NWS
• Sensor
– active measurements even though non-intrusiveness was an important design goal
- does not passively monitor TCP (i.e. ignores available data)
– strange methodology:
(Large message throughput) “Empirically, we have observed that a message size
of 64K bytes (..) yields meaningful results“
– ignores packet size ( = measurement granularity ) and path characteristics
– trivial method - much more sophisticated methods
available (e.g. packet pair - later!)
– point-to-point measurements: distributed infrastructure not taken into account
• Forecaster
– relies on these weird measurements, where we don‘t know much about the
distribution (but we do know some things about net traffic IFF properly measured)
– uses quite trivial models (but they may in fact suffice...)
Uni Innsbruck Informatik - 24
Exploiting the Distributed Infrastructure
• Example problem:
– C allocates tasks to A and B (CPU, memory available); both send results to C
– B hinders A - task of B should have been kept at C!
• Path changes are rare - thus, possible to detect potential problem in advance
– generate test messages from A, B to C - identify signature from B in A‘s traffic
• Another issue in this scenario: how valid is a prediction that A obtains if a
measurement / prediction system does not know about the shared bottleneck?
Uni Innsbruck Informatik - 25
Exploiting longevity
• Time scale of traffic fluctuations < time scale of path changes
 knowledge of link capacities may be more useful than traffic estimate
• Underlying technique: packet pair
– send two packets p1 and p2 in a row; high probability that p2 is enqueued
exactly behind p1 at bottleneck
– at receiver: calculate bottleneck bandwidth via time between p1 and p2
– minimize error via multiple probes
– TCP with “Delayed ACK“ receiver automatically sends packet pairs
 passive TCP receiver monitoring is quite good!
Uni Innsbruck Informatik - 26
Traffic prediction by monitoring TCP
• TCP propagates bottleneck self-similarity to end systems (“samples bandwidth“)
• Automatic prediction? Complex, but possible, I think - e.g.:
Yantai Shu, Zhigang Jin, Jidong Wang, Oliver W. W. Yang: Prediction-Based Admission
Control Using FARIMA Models. ICC (3) 2000: 1325-1329
Results from measuring TCP throughput at equidistant intervals
Available bandwidth
TCP sending rate
Results from proper TCP monitoring (loss as a congestion indicator)
Recent related paper
(more realistic,
simpler approach):
SIGCOMM 2005
Uni Innsbruck Informatik - 27
Grid-Network Simulation
Uni Innsbruck Informatik - 28
Procedure
• Grid simulator only simulates one
execution on one machine
• File transfers: generate scenario +
invoke network simulator
• Possibility: data transfers influencing
each other
Uni Innsbruck Informatik - 29
Example scenario
Tasks = {T1, T2, T3, T4}
Resources = {R1, R2, R3, R4}
Data transfers = {D1, D2, D3, D4}
Case 1: All tasks and data
transfers have equal duration
Grid Simulator / Netzwerk Simulator
Uni Innsbruck Informatik - 30
Example scenario /2
Data transfers with different duration
Grid Simulator / Netzwerk Simulator
Uni Innsbruck Informatik - 31
Conclusion
• Implementation in the works
• Method tackles an important and current problem, but...
• Open question: how much time needed between two clusters?
– Depends on background traffic and network topology
• Time consuming
– Repeated simulation of data transfers
– Total # parameters = (# Grid parameters) * (# network parameters)
• On the other hand...
– User = Research group which also runs a Grid
– Easy to distribute (parameter study)  Grid simulation on the Grid
– Seems strange (recursion), but makes sense: one Grid application for
carrying out an analysis with numerous environment conditions
Uni Innsbruck Informatik - 32
QoS for the Grid
Uni Innsbruck Informatik - 33
QoS: the state-of-the-art
:-(
Papers from SIGCOMM‘03 RIPQOS Workshop: “Why do we care, what have we learned?“
• QoS`s Downfall: At the bottom, or not at all! Jon Crowcroft, Steven Hand, Richard
Mortier,Timothy Roscoe, Andrew Warfield
• Failure to Thrive: QoS and the Culture of Operational Networking Gregory Bell
• Beyond Technology: The Missing Pieces for QoS Success Carlos Macian, Lars
Burgstahler, Wolfgang Payer, Sascha Junghans, Christian Hauser, Juergen Jaehnert
• Deployment Experience with Differentiated Services Bruce Davie
• Quality of Service and Denial of Service Stanislav Shalunov, Benjamin Teitelbaum
• Networked games --- a QoS-sensitive application for QoS-insensitive users? Tristan
Henderson, Saleem Bhatti
• What QoS Research Hasn`t Understood About Risk Ben Teitelbaum, Stanislav
Shalunov
• Internet Service Differentiation using Transport Options:the case for policy-aware
congestion control Panos Gevros
Uni Innsbruck Informatik - 34
Key reasons for QoS failure
• Required participation of end users and all intermediate ISPs
– “normal“ Internet users want Internet-wide QoS, or no QoS at all
– In a Grid, a “virtual team“ wants QoS between its nodes
– Members of the team share the same ISPs - flow of $$$ is possible
• Technical inability to provision individual (per-flow) QoS
– “normal“ Internet users
• unlimited number of flows come and go at any time
• heterogeneous traffic mix
– Grid users
• number of members in a “virtual team“ may be limited
• clear distinction between bulk data transfer and SOAP messages
• appearance of flows mostly controlled by machines, not humans
•  QoS can work for the Grid !
Uni Innsbruck Informatik - 35
Proposed architecture
• Goal: efficient per-flow QoS without signaling to routers
• Idea: use traditional coarse-grain QoS (DiffServ) to differentiate between
– long-lived bulk data transfer with advance reservation (EF) and
– everything else (= SOAP etc. over TCP) (best effort)
• Allows us to assume isolated traffic; planned to drop this requirement later
• Because data transfers are long lived, apply admission control
– Flows signal to resource broker (RB) when joining or leaving the network
• Mandate usage of one particular congestion control mechanism for all flows
in the EF aggregate
– Enables efficient resource usage because flows are elastic
Uni Innsbruck Informatik - 36
Key ingredients of our QoS soup
• Link capacities must be known, paths should be stable
(capacity information should be updated upon routing change)
• Shared bottlenecks must be known
• Bottlenecks must be fairly shared by congestion control mechanism
irrespective of RTT (max-main fairness required, i.e. all flows must
increase their rates until they reach their limit)
• No signaling to routers = no way to enforce proper behavior
 there must be no cheaters
– User incentive: fair behavior among cooperating nodes among which Grid
application is distributed
– Unfair behavior between Grid application 1 and 2 in same Grid neglected
(usually acceptable, as used by same Virtual Organization)
Uni Innsbruck Informatik - 37
Link capacities must be known
• Can be attained with measurements
• Working on permanently active, (mostly) passive measurement system
for the Grid that detects capacity with packet pair
– send two packets p1 and p2 in a row; high probability that p2 is enqueued
exactly behind p1 at bottleneck
– at receiver: calculate bottleneck bandwidth via time between p1 and p2
– e.g. TCP: “Delayed ACK“
receiver automatically sends
packet pairs
 passive TCP receiver
monitoring is quite good!
– exploit longevity - minimize
error by listening for a
long time
Uni Innsbruck Informatik - 38
Shared bottlenecks must be known
• Simple basis: distributed traceroute tool
– enhancement: traceroute terminates early upon detection of known hop
• Handle “black holes“ in traceroute
– generate test messages from A, B to C - identify signature from B in A‘s traffic
– method has worked in the past: “controlled flooding“ for DDoS detection
Uni Innsbruck Informatik - 39
Congestion Control mechanism must be
max-min fair
•
Was once said to be impossible without per-flow state in routers
–
–
•
not true; XCP and some others
but these explicit require router support...
Main problem: dependence on RTT
–
three good indications that this can be removed without router support
1. CADPC/PTP (my Ph.D. thesis)...
•
max-min fairness based on router feedback, but only capacity and available
bandwidth (could also be obtain by measuring)
2. Personal comment by Sally Floyd
•
Reference to old paper on “phase effects“
3. TCP Libra
•
increase/decrease
factors are f(RTT)
Problem: efficiency - no max-min fair “high-speed“ CC mechanism without
router support
–
–
searched for a long time
now: plan to change existing one based on knowledge from above examples
Uni Innsbruck Informatik - 40
Per-flow QoS without signaling to routers
Traditional method:
signaling to edge
routers (e.g. with
COPS) at this point!
Synchronization
Synchronization of
of
distributed
distributed (P2P
(P2P based)
based)
database;
database; all
linkflows
capacities
known
1. 3.
may
2.
4.
II
yes
ok
quit
join?
known
to all
to all
brokers
brokers
continuous measurements;
update to BB upon path change
Uni Innsbruck Informatik - 41
Efficiency via elasticity
4 kbs
Flow 4
Flow 3
Flow 2
Bottleneck
Bandwidth
(kbs)
Flow 1
End 1
End 2
End 3
End 4
Time (seconds)
• QoS guarantees in Grid: „File will be transferred within X seconds“
 enables flexible resource usage
Uni Innsbruck Informatik - 42
Efficiency via elasticity /2
4 kbs
Flow 4
Flow 3
Bottleneck
Bandwidth
(kbs)
Flow 2
E2’
t1 - E1
E2
E3’
E3
E4’
E4
Time (seconds)
• Flow 1 stopped, flows 2-4 automatically increase their rates
– leading to earlier termination times E2‘-E4‘; known to (calculated by) BB
Uni Innsbruck Informatik - 43
Efficiency via elasticity /3
4 kbs
Flow 4
Flow 3
Bottleneck
Bandwidth
(kbs)
Flow 2
E2’
t2 – Flow 5 wants to
get admission here
E2
E3’
E3
E4’
E4
Time (seconds)
• Flow 5 asks BB for admission
– BB knows about current rates and promised E2-E4, grants access
Uni Innsbruck Informatik - 44
Efficiency via elasticity /4
4 kbs
Flow 5
Flow 4
Flow 3
Bottleneck
Bandwidth
(kbs)
E2”
Flow 2
t2 – Flow 5 gets
admission here
E2’
E2
E3”
E3’
E3
E4”
E4’
E4
E5
Time (seconds)
• Flow 2 terminates in time
– Flows 3-5 will also terminate in time
Additional flow admitted
and earlier termination
times than promised!
Uni Innsbruck Informatik - 45
Elasticity without Congestion Control?
• Significant amount of additional signaling necessary
4 kbs
Flow-4
As flow 5 is admitted, signal
“reduce your rates“ to
flows 2-4 required!
Flow-3
Bottleneck
Bandwidth
Flow-2
Flow-1
Time
As Flow-1 stops, Flows 2-4
could increase their rates
Without congestion control,
signal “increase your rates“
to flows 2-4 required!
Uni Innsbruck Informatik - 46
Additional considerations
• How to assign different rates to different flows?
–
–
–
–
max-min fairness: if a sender “acts“ like two, it obtains twice the rate
consider rate consisting of slots (e.g. 1 kbit/s = 1 slot)
flows can consist of several slots
let congestion control mechanism operate on slots
• Possibility: admit new flows even in scenario below
4 kbs
Flow 5
Must introduce unfairness:
only flow 2 can reduce rate
Flow 4
Bottleneck
Bandwidth
(kbs)
Flow 3
t2 – Flow 5 gets
admission here
E3”
E2”
Flow 2
E2’
E2
E3’
E3
Time (seconds)
E4’
E4”
E4
E5
Disadvantage: more
signaling again!
Uni Innsbruck Informatik - 47
Difficult & distant future work
• Drop requirement of traffic isolation via DiffServ
– constantly obtain and update conservative estimate of available bandwidth
using packet pair (works without saturating link)
– ensure that limit is never exceeded; “condition red“ otherwise!
– Some open questions...
• does this require the CC mechanism to be TCP-friendly?
• condition red: reduce slots, or let flows be aggressive for a short time?
• How to handle routing changes
– will be noticed, but can reduce capacity  break QoS guarantee
– condition red; can happen in worst case, but to be avoided at all cost
– mitigation methods
• very conservative estimate of available bandwidth; leave headroom
• tell senders to reroute via intermediate end systems
• Bottom line: lots of complicated issues, but possible to solve them
Uni Innsbruck Informatik - 48
Conclusion
Uni Innsbruck Informatik - 49
Conclusion
• Grid applications show special requirements and properties from a network
perspective
– and it is reasonable to develop tailored Internet technology for them.
• There is another class of such applications...
• Multimedia.
• For multimedia applications, an immense number of network enhancements
(even IETF standards) exist.
• For the Grid, there is nothing.
• This is a research gap; let‘s fill it together!
– submit a paper to GridNets 2007 !
Reminder: if done right,
such research is also
applicable to other systems
with machine-only traffic
Uni Innsbruck Informatik - 50
Thank you!
Questions?