Web service composition requests are usually combined with end-to-end QoS requirements, which are specified in terms of non-functional properties (e.g. response time, throughput and price). The goal of QoSaware service composition is to select the best combination of services that meet these end-to-end requirements, while maximizing the value of a pre-defined utility function. This problem can be modeled as a multidimension multi-choice 0-1 knapsack problem, which is known as NPhard in the strong sense. Existing solutions that rely on general purpose solvers suffer from poor performance, which render them inappropriate for applications with dynamic and real-time requirements. Moreover, global optimization techniques assume a centralized system model, which contradicts with the distributed and loosely-coupled environment of web services. The aim of this thesis is to develop scalable QoS optimization solutions that fit better to the distributed environment of web services. The idea is to decompose global constraints into local constraints that have to be fulfilled by a set of distributed service brokers. A solution that combines global optimization and local selection techniques is proposed.
The service-oriented computing paradigm and its realization through standardized Web service technologies provide a promising solution for the seamless integration of business applications to create new value-added services. Industrial practice witnesses a growing interest in this ad-hoc service composition. With the growing number of alternative web services that provide the same functionality but differ in quality parameters, the composition problem becomes a decision problem on the selection of component services with regards to functional and non-functional requirements. In this work, we look at the non-functional requirements, namely quality of service parameters in composing web services. 1.1
Consider for example the personalized multimedia delivery scenario in Figure 1.
A PDA user requests the latest news from a service provider. Available
multimedia content includes a news ticker and topical videos in MPEG 2 only. The
following services are are required to serve the user’s request: a transcoding
service for the multimedia content to fit the target format, a compression service
to adapt the content to the wireless link, a text translation service for the ticker,
and also a merging service to integrate the ticker with the video stream. The
user request can be associated with some end-to-end QoS requirements (like
bandwidth, latency and price). The service composer has to ensure that the
aggregated QoS values of the selected services match the user requirements.
Dynamic changes due to changes in the QoS requirements (e.g. the user switched
to a network with lower bandwidth) or failure of some services (e.g. some of the
selected services become unavailable) can occur at run-time. Therefore, a quick
response to adaptation requests is important in such applications.
Two general approaches exists for the QoS-driven service composition: local
optimization and global optimization. In the local optimization approach, one service
is selected from each service class independently based on its local utility value.
This approach is very efficient as the time complexity of the local optimization
approach is linear with respect to the number of service candidates. However,
local optimization cannot satisfy end-to-end QoS requirements (like maximum
total response time). On the other hand, the global optimization approach aims
at solving the problem on the composite service level. This approach seeks the
service composition, which maximizes the overall utility value, while
guaranteeing global constraints. The global optimization problem can be modeled as
Multi-Choice Multidimensional Knapsack problem (MMKP), which is known to
be NP-hard in the strong sense [
The aim of this PhD thesis is to address the performance and scalability issues of QoS aware service selection by applying a scalable distributed heuristic that combines global and local optimization techniques. The approach contributes the following results to the state of the art: 1. Decomposition of global QoS constraints into local constraints is modeled as a mixed integer program. The size of the resulting program is independent on the number of service candidates and hence can be solved more efficiently than existing MIP-based solutions. 2. Selection of component services is solved using guided local optimization.
The local optimization is performed for each service class independently and in parallel to further improve the performance. 3. Extensive evaluation of the approach by comparing its performance and quality with existing exact and heuristic solutions. The evaluation will be done by simulation as well as in a large real world environment, e.g. PlanetLab. 2
The QoS-based web service selection and composition in service-oriented
applications has recently gained the attention of many researchers [
A Distributed Approach for Web Service QoS Optimization We divide the QoS-aware service composition problem into two sub-problems that can be solved more efficiently in two subsequent phases. In the first phase, we use global optimization techniques to find the best decomposition of global QoS constraints into local constraints on the component service level. In the second phase, we use local selection to find the best component services that satisfy the local constraints from the first phase.
We assume an architecture consisting of a service composer and a number of service brokers. The service composer instantiates a composite service in collaboration with the service brokers. Each service broker is responsible for managing QoS information of a set of web service classes. A list of available web services is maintained by the service broker along with registered measurements of their non-functional properties, i.e. QoS attributes, like response time, throughput, price etc. For the sake of simplicity we assume in this paper that each service class is maintained by one service broker. The two phases of our approach are described in the next subsections in more details. 3.1
In order to avoid discarding any service candidates that might be part of a
feasible composition, the decomposition algorithm needs to ensure that the local
constraints are relaxed as much as possible while meeting global constraints.
To solve this problem, we divide the quality range of each QoS attribute into a
set of discrete quality values, which we call “quality levels”. We then use mixed
integer programming (MIP) to find the best combination of these quality levels
for using them as local constraints. The size of our MIP model is much smaller
than the size of the MIP model in [
Quality Levels: In this paper, we use a simple method for constructing the quality levels. For each service class Si, we divide the quality range of each of the m QoS attributes into d quality levels: qi1k, ..., qidk, 1 ≤ k ≤ m as follows: Qmin(i, k) qizk = z−1 + Qmax(i,k)−Qmin(i,k)
qik d Qmax(i, k) if z = 1 if 1 < z < d if z = d where Qmin(i, k) and Qmax(i, k) are the local minimum and maximum values, respectively, for the kth attribute of the service class Sj . We then assign each quality level qizk a value between 0 and 1, which indicates the probability pizk that using this quality level as a local constraint would lead to finding a solution. The probability pizk for the zth level of qk at Si is computed as follows: pizk = h/l where h is the number of service candidates satisfying qizk and l is the total number of service candidates at Si.
MIP Formulation: The goal of our MIP model is to find the best decomposition of QoS constraints into local constraints. Therefore, we use a binary decision variable xizk for each local quality level qizk such that xik = 1 if qizk is z selected as a local constraint for the QoS attribute qk at the service class Si, and xizk = 0 otherwise. To ensure that only one quality level is selected from the set (1) (2) of d levels of the QoS attribute qk at the service class Si, we add the following set of constraints to the model:
d
X xizk = 1, ∀i, ∀k, 1 ≤ i ≤ n, 1 ≤ k ≤ m
z=1
where n is the number of service classes and m is the number of QoS constraints.
Note that the total number of variables in the model equals to n ∗ m ∗ d, i.e.
independent on the number of service candidates per class l. By ensuring that
the number of quality levels d is small enough such that m ∗ d ≤ l we can ensure
that the size of our MIP model is smaller than the size of the model used in [
n m maximize Y Y pizk , 1 ≤ z ≤ d i=1 k=1 n m d maximize X X X ln(pizk) ∗ xizk
i=1 k=1 z=1 We use the logarithmic function to linearize (3) in order to be able to use it in the MIP model: By solving this model using any MIP solver methods, we get a set of local quality levels that we use in the second phase for guiding local search. 3.2
We use the local constraints obtain from the first phase as upper bounds for
the QoS values of component services. Web services that violate these local
constraints are skipped from the search. We then sort the qualified services by
their utility values and select the top service from each class. In order to
evaluate the multi-dimensional quality of a given web service we use a Multiple
Attribute Decision Making approach: i.e. the Simple Additive Weighting (SAW)
technique [
We compute the utility U (sji) of the i-th service candidate in class Sj as: r U (sji) = X k=1
Qmax(j, k) − qk(sji) Qmax′(k) − Qmin′(k) · wk (5) r with wk ∈ R0+ and Pk=1 wk = 1 being the weight of qk to represent user’s priorities. 4
This PhD thesis is aimed at the development of distributed and scalable solutions to the global QoS optimization problem for web service compositions. Unlike existing approaches that model the problem as a conventional combinatorial optimization problem, we model the problem as a distributed optimization problem by exploiting the special characteristics and structure of the web service environment. Current results of this work indicate a very promising improvement over existing solutions. The next steps of this work include extending the existing model to support different styles of web service compositions and QoS constraints. We also plan to evaluate the performance of our approach against existing exact and approximate solutions by extensive simulations as well as in a large real world environment, e.g. PlanetLab.