A Dominance-Based Approach for Selection in Service Composition
Chaogang Tang
1,2,3
, Qing Li
2,3
, Yan Xiong
1,3
, An Liu
1,2,3
, and Shiting Wen
1,2,3
1
Department of Computer Science and Technology,
University of Science & Technology of China, Hefei, China
2
Department of Computer Science, City University of Hong Kong, Hong Kong, China
3
Joint Research Lab of Excellence, CityU-USTC Advanced Research Institute, Suzhou, China
tcg@mail.ustc.edu.cn
, itqli@cityu.edu.hk, yxiong@ustc.edu.cn,
liuan@ustc.edu
,wst1029@mail.ustc.edu.cn
Abstract—Considering the dynamics of Web service
environments and concurrence of requests, we propose a
service selection scheme, which adopts top-k dominating
queries to generate a composition solution rather than only
selects the best composition solution for a given request. The
experimental results have investigated efficiency and
effectiveness of our approach and shown that it outperforms
baseline and traditional methods for service selection.
Keywords—dynamics; top-k; dominating; concurrency; service
selection
I. INTRODUCTION
Web services are platform-independent, loosely coupled,
self-contained, programmable web-enabled applications that
can be described, published, discovered, coordinated, and
configured using XML artifacts (open standards) for the
purpose of developing distributed interoperable applications.
Due to the wide application of SOA, large quantities of Web
services have been deployed over the Internet or the Web for
service users. As the requirements from service users
become more and more complicated, an atomic service often
can not handle a request by itself due to the limited
capabilities. This calls for composite services to combine
existing distributed atomic services, so as to perform the
complicated functionalities. The selection of component
services (atomic service) for a composite service is vital yet,
at the same time, also very arduous. This is because on one
hand, the number of alternative Web services which provide
the same functionality but differ in quality parameters, is
growing quickly; on the other hand, inappropriate selection
of component services can result in the degradation of a
composite service in terms of the quality of web service
(QoWS). For example, for a composite service that contains a
parallel structure, the response time of the composite service
is up to the component service having the maximum
response time rather than other ones within the parallel
module. Therefore the service selection in the parallel
module is to make sure that the response time of the
component service with the maximum response time is as
small as possible.
If we take into account the dynamics of Web service
environments, the service selection will become even more
complicated. This is because a current-best candidate service
for a component service may not be the best one at a later
time. In the dynamic Web service environments, the
performance of the Internet is unpredictable; the reliability
and effectiveness of remote Web services are also unclear.
Therefore, it can not be guaranteed that the QoWS attributes
of Web services do not fluctuate with the dynamic Web
service environments. Specially, we list three reasons for this
dynamic fluctuation:
• continuous responses to service requests. The overload
of service server will give rise to the fluctuation of the
overall performance of provided service, and usually
this fluctuation turns into QoWS degradation (e.g.
longer response time);
• network performance. Some QoWS attributes (e.g.
response time) may vary or subject to the quality of
network (e.g. long latency, network disconnection, etc.);
• intentional behaviors. For example, service providers
sometimes do not deliver their claimed QoWS, so as to
reduce cost or for other purposes.
In this paper, we focus on the former two reasons that
lead to QoWS fluctuation. One serious consequence that
results from the aforementioned QoWS degradation is the
increase of response time. As an important metrics of QoWS
criteria, the growth of response time, which means that
service users need to wait for a longer time than they expect,
may even result in an unacceptable completion time,
therefore considerable losses to service users may occur
(e.g., in terms of lost business revenue, time, or penalties
incurred by missing contractual deadlines). We observe that
in the context of dynamic service environments, few works
have taken concurrency into consideration when a composite
service is planned. By concurrency here we mean that a lot
of requests to a composite service arrive concurrently. We
illustrate this by a simple example here. Suppose that a
composite service CS consists of two component services
denoted as s
1
and s
2
respectively. There are three candidate
services (s
11
, s
12
and s
13
) which can perform the functionality
of s
1
and two candidate services (s
21
and s
22
) for s
2
.
According to the traditional service selection method which,
based on a utility function, aggregates all the values from all
the dimensions with respect to QoWS into a single value. Let
us assume the best composition scheme for our example is
s
11
and s
21
, which means that when CS receives a request, it
will employ s
11
and s
21
to execute it. So far there have been a
lot of real-time systems such as real-time ticket ordering
system, stock trading, and navigational driving guide, etc.,
which are characterized by timeliness and lots of concurrent
requests. Assume for our example that there are 1000
2011 Eighth IEEE International Conference on e-Business Engineering
978-0-7695-4518-9/11 $26.00 © 2011 IEEE
DOI 10.1109/ICEBE.2011.16
36