14-12-2012, 02:58 PM
Top K Query for QoS-Aware Automatic Service Composition
Top K Query for QoS-Aware.pdf (Size: 2.4 MB / Downloads: 60)
Abstract
With the proliferation of Web services, service engineers demand automatic service composition algorithms that
not only synthesize the correct service compositions from thousands of services but also satisfy the quality requirements of
users. This is known as QoS-aware automatic service composition problem. Our observation is that current research of only
finding the optimal service composition has several shortcomings. Users have to utilize the optimal one, which will make it rigid,
and consequently brings about problems, such as overload of ”hot services” and lack of choices for users. To cope with these
problems, we propose top k query. Specifically, we extend our QSynth which won the performance championship ofWeb Service
Challenge 2009 and 2010, to support the query of top k service composition results. The so-called QSynth-Top-K can act as
a wizard for service composition modeling. In this wizard, a progressive and incremental Key-Path-Based Loose(KPL) algorithm
with 100% accuracy is proposed and implemented. Evaluations show that, compared to the state of the art, QSynth-Top-K
achieves superior scalability and accuracy with respect to a large variety of composition scenarios. Moreover, we generalize
a new graph problem: top k DAGs (Directed Acyclic Graphs) problem based on the above work. Besides top k query of QoSaware
automatic service composition presented in this paper, applications of this new graph problem contains supply chain, API
recommender and so on. KPL algorithm illustrated in this paper can address them efficiently too.
INTRODUCTION
Service composition aims at reusing and composing existing
atomic Web services to build rich functionalities, and
becomes very popular when developing service oriented
applications. The service composition result is also named
as composite service, which defines the invoking structure
and the control flow of participating atomic services. As the
number of Web services in the Internet becomes large [1],
it will be far from practical to ask users to manually select
and composite interoperable services. Automatic service
composition, which could automatically generate correct
service compositions that satisfying the functional request,
comes into being, and attracts lots of attention from both
research and industrial communities [2], [3], [4], [5]. Real
scenarios in Amazon [6] and SAP [7] show that it is helpful
for modeling and verifying of service compositions.
A Motivating Example
In order to illustrate (top k) QoS-aware automatic service
composition concretely, we use an example to explain it
first. Then, we present its new challenges.
This example is about online document preparation system.
Assuming that you have got a document, and you
want an online service to convert it to PDF file and to
fax it to someone else as quickly as possible. This process
is illustrated in the top of Fig.1, which contains four
tasks: ”virus check”, ”spell check”, ”pdf conversion” and
”fax”. Each task can be fulfilled by one atomic service
or a composite service. Particularly, for spell check, you
have ”dictionary service”, ”thesaurus service”, ”grammar
service” together to fulfill it.
WSLA
The Web Service Level Agreement (WSLA) language[19]
focuses on the contracting between the service provider and
customer. It is used to specify quality of service within a
Service Level Agreement (SLA). A quality dimension is
expressed by a SLA parameter and described with name,
type, unit, definition and purpose. The work in [19] presents
a nice solution about How to get the QoS of a service.
QoS Computation Rules
Given a composite service, we need to calculate its overall
QoS based on its contained atomic services. Moreover, we
use the overall QoS to rank the service composition result.
In order to calculate overall QoS, we first define four types
of QoS measures:
sum type (such as response time)
min type (such as throughput)
multiplication type (such as reputation)
max type
In addition, these QoS types can be categorized into two
classes [18], [20].
Negative: the higher the value, the lower the quality,
such as response time and price.
Positive: the higher the value, the higher the quality,
such as throughput and reputation.
Sim-Dijkstra Algorithm
This section presents Sim-Dijkstra algorithm[12] in the
first step which is used to get optimal key paths. It starts
a forward search from Start node. In this process, we
record all the enabled services, enabled inputs and their
corresponding providers. These information are necessary
for retrieving the optimal key paths then.
Details of Algorithm
The general idea of this algorithm is: we generate all
enabled services on the graph G by a forward search from
Start. But every time, we deal with the enabled service
in the priority queue with the optimal overall QoS first.
We then get its enabled successors and put them into the
priority queue recursively. This approach is presented in
Algorithm 1. In the original Sim-Dijkstra algorithm[12], it
stops when End node is enabled even the priority queue,
”enableSers”, is not empty. While Sim-Dijkstra algorithm
here will terminate only when the priority queue is empty.
Algorithm details: this algorithm starts by adding the
enabled nodes by Start into the priority queue (Line 1
in Algorithm 1). The priorities of services in the queue
are based on allQoS of them. So we pop the service
with the best allQoS in the priority queue every time.
For the popped service, we subtract the counts of its
successors according to its outputs. Whenever a service’s
count becomes zero, the corresponding service is enabled.
We add this new enabled service into the priority queue
and conduct the above process recursively until the queue
is empty (Lines 2-10 in Algorithm 1). The corresponding
information are recorded in PRT as shown in Fig.6.
EVALUATION
In this section, we compare KPL algorithm with state of the
art solutions. KPL algorithm is implemented and integrated
in QSynth-Top-K. In our evaluation, the generated workload
is based on public Web Service Challenge test set generator
[21] and real Web services’ QoS values from [22]. In order
to prove the scalability and efficiency of our algorithm in
different and even extreme conditions, we generate three
groups of data sets and each group contains six different test
sets by varying three parameters: the number of concepts,
the number of services and the solution-depth. Here, each
Web service has the corresponding response time (the unit
is ms). The three groups of Web services are shown in
Table 4. All the experiments are carried out on a 2.4GHz
machine with 4 GB RAM running Windows 7.
Real QoS
In order to evaluate KPL algorithm in real scenarios, we
also conduct experiments on some real Web services’ QoS
values from [22], where about 2000 real Web services’ QoS
values are collected. With regard to these real Web services’
QoS values, we replace the synthetic response time with
them for the generated Web services (We do not use real
Web services in the experiment. Because there is still not
enough semantic information for their WSDL documents
now.
RELATED WORK
QoS-Aware Automatic Service Composition
In SOC paradigm, since it is always impossible to find
composition results manually from huge amount of services,
automatic service composition is proposed, which
aims to enable automatic search of service compositions
for given requests. There are mainly two categories of
approaches: AI planning [2], [27], [3], [28] and graph
search [5], [29], [30]. In addition to these centralized
algorithms, a distributed approach is put forward in [31],
which improves system performance by utilizing distributed
computing resources. These solutions for automatic service
composition do not consider non-functional attribution of
service. They usually return the service composition results
with fewer services or less depth.
On the other hand, to guarantee local or global QoS requirements
of service composition, service selection problem
has attracted a lot of attention [20], [18], [32], where
Integer Programming, multichoice 0-1 knapsack problem or
a multiconstraint optimal path problem, genetic algorithms
are adopted. Moreover, the authors in [33] propose a
community-centric approach for service selection. Assisted
by the service community, the users can explore the space
of potential composition opportunities without having to
understand too many details of individual candidate services.
Research in [34] focuses on the routing aspect of
QoS-aware service selection problem. So its goal is to
achieve efficient network usage while guaranteeing the QoS
of services, which is like network configuration problem.
In essence, these approaches for service selection usually
assume the existence of a predefined abstract process or
template, a set of ”abstract” tasks or service classes, and the
service instances with same functionality for each task. This
assumption maybe not true in real service environment.
CONCLUSIONS
Most current work on QoS-aware automatic service composition
problem is about how to find (near) optimal composition
result. However, this will bring many limitations
to both service’s users and providers. To cope with these
limitations, we address top k query for QoS-aware automatic
service composition problem. An efficient system,
QSynth-Top-K which adopts KPL algorithm, is designed
and implemented in this paper. Experiments on public data
sets and real Web service QoS show that QSynth-Top-K has
good scalability, efficiency, 100% accuracy, which is better
than related works. Moreover, we present how to extend
KPL algorithm to support multiple QoS measurements.
Finally, a new graph problem, top k DAGs problem, is
generalized. Many other problems from different fields can
be transmitted into this new graph problem besides top
k query of automatic service composition, such as supply
chain and API recommender.