Transcript Provisioning Service Workflows

Flexible Provisioning
of Service Workflows
Sebastian Stein
Supervisors:
Nick Jennings
Terry Payne
KEG Seminar, Aston University
4th March 2008
Agenda

Background & Motivation

Flexible Service Provisioning

On-Demand Invocation
 Advance Agreements

Conclusions
2
Flexible Provisioning of Service Workflows
Background & Motivation
Background

Computer systems are increasingly distributed:

E-commerce
Use of Internet for purchases in UK businesses
80
70
60
50
%
2002
40
2003
2004
30
20
10
0
Large businesses (1000+ empl.)
4
All businesses
Source: National Statistics Website, http://www.statistics.gov.uk/downloads/theme_economy/ecommerce_report_2004.pdf
Flexible Provisioning of Service Workflows
Background

Computer systems are increasingly distributed:

E-commerce
 High performance computing
5
Flexible Provisioning of Service Workflows
Service-Oriented Computing

Distributed agents offer their capabilities as computer services, which
are high-level behaviours that can be procured by consumers in
order to achieve their objectives. These include:



Traditional business services (e.g., ordering components, making logistic
arrangements, booking a flight ticket),
Computational services (e.g., data analysis, transformation and communication),
Information services (e.g., yellow pages, weather forecast, financial data).
6
Flexible Provisioning of Service Workflows
Workflows



Services are rarely used in isolation.
Usually, they form the building blocks for more complex
applications.
Definition: A workflow is a collection of tasks and their
dependencies.
7
Flexible Provisioning of Service Workflows
Taverna Workflow (myGrid)
8
Source: Exploring Williams-Beuren Syndrome Using myGrid, Hannah Tipney ,
http://www.mygrid.org.uk/wiki/pub/Mygrid/PresentationStore/ISMB04_Glasgow.ppt
Flexible Provisioning of Service Workflows
Pegasus Workflow
9
Source: Pegasus Teragrid Talk SC2005 Seattle Washington, http://pegasus.isi.edu/pegasus/presentations/pegasus-tg-final.ppt
Flexible Provisioning of Service Workflows
Service Provisioning

Services are dynamically provisioned (selected) by consumers at run-time.
Value
-$20
-$25
-$10
$100
24 h
Deadline
-$5

Failure!
Services are provided by autonomous agents.
 These may be unreliable (may fail or take longer than expected)…
 …and heterogeneous.
10
Flexible Provisioning of Service Workflows
Problem Statement

How to design a service consuming agent able to deal
effectively and efficiently with unreliable and
heterogeneous service providers when executing
complex workflows.
11
Flexible Provisioning of Service Workflows
Related Work

Many current approaches concentrate on functional aspects of
services and assume their behaviour to be deterministic.

Some work explicitly considers service failures:

Exception handling (e.g., fault handlers in WS-BPEL),
 Fixed redundancy (e.g., SETI@home, replicated Web services),
 Retry and timeout policies (Zeng 2005, Erradi 2006),
 Non-functional service constraints (McIlraith and Son 2002).

These require significant manual input!
12
Flexible Provisioning of Service Workflows
Related Work (Quality-of-Service Optimisation)

Local task QoS optimisation (Zeng 2004):



For each task, provision the provider that optimises some property for that
task (e.g., cost, reliability, duration).
Global workflow QoS optimisation (Zeng 2003, Yu/Lin 2005):

Provision one provider for each task, so that a weighted sum of global
performance characteristics is optimised:

Adaptive variants re-provision upon failure (Canfora 2005).
But: These do not reason explicitly about failures, rely on
manually specified weights and constraints, and select single
provider for each task.
13
Flexible Provisioning of Service Workflows
Flexible Provisioning
On-Demand Invocation
Central Idea

How to address uncertainty during provisioning?
Existing work mostly relies on single
service for each workflow task.
We can do better by
exploiting parallel and
serial redundancy.
… and by taking into
consideration service
heterogeneity.
15
Flexible Provisioning of Service Workflows
Service Model

We devised an abstract model to describe a serviceoriented system.
• Cost:
c(s1) = £100
• Failure Prob.:
f(s1) = 0.01
• Duration:

Assumptions:




16
Flexible Provisioning of Service Workflows
Assume silent “crash” failures.
Providers paid on invocation.
Failures and durations are independent.
Free disposal of redundant services (but
cost still incurred!)

Utility function:
Flexible Strategy

We want to find a provisioning allocation for each task, e.g.:

This is an optimisation problem:
Expected reward
17
Flexible Provisioning of Service Workflows
Expected cost
Why is this difficult?

Intuitively,
 Combinatorial problem:


Difficult objective function (probabilistic durations).
Based on this, we can show that provisioning is inherently hard...
18
Flexible Provisioning of Service Workflows
Provisioning Problem
Knapsack
PERT CDF
(NP-complete)
(#P-complete)
Provisioning
KS mp PROV
CDF tp PROV

Provisioning is NP-hard

Big problem as we wanted efficient methods for realistic workflows!
19
Flexible Provisioning of Service Workflows

Provisioning is #P-hard
Flexible Strategy

Approximate the expected utility of an allocation using a
heuristic utility function:
Estimated utility
Success probability
Estimated workflow
duration pdf

Optimise this with local search.
20
Flexible Provisioning of Service Workflows
Reward function
Estimated cost
Local Task Calculations

We start by calculating a number of performance parameters for each
task in the workflow:
2 Service populations:
Cost:
£1
£30
Success:
25%
95%
Duration:
Exp
(80)
Gamma
(10,6)
Success Probability: 95.00%
Expected Cost: £30.00
Expected Duration: 60.50 min
Variance: 361.19 min2
Success Probability: 96.83%
Expected Cost: £7.23
Expected Duration: 75.59 min
Variance: 4030.84 min2
Success Probability: 99.99%
Expected Cost: £26.15
Expected Duration: 56.23 min
Variance: 1501.57 min2
21
Flexible Provisioning of Service Workflows
Global Workflow Calculations

These task parameters are then combined to estimate the
overall expected profit:
30 £10
95%
100%52£24
345
266
80%22£3
7
99%
£5
25
100%15£42
164
90%43£30
111
Global Parameters:
Success Probability: 68%
Estimated Cost: £98.40
Estimated Duration: 132 min
Variance: 912 min2
292
= 162.48
0.68
22
Flexible Provisioning of Service Workflows
383.64
98.40
Empirical Evaluation

To test the strategy, we compare it to a number of benchmarks:

Naïve: Provisions a single provider for each task.
 Models
current approaches that do not consider service unreliability.

Global QoS: Optimises weighted QoS measures over entire
workflow (set all wi=1/3, use maximum utility and zero reward time
as budget/time constraints).

Adaptive Global QoS: As above, but also uses timeouts and reprovisions dynamically.

Local QoS: Optimises weighted QoS measure for each task.
23
Flexible Provisioning of Service Workflows
Empirical Evaluation
24
Flexible Provisioning of Service Workflows
Empirical Evaluation
25
Flexible Provisioning of Service Workflows
Empirical Evaluation
26
Flexible Provisioning of Service Workflows
Empirical Evaluation
27
Flexible Provisioning of Service Workflows
Empirical Evaluation
28
Flexible Provisioning of Service Workflows
Further Results

We can compare our performance to an
optimal strategy for very small workflows
(3 tasks!).

Achieves around 98% of optimal utility.

Results indicate that our strategy is
robust to inaccurate information (with
errors up to 10-15%). Beyond that,
generally degrades gracefully, but
problems when expected utility very low.

Trends hold on larger workflows (tested
up to 1000 tasks).
29
Flexible Provisioning of Service Workflows
So far…

We have proposed a flexible provisioning strategy that deals
with uncertain service providers:

By provisioning multiple providers redundantly for critical tasks.
 By re-provisioning services that seem to have failed.
 By exploiting the heterogeneity of providers.

Our strategy outperforms the state of the art in flexible
service provisioning.

But so far, our strategy:

Assumes that service populations are static throughout execution.
 Assumes that services are always invoked on demand.
 Does not adapt to new information during execution.
30
Flexible Provisioning of Service Workflows
Flexible Provisioning
Advance Agreements
Advance Provisioning


Increasingly, services will be offered in the context of prenegotiated agreements (this is already emerging in
computational Grids).
The agreements form a contract about when and how a service
will be provided in the future.
I need service X in 2 hours.
Reservation Cost:
Invocation Cost:
Start time:
Completion time:
32
Flexible Provisioning of Service Workflows
£20
£10
2:00
2:30
Advance Provisioning

Performance characteristics might vary depending on time of
provisioning (e.g., airline pricing policies):
Contract Term
On-Demand
1h Advance
12h Advance
Cost
£10
£5
£15
Duration
45min
20min
10min
Failure Probability
10%
2%
0.1%
33
Flexible Provisioning of Service Workflows
Modified System Model

Model a dynamic market:
Consumer
Providers
0

100
200
Each time step:

Providers post offers, according to some
stochastic process.
 Consumer provisions offers.
 Offers disappear (acquired by other consumers
or withdrawn).
34
Flexible Provisioning of Service Workflows
300
Service Type: T1
Start Time:
End Time:
Reservation Cost:
Execution Cost:
Penalty:
Failure Probability:
Defection Probability:
200
220
£1
£5
£20
10%
50%
Challenges

Future availability of offers uncertain.

Fixing advance agreements may mean that reservations costs
are lost if preceding services fail.

Need to balance benefits of advance provisioning with risk!
35
Flexible Provisioning of Service Workflows
Our Approach

Gradual Provisioning:
High-level decision
Provisioned
Completed
Failure



First make high-level provisioning decisions (how and when to
provision tasks).
Follow these at run-time.
Adapt strategies when failures occur.
36
Flexible Provisioning of Service Workflows
High-Level Decisions

Assume we have a set of atomic provisioning strategies for
each service type:
…
…
Service Types
Strategies

Strategy w:
• Advance time
• Number of offers
• Selection strategy
Expected
performance:
• Reservation cost
• Execution cost
• Failure probability
• Duration (if successful)
• Duration (if failed)
• Variances of above
Performance statistics of strategies are learnt offline by
observing the market.
37
Flexible Provisioning of Service Workflows
Contingency Planning


Atomic strategies represent single attempt at completing a task.
We can build simple plans from several such strategies to deal
with failures:
Try strategy x
(e.g., cheapest offer, 10 min in advance)
Success?
yes
Done
no
Try strategy y
(e.g., 2 most reliable offers, immediately)
no
Success?
38
Flexible Provisioning of Service Workflows
yes
Done
Expected task
performance:
• Success probability
• Reservation cost
• Execution cost
• Duration
• Variance
Overlapping Provisioning


Finally, associate a late probability pl with each task plan.
This indicates when services should be provisioned.
provision after tx-1
tx-2
tx-1
tx
pl = 0.0


provision during tx-1
tx-2
tx-1
pl = 0.05
tx
provision after tx-2
tx-2
tx-1
tx
pl = 0.1
Higher pl results in less delays when provisioning in advance,
but also increases probability that provisioned offers are lost
when preceding tasks overrun.
Use heuristic based on critical path to estimate delays and to
determine during which task to provision.
39
Flexible Provisioning of Service Workflows
Strategy Summary
Create initial strategy S

Given a high-level plan and late
probability for each task, estimate utility
in a similar manner as for on demand
invocation, but include delays and
reservation costs.
Start of time step:
Update S with outcomes
Optimise S
Realise high-level
decisions

yes
Invoke due services
Optimise this using simulated annealing.
Was S altered in
previous step?

At run-time, follow task strategies, then
incorporate information about
provisioned offers and adapt strategy
accordingly.
no
Expected
Utility of S > 0?
no
Abandon workflow
40
Flexible Provisioning of Service Workflows
yes
Provision chosen services
Empirical Evaluation

Small 8-task workflow with 5 service types.

Offer characteristics drawn from uniform distributions.

Comparison with three benchmark strategies:

Global QoS
 Adaptive Global QoS
 Local QoS

Also assume services always provide refunds for failures.
41
Flexible Provisioning of Service Workflows
Empirical Evaluation
42
Flexible Provisioning of Service Workflows
Empirical Evaluation
43
Flexible Provisioning of Service Workflows
Empirical Evaluation
44
Flexible Provisioning of Service Workflows
Empirical Evaluation
45
Flexible Provisioning of Service Workflows
Conclusions

We proposed a novel algorithm that uses redundancy and
dynamic re-provisioning to deal with uncertain service
providers.

It does this in a flexible way by reasoning about service
behaviours in the context of a decision-theoretic framework.

We first showed how it applies to scenarios where services are
invoked on-demand, then extended it to environments with
advance agreements.

In most scenarios considered, our strategy outperforms the
state of the art in service provisioning.
46
Flexible Provisioning of Service Workflows
Future Work

Improved prediction of workflow durations.

More expressive workflow models with branches and loops.

Consider more dynamic environments.

Incorporate meta-reasoning about time spent on optimisation.
47
Flexible Provisioning of Service Workflows
Bibliography

Presented work from:



Related work on homogeneous providers:


Stein, Jennings, Payne (2007). Provisioning Heterogeneous and Unreliable Providers for
Service Workflows. In: AAAI-07. pp. 1452-1458.
Stein, Jennings, Payne (2008). Flexible Service Provisioning with Advance Agreements. In:
AAMAS-08. (in press).
Stein, Payne, Jennings (2008). Flexible Provisioning of Web Service Workflows. In: ACM
Toit 8(4). (in press).
Other related work on QoS-based optimisation:




Zeng et al (2003). Quality driven web services composition. In: WWW-03. pp. 411-421.
Zeng et al (2004). QoS-Aware Middleware for Web Services Composition. In IEEE Soft.
Eng. pp. 311-327.
Yu and Lin (2005). Service Selection Algorithms for Composing Complex Services with
Multiple QoS Constraints. In: ICSOC-05.
Canfora et al (2005). QoS-Aware Replanning of Composite Web Services. In: ICWS-05.
pp. 121-129.
48
Flexible Provisioning of Service Workflows
Thank you!
Any Questions?
This work was sponsored by:
: