Multiagent resource allocation in service networks

Karänke, Paul

Eingang zum Volltext

Karänke, Paul

Multiagent resource allocation in service networks

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:100-opus-9802
URL: http://opus.uni-hohenheim.de/volltexte/2014/980/

pdf-Format:

Dokument 1.pdf (1.228 KB)

Gedruckte Ausgabe:

Print-on-Demand-Kopie

Dokument in Google Scholar suchen:

Social Media:

Export:

Abrufstatistik:

SWD-Schlagwörter:

Ressourcen , Agenten , Allokation , Dienstleistung , Netzwerk

Freie Schlagwörter (Englisch):

resource , agents , allocation , services , network

Institut:

Institut für Health Care & Public Management

Fakultät:

Fakultät Wirtschafts- und Sozialwissenschaften

DDC-Sachgruppe:

Wirtschaft

Dokumentart:

Dissertation

Hauptberichter:

Kirn, Stefan Prof. Dr.

Sprache:

Englisch

Tag der mündlichen Prüfung:

17.03.2014

Erstellungsjahr:

2014

Publikationsdatum:

27.06.2014

Lizenz:

Veröffentlichungsvertrag mit der Universitätsbibliothek Hohenheim

Kurzfassung auf Englisch:

The term service network (SN) denotes a network of software services in which complex software applications are provided to customers by aggregating multiple elementary services. These networks are based on the service-oriented computing (SOC) paradigm, which defines the fundamental technical concepts for software services over electronic networks, e.g., Web services and, most recently, Cloud services. For the provision of software services to customers, software service providers (SPs) have to allocate their scarce computational resources (i.e., hardware and software) of a certain quality to customer requests. The SOC paradigm facilitates interoperability over organizational boundaries by representing business relationships on the software system level. Composite software services aggregate multiple software services into software applications. This aggregation is denoted as service composition. The loose coupling of services leads to SNs as dynamic entities with changing interdependencies between services.
For composite software services, these dependencies exist across SN tiers; they result from the procurement of services, which are themselves utilized to produce additional services, and constitute a major problem for resource allocation in SNs. If these dependencies are not considered, the fulfillment of agreements may become unaccomplishable (overcommitment). Hence, the consideration of service dependencies is crucial for the allocation of service providers resources to fulfill customer requests in SNs.
However, existing resource allocation methods, which could consider these dependencies -- such as combinatorial auctions with a central auctioneer for the whole SN -- are not applicable, since there are no central coordinating entities in SNs. The application of an allocation mechanism that does not consider these dependencies might negatively affect the actual service delivery; results are penalty payments as well as a damage to the reputation of the providers.
This research is conducted in accordance to the design science paradigm in information system research. It is a problem-solving paradigm, which targets the construction and evaluation of IT artifacts. The objectives of this research are to develop and evaluate an allocation protocol, which can consider multi-tier service dependencies without the existence of central coordinating entities. Therefore, an interaction protocol engineering (IPE) perspective is applied to solve the problem of multi-tier dependencies in resource allocation. This approach provides a procedure model for designing interaction protocols for multiagent systems, and is closely related to the well-established area of communication protocol engineering.
Automated resource allocation in SNs is analyzed in this research by representing the actors as autonomous software agents in the software system. The actors delegate their objectives to their software agents, which conduct the negotiations for service provision on their behalf. Thus, these agents communicate concerning the resource allocation; in this process, the sequence of communication interactions is crucial to the problem addressed. Interaction protocols define a structured exchange of defined messages between agents; they facilitate agent conversations.
When multiple agents have to reach agreements by negotiation and bargaining, such as in case with allocating scarce resources, game theory provides means to formalize and analyze the most rational choice of actions for the interacting agents. Based on a formal framework for resource allocation in SNs, this research first performs a game-theoretic problem analysis; it is concerned with the existence, as well as the complexity of computing optimal allocations. In addition, Nash equilibria are analyzed for optimal allocations. Second, a distributed, auction-based allocation protocol, which prevents overcommitments and guarantees socially optimal allocations for single customer requests under certain assumptions, is proposed. Therefore, a game-theoretic model and an operationizable specification of the protocol are presented. Third, it is formally verified that the protocol enables multi-tier resource allocation and avoids overcommitments by proofs for the game-theoretic model and by model checking for the interaction protocol specification; using the model checker Spin, safety properties like the absence of deadlock are as well formally verified as the protocol enabling multi-tier resource allocation. Fourth, the efficacy and the benefits of the proposed protocol are demonstrated by multiagent simulation for concurrent customers. The experimental evaluation provides evidence of the protocols efficiency compared to the socially optimal allocation as a centralized benchmark in different settings, e.g., network topologies and different bidding policies.

Kurzfassung auf Deutsch:

Der Begriff Service Network (SN) bezeichnet ein Netzwerk von Software-Services, in dem komplexe Software-Applikationen durch Aggregation mehrerer elementarer Services für Kunden bereitgestellt werden. Diese Netzwerke basieren auf dem Paradigma des Service-oriented Computing, welches die grundlegenden technischen Konzepte für Software-Services über elektronische Netzwerke bereitstellt, d.h. Web Services und zuletzt Cloud-Computing. Für die Bereitstellung von Software-Services für Kunden müssen Software-Anbieter ihre knappen Ressourcen (d.h. Hardware und Software) einer bestimmten Qualität zu Kundenanfragen allozieren, also entsprechende Ressourcen reservieren, um Software-Services in der vereinbarten Dienstgüte bereitzustellen. Zusammengesetzte Software-Services aggregieren mehrere Software-Services zu Software-Applikations-Services. Diese Aggregation wird als Service-Komposition bezeichnet. Die lose Kopplung von Services macht SNs zu dynamischen Entitäten mit sich verändernden Interdependenzen zwischen den Services.
Für zusammengesetzte Software-Services existieren solche Abhängigkeiten über mehrere SN-Stufen; sie ergeben sich durch die Beschaffung von Services, welche für die Produktion von weiteren Services verwendet werden, und stellen ein Hauptproblem bei der Ressourcenallokation in SN dar. Werden diese Abhängigkeiten nicht berücksichtigt, kann die Erfüllung von Vereinbarungen undurchführbar werden (overcommitment). Daher ist die Berücksichtigung von Service-Abhängigkeiten bei der Allokation von Ressourcen der Service-Anbieter für die Erfüllung der Kundenanfragen in SNs entscheidend.
Existierende Methoden der Ressourcenallokation, welche diese Abhängigkeiten berücksichtigen könnten -- wie kombinatorische Auktionen mit einem zentralen Auktionator für das gesamte SN -- sind jedoch nicht anwendbar, da in SNs keine zentralen Koordinationsentitäten existieren. Der Einsatz eines Allokationsmechanismus, welcher diese Abhängigkeiten nicht berücksichtigt, kann die konkrete Service-Erbringung negativ beeinflussen und somit in Strafzahlungen und einer Beeinträchtigung der Reputation der Service-Anbieter resultieren.
Die vorliegende Forschungsarbeit wird in Übereinstimmung mit dem Design Science-Paradigma durchgeführt. Dabei handelt es sich um ein Problemlösungs-Paradigma, welches die Konstruktion und Evaluation von IT-Artefakten zum Ziel hat. Ziel dieser Forschungsarbeit ist die Entwicklung und Evaluation eines Allokationsprotokolls, welches mehrstufige Service-Abhängigkeiten ohne die Existenz zentraler, koordinierender Entitäten berücksichtigen kann. Zu diesem Zweck wird eine Interaction-Protocol-Engineering (IPE)-Perspektive eingenommen, um das Problem mehrstufiger Abhängigkeiten bei der Ressourcenallokation zu lösen. Dieser Ansatz stellt ein Vorgehensmodell für den Entwurf von Interaktionsprotokollen für Multiagentensysteme zur Verfügung.
Diese Forschungsarbeit analysiert die automatisierte Ressourcenallokation in SNs durch die Repräsentation der Akteure als autonome Softwareagenten im Softwaresystem. Die Akteure delegieren ihre Ziele an ihre Softwareagenten, welche in deren Auftrag die Verhandlung für die Service-Erbringung durchführen. Somit kommunizieren diese Softwareagenten bezüglich der Ressourcenallokationen; dabei ist die Abfolge der Interaktionen für das adressierte Problem elementar. Interaktionsprotokolle definieren einen strukturierten Austausch bestimmter Nachrichten zwischen Agenten.
Wenn mehrere Agenten Vereinbarungen durch Verhandlungen treffen müssen, wie im Falle der Allokation knapper Ressourcen, stellt die Spieltheorie Methoden bereit, um rationale Entscheidungen der Aktionen für interagierende Agenten zu analysieren. Basierend auf einem formalen Modell für Ressourcenallokation in SN führt diese Forschungsarbeit eine spieltheoretische Problemanalyse durch. Hierbei werden insbesondere mehrstufige Abhängigkeiten von Vereinbarungen berücksichtigt. Die Problemanalyse befaßt sich mit der Existenz sowie der Komplexität der Berechnung optimaler Allokationen. Es wird ein verteiltes, Auktions-basiertes Allokationsprotokoll, welches overcommitments vermeidet, vorgeschlagen.
Basierend auf dem spieltheoretischen Modell wird gezeigt, daß das vorgeschlagene Protokoll overcommitments vermeidet und sozial optimale Allokationen für einzelne Kundenanfragen unter bestimmten Annahmen garantiert. Darüber hinaus wird der Modellprüfer Spin verwendet, um bestimmte formale Eigenschaften der Beschreibung des Protokolls zu beweisen. Abschließend werden die Anwendbarkeit und der Nutzen des vorgeschlagenen Protokolls mittels Multiagentensimulation demonstriert. In den Simulationsexperimenten wird die Effizienz des Protokolls mit der optimalen Allokation als zentralisiertes Benchmark in unterschiedlichen Einstellungen (z.B. Netzwerktopologien oder Anzahl von Kunden- und Anbieter-Agenten) für verschiedene Bietrichtlinien für Anbieter verglichen.