• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

QoS-aware automatic syntactic service composition problem: Complexity and resolution

Thumbnail
Date
2018
Dewey
Informatique générale
Sujet
Service composition; Web Service Challenge; AND/OR constraints; QoS optimization
Journal issue
Future Generation Computer Systems
Volume
80
Publication date
2018
Article pages
311-321
DOI
http://dx.doi.org/10.1016/j.future.2017.04.009
Forthcoming
oui
URI
https://basepub.dauphine.fr/handle/123456789/17064
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Gabrel, Virginie
Manouvrier, Maude
Moreau, Kamil
Murat, Cécile
Type
Article accepté pour publication ou publié
Abstract (EN)
Automatic syntactic service composition problem consists in automatically selecting services, from a registry, by matching their input and output data. The composite service, resulting from this selection, allows producing a set of output data, needed by a user, from a set of input data, given by the user. Adding Quality-Of-Service (QoS) values for each service (for example execution time and cost values), this selection problem becomes an optimization one called the QoS-aware automatic syntactic service composition problem. Depending on the QoS criterion used, many models and algorithms resolving the aforementioned problem are proposed in the literature. The aim of this article is twofold. Firstly, we provide a unified understanding of the wide variety of existing approaches and we analyse and compare the theoretical complexity induced by each QoS criterion. We state that optimal solution for execution time or throughput QoS criteria can be determined in polynomial time but optimality is no more guaranteed in polynomial time for QoS criteria like cost or reliability. Indeed, we show that the composition problem becomes NP-hard when optimizing such QoS criteria. Secondly, we propose a novel approach for solving more efficiently polynomial cases. This approach is based on a scheduling formulation with AND/OR constraints, using a directed graph structure. For the Web Service Challenge-09 benchmark (considering execution time and throughput QoS criteria), our exact algorithm outperforms the related work.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.