PhD Theses at KOM

QoS-aware Service Selection - Optimization Mechanisms and Decision Support for Complex Service-based Workflows

Dieter Schuller

Wednesday July 17, 2013

English abstract:

In competitive markets where enterprises produce and offer similar products and services, a high degree of flexibility and efficiency regarding the execution of business processes is required. Flexible adaptations of business processes due to changing customer requirements have to be realized at minimum costs. To achieve and enable the implementation of flexible processes, the paradigm of Service-oriented Architectures is often recommended. Realizing a service-oriented approach enables business processes to be supported and executed by the use of services, which encapsulate business logic and functionality. Following the vision of the Internet of Services, services for different areas of life and business will be available at, e.g., service marketplaces. If services are offered at these marketplaces and provide comparable functionalities, such that they are equally appropriate to execute certain parts of business processes at different cost and quality levels, enterprises will have the possibility to select among them based on non-functional aspects such as required degrees of Quality of Service. The problem of selecting services from a set of equally appropriate ones on the basis of cost and Quality of Service is well-recognized in the literature. It is commonly referred to as Service Selection Problem.

While many related approaches and work exists in the literature addressing the Service Selection Problem and providing optimal as well as heuristic solutions to it, the process structures and workflow patterns considered and supported are rather straightforward. This limitation is addressed in this thesis by focusing on complex, interlaced, acyclic as well as cyclic structured and unstructured workflows, that so far have not been accounted for. Hence, corresponding aggregation specifications have been developed enabling the aggregation of non-functional service values according to different workflow patterns. In this respect, best-, worst-, and average-case analyses can be carried out. The work at hand thereby aims at computing optimal solutions to the aforementioned problem. To achieve this, an optimization framework has been developed for specifying and formulating the Service Selection Problem as an optimization problem.

In addition to providing the mentioned solution approach for computing optimal solutions to the Service Selection Problem, a heuristic solution method has been developed coping for scalability issues. Both approaches are thereby based on deterministic values for considered non-functional service attributes.

As Quality of Service is not necessarily always deterministic, such values may differ. If an optimal solution to the Service Selection Problem, which corresponds to an optimal selection of services, has been computed that satisfies specified constraints on Quality of Service, such constraints may still be violated when actually executing the selected services. As these services possibly show a different behavior at runtime with respect to Quality of Service compared to the expected deterministic values assumed for the optimization, corresponding constraints might be violated and potentially lead to severe consequences such as penalties. In order to assess and reduce potentially negative consequences of differing Quality of Service, the work at hand provides a simulation-based adaptation framework which focuses on reducing the risk of uncertainty and therewith of a potential negative impact of stochastic Quality of Service behavior. Evaluation results show that reductions in total cost up to 30% can be achieved - depending on the considered scenario - by reducing penalty costs that accrue due to the violation of Quality of Service constraints.

German abstract:

In kompetitiven Märkten, in denen Unternehmen ähnliche Produkte und Dienste anbieten, ist ein hoher Grad an Flexibilität und Effizienz hinsichtlich der Ausführung von Geschäftsprozessen erforderlich. Flexible Anpassungen besagter Geschäftsprozesse aufgrund von sich ändernden Kundenanforderungen müssen zu minimalen Kosten realisiert werden können. Das Paradigma der Dienstbasierten Architekturen wird dabei hinsichtlich der Umsetzung von flexiblen Geschäftsprozessen häufig empfohlen. Durch die Realisierung eines Dienst-basierten Ansatzes können Geschäftsprozesse mithilfe von Diensten, die Geschäftslogik sowie Funktionalität kapseln, unterstützt und ausgeführt werden. Der Vision des Internets der Dienste folgend werden Dienste für verschiedene Lebens- und Geschäftsbereiche beispielsweise auf Marktplätzen für Dienste verfügbar sein. Falls Dienste auf solchen Marktplätzen angeboten werden und ähnliche Funktionalitäten zu unterschiedlichen Preisen sowie mit unterschiedlichen Dienstgüteniveaus bereitstellen, sodass sie ähnlich geeignet sind, um bestimmte Teile von Geschäftsprozessen auszuführen, haben Unternehmen die Möglichkeit, basierend auf nicht-funktionalen Aspekten wie benötigtem Dienstgüteniveau zwischen diesen zu wählen. Das Problem, zwischen ähnlich geeigneten Diensten auf Kosten und Dienstgüte basierend zu wählen, ist in der Literatur weithin bekannt. Es wird gewöhnlich als Dienst-Selektions-Problem bezeichnet.

Obwohl viele verwandte Ansätze und Arbeiten in der Literatur existieren, die das Dienst-Selektions-Problem adressieren und optimale sowie heuristische Lösungen bereitstellen, sind die dabei berücksichtigten und unterstützten Prozess- und Arbeitsablaufstrukturen eher überschaubar. Die vorliegende Arbeit adressiert die genannte Limitierung und fokussiert dabei auf komplexe, verschachtelte, azyklische sowie zyklische, strukturierte und unstrukturierte Arbeitsabläufe, die bisher noch nicht berücksichtigt wurden. Entsprechend wurden Aggregationsspezifikationen entwickelt, die die Aggregation von nicht-funktionalen Dienstwerten gemäß verschiedener Arbeitsablaufstrukturen ermöglichen. In diesem Zusammenhang können sowohl der beste, der durchschnittliche, sowie der ungünstigste Fall betrachtet und analysiert werden. Die vorliegende Arbeit zielt dabei auf die Berechnung von optimalen Lösungen für das zuvor genannte Dienst-Selektions-Problem ab. Um dies zu erreichen, wurde für die Spezifikation und Formulierung des Dienst-Selektions-Problems als Optimierungsproblem ein Optimierungsrahmenwerk entwickelt.

Um Skalierbarkeitsaspekte zu berücksichtigen, wurde zusätzlich zu dem erwähnten Lösungsansatz für die Berechnung von optimalen Lösungen für das Dienst-Selektions-Problem ein heuristischer Lösungsansatz entwickelt. Beide Ansätze basieren dabei auf deterministischen Werten für die berücksichtigten nicht-funktionalen Dienstattribute.

Da Dienstgüte jedoch nicht notwendiger Weise stets deterministisch ist, können solche Werte durchaus auch schwanken. Wenn eine optimale Lösung für das Dienst-Selektions-Problem, was einer optimalen Selektion von Diensten entspricht, berechnet wurde, die spezifizierte Nebenbedingungen hinsichtlich der Dienstgüte einhält, kann es dennoch vorkommen, dass diese Nebenbedingungen bei der Ausführung der Dienste verletzt werden. Da diese Dienste zur Laufzeit möglicherweise ein anderes Verhalten hinsichtlich Dienstgüte aufzeigen verglichen mit den deterministischen Werten, die für die Optimierung angenommen wurden, können besagte Nebenbedingungen verletzt werden, was möglicherweise zu schwerwiegenden Konsequenzen wie Strafen führen kann. Um mögliche, negative Konsequenzen aufgrund von schwankendem Dienstgüteverhalten zu bewerten und zu reduzieren, stellt die vorliegende Arbeit ein Simulationsbasiertes Anpassungsrahmenwerk zur Verfügung. Das Rahmenwerk zielt auf die Reduktion des Risikos ab, das sich durch die Unsicherheit hinsichtlich der tatsächlich auftretenden Dienstgüteeigenschaften ergibt, und somit auf potenziell negative Auswirkungen von stochastischem Dienstgüteverhalten. Evaluationsergebnisse zeigen, dass die Gesamtkosten durch eine Reduktion der Strafzahlungen, die aufgrund von Dienstgüteverletzungen anfallen, um bis zu 30% reduziert werden können - abhängig vom betrachteten Szenario.

PhD Theses