Zusammenfassung In Serviceorientierten Architekturen können Geschäftsprozesse durch Komposition von lose gekoppelten Services realisiert werden. Sind entsprechende Services auf Service-Marktplätzen vorhanden, kann ein Service-Konsument zwischen Services wählen, die die von ihm benötigte Funktionalität bereitstellen, basierend auf deren Dienstgüte (engl.: Quality of Service - QoS). Diese QoS-basierte Service-Selektion wird in der Literatur zumeist für Zustandslose Services durchgeführt. Zustandsbehaftete Services können, je nach tatsächlichem Ausführungspfad, verschiedene Ausprägungen in ihren QoS-Attributen annehmen, was in verwandten Arbeiten bisher nicht berücksichtigt wird. In der vorliegenden Arbeit werden Ansätze skizziert, mit denen die QoS-basierte ServiceSelektion auch für Zustandsbehaftete Services durchgeführt werden kann.
In hoch kompetitiven Märkten, in denen die agierenden Unternehmen ähnliche
Produkte und Services anbieten (wie bspw. in der Finanzindustrie), ist es
erforderlich, dass die Geschäftsprozesse effizient ausgeführt werden. Zudem müssen
Unternehmen in solchen Märkten in der Lage sein, ihre Geschäftsprozesse
dynamisch und flexibel an sich ändernde, marktgetriebene Rahmenbedingungen
anzupassen. Diese Flexibilität können Unternehmen durch die Umsetzung einer
Serviceorientierten Architektur (SOA) erreichen, in der lose gekoppelte Services –
mit einer mehr oder weniger grob granularen Funktionalität (vgl. [
Um die Realisation der Geschäftsprozesse möglichst effizient zu gestalten,
sollten diejenigen Services eingesetzt werden, die sowohl die notwendigen
Funktionalitäten bereitstellen als auch den qualitativen Anforderungen der Unternehmen
genügen. Diese Services müssen dabei nicht notwendigerweise ausschließlich im
eigenen Unternehmen vorhanden sein. Sind (aus funktionaler Sicht)
entsprechende Services auf Service Marktplätzen verfügbar – wie in der Vision des
Internet of Services postuliert – können Unternehmen zwischen Services (die
die benötigte Funktionalität bereitstellen) basierend auf deren Qualität (engl.:
Quality of Service – QoS) wählen. Dieses Service-Selektions-Problem (SSP) wurde
in der Literatur bereits in vielen Arbeiten (bspw. in [
Im folgenden Abschnitt 2 wird die vorliegende Arbeit von verwandten Arbeiten abgegrenzt. In Abschnitt 3 wird das SSP (für Zustandslose Services) vorgestellt, für dessen Lösung feste (eindeutige) QoS-Werte erforderlich sind. Die besonderen Eigenschaften für Zustandsbehaftete Services werden anschließend in Abschnitt 4 beschrieben. Darauf aufbauend skizziert Abschnitt 5 mögliche Ansätze für das SSP mit Zustandsbehafteten Services. Abschnitt 6 dient der Zusammenfassung des vorliegenden Beitrags sowie der Vorstellung von Ideen für zukünftige Arbeiten. 2
Das SSP (für Zustandslose Services) wurde in der Literatur bereits von vielen
Autoren adressiert. In einigen Arbeiten (bspw. in [
Der vorliegende Ansatz zielt ebenfalls auf die Berechnung einer (nahezu) optimalen Lösung für das SSP ab. Die Kenntnis aller möglichen Ausführungspfade wird dabei jedoch nicht benötigt, wodurch sich der vorliegende Ansatz von verwandten Arbeiten in diesem Bereich abgrenzt. Des Weiteren können auch rekursive Verschachtelungen von Workflowpatterns berücksichtigt werden, was nach unserem Wissensstand in verwandten Arbeiten nicht adressiert wurde. 3
Bei der QoS-basierten Service-Selektion geht es darum, für einen abstrakten Workflow (bspw. in Business Process Modeling Notation – BPMN) konkrete Services zu finden, die die einzelnen Workflow-Schritte (d. h., die abstrakten Services) realisieren. Das Ergebnis der Service-Selektion stellt dabei einen Ausführungsplan PS1
PS2
PS8 PS12
PS9
PS10 PS13 PS6
PS11
PS14 Abbildung 1: Beispiel für einen Workflow PS7
PS15 dar, in dem eine Zuordnung von konkreten Services zu den einzelnen abstrakten Services vorgenommen wird.
Um ein solches SSP spezifizieren und lösen zu können, müssen die
QoSAttribute der infrage kommenden Services entsprechend ihrer Anordnung im
Workflow aggregiert werden. In der vorliegenden Arbeit berücksichtigen wir
dabei die Workflowpatterns Sequenz, AND-Split/-Join, XOR-Split/-Join, die
in [
Die Menge der abstrakten Services bezeichnen wir mit I, i ∈ I = {1, ..., n}. Jedem abstrakten Service wird exakt ein konkreter Service j ∈ Ji = {1, ..., mi} zugeordnet. Dabei geben die Entscheidungsvariablen xij ∈ {0, 1} wider, ob ein konkreter Service j einem abstrakten Service i zugeordnet ist. Als nichtfunktionale bzw. QoS-Parameter verwenden wir Ausführungszeit e (benötigte Zeit, um einen Service auszuführen), Kosten c (Kosten für die Invokation eines Services), Zuverlässigkeit r (Wahrscheinlichkeit, dass der Service erfolgreich ausgeführt wird), sowie Durchsatz d (Anzahl paralleler Service Invokationen). Mit diesen Parametern lassen sich die Aggregationstypen Summation, Multiplikation sowie Min/Max-Operator abdecken, sodass weitere QoS-Parameter, die zu diesen Aggregationstypen gehören, leicht eingefügt werden können. Bezüglich möglicher Verzweigungen definieren wir die Menge L der Pfade l als l ∈ L = {1, ..., l#}. D. h., l stellt die entsprechende Pfad-Nummer innerhalb einer Verzweigung dar. Die AND-Verzweigung nach P S1 erzeugt drei Pfade l, d. h. L = {1, 2, 3}. Die Menge der abstrakten Services innerhalb einer Verzweigung L wird mit IWL ⊆ I bezeichnet. IWl ⊆ IWL stellt die Menge der abstrakten Services eines Pfads l dar. Das Ergebnis der Service-Selektion, d. h. die Menge der selektierten Services, wird durch S dargestellt. Gibt es bei dem betrachteten Workflow mehrere Ausführungsmöglichkeiten bzw. mehrere Ausführungspfade (wie bspw. bei dem XOR-Split nach P S2 in Abbildung 1), ist zur Planungszeit nicht bekannt, welcher der möglichen Pfade ausgeführt wird.
In einer Average-Case Analyse werden Wahrscheinlichkeiten pl für mögliche Pfade l angenommen, die angeben, mit welcher Wahrscheinlichkeit (bei einem XOR-Split) ein bestimmter Pfad ausgeführt wird, und bei Berechnung einer
Sequenz AND-Split/-Join XOR-Split/-Join Loop e P P eijxij max( P P eijxij) P pl P P eijxij 1−1ρi eij i∈IS j∈Ji l∈L i∈IWl j∈Ji l∈L i∈IWl j∈Ji c P P cijxij P P P cijxij P pl P P cijxij 1−1ρi cij i∈IS j∈Ji l∈L i∈IWl j∈Ji l∈L i∈IWl j∈Ji r Q P rijxij Q Q P rijxij P pl Q P rijxij (11−−ρρii)rrijij i∈IS j∈Ji l∈L i∈IWl j∈Ji l∈L i∈IWl j∈Ji d min( P dijxij) ml∈iLn(i∈mIiWnl(jP∈Ji dijxij)) P pl min ( P dijxij) dij i∈IS j∈Ji l∈L i∈IWl j∈Ji
Tabelle 1: Average-Case Aggregationsfunktionen
Lösung für das SSP berücksichtigt. Hierfür verwenden wir die
Aggregationsfunktionen in Tabelle 1, die in unserer Arbeit in [
Bei einer Worst-Case-Analyse betrachtet man im Unterschied zu der
AverageCase-Analyse für jeden QoS-Parameter den schlechtest möglichen Pfad – bspw.
den Pfad mit der größten aggregierten Ausführungszeit oder mit der geringsten
Zuverlässigkeit. Dies können durchaus unterschiedliche Pfade für die verschiedenen
QoS-Parameter sein. Das Ergebnis einer solchen Service-Selektion für den
WorstCase wäre ein Ausführungsplan, der die QoS-Restiktionen für den gesamten
Workflow auf keinen Fall verletzt. Bei einer Best-Case-Analyse wird analog
der Worst-Case-Analyse für jeden QoS-Parameter der best mögliche Pfad bei
der Optimierung berücksichtigt. Das bedeutet, dass für die jeweils anderen
Pfade die Restriktionen nicht berücksichtigt und insofern (höchstwahrscheinlich)
verletzt werden. Das Ergebnis einer solchen Service-Selektion führt zu einem
Ausführungsplan, bei dem die Zielfunktion den best möglichen Wert im Vergleich
zur Worst-Case und Avg-Case-Analyse aufweist, jedoch werden die Restriktionen
möglicherweise in keinem der möglichen Ausführungspfade eingehalten. Bezüglich
der in Tabelle 1 angegebenen Average-Case-Aggregationsfunktionen würden sich
bei einer Worst-/Best-Case-Analyse lediglich die Funktionen für XOR-Split/-Join
ändern – wie in [
Unabhängig davon, welche dieser drei möglichen Analysen schlussendlich
durchgeführt wird, würde bei der Optimierung des SSPs (wie in [
Ein Zustandsbehafteter Service ist ein offenes System mit eigenem Kontrollfluss und eigenen Zuständen. Ein Zustand umfasst wie bei einem abgeschlossenen System den aktuellen Wert aller Systemgrößen. Der Kontrollfluss ändert den Zustand des Systems basierend auf dem aktuellen Zustand: Es werden Entscheidungen basierend auf Systemgrößen oder nichtdeterministisch getroffen. Zudem werden besagte Systemgrößen manipuliert. Der Unterschied zu einem abgeschlossenen System besteht darin, dass ein Service mit seiner Umwelt kommuniziert. Diese Umwelt kann wiederum aus mehreren Services bestehen. So kann beispielsweise ein Service zur Buchung einer Reise an einen Service für die Hotelsuche und einen Service zur Flugsuche gebunden sein. Die Ein- und Ausgabedaten eines Zustandsbehafteten Services sind also Ein- und Ausgabeströme von Nachrichten der Umwelt. Die Reaktion des Services auf eine bestimmte Nachricht seiner Umwelt ist stets abhängig von seinem inneren Zustand: So wird beispielsweise eine bestimmte Anfrage a erst genehmigt, wenn von der Umwelt vorher bereits Nachricht b gesendet wurde. An seinem inneren Zustand kann der Service erkennen, ob b bereits empfangen wurde oder nicht.
Da zur Planungszeit das genaue Verhalten der Umwelt nicht bekannt ist, also nicht vorausgesagt werden kann, welche Nachrichten genau an den Service gesendet werden, können wir auch nicht genau sagen, welcher Pfad des Kontrollflusses tatsächlich während der Ausführung gewählt wird. Daher ist auch zur Planungszeit nicht klar, welche Operationen wie häufig und in welcher Reihenfolge ausgeführt werden. Dies macht die Angabe von fixen QoS-Werten für einen Zustandsbehafteten Service in der Regel unmöglich.
Es ist jedoch möglich, Wertebereiche V für jeden einzelnen QoS-Parameter
anzugeben (bspw. Ve, Vc, Vr, Vd), die jeden möglichen Pfad des Kontrollflusses
abdecken. Die einfachste Variante dafür ist ein Intervall, das eine untere und eine
obere Grenze für jeden QoS-Parameter angibt. In einigen Fällen ist es schwierig
oder gar unmöglich, eine genaue obere oder untere Grenze für einen Parameter
anzugeben. In diesem Falle muss entweder approximiert oder das fehlende Wissen
über eine Schranke als offenes Intervall kodiert werden. Alternativ zu Intervallen
können wir uns bspw. Paare aus Erwartungswert und Standardabweichung
vorstellen. Das Finden solcher genauen oder approximierten Wertebereiche kann auf
unterschiedliche Art und Weise geschehen. Eine Variante ist es, das Modell des
Services zu analysieren [
Stehen keine eindeutigen QoS-Werte für die einzelnen Services zur Verfügung sondern Wertebereiche, gestaltet sich der Vergleich zweier Services bezüglich ihrer QoS schwieriger. Dies wird an folgendem Beispiel verdeutlicht: Kostet ein Service S1 bspw. fest 2ct pro Invokation und benötigt er dabei fest 3s (Ausführungszeit), so können diese Werte mit denjenigen von Service S2 verglichen werden, der bspw. fest 3ct kostet bei einer festen Ausführungszeit von 2s. Hinsichtlich Kosten wäre S1 besser als S2, hinsichtlich Ausführungszeit wäre S2 zu bevorzugen. Über die individuelle Präferenz des Nutzers hinsichtlich der verschiedenen QoS-Parameter kann dann entschieden werden, welcher Service ausgewählt werden soll. Sind jedoch Wertebereiche anstatt fester Werte für jeden QoS-Parameter gegeben, ist diese Entscheidung nicht mehr trivial. Zwei Services können ohne Weiteres nicht miteinander verglichen werden. Insofern kann auch kein Ranking für die Kandidaten von Services für eine abstrakte Aktivität erstellt werden. Für die Service-Selektion müssen Services jedoch miteinander verglichen werden können.
Im Folgenden werden daher Ansätze skizziert, um das SSP bei Vorliegen von Wertebereichen für einzelne QoS-Parameter zu lösen. Für jeden Ansatz wird eine Annahme bezüglich der Spezifikation des Wertebereichs getroffen. Für den jeweils erstellten Ausführungsplan können die QoS für den gesamten Workflow zwar nicht eindeutig bestimmt werden, sie haben allerdings je nach Verfahren bestimmte Eigenschaften. 5.1
Für dieses Verfahren wird angenommen, dass der Wertebereich in Form eines geschlossenen Intervalls vorliegt. Für jeden Service wird für jeden QoS-Parameter der jeweils schlechteste Wert – Worst QoS – für das Optimierungsproblem herangezogen. Der schlechteste Wert ist für jeden QoS-Parameter entweder die linke oder rechte Grenze des Intervalls: e := max(Ve), c := max(Vc), r := min(Vr), d := min(Vd). Um hier tatsächlich eine Worst-Case Abschätzung zu erhalten, schlagen wir vor, eine Worst-Case-Analyse durchzuführen (vgl. Abschnitt 3). Ergebnis dieser Worst-Case-Analyse ist ein Ausführungsplan. Um nun dem Umstand Rechnung zu tragen, dass keine fixen QoS Werte sondern lediglich QoS Intervalle haben, werden in einem zweiten Schritt für die erhaltene Selektion von Services QoS-Intervalle V We, V Wc, V Wr, V Wd für den gesamten Workflow berechnet. Hierfür werden die unteren und oberen Schranken durch Aggregation der jeweils schlechtesten bzw. besten Werte der jeweiligen QoS-Intervalle (der selektierten Services) bestimmt. D. h., min(V We) = Aggregate(min(Vej )|∀j ∈ S) und max(V We) = Aggregate(max(Vej )|∀j ∈ S), wobei sich Aggregate auf die Verwendung der entsprechenden Aggregationsfunktion in Tabelle 1 bezieht. Die Berechnung der entsprechenden Intervalle für die anderen QoS-Parameter erfolgt analog. Somit wird ein Ausführungsplan erstellt, für den die gegebenen QoSRestiktionen stets eingehalten werden und für den die aggregierten QoS-Werte in den entsprechenden Intervallen [min(V W ), max(V W )] liegen.
Zusammenfassend sei an dieser Stelle noch mal erwähnt, dass für die Durchführung der Worst-Case-Analyse die untere/obere QoS Intervallgrenze der einzelnen Services herangezogen wird, um diese Services für die Optimierung miteinander vergleichen zu können, was (wie oben erwähnt) eine Voraussetzung zur Durchführung der Optimierung darstellt. Für die Berechnung der zu erwartenden QoS für den gesamten Workflow werden anschließend sowohl die oberen als auch unteren QoS Intervallgrenzen der ausgewählten Services berücksichtigt, um auf diese Weise das ganze QoS Intervall eines Services abdecken zu können. 5.2
Ein zweiter möglicher Lösungsansatz funktioniert unter der Annahme, dass für jeden QoS-Parameter der Wertebereich in Form von Mittelwert und Standardabweichung vorliegt. Diese können bspw. durch Simulation oder Monitoring gefunden werden (vgl. Abschnitt 4). Es bietet sich die Durchführung einer Average-CaseAnalyse an (vgl. Abschnitt 3), für die die besagten Mittelwerte der einzelnen QoS-Parameter herangezogen würden. Das Ergebnis wäre ein Ausführungsplan, der die Restriktionen im Durchschnitt erfüllt. Mithilfe der Standardabweichungen für die QoS-Werte der selektierten Services oder durch Simulation ließe sich ebenfalls ein Intervall für die QoS-Werte des gesamten Workflows gemäß des errechneten Ausführungsplans generieren. 5.3
Analog zu Abschnitt 5.1 könnten für die Service-Selektion auch die jeweiligen besten Werte aus den QoS-Intervallen (e := min(Ve), c := min(Vc), r := max(Vr), d := max(Vd)) herangezogen werden. Mit diesen würde eine Best-Case-Analyse durchgeführt. Basierend auf dem berechneten Ausführungsplans ließen sich analog zu Abschnitt 5.1 Intervalle für die QoS-Werte auf Workflow-Ebene bestimmen. Jedoch ist bei Durchführung einer Best-Case-Analyse sowie durch die Wahl der jeweils besten Werte für die QoS-Parameter die Wahrscheinlichkeit eher hoch, dass bei der Ausführung des auf diese Weise erstellten Ausführungsplans die QoS-Restriktionen verletzt werden. 6
Das SSP wird in der Literatur in vielen wissenschaftlichen Arbeiten diskutiert.
Nach unserem Wissensstand wurden hier jedoch stets Zustandslose Services
berücksichtigt. In der vorliegenden Arbeit wurde das SSP mit Zustandsbehafteten
Services adressiert. Die Herausforderung besteht dabei darin, dass für die infrage
kommenden Services keine eindeutigen QoS-Werte existieren (vgl. Abschnitt 4).
In unserer Arbeit in [